論文の概要: 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) が証明したよりも強いアルゴリズム的制限を示唆している。
関連論文リスト
- Probabilistic Reasoning in Generative Large Language Models [21.335836561959887]
本稿では,Large Language Models (LLM) が,確率値を介して明示的に定量化される不確実性を含む情報を含むテキストを推論する際に直面する課題について考察する。
LLMの確率論的推論能力をテストするために設計された新しいデータセットであるBayesian Linguistic Inference dataset (BLInD)を紹介する。
本稿では,Pythonのコード,確率的推論アルゴリズム,確率論的論理プログラミングなど,様々な形式的表現に問題をマッピングする戦略を提案する。
論文 参考訳(メタデータ) (2024-02-14T23:05:44Z) - Probabilistic relations for modelling epistemic and aleatoric
uncertainty: semantics and automated reasoning with theorem proving [0.7219077740523682]
確率的プログラミングは、一般的なコンピュータプログラミング、統計的推論、形式的意味論を組み合わせたものである。
私たちの仕事は、Hehner氏の予測確率的プログラミングに基づいていますが、彼の仕事が広く採用されるにはいくつかの障害があります。
ロボットのローカライゼーションの問題,機械学習の分類,確率ループの終了など,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) - Marginal Inference queries in Hidden Markov Models under context-free
grammar constraints [0.348097307252416]
隠れモデル(HMM)における文脈自由文法(CFG)の可能性の計算問題に対処する。
問題は NP-Hard であり、CFG が 2 以下のあいまいさの次数を持つという約束があるにもかかわらずである。
次に,不明瞭なCFGの場合の確率を近似するために,完全ランダム化近似法を提案する。
論文 参考訳(メタデータ) (2022-06-26T12:44:18Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳(メタデータ) (2021-10-21T07:28:11Z) - Logical Credal Networks [87.25387518070411]
本稿では,論理と確率を組み合わせた先行モデルの多くを一般化した表現的確率論的論理である論理的クレダルネットワークを紹介する。
本稿では,不確実性のあるマスターミンドゲームを解くこと,クレジットカード詐欺を検出することを含む,最大後部推論タスクの性能について検討する。
論文 参考訳(メタデータ) (2021-09-25T00:00:47Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文 参考訳(メタデータ) (2020-07-30T04:18:51Z) - Logic, Probability and Action: A Situation Calculus Perspective [12.47276164048813]
論理と確率の統一は、AIにおける長年の関心事である。
現状計算における論理・確率・行動の統合に関する最近の結果について考察する。
結果は認知ロボティクスの文脈で動機づけられる。
論文 参考訳(メタデータ) (2020-06-17T13:49:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。