論文の概要: On the Complexity of Counterfactual Reasoning
- arxiv url: http://arxiv.org/abs/2211.13447v2
- Date: Fri, 19 May 2023 05:19:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 19:33:49.794289
- Title: On the Complexity of Counterfactual Reasoning
- Title（参考訳）: 反実的推論の複雑さについて
- Authors: Yunqiu Han, Yizuo Chen, Adnan Darwiche
- Abstract要約: 本研究は, 完全特定SCM上での協調的・介入的推論に比較して, 対実的推論は困難ではないことを示す。
我々は、結果を2つ以上の世界を考える必要がある一般的な反事実的推論にまで拡張する。
- 参考スコア（独自算出の注目度）: 9.614694312155795
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the computational complexity of counterfactual reasoning in relation
to the complexity of associational and interventional reasoning on structural
causal models (SCMs). We show that counterfactual reasoning is no harder than
associational or interventional reasoning on fully specified SCMs in the
context of two computational frameworks. The first framework is based on the
notion of treewidth and includes the classical variable elimination and
jointree algorithms. The second framework is based on the more recent and
refined notion of causal treewidth which is directed towards models with
functional dependencies such as SCMs. Our results are constructive and based on
bounding the (causal) treewidth of twin networks -- used in standard
counterfactual reasoning that contemplates two worlds, real and imaginary -- to
the (causal) treewidth of the underlying SCM structure. In particular, we show
that the latter (causal) treewidth is no more than twice the former plus one.
Hence, if associational or interventional reasoning is tractable on a fully
specified SCM then counterfactual reasoning is tractable too. We extend our
results to general counterfactual reasoning that requires contemplating more
than two worlds and discuss applications of our results to counterfactual
reasoning with a partially specified SCM that is coupled with data. We finally
present empirical results that measure the gap between the complexities of
counterfactual reasoning and associational/interventional reasoning on random
SCMs.
- Abstract（参考訳）: 構造因果モデル(scms)における連想的・介入的推論の複雑性に関連して,反事実的推論の計算複雑性について検討した。
本稿では,2つの計算フレームワークの文脈において,完全に指定されたSCM上での協調的あるいは介入的推論よりも反実的推論が困難であることを示す。
最初のフレームワークはtreewidthの概念に基づいており、古典的な変数除去とジョインツリーアルゴリズムを含んでいる。
第2のフレームワークは、SCMのような機能的依存関係を持つモデルに向けられた、より最近で洗練された因果木幅の概念に基づいている。
我々の結果は構成的であり、基礎となるSCM構造の(因果的)ツリー幅に対して、実と虚の2つの世界を考える標準的な反実的推論で使われる双対ネットワークの(因果的)ツリー幅の有界化に基づいている。
特に、後者(causal)の木の幅は、前者プラス1の2倍以下であることを示す。
したがって、完全に指定されたSCM上で結合的または介入的推論が抽出可能であれば、反事実的推論も抽出可能となる。
我々は,2つ以上の世界を考える一般の反実的推論に結果を拡張し,データと結合した部分的特定SCMを用いて反実的推論への応用について議論する。
最終的に、対実的推論の複雑さとランダムなSCMにおける連帯的・インターベンショナル推論のギャップを測る実験結果を示す。
関連論文リスト
- CreDes: Causal Reasoning Enhancement and Dual-End Searching for Solving Long-Range Reasoning Problems using LLMs [13.977459316171013]
大規模言語モデル(LLM)は、長距離推論を含む最適化問題に対処する際の限界を実証している。
本稿では、因果関係強化(CRE)機構と個別治療効果(ITE)を組み合わせて、因果関係の確固たる正当性を保証する。
実験により、CreDesは精度と時間効率の両方で既存のState-Of-The-Art(SOTA)ソリューションを著しく上回っていることが示された。
論文 参考訳（メタデータ） (2024-10-02T16:05:01Z) - Cause and Effect: Can Large Language Models Truly Understand Causality? [1.2334534968968969]
本研究では,CARE CA(Content Aware Reasoning Enhancement with Counterfactual Analysis)フレームワークという新しいアーキテクチャを提案する。
提案するフレームワークには,ConceptNetと反ファクト文を備えた明示的な因果検出モジュールと,大規模言語モデルによる暗黙的な因果検出が組み込まれている。
ConceptNetの知識は、因果的発見、因果的識別、反事実的推論といった複数の因果的推論タスクのパフォーマンスを向上させる。
論文 参考訳（メタデータ） (2024-02-28T08:02:14Z) - Answering Causal Queries at Layer 3 with DiscoSCMs-Embracing
Heterogeneity [0.0]
本稿では, 分散一貫性構造因果モデル (DiscoSCM) フレームワークを, 反事実推論の先駆的アプローチとして提唱する。
論文 参考訳（メタデータ） (2023-09-17T17:01:05Z) - When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。
具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。
コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
論文 参考訳（メタデータ） (2023-08-29T17:22:39Z) - A Semantic Approach to Decidability in Epistemic Planning (Extended
Version) [72.77805489645604]
我々は決定可能性を達成するために新しい意味論的アプローチを用いる。
具体的には、知識の論理S5$_n$と(知識)可換性と呼ばれる相互作用公理を拡大する。
我々は,本フレームワークが,独立した知識である共通知識の有限的非固定点的特徴を認めていることを証明した。
論文 参考訳（メタデータ） (2023-07-28T11:26:26Z) - Comparing Causal Frameworks: Potential Outcomes, Structural Models,
Graphs, and Abstractions [10.889531739861562]
本稿では, ルビン因果モデル (RCM) と構造因果モデル (SCM) の関係を明らかにすることを目的とする。
主要な結果は、SCMフレームワークによって暗示される代数的原則に違反しているものを含む全てのRCMが、表現可能なRCMの抽象化として現れることを示している。
論文 参考訳（メタデータ） (2023-06-25T21:57:20Z) - Modeling Hierarchical Reasoning Chains by Linking Discourse Units and
Key Phrases for Reading Comprehension [80.99865844249106]
本稿では,論理的推論の基盤として,対話レベルと単語レベルの両方の文脈を扱う総合グラフネットワーク(HGN)を提案する。
具体的には、ノードレベルの関係とタイプレベルの関係は、推論過程におけるブリッジと解釈できるが、階層的な相互作用機構によってモデル化される。
論文 参考訳（メタデータ） (2023-06-21T07:34:27Z) - Counterfactuals Modulo Temporal Logics [1.90365714903665]
ルイスの反事実論は、多くの現代の因果性の概念の基礎となっている。
我々はこの理論を時間方向に拡張し、無限列上の記号的対実的推論を可能にする。
論文 参考訳（メタデータ） (2023-06-15T07:40:36Z) - Neural Causal Models for Counterfactual Identification and Estimation [62.30444687707919]
本稿では,ニューラルモデルによる反事実文の評価について検討する。
まず、神経因果モデル(NCM)が十分に表現可能であることを示す。
第2に,反事実分布の同時同定と推定を行うアルゴリズムを開発する。
論文 参考訳（メタデータ） (2022-09-30T18:29:09Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳（メタデータ） (2020-11-04T10:25:13Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。