論文の概要: From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy

• arxiv url: http://arxiv.org/abs/2405.07373v3
• Date: Thu, 06 Feb 2025 18:53:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-07 14:30:06.337677
• Title: From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
• Title（参考訳）: 確率から対物へ:パールの因果的階層における満足度の複雑さの増大
• Authors: Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz,
• Abstract要約: PCHのレベルによって, NPPP, PSPACE, NEXP完全満足度の問題が生じることを示す。 一方、完全言語の場合、すなわち加法、余分化、乗算が可能である場合、反事実レベルの満足度は確率的・因果的なレベルと同じであることを示す。
• 参考スコア（独自算出の注目度）: 3.44747819522562
• License:
• Abstract: The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the progressive sophistication of human thought regarding causation. We investigate the computational complexity aspects of reasoning in this framework focusing mainly on satisfiability problems expressed in probabilistic and causal languages across the PCH. That is, given a system of formulas in the standard probabilistic and causal languages, does there exist a model satisfying the formulas? Our main contribution is to prove the exact computational complexities showing that languages allowing addition and marginalization (via the summation operator) yield NP^PP, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. These are the first results to demonstrate a strictly increasing complexity across the PCH: from probabilistic to causal and counterfactual reasoning. On the other hand, in the case of full languages, i.e. allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels, solving an open problem in the field.
• Abstract（参考訳）: パールの因果的階層(英語版)(PCH)の枠組みは、因果関係に関する人間の思考の進歩的洗練を反映した確率論的(純粋に観察的)、介入的(英語版)、反ファクト的(英語版)の3つのタイプの推論を定式化する。 本稿では,PCH全体にわたる確率的および因果的言語で表される満足度問題を中心に,この枠組みにおける推論の計算複雑性の側面を考察する。 つまり、標準確率言語および因果言語における式体系を考えると、式を満たすモデルが存在するだろうか? 我々の主な貢献は、加法および余剰化が可能な言語が、PCHのレベルに応じてNP^PP, PSPACE-, NEXP完全満足度問題をもたらすことを示す正確な計算複雑性を証明することである。 これらは、確率論的から因果的・反事実的推論まで、PCH全体の複雑さを厳密に増加させる最初の結果である。 一方、完全言語の場合、すなわち加法、余分化、乗算が可能である場合、反事実レベルの満足度は確率的および因果的なレベルと同じであり、この分野におけるオープンな問題を解く。

関連論文リスト

• Algorithmic causal structure emerging through compression [53.52699766206808]
  因果関係,対称性,圧縮の関係について検討する。 我々は、学習と圧縮の既知の関係を因果モデルが識別できないような環境に構築し、一般化する。 我々はアルゴリズム因果関係を因果関係の代替的定義として定義する。
  論文  参考訳（メタデータ） (2025-02-06T16:50:57Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• On Probabilistic and Causal Reasoning with Summation Operators [3.1133049660590615]
  各因果言語における推論は、計算複雑性の観点からは、単に確率的あるいは「相関的」な推論と同じくらい困難であることを示す。 因果推論のための$do$-calculus of Pearl (2009)のようなアプリケーションに現れる一般的なデバイスをキャプチャするための和演算子を導入する。 意外なことに、ランダム変数値に対する自由変数の許容は、これらのランダム変数の範囲が制限されない限り、決定不可能なシステムをもたらす。
  論文  参考訳（メタデータ） (2024-05-05T22:32:01Z)
• The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
  本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。 この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。 我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
  論文  参考訳（メタデータ） (2023-05-16T15:01:22Z)
• MetaLogic: Logical Reasoning Explanations with Fine-Grained Structure [129.8481568648651]
  複雑な実生活シナリオにおけるモデルの論理的推論能力を調べるためのベンチマークを提案する。 推論のマルチホップ連鎖に基づいて、説明形式は3つの主成分を含む。 この新たな説明形式を用いて,現在のベストモデルの性能を評価した。
  論文  参考訳（メタデータ） (2022-10-22T16:01:13Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。 我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
  論文  参考訳（メタデータ） (2022-09-29T17:56:25Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Causal Expectation-Maximisation [70.45873402967297]
  ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。 我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。 我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
  論文  参考訳（メタデータ） (2020-11-04T10:25:13Z)
• Algorithms for Causal Reasoning in Probability Trees [13.572630988699572]
  離散確率木における因果推論のための具体的なアルゴリズムを提案する。 我々の研究は因果推論の領域を非常に一般的な離散過程のクラスへと拡張する。
  論文  参考訳（メタデータ） (2020-10-23T08:51:52Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• Probabilistic Reasoning across the Causal Hierarchy [10.138180861883635]
  私たちの言語は厳格に表現力を高めている。 それぞれの言語に対する満足度と妥当性は空間的に決定可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-09T08:52:14Z)

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

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