論文の概要: On the Expressive Power of Tree-Structured Probabilistic Circuits

• arxiv url: http://arxiv.org/abs/2410.05465v2
• Date: Thu, 24 Oct 2024 21:15:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-01 18:28:00.624407
• Title: On the Expressive Power of Tree-Structured Probabilistic Circuits
• Title（参考訳）: 木構造確率回路の表現力について
• Authors: Lang Yin, Han Zhao,
• Abstract要約: 我々は、$n$変数に対して、同じ確率分布を計算する同値木の大きさに準多項式上界$nO(log n)$が存在することを示す。 また,木面の深さ制限を考慮すれば,木面とDAG構造PCとの間には超ポリノミカルな分離が存在することを示す。
• 参考スコア（独自算出の注目度）: 8.160496835449157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic circuits (PCs) have emerged as a powerful framework to compactly represent probability distributions for efficient and exact probabilistic inference. It has been shown that PCs with a general directed acyclic graph (DAG) structure can be understood as a mixture of exponentially (in its height) many components, each of which is a product distribution over univariate marginals. However, existing structure learning algorithms for PCs often generate tree-structured circuits or use tree-structured circuits as intermediate steps to compress them into DAG-structured circuits. This leads to the intriguing question of whether there exists an exponential gap between DAGs and trees for the PC structure. In this paper, we provide a negative answer to this conjecture by proving that, for $n$ variables, there exists a quasi-polynomial upper bound $n^{O(\log n)}$ on the size of an equivalent tree computing the same probability distribution. On the other hand, we also show that given a depth restriction on the tree, there is a super-polynomial separation between tree and DAG-structured PCs. Our work takes an important step towards understanding the expressive power of tree-structured PCs, and our techniques may be of independent interest in the study of structure learning algorithms for PCs.
• Abstract（参考訳）: 確率回路(PC)は、確率分布を高速かつ正確な確率的推論のためにコンパクトに表現する強力なフレームワークとして登場した。 一般有向非巡回グラフ(DAG)構造を持つPCは、指数関数的に(その高さにおいて)多くの成分の混合として理解でき、それぞれが単変量辺面上の積分布である。 しかし、PC用の既存の構造学習アルゴリズムは、しばしば木構造回路を生成するか、木構造回路を中間ステップとして使用してDAG構造回路に圧縮する。 このことは、PC構造に対するDAGとツリーの間に指数的ギャップが存在するかどうかという興味深い問題を引き起こす。 本稿では、この予想に対して、$n$変数に対して、同じ確率分布を計算する同値木の大きさに準多項式上界$n^{O(\log n)}$が存在することを証明して、負の答えを与える。 一方,木面の深さ制限が与えられた場合,木面とDAG構造PCとの間にはスーパーポリノミカルな分離が存在することを示す。 我々の研究は、木構造PCの表現力を理解するための重要な一歩を踏み出し、我々の技術は、PCの構造学習アルゴリズムの研究に独立した関心を持つかもしれない。

関連論文リスト

• Restructuring Tractable Probabilistic Circuits [33.76083310837078]
  確率回路(PC)は、トラクタブル推論をサポートする確率モデルのための統一表現である。 既存の乗算アルゴリズムでは、回路は同じ構造を尊重する必要がある。 異なるvtreeを重畳する回路を乗算する新しい時間アルゴリズムがもたらされることを示す。
  論文  参考訳（メタデータ） (2024-11-19T06:10:22Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models [20.07977560803858]
  我々は、構造化分解可能なPCにおける(マルジナル)決定性の新規な定式化であるmd-vtreesを紹介する。 我々は,PC上でのバックドア調整などの因果推論クエリに対して,最初のpolytimeアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-17T13:48:16Z)
• Bayesian Structure Scores for Probabilistic Circuits [13.441379161477272]
  確率回路(PC)は、抽出可能な推論を伴う確率の顕著な表現である。 我々は、決定論的PCのためのベイズ構造スコア、すなわちパラメータを疎外した構造可能性を開発する。 ログのように適合するトレーニング時間とモデルの間には、良好なトレードオフが達成されます。
  論文  参考訳（メタデータ） (2023-02-23T16:12:19Z)
• Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm [0.0]
  パージ・アンド・マージアルゴリズムは、因子を選択的にマージすることで、可鍛グラフ構造を木構造に向けるように設計されている。 このアプローチは,Sudoku,Fill-a-pix,Kakuroなど,数多くの制約満足パズルに対して評価される。 これらのタスクは CSP のバイナリ論理に限られていたが、一般の PGM 推論への拡張の約束があると考えている。
  論文  参考訳（メタデータ） (2021-09-30T21:20:52Z)
• 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)
• Probabilistic Generating Circuits [50.98473654244851]
  効率的な表現のための確率的生成回路(PGC)を提案する。 PGCは、非常に異なる既存モデルを統一する理論的なフレームワークであるだけでなく、現実的なデータをモデル化する大きな可能性も示している。 我々はPCとDPPの単純な組み合わせによって簡単に仮定されない単純なPGCのクラスを示し、一連の密度推定ベンチマークで競合性能を得る。
  論文  参考訳（メタデータ） (2021-02-19T07:06:53Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  本研究では,高次元scRNA-seqデータから意味のある木構造を同定する手法を提案する。 次に、低次元空間におけるデータのツリー構造を強調する木バイアスオートエンコーダDTAEを紹介する。
  論文  参考訳（メタデータ） (2021-02-11T08:48:48Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。 統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
  論文  参考訳（メタデータ） (2021-01-22T01:57:35Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Strudel: Learning Structured-Decomposable Probabilistic Circuits [37.153542210716004]
  Strudelは構造化分解可能なPCのためのシンプルで高速で正確な学習アルゴリズムである。 より正確なシングルPCモデルをより少ないイテレーションで提供し、PCのアンサンブルを構築する際に学習を劇的にスケールする。 標準密度推定ベンチマークと挑戦的推論シナリオにこれらの利点を示す。
  論文  参考訳（メタデータ） (2020-07-18T04:51:31Z)

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

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