論文の概要: On the Hardness of Approximating Distributions with Probabilistic Circuits

• arxiv url: http://arxiv.org/abs/2506.01281v1
• Date: Mon, 02 Jun 2025 03:35:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:34.02042
• Title: On the Hardness of Approximating Distributions with Probabilistic Circuits
• Title（参考訳）: 確率回路による近似分布の硬さについて
• Authors: John Leland, YooJung Choi,
• Abstract要約: 任意の分布を有界$f$-divergenceで近似することは任意のモデルに対して$mathsfNP$-hardであることを示す。 次に、分解可能なPCのクラスとさらに決定論的PCとの近似の指数的なサイズギャップを証明した。
• 参考スコア（独自算出の注目度）: 8.582070926175966
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental challenge in probabilistic modeling is balancing expressivity and tractable inference. Probabilistic circuits (PCs) aim to directly address this tradeoff by imposing structural constraints that guarantee efficient inference of certain queries while maintaining expressivity. Since inference complexity on PCs depends on circuit size, understanding the size bounds across circuit families is key to characterizing the tradeoff between tractability and expressive efficiency. However, expressive efficiency is often studied through exact representations, where exactly encoding distributions while enforcing various structural properties often incurs exponential size blow-ups. Thus, we pose the following question: can we avoid such size blow-ups by allowing some small approximation error? We first show that approximating an arbitrary distribution with bounded $f$-divergence is $\mathsf{NP}$-hard for any model that can tractably compute marginals. We then prove an exponential size gap for approximation between the class of decomposable PCs and additionally deterministic PCs.
• Abstract（参考訳）: 確率論的モデリングにおける根本的な課題は、表現性と抽出可能な推論のバランスである。 確率回路(PC)は、表現性を維持しながら、特定のクエリの効率的な推論を保証する構造的制約を課すことにより、このトレードオフに対処することを目的としている。 PC上の推論複雑性は回路サイズに依存するため、回路ファミリ間のサイズ境界を理解することは、トラクタビリティと表現効率のトレードオフを特徴づける鍵となる。 しかし、表現効率はしばしば正確な表現を通して研究され、そこでは分布を正確に符号化し、様々な構造的特性を強制することは指数的な大きさの爆発を引き起こす。 このようにして、小さな近似誤差を許容することで、そのような大きさの爆発を避けることができるだろうか? まず、有界な$f$-分数で任意の分布を近似することは任意のモデルに対して$\mathsf{NP}$-hardであることを示す。 次に、分解可能なPCのクラスとさらに決定論的PCとの近似の指数的なサイズギャップを証明した。

関連論文リスト

• 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 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)
• 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)

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

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