論文の概要: DPER: Dynamic Programming for Exist-Random Stochastic SAT
- arxiv url: http://arxiv.org/abs/2205.09826v1
- Date: Thu, 19 May 2022 19:54:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2022-05-24 14:05:29.207455
- Title: DPER: Dynamic Programming for Exist-Random Stochastic SAT
- Title（参考訳）: DPER: 既存の確率SATのための動的プログラミング
- Authors: Vu H. N. Phan and Moshe Y. Vardi
- Abstract要約: 本稿では,ER-SSAT問題として,SSAT問題と重み付きモデルカウント(WMC)問題を組み合わせた。
我々は、このWPMCフレームワークを拡張して、ER-SSATを正確に解き、動的プログラミングの解法DPERを実装します。
- 参考スコア（独自算出の注目度）: 26.704502486686128
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In Bayesian inference, the maximum a posteriori (MAP) problem combines the
most probable explanation (MPE) and marginalization (MAR) problems. The
counterpart in propositional logic is the exist-random stochastic
satisfiability (ER-SSAT) problem, which combines the satisfiability (SAT) and
weighted model counting (WMC) problems. Both MAP and ER-SSAT have the form
$\operatorname{argmax}_X \sum_Y f(X, Y)$, where $f$ is a real-valued function
over disjoint sets $X$ and $Y$ of variables. These two optimization problems
request a value assignment for the $X$ variables that maximizes the weighted
sum of $f(X, Y)$ over all value assignments for the $Y$ variables. ER-SSAT has
been shown to be a promising approach to formally verify fairness in supervised
learning. Recently, dynamic programming on graded project-join trees has been
proposed to solve weighted projected model counting (WPMC), a related problem
that has the form $\sum_X \max_Y f(X, Y)$. We extend this WPMC framework to
exactly solve ER-SSAT and implement a dynamic-programming solver named DPER.
Our empirical evaluation indicates that DPER contributes to the portfolio of
state-of-the-art ER-SSAT solvers (DC-SSAT and erSSAT) through competitive
performance on low-width problem instances.
- Abstract（参考訳）: ベイズ推定では、最大アフターイ(MAP)問題は最も可能性の高い説明(MPE)と限界化(MAR)の問題を組み合わせている。
命題論理のもう1つの問題は、確率的満足度(ER-SSAT)問題であり、これはSATと重み付きモデルカウント(WMC)問題を組み合わせたものである。
map と er-ssat のどちらも、$\operatorname{argmax}_x \sum_y f(x, y)$ の形をしている。
これら2つの最適化問題は、$y$変数のすべての値代入に対して$f(x, y)$の重み付き和を最大化する$x$変数の値代入を要求する。
ER-SSATは教師あり学習における公正性を正式に検証するための有望なアプローチであることが示されている。
近年, 重み付き射影モデルカウント (WPMC) の解法として, $\sum_X \max_Y f(X, Y)$ が提案されている。
我々は、このWPMCフレームワークを拡張して、ER-SSATを正確に解き、動的プログラミングの解法DPERを実装します。
我々の実証評価は、DPERが低幅問題インスタンス上での競合性能を通じて、最先端のER-SSATソルバ(DC-SSATとerSSAT)のポートフォリオに寄与していることを示している。
関連論文リスト
- An Exact Solver for Satisfiability Modulo Counting with Probabilistic Circuits [16.645967034009225]
SMC (Satifiability Modulo Counting) は、最近提案された一般言語である。
我々は,確率的推論プロセスにおいて,下界と上界を効率的に追跡する正確なSMC解法であるKOCO-SMCを提案する。
論文 参考訳（メタデータ） (2025-03-02T20:28:20Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
自動機構設計のための線形プログラム(LP)に最適解のクラスを解析的に導出する。
これらの解は、元の定式化における変数の総数よりも指数関数的に小さい基本変数の集合を用いて表すことができる。
本稿では,この用語の評価をマルチアーム・バンディット(MAB)問題に翻訳することでこの問題に対処する。
論文 参考訳（メタデータ） (2024-11-30T03:59:36Z) - Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
本稿では,自然言語問題記述から解法対応最適化モデルを自動生成する,$textitautoformulation$の問題にアプローチする。
オートフォーミュレーションの3つの主要な課題を識別する: $textit(1)$ 巨大で問題に依存した仮説空間、および$textit(2)$ 不確実性の下でこの空間を効率的かつ多様に探索する。
我々は,$textitLarge Language Models$と$textitMonte-Carlo Tree Search$を併用した新しい手法を提案する。
論文 参考訳（メタデータ） (2024-11-03T20:41:38Z) - Metareasoning in uncertain environments: a meta-BAMDP framework [1.0923877073891441]
正しい$P$を見つけることは、推論プロセスの空間上の最適化問題として表すことができる。
本稿では,未知の報酬/遷移分布を持つ環境におけるメタ推論を扱うメタベイズ適応型MDPフレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-02T13:15:01Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳（メタデータ） (2023-12-16T12:44:36Z) - Modeling Complex Mathematical Reasoning via Large Language Model based
MathAgent [15.81048994298046]
大規模言語モデル (LLM) は複雑な数学的問題を解く上で困難に直面している。
本稿では, エージェントベースのゼロショットフレームワークを用いて, LLMの数学的解法を公式に記述し, 拡張する。
miniF2FとMATHの実験では、PreRとMathAgentsの有効性が実証されている。
論文 参考訳（メタデータ） (2023-12-14T13:33:50Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - DPO: Dynamic-Programming Optimization on Hybrid Constraints [26.704502486686128]
ベイズ推定において、最も可能性の高い説明(MPE)問題は、いくつかの証拠から最も高い確率で変数のインスタンス化を要求する。
ブール MPE は (部分重み付き) MaxSAT への還元によって解けることが知られている。
我々はDPMC上に構築し,MPEを正確に解く動的プログラミングであるDPOを導入する。
論文 参考訳（メタデータ） (2022-05-17T21:18:54Z) - Iterative Feature Matching: Toward Provable Domain Generalization with
Logarithmic Environments [55.24895403089543]
ドメインの一般化は、限られた数のトレーニング環境からのデータで、目に見えないテスト環境でうまく機能することを目的としています。
我々は,O(logd_s)$環境のみを見た後に一般化する予測器を高確率で生成することを保証する反復的特徴マッチングに基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-18T04:39:19Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。