論文の概要: Probabilistic and Causal Satisfiability: the Impact of Marginalization
- arxiv url: http://arxiv.org/abs/2405.07373v2
- Date: Fri, 7 Jun 2024 12:35:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-10 19:08:28.949172
- Title: Probabilistic and Causal Satisfiability: the Impact of Marginalization
- Title（参考訳）: 確率的満足度と因果的満足度:マリナライゼーションの影響
- Authors: Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz,
- Abstract要約: 確率的・因果的言語で表される満足度問題に焦点をあてる。
線形言語はNPPP-, PSPACE-, NEXP完全満足度問題をもたらすことを示す。
また、与えられたベイズネットワーク、有向非巡回グラフ構造、あるいは小さなサイズに制限された制約付きモデルについても検討する。
- 参考スコア（独自算出の注目度）: 3.44747819522562
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: 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? The resulting complexity changes depending on the level of the hierarchy as well as the operators allowed in the formulas (addition, multiplication, or marginalization). We focus on formulas involving marginalization that are widely used in probabilistic and causal inference, but whose complexity issues are still little explored. Our main contribution are the exact computational complexity results showing that linear languages (allowing addition and marginalization) yield NP^PP-, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. Moreover, we prove that the problem for the full language (allowing additionally multiplication) is complete for the class succ$\exists$R for languages on the highest, counterfactual level, which extends previous results for the lower levels of the PCH. Finally, we consider constrained models that are restricted to a given Bayesian network, a Directed Acyclic Graph structure, or a small polynomial size. The complexity of languages on the interventional level is increased to the complexity of counterfactual languages without such a constraint, that is, linear languages become NEXP-complete. On the other hand, the complexity on the counterfactual level does not change. The constraint on the size reduces the complexity of the interventional and counterfactual languages to NEXP-complete.
- Abstract（参考訳）: パールズ・コーサル・ヒエラルキー(PCH)の枠組みは、因果関係に関する人間の思考の進歩的洗練を反映した観察的、介入的、反ファクト的という3つのタイプの推論を定式化した。
本稿では,PCH全体にわたる確率的および因果的言語で表される満足度問題を中心に,この枠組みにおける推論の計算複雑性の側面を考察する。
つまり、標準確率言語および因果言語における式体系を考えると、式を満たすモデルが存在するだろうか?
結果として生じる複雑性は、階層のレベルや公式で許される演算子(加算、乗算、余剰化)によって変化する。
我々は,確率的および因果推論に広く用いられている辺縁化を含む式に着目するが,その複雑性問題はほとんど検討されていない。
我々の主な貢献は、線形言語(加算と余剰化が可能である)がPCHのレベルに応じてNP^PP-, PSPACE-, NEXP完全満足度問題をもたらすことを示す正確な計算複雑性の結果である。
さらに、PCHの下位レベルに対する前の結果を拡張した最も高い対実レベルの言語に対するクラス Succ$\exists$R に対して、完全言語(余剰乗算も可能)の問題は完備であることを示す。
最後に、与えられたベイズネットワーク、有向非巡回グラフ構造、あるいは小さな多項式サイズに制限された制約付きモデルを考える。
介入レベルでの言語の複雑さは、そのような制約のない反事実言語の複雑さ、すなわち線形言語がNEXP完全になるまで増大する。
一方、対物レベルの複雑さは変わらない。
サイズに対する制約は、介入言語と反ファクト言語の複雑さをNEXP完全に減らす。
関連論文リスト
- 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) - Parrot Mind: Towards Explaining the Complex Task Reasoning of Pretrained Large Language Models with Template-Content Structure [66.33623392497599]
テンプレート・コンテント構造(T-C構造)と呼ばれる構造は指数レベルから線形レベルへの可能な空間を減少させることができることを示す。
モデルがタスク構成を達成でき、線形から対数への学習に必要なスペースをさらに削減できることを実証する。
論文 参考訳（メタデータ） (2023-10-09T06:57:45Z) - When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。
具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。
コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
論文 参考訳（メタデータ） (2023-08-29T17:22:39Z) - The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。
この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。
我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
論文 参考訳（メタデータ） (2023-05-16T15:01:22Z) - Optimistic MLE -- A Generic Model-based Algorithm for Partially
Observable Sequential Decision Making [48.87943416098096]
本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。
我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
論文 参考訳（メタデータ） (2022-09-29T17:56:25Z) - Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
我々は構造化出力予測(SOP)のための予測層を設計する。
予測が事前に定義されたシンボリック制約のセットと一致していることを保証するため、任意のニューラルネットワークにプラグインすることができる。
我々のセマンティック確率層(SPL)は、構造化された出力空間上で複雑な相関や制約をモデル化することができる。
論文 参考訳（メタデータ） (2022-06-01T12:02:38Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳（メタデータ） (2020-06-22T17:58:54Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である
本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。
また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文 参考訳（メタデータ） (2020-01-13T13:16:13Z) - Probabilistic Reasoning across the Causal Hierarchy [10.138180861883635]
私たちの言語は厳格に表現力を高めている。
それぞれの言語に対する満足度と妥当性は空間的に決定可能であることを示す。
論文 参考訳（メタデータ） (2020-01-09T08:52:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。