論文の概要: On the Hardness of Approximating Distributions with Tractable Probabilistic Models
- arxiv url: http://arxiv.org/abs/2506.01281v2
- Date: Fri, 24 Oct 2025 20:14:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 17:41:21.613381
- Title: On the Hardness of Approximating Distributions with Tractable Probabilistic Models
- Title（参考訳）: トラクタブル確率モデルによる近似分布の硬さについて
- Authors: John Leland, YooJung Choi,
- Abstract要約: 本稿では,$f$-divergencesに基づく確率回路を用いた近似分布について検討する。
任意の分布を有界$f$-divergenceで近似することは任意のモデルに対して$mathsfNP$-hardであることを示す。
- 参考スコア（独自算出の注目度）: 2.9726600487327093
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A fundamental challenge in probabilistic modeling is to balance expressivity and inference efficiency. Tractable probabilistic models (TPMs) aim to directly address this tradeoff by imposing constraints that guarantee efficient inference of certain queries while maintaining expressivity. In particular, probabilistic circuits (PCs) provide a unifying framework for many TPMs, by characterizing families of models as circuits satisfying different structural properties. Because the complexity of inference on PCs is a function of the circuit size, understanding the size requirements of different families of PCs is fundamental in mapping the trade-off between tractability and expressive efficiency. However, the study of expressive efficiency of circuits are often concerned with exact representations, which may not align with model learning, where we look to approximate the underlying data distribution closely by some distance measure. Moreover, due to hardness of inference tasks, exactly representing distributions while supporting tractable inference often incurs exponential size blow-ups. In this paper, we consider a natural, yet so far underexplored, question: can we avoid such size blow-up by allowing for some small approximation error? We study approximating distributions with probabilistic circuits with guarantees based on $f$-divergences, and analyze which inference queries remain well-approximated under this framework. We show that approximating an arbitrary distribution with bounded $f$-divergence is $\mathsf{NP}$-hard for any model that can tractably compute marginals. In addition, we prove an exponential size gap for approximation between the class of decomposable PCs and that of decomposable and deterministic PCs.
- Abstract（参考訳）: 確率的モデリングにおける根本的な課題は、表現性と推論効率のバランスをとることである。
トラクタブル確率モデル(TPM)は、表現性を維持しながら、特定のクエリの効率的な推論を保証する制約を課すことによって、このトレードオフに対処することを目的としている。
特に、確率回路(PC)は、異なる構造特性を満たす回路としてモデルの族を特徴付けることで、多くのTPMに対して統一的な枠組みを提供する。
PC上の推論の複雑さは回路サイズの関数であるため、PCの異なるファミリーのサイズ要件を理解することは、トラクタビリティと表現効率のトレードオフをマッピングする上で基本となる。
しかし、回路の表現効率の研究は、モデル学習と一致しない正確な表現にしばしば関係しており、そこでは、基礎となるデータ分布をある程度の距離測度で近似することを検討する。
さらに、推論タスクの硬さのため、抽出可能な推論をサポートしながら分布を正確に表現し、指数関数的な大きさの爆発を引き起こすことが多い。
本論では,そのような大きさの爆発を避けるために,小さな近似誤差を許容して,そのような大きさの爆発を避けることができるのか,という疑問を提起する。
本稿では,$f$-divergencesに基づく保証付き確率回路を用いた近似分布について検討し,この枠組みの下でどの推論クエリが適切に近似されているか分析する。
任意の分布を有界$f$-divergenceで近似することは任意のモデルに対して$\mathsf{NP}$-hardであることを示す。
さらに,分解可能なPCのクラスと分解可能なPCのクラスとの近似の指数的サイズギャップを証明した。
関連論文リスト
- The Limits of Tractable Marginalization [23.716205079188608]
マージナライゼーション(Marginalization) -- すべての代入をその入力のサブセットにまとめること -- は、基本的な計算問題である。
関数に対して仮想的なエビデンスを余分に実行する効率的な実RAMが存在する場合、その関数のマルチ線形表現のための小さな回路が存在することを示す。
その結果、関数に対して仮想的なエビデンスを余分に実行する効率的な実RAMが存在する場合、その関数のマルチ線形表現のための小さな回路が存在することを示す。
論文 参考訳（メタデータ） (2025-04-17T07:54:56Z) - Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress [2.2164989053903805]
グラフィカルモデルにおける変数除去による効率的な確率的推論は最適な除去順序を必要とする。
我々は、テンソルネットワークにおける効率的な収縮順序を見つけるために強化学習アプローチを適用する。
推論中に特定の構造を活用することで、中間結果のコンパクトな符号化を導入することができることを示す。
論文 参考訳（メタデータ） (2025-03-11T18:00:23Z) - Robust Counterfactual Inference in Markov Decision Processes [1.5197843979051473]
現在のアプローチでは、カウンターファクトを識別するために特定の因果モデルを想定している。
反実遷移確率の厳密な境界を計算できる新しい非パラメトリック手法を提案する。
論文 参考訳（メタデータ） (2025-02-19T13:56:20Z) - Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
最適公正表現はいくつかの有用な構造特性を持つことを示す。
そこで,これらの近似問題は,凹凸プログラミング法により効率的に解けることを示す。
論文 参考訳（メタデータ） (2024-09-26T08:46:48Z) - Scalable Computation of Causal Bounds [11.193504036335503]
本研究では、未観測の共創者と離散値の観測変数を持つ因果グラフ上の因果クエリの計算バウンダリの問題を考察する。
このような境界を計算するための既存の研究されていないアプローチは、線形プログラミング(LP)の定式化を使用しており、既存の解法にはすぐに難解になる。
このLPは,既存の手法に比べてはるかに大きな因果推論問題に対する境界を計算することができることを示す。
論文 参考訳（メタデータ） (2023-08-04T21:00:46Z) - Efficient Computation of Counterfactual Bounds [44.4263314637532]
我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。
近似の精度を信頼性のある間隔で評価する。
論文 参考訳（メタデータ） (2023-07-17T07:59:47Z) - Exact Bayesian Inference on Discrete Models via Probability Generating
Functions: A Probabilistic Programming Approach [7.059472280274009]
離散統計モデルに対する正確なベイズ推定法を提案する。
我々は、離散的かつ連続的なサンプリング、離散的な観察、アフィン関数、(確率的な)分岐、離散的な事象の条件付けをサポートする確率的プログラミング言語を使用する。
我々の推論手法は確実に正確で完全に自動化されている。
論文 参考訳（メタデータ） (2023-05-26T16:09:59Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Probabilistic Generating Circuits [50.98473654244851]
効率的な表現のための確率的生成回路(PGC)を提案する。
PGCは、非常に異なる既存モデルを統一する理論的なフレームワークであるだけでなく、現実的なデータをモデル化する大きな可能性も示している。
我々はPCとDPPの単純な組み合わせによって簡単に仮定されない単純なPGCのクラスを示し、一連の密度推定ベンチマークで競合性能を得る。
論文 参考訳（メタデータ） (2021-02-19T07:06:53Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳（メタデータ） (2020-11-04T10:25:13Z) - Probabilistic Circuits for Variational Inference in Discrete Graphical
Models [101.28528515775842]
変分法による離散的グラフィカルモデルの推論は困難である。
エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。
Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。
選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
論文 参考訳（メタデータ） (2020-10-22T05:04:38Z) - Polynomial-Time Exact MAP Inference on Discrete Models with Global
Dependencies [83.05591911173332]
ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。
本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
論文 参考訳（メタデータ） (2019-12-27T13:30:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。