論文の概要: Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees

• arxiv url: http://arxiv.org/abs/2309.08883v1
• Date: Sat, 16 Sep 2023 05:34:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-19 18:54:08.368230
• Title: Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees
• Title（参考訳）: 確率的保証者による象徴的、統計的AI統合のための満足度モデュロの解決
• Authors: Jinzhao Li, Nan Jiang, Yexiang Xue
• Abstract要約: 満足度モデュロカウント(Satifiability Modulo Counting、SMC)は、象徴的な意思決定と統計的推論の両方を必要とする問題を包含する。 XOR-SMCは、SMCで数えられるモデルをSAT式に置き換えることで、非常に難解なSMCを満足できる問題に変換する。 XOR-SMC は真の最適値に近い解を見つけ、SMC における難解なモデルカウントのよい近似を見つけるのに苦戦するいくつかの基本値を上回る。
• 参考スコア（独自算出の注目度）: 18.7083987727973
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Satisfiability Modulo Counting (SMC) encompasses problems that require both symbolic decision-making and statistical reasoning. Its general formulation captures many real-world problems at the intersection of symbolic and statistical Artificial Intelligence. SMC searches for policy interventions to control probabilistic outcomes. Solving SMC is challenging because of its highly intractable nature($\text{NP}^{\text{PP}}$-complete), incorporating statistical inference and symbolic reasoning. Previous research on SMC solving lacks provable guarantees and/or suffers from sub-optimal empirical performance, especially when combinatorial constraints are present. We propose XOR-SMC, a polynomial algorithm with access to NP-oracles, to solve highly intractable SMC problems with constant approximation guarantees. XOR-SMC transforms the highly intractable SMC into satisfiability problems, by replacing the model counting in SMC with SAT formulae subject to randomized XOR constraints. Experiments on solving important SMC problems in AI for social good demonstrate that XOR-SMC finds solutions close to the true optimum, outperforming several baselines which struggle to find good approximations for the intractable model counting in SMC.
• Abstract（参考訳）: SMC(Satifiability Modulo Counting)は、象徴的な意思決定と統計的推論の両方を必要とする問題を含む。 その一般的な定式化は、象徴的および統計的人工知能の交差点で多くの現実世界の問題を捉えている。 SMCは確率的結果を制御するための政策介入を探索する。 SMCの解法は、非常に難解な性質($\text{NP}^{\text{PP}}$-complete)のために困難であり、統計的推論と記号的推論を取り入れている。 SMC解決に関するこれまでの研究は、特に組合せ制約が存在する場合、証明可能な保証が欠如し、また/または準最適経験的性能に悩まされている。 本稿では,NPオーラへのアクセスが可能な多項式アルゴリズムであるXOR-SMCを提案する。 XOR-SMCは、SMCで数えられるモデルを、ランダムなXOR制約を受けるSAT式に置き換えることで、非常に難解なSMCを満足できる問題に変換する。 社会的善のためのAIにおける重要なSMC問題の解決に関する実験は、XOR-SMCが真に最適に近い解を見つけることを示した。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Worst-Case Analysis is Maximum-A-Posteriori Estimation [9.61085323616992]
  プログラムの最悪のリソース使用は、多くのソフトウェアエンジニアリングタスクに有用な情報を提供することができる。 本稿では,DSE-SMCとよばれる,汎用的で適応的で音質の高いファジリングフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-15T08:24:02Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  本稿では,最小化問題と最小化問題の両方に対して,MC-SGMの包括的一般化解析を行う。 我々はスムーズかつ非スムーズなケースに対して最適な過剰人口リスク境界を確立する。 コンベックス・コンケーブ問題に対する最初期のほぼ最適な収束率を期待と高い確率で開発する。
  論文  参考訳（メタデータ） (2022-09-16T15:42:51Z)
• Bayesian Statistical Model Checking for Multi-agent Systems using HyperPCTL* [6.574517227976925]
  本稿では,離散時間マルコフ連鎖(DTMC)上のHyperPCTL*論理で定義された確率的ハイパープロパティの統計モデルチェック(SMC)のためのベイズ的手法を提案する。 提案アルゴリズムは,与えられたHyperPCTL*の公式の満足度を推定するために必要なサンプル数と検証時間の両方において,より優れた性能を発揮する。
  論文  参考訳（メタデータ） (2022-09-06T17:36:28Z)
• SMT-based Weighted Model Integration with Structure Awareness [18.615397594541665]
  本研究では,SMTに基づく列挙法と問題構造を効果的に符号化するアルゴリズムを開発した。 これにより,冗長モデルの生成を回避し,計算コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2022-06-28T09:46:17Z)
• Variational Combinatorial Sequential Monte Carlo Methods for Bayesian Phylogenetic Inference [4.339931151475307]
  Vari Combinatorial Monte Carlo (VCSMC) は複雑な構造について学習するための変分探索を確立する強力なフレームワークである。 本稿では,VCSMC と CSMC が,従来のタスクよりも高い確率空間を探索できることを示す。
  論文  参考訳（メタデータ） (2021-05-31T19:44:24Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。