論文の概要: The Hardness of Reasoning about Probabilities and Causality

• arxiv url: http://arxiv.org/abs/2305.09508v1
• Date: Tue, 16 May 2023 15:01:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-17 14:28:45.224533
• Title: The Hardness of Reasoning about Probabilities and Causality
• Title（参考訳）: 確率と因果関係に関する推論の難しさ
• Authors: Benito van der Zander and Markus Bl\"aser and Maciej Li\'skiewicz
• Abstract要約: 本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。 この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。 我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
• 参考スコア（独自算出の注目度）: 5.190207094732672
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective. We focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference. The main contribution of this work is establishing the exact computational complexity of these satisfiability problems. We introduce a new natural complexity class, named succ$\exists$R, which can be viewed as a succinct variant of the well-studied class $\exists$R, and show that the problems we consider are complete for succ$\exists$R. Our results imply even stronger algorithmic limitations than were proven by Fagin, Halpern, and Megiddo (1990) and Moss\'{e}, Ibeling, and Icard (2022) for some variants of the standard languages used commonly in probabilistic and causal inference.
• Abstract（参考訳）: 本稿では,計算複雑性の観点から,量的確率論的推論と因果関係推論を完全表現できる形式言語について検討する。 我々は、確率的および因果推論において多くのタスクを表現できる例式を満足度問題に焦点をあてる。 この研究の主な貢献は、これらの満足度問題の正確な計算複雑性を確立することである。 我々は、よく研究されたクラス $\exists$R の簡潔な変種と見なすことができる succ$\exists$R という新しい自然複雑性クラスを導入し、我々が考える問題は succ$\exists$R に対して完備であることを示す。 我々の結果は、確率的および因果推論で一般的に使用される標準言語の変種に対して、Fagin, Halpern, Megiddo (1990) と Moss\'{e}, Ibeling, Icard (2022) が証明したよりも強いアルゴリズム的制限を示唆している。

関連論文リスト

• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  大規模言語モデル(LLM)は、高い精度で算術語問題を解くことができるが、訓練された言語よりも複雑な問題にどのように一般化するかは、ほとんど分かっていない。 本研究では、任意に複雑な算術証明問題に対する LLM の評価フレームワーク、MathGAP を提案する。
  論文  参考訳（メタデータ） (2024-10-17T12:48:14Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
  完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。 実験的評価は我々のアプローチの可能性を示唆している。
  論文  参考訳（メタデータ） (2024-07-06T12:08:38Z)
• Probabilistic and Causal Satisfiability: the Impact of Marginalization [3.44747819522562]
  確率的・因果的言語で表される満足度問題に焦点をあてる。 線形言語は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)
• Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving [0.3441021278275805]
  確率的プログラミングは、一般的なコンピュータプログラミング、統計的推論、形式的意味論を組み合わせたものである。 ProbURelは、Hehnerの予測確率的プログラミングに基づいているが、彼の作品が広く採用されるにはいくつかの障害がある。 コントリビューションには、Unified Theories of Programming(UTP)を使用した関係の形式化や、ブラケット外の確率などが含まれています。 ロボットのローカライゼーションの問題,機械学習の分類,確率ループの終了など,6つの事例で研究成果を実演する。
  論文  参考訳（メタデータ） (2023-03-16T23:36:57Z)
• $\omega$PAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs [64.25762042361839]
  $omega$PAP 空間は表現的微分可能および確率的プログラミング言語についての推論のための空間である。 我々の意味論は、最も実践的な確率的で微分可能なプログラムに意味を割り当てるのに十分である。 確率プログラムのトレース密度関数のほぼすべての微分可能性を確立する。
  論文  参考訳（メタデータ） (2023-02-21T12:50:05Z)
• Logical Credal Networks [87.25387518070411]
  本稿では,論理と確率を組み合わせた先行モデルの多くを一般化した表現的確率論的論理である論理的クレダルネットワークを紹介する。 本稿では,不確実性のあるマスターミンドゲームを解くこと,クレジットカード詐欺を検出することを含む,最大後部推論タスクの性能について検討する。
  論文  参考訳（メタデータ） (2021-09-25T00:00:47Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)
• 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)

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

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