論文の概要: Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm

• arxiv url: http://arxiv.org/abs/2110.00091v1
• Date: Thu, 30 Sep 2021 21:20:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-04 14:32:38.106249
• Title: Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm
• Title（参考訳）: 確率的グラフモデルの強化:パージ・アンド・マージアルゴリズム
• Authors: Simon Streicher and Johan du Preez
• Abstract要約: パージ・アンド・マージアルゴリズムは、因子を選択的にマージすることで、可鍛グラフ構造を木構造に向けるように設計されている。 このアプローチは,Sudoku,Fill-a-pix,Kakuroなど,数多くの制約満足パズルに対して評価される。 これらのタスクは CSP のバイナリ論理に限られていたが、一般の PGM 推論への拡張の約束があると考えている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic graphical models (PGMs) are powerful tools for solving systems of complex relationships over a variety of probability distributions. Tree-structured PGMs always result in efficient and exact solutions, while inference on graph (or loopy) structured PGMs is not guaranteed to discover the optimal solutions. It is in principle possible to convert loopy PGMs to an equivalent tree structure, but for most interesting problems this is impractical due to exponential blow-up. To address this, we developed the purge-and-merge algorithm. The idea behind this algorithm is to iteratively nudge a malleable graph structure towards a tree structure by selectively merging factors. The merging process is designed to avoid exponential blow-up by making use of sparse structures from which redundancy is purged as the algorithm progresses. This approach is evaluated on a number of constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro. On these tasks, our system outperformed other PGM-based approaches reported in the literature. Although these tasks were limited to the binary logic of CSP, we believe it holds promise for extension to general PGM inference.
• Abstract（参考訳）: 確率的グラフィカルモデル(PGM)は、様々な確率分布上の複雑な関係のシステムを解く強力なツールである。 木構造PGMは常に効率的かつ正確な解をもたらすが、グラフ(またはループ)構造PGMの推論は最適解を発見することが保証されない。 ループ状のPGMを等価な木構造に変換することは原則として可能であるが、最も興味深い問題に対して、指数的爆破による非現実的である。 そこで我々は,purge-and-mergeアルゴリズムを開発した。 このアルゴリズムの背景にある考え方は、因子を選択的にマージすることで、可換グラフ構造を木構造に向けて反復的に掘り下げることである。 マージングプロセスは、アルゴリズムが進行するにつれて冗長性が浄化されるスパース構造を利用することで、指数的な爆発を避けるように設計されている。 このアプローチは,Sudoku,Fill-a-pix,Kakuroなど,数多くの制約満足パズルに対して評価される。 これらの課題において,本システムは文献で報告されている他のpgmベースのアプローチよりも優れていた。 これらのタスクは CSP のバイナリ論理に限られていたが、一般の PGM 推論への拡張の約束があると考えている。

関連論文リスト

• On the Expressive Power of Tree-Structured Probabilistic Circuits [8.160496835449157]
  我々は、$n$変数に対して、同じ確率分布を計算する同値木の大きさに準多項式上界$nO(log n)$が存在することを示す。 また,木面の深さ制限を考慮すれば,木面とDAG構造PCとの間には超ポリノミカルな分離が存在することを示す。
  論文  参考訳（メタデータ） (2024-10-07T19:51:30Z)
• Inference for Probabilistic Dependency Graphs [42.03917543423699]
  確率依存グラフ (PDGs) は確率モデルの柔軟なクラスである。 離散変数を持つPDGに対する最初のトラクタブル推論アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-11-09T18:40:12Z)
• Scaling Integer Arithmetic in Probabilistic Programs [21.26857534769979]
  本稿では、整数演算のリッチな論理構造を利用する離散分布のバイナリ符号化戦略を提案する。 このアプローチは算術演算ではるかに大きな整数分布にスケールできることが示される。
  論文  参考訳（メタデータ） (2023-07-25T22:21:07Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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