論文の概要: Probabilistic and Causal Satisfiability: Constraining the Model

• arxiv url: http://arxiv.org/abs/2504.19944v1
• Date: Mon, 28 Apr 2025 16:14:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:54.508073
• Title: Probabilistic and Causal Satisfiability: Constraining the Model
• Title（参考訳）: 確率的・因果的満足度:モデルによる制約
• Authors: Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, Benito van der Zander,
• Abstract要約: 確率論的および因果推論における充足可能性問題の複雑性について検討する。 基本的な用語は、原子事象に対する命題公式の確率である。 モデルに2つの新たな次元を加えることで、この作業線を拡張します。
• 参考スコア（独自算出の注目度）: 0.49399484784577985
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables $X_1, X_2,\ldots$ over finite domains, the basic terms are probabilities of propositional formulas over atomic events $X_i = x_i$, such as $P(X_1 = x_1)$ or $P(X_1 = x_1 \vee X_2 = x_2)$. The basic terms can be combined using addition (yielding linear terms) or multiplication (polynomial terms). The probabilistic satisfiability problem asks whether a joint probability distribution satisfies a Boolean combination of (in)equalities over such terms. Fagin et al. (1990) showed that for basic and linear terms, this problem is NP-complete, making it no harder than Boolean satisfiability, while Moss\'e et al. (2022) proved that for polynomial terms, it is complete for the existential theory of the reals. Pearl's Causal Hierarchy (PCH) extends the probabilistic setting with interventional and counterfactual reasoning, enriching the expressiveness of languages. However, Moss\'e et al. (2022) found that satisfiability complexity remains unchanged. Van der Zander et al. (2023) showed that introducing a marginalization operator to languages induces a significant increase in complexity. We extend this line of work by adding two new dimensions to the problem by constraining the models. First, we fix the graph structure of the underlying structural causal model, motivated by settings like Pearl's do-calculus, and give a nearly complete landscape across different arithmetics and PCH levels. Second, we study small models. While earlier work showed that satisfiable instances admit polynomial-size models, this is no longer guaranteed with compact marginalization. We characterize the complexities of satisfiability under small-model constraints across different settings.
• Abstract（参考訳）: 確率論的および因果推論における充足可能性問題の複雑性について検討する。 有限領域上の確率変数 $X_1, X_2,\ldots$ が与えられたとき、基本項は、$P(X_1 = x_1)$ や $P(X_1 = x_1 \vee X_2 = x_2)$ のような原子イベント上の命題公式の確率である。 基本項は加法 (yielding linear term) または乗法 (polynomial term) を用いて結合することができる。 確率的満足度問題は、結合確率分布がそのような項上の(不等式の)ブール結合を満たすかどうかを問う。 Fagin et al (1990) は、基本的な項と線型項について、この問題は NP 完全であり、ブール適合性ほど難しくはないことを示したが、Moss\'e et al (2022) は多項式項について、実数の存在論的理論に完全であることを証明した。 パールのCausal Hierarchy (PCH)は、介入的および反ファクト的推論によって確率的設定を拡張し、言語の表現力を高めている。 しかし、Moss\'e et al (2022) は満足度複雑性が変化しないことを示した。 Van der Zander et al (2023) は、言語に余分化演算子を導入すると、複雑さが著しく増加することを示した。 モデルに2つの新たな次元を加えることで、この作業線を拡張します。 まず、Pearlのdo-calculusのような設定によって動機づけられた構造因果モデルのグラフ構造を修正し、異なる算術とPCHレベルにわたってほぼ完全なランドスケープを与える。 第二に、我々は小さなモデルについて研究する。 初期の研究は、満足できるインスタンスは多項式サイズのモデルを認めることを示したが、これはもはやコンパクトな余分化では保証されない。 異なる設定の小さなモデル制約下での満足度の複雑さを特徴付ける。

関連論文リスト

• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。 近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。 非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
  論文  参考訳（メタデータ） (2024-10-31T15:56:50Z)
• From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
  PCHのレベルによって, NPPP, PSPACE, NEXP完全満足度の問題が生じることを示す。 一方、完全言語の場合、すなわち加法、余分化、乗算が可能である場合、反事実レベルの満足度は確率的・因果的なレベルと同じであることを示す。
  論文  参考訳（メタデータ） (2024-05-12T20:25:36Z)
• On Probabilistic and Causal Reasoning with Summation Operators [3.1133049660590615]
  各因果言語における推論は、計算複雑性の観点からは、単に確率的あるいは「相関的」な推論と同じくらい困難であることを示す。 因果推論のための$do$-calculus of Pearl (2009)のようなアプリケーションに現れる一般的なデバイスをキャプチャするための和演算子を導入する。 意外なことに、ランダム変数値に対する自由変数の許容は、これらのランダム変数の範囲が制限されない限り、決定不可能なシステムをもたらす。
  論文  参考訳（メタデータ） (2024-05-05T22:32:01Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
  本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。 この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。 我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
  論文  参考訳（メタデータ） (2023-05-16T15:01:22Z)
• Structure Learning and Parameter Estimation for Graphical Models via Penalized Maximum Likelihood Methods [0.0]
  論文では、静的なベイジアンネットワーク(BN)と、その名前が示すように時間成分を持つ連続時間ベイジアンネットワークという2つの異なるタイプのPGMについて考察する。 私たちは、PGMを学ぶための最初のステップである、真の構造を回復することに興味を持っています。
  論文  参考訳（メタデータ） (2023-01-30T20:26:13Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)
• Causal Expectation-Maximisation [70.45873402967297]
  ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。 我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。 我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
  論文  参考訳（メタデータ） (2020-11-04T10:25:13Z)
• Model Interpretability through the Lens of Computational Complexity [1.6631602844999724]
  民間の解釈可能性主張が計算複雑性理論に相関しているかどうかを考察する。 線形モデルとツリーモデルの両方がニューラルネットワークよりも厳密に解釈可能であることを示す。
  論文  参考訳（メタデータ） (2020-10-23T09:50:40Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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