論文の概要: DPO: Dynamic-Programming Optimization on Hybrid Constraints
- arxiv url: http://arxiv.org/abs/2205.08632v1
- Date: Tue, 17 May 2022 21:18:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-19 23:28:57.060708
- Title: DPO: Dynamic-Programming Optimization on Hybrid Constraints
- Title（参考訳）: DPO:ハイブリッド制約の動的プログラミング最適化
- Authors: Vu H. N. Phan and Moshe Y. Vardi
- Abstract要約: ベイズ推定において、最も可能性の高い説明(MPE)問題は、いくつかの証拠から最も高い確率で変数のインスタンス化を要求する。
ブール MPE は (部分重み付き) MaxSAT への還元によって解けることが知られている。
我々はDPMC上に構築し,MPEを正確に解く動的プログラミングであるDPOを導入する。
- 参考スコア（独自算出の注目度）: 26.704502486686128
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In Bayesian inference, the most probable explanation (MPE) problem requests a
variable instantiation with the highest probability given some evidence. Since
a Bayesian network can be encoded as a literal-weighted CNF formula $\varphi$,
we study Boolean MPE, a more general problem that requests a model $\tau$ of
$\varphi$ with the highest weight, where the weight of $\tau$ is the product of
weights of literals satisfied by $\tau$. It is known that Boolean MPE can be
solved via reduction to (weighted partial) MaxSAT. Recent work proposed DPMC, a
dynamic-programming model counter that leverages graph-decomposition techniques
to construct project-join trees. A project-join tree is an execution plan that
specifies how to conjoin clauses and project out variables. We build on DPMC
and introduce DPO, a dynamic-programming optimizer that exactly solves Boolean
MPE. By using algebraic decision diagrams (ADDs) to represent pseudo-Boolean
(PB) functions, DPO is able to handle disjunctive clauses as well as XOR
clauses. (Cardinality constraints and PB constraints may also be compactly
represented by ADDs, so one can further extend DPO's support for hybrid
inputs.) To test the competitiveness of DPO, we generate random XOR-CNF
formulas. On these hybrid benchmarks, DPO significantly outperforms MaxHS,
UWrMaxSat, and GaussMaxHS, which are state-of-the-art exact solvers for MaxSAT.
- Abstract（参考訳）: ベイズ推定において、最も可能性の高い説明(MPE)問題は、いくつかの証拠から最も高い確率で変数のインスタンス化を要求する。
ベイジアンネットワークはリテラル重み付き CNF 公式 $\varphi$ としてエンコードできるので、より一般的な問題 Boolean MPE について研究し、モデル $\tau$ of $\varphi$ を最大重みで要求し、そこで $\tau$ はリテラルの重みの積である。
ブール MPE は (部分重み付き) MaxSAT への還元によって解けることが知られている。
近年,プロジェクト・ジョイント・ツリーの構築にグラフ分解技術を活用した動的プログラミングモデルカウンタDPMCが提案されている。
project-join treeは、節を結合して変数を射出する方法を指定する実行計画である。
DPMC上に構築し,動的プログラミングオプティマイザであるDPOを導入し,Boolean MPEを正確に解いた。
代数的決定図(ADD)を用いて擬ブール関数(PB)を表現することにより、DPOはXOR節と同様に可解節を扱うことができる。
(カーディナリティ制約やPB制約もコンパクトにABDで表現できるため、DPOによるハイブリッド入力のサポートをさらに拡張することができる。)
DPOの競合性をテストするために、ランダムなXOR-CNF式を生成する。
これらのハイブリッドベンチマークでは、DPOはMaxSATの最先端の正確な解法であるMaxHS、UWrMaxSat、GaussMaxHSを大きく上回っている。
関連論文リスト
- Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
Transfer $Q*$は、ベースラインモデルを通してターゲット報酬$r$の最適値関数を推定する。
提案手法は, 従来のSoTA法で観測された準最適差を著しく低減する。
論文 参考訳（メタデータ） (2024-05-30T21:36:12Z) - 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) - DiNADO: Norm-Disentangled Neurally-Decomposed Oracles for Controlling Language Models [55.06442277395388]
NeurAlly-Decomposed Oracle (NADO)は、大きな言語モデルで制御可能な生成のための強力なアプローチである。
バニラNADOは低確率制御信号の減衰勾配に悩まされる。
本稿では,NADOアルゴリズムの性能向上を図るために,NADOアルゴリズムの改良版であるDiNADOを提案する。
論文 参考訳（メタデータ） (2023-06-20T18:36:52Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming
Approach to Solving POMDPs [17.956744635160568]
我々は,Belief Branch and Bound RTDP (B$3$RTDP) と呼ぶRTDP-Belアルゴリズムの拡張を提案する。
我々のアルゴリズムは有界値関数表現を使い、これを2つの新しい方法で活用する。
B$3$RTDPは、既知のPOMDP問題に対する最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に実証した。
論文 参考訳（メタデータ） (2022-10-22T21:42:59Z) - DPER: Dynamic Programming for Exist-Random Stochastic SAT [26.704502486686128]
本稿では,ER-SSAT問題として,SSAT問題と重み付きモデルカウント(WMC)問題を組み合わせた。
我々は、このWPMCフレームワークを拡張して、ER-SSATを正確に解き、動的プログラミングの解法DPERを実装します。
論文 参考訳（メタデータ） (2022-05-19T19:54:34Z) - DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
本稿では,ハイブリッド制約を用いた一般化MaxSAT問題の解法について,新しい動的プログラミング手法を提案する。
我々の汎用フレームワークは、MaxSAT、Min-MaxSAT、MinSATといったCNF-MaxSATの多くの一般化をハイブリッド制約で認めている。
実験の結果、DPMSは様々な手法に基づく他のアルゴリズムがすべて失敗し、特定の問題を迅速に解決できることがわかった。
論文 参考訳（メタデータ） (2022-05-08T00:31:53Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
論文 参考訳（メタデータ） (2022-02-07T14:43:35Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳（メタデータ） (2021-06-03T07:22:48Z) - Your GAN is Secretly an Energy-based Model and You Should use
Discriminator Driven Latent Sampling [106.68533003806276]
本研究では,潜時空間におけるサンプリングは,潜時空間の前対数密度と判別器出力スコアの和によって誘導されるエネルギーベースモデルに従って,潜時空間におけるサンプリングを行うことによって達成できることを示す。
判別器駆動潜時サンプリング(DDLS)は,高次元画素空間で動作する従来の手法と比較して,高効率であることを示す。
論文 参考訳（メタデータ） (2020-03-12T23:33:50Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。