論文の概要: On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

• arxiv url: http://arxiv.org/abs/2608.31120v1
• Date: Mon, 31 Aug 2026 17:32:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-01 18:31:31.542284
• Title: On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
• Title（参考訳）: 逐次符号化された条件分布の整合性問題の複雑性について
• Abstract要約: 本稿では,機械学習における確率モデルにおけるトレードオフについて検討する。 一対の条件分布 p(x|y) と p(y|x) は任意の関節分布 p(x,y) とは相容れない。 離散確率変数の場合、条件が確率テーブルとして符号化されるとき、互換性問題は既知の解を持つ。
• 参考スコア（独自算出の注目度）: 6.582423386446727
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.
• Abstract（参考訳）: この論文の動機は、機械学習で使用される確率モデルにおいて暗黙的なトレードオフを調べることである。 モデルはしばしば条件付き確率の形で予測するために使われる。 しかし、条件分布 p(x|y) と p(y|x) の対は、任意の関節分布 p(x,y) とは相容れない。 そのような条件が2つ与えられた場合、相反する結合が存在するかどうかを決定することは、相反問題として知られている。 離散確率変数の場合、条件が確率テーブルとしてエンコードされるとき、整合性問題は既知の解を持ち、計算的に抽出可能である。 本稿では,条件分布を演算回路として符号化した簡潔な問題の形式化と研究を行う。 これは、ニューラルネットワークモデルを含む高次元設定における確率的モデリングの実践的応用に適用できる。 条件文の簡潔な回路表現では、互換性の問題が難解であることを示す。 すべての確率が 0 でない場合、問題は co-NP-完全である。 確率がゼロである場合、互換性のいくつかの概念が区別可能であることを示す実例を示し、問題の複数バージョンがPSPACE完全であることを証明する。 さらに、多項式階層が崩壊しないと仮定すると、関節を簡潔に表現できない相反する簡潔な条件が存在することを示す。 確率論的モデリングと機械学習におけるこれらの結果の意味について論じる。

関連論文リスト

• How to Verify Consistency of Probabilistic Claims [49.47758039235095]
  予測モデルの一貫性を証明するために,対話型PCPを構築する。 添加音の小さなギャップがBへの依存を除去することを示す。 我々は,対話型PCPを,自身の一貫性を証明するための予測モデルに向けた第一歩だと考えている。
  論文  参考訳（メタデータ） (2026-08-11T17:41:39Z)
• Probabilistic and Causal Satisfiability: Constraining the Model [0.49399484784577985]
  確率論的および因果推論における充足可能性問題の複雑性について検討する。 基本的な用語は、原子事象に対する命題公式の確率である。 モデルに2つの新たな次元を加えることで、この作業線を拡張します。
  論文  参考訳（メタデータ） (2025-04-28T16:14:06Z)
• User-defined Event Sampling and Uncertainty Quantification in Diffusion Models for Physical Dynamical Systems [49.75149094527068]
  拡散モデルを用いて予測を行い,カオス力学系に対する不確かさの定量化が可能であることを示す。 本研究では,雑音レベルが低下するにつれて真の分布に収束する条件付きスコア関数の確率的近似法を開発する。 推論時に非線形ユーザ定義イベントを条件付きでサンプリングすることができ、分布の尾部からサンプリングした場合でもデータ統計と一致させることができる。
  論文  参考訳（メタデータ） (2023-06-13T03:42:03Z)
• Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach [7.059472280274009]
  離散統計モデルに対する正確なベイズ推定法を提案する。 我々は、離散的かつ連続的なサンプリング、離散的な観察、アフィン関数、(確率的な)分岐、離散的な事象の条件付けをサポートする確率的プログラミング言語を使用する。 我々の推論手法は確実に正確で完全に自動化されている。
  論文  参考訳（メタデータ） (2023-05-26T16:09:59Z)
• The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
  本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。 この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。 我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
  論文  参考訳（メタデータ） (2023-05-16T15:01:22Z)
• Marginal Inference queries in Hidden Markov Models under context-free grammar constraints [0.348097307252416]
  隠れモデル(HMM)における文脈自由文法(CFG)の可能性の計算問題に対処する。 問題は NP-Hard であり、CFG が 2 以下のあいまいさの次数を持つという約束があるにもかかわらずである。 次に,不明瞭なCFGの場合の確率を近似するために,完全ランダム化近似法を提案する。
  論文  参考訳（メタデータ） (2022-06-26T12:44:18Z)
• On the Generative Utility of Cyclic Conditionals [103.1624347008042]
  2つの条件付きモデル$p(x|z)$を用いて、共同分布$p(x,z)$をモデル化できるかどうか、また、どのようにしてサイクルを形成するかを検討する。 本稿では,周期条件生成モデリングのためのCyGenフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-06-30T10:23:45Z)
• Probabilistic Generating Circuits [50.98473654244851]
  効率的な表現のための確率的生成回路(PGC)を提案する。 PGCは、非常に異なる既存モデルを統一する理論的なフレームワークであるだけでなく、現実的なデータをモデル化する大きな可能性も示している。 我々はPCとDPPの単純な組み合わせによって簡単に仮定されない単純なPGCのクラスを示し、一連の密度推定ベンチマークで競合性能を得る。
  論文  参考訳（メタデータ） (2021-02-19T07:06:53Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。 我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。 まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
  論文  参考訳（メタデータ） (2020-08-19T16:04:34Z)
• Coupling-based Invertible Neural Networks Are Universal Diffeomorphism Approximators [72.62940905965267]
  結合フロー(CF-INN)に基づく可逆ニューラルネットワークは、画像合成や表現学習など、さまざまな機械学習応用を有する。 CF-INNは可逆関数に対する普遍近似器か? 我々は、ある微分同相類に対する普遍性の同値性を示す一般的な定理を証明する。
  論文  参考訳（メタデータ） (2020-06-20T02:07:37Z)

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

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