The Hardness of Reasoning about Probabilities and Causality
- URL: http://arxiv.org/abs/2305.09508v1
- Date: Tue, 16 May 2023 15:01:22 GMT
- Title: The Hardness of Reasoning about Probabilities and Causality
- Authors: Benito van der Zander and Markus Bl\"aser and Maciej Li\'skiewicz
- Abstract summary: We study languages capable of expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects.
The main contribution of this work is establishing the exact computational complexity of 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.
- Score: 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.
Related papers
- Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
We develop an algorithm for the complex task of computing the probability of a set of arguments being a complete extension.
An experimental evaluation shows promise of our approach.
arXiv Detail & Related papers (2024-07-06T12:08:38Z) - Probabilistic and Causal Satisfiability: the Impact of Marginalization [3.44747819522562]
We focus on satisfiability problems expressed in probabilistic and causal languages.
We show that linear languages (allowing addition and marginalization) yield NPPP-, PSPACE-, and NEXP-complete satisfiability problems.
We also consider constrained models that are restricted to a given Bayesian network, a Directed Acyclic Graph structure, or a small size.
arXiv Detail & Related papers (2024-05-12T20:25:36Z) - On Probabilistic and Causal Reasoning with Summation Operators [3.1133049660590615]
We show that reasoning in each causal language is as difficult, from a computational complexity perspective, as reasoning in its merely probabilistic or "correlational" counterpart.
We introduce a summation operator to capture common devices that appear in applications, such as the $do$-calculus of Pearl (2009) for causal inference.
Surprisingly, allowing free variables for random variable values results in a system that is undecidable, so long as the ranges of these random variables are unrestricted.
arXiv Detail & Related papers (2024-05-05T22:32:01Z) - Probabilistic relations for modelling epistemic and aleatoric
uncertainty: semantics and automated reasoning with theorem proving [0.7219077740523682]
Probabilistic programming combines general computer programming, statistical inference, and formal semantics.
Our work is based on Hehner's predicative probabilistic programming, but there are several obstacles to the broader adoption of his work.
We demonstrate our work with six examples, including problems in robot localisation, classification in machine learning, and the termination of probabilistic loops.
arXiv Detail & Related papers (2023-03-16T23:36:57Z) - $\omega$PAP Spaces: Reasoning Denotationally About Higher-Order,
Recursive Probabilistic and Differentiable Programs [64.25762042361839]
$omega$PAP spaces are spaces for reasoning denotationally about expressive differentiable and probabilistic programming languages.
Our semantics is general enough to assign meanings to most practical probabilistic and differentiable programs.
We establish the almost-everywhere differentiability of probabilistic programs' trace density functions.
arXiv Detail & Related papers (2023-02-21T12:50:05Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
Most datasets only capture a simpler subproblem and likely suffer from spurious features.
We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features.
Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound.
Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
arXiv Detail & Related papers (2021-10-21T07:28:11Z) - Logical Credal Networks [87.25387518070411]
This paper introduces Logical Credal Networks, an expressive probabilistic logic that generalizes many prior models that combine logic and probability.
We investigate its performance on maximum a posteriori inference tasks, including solving Mastermind games with uncertainty and detecting credit card fraud.
arXiv Detail & Related papers (2021-09-25T00:00:47Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
We study the exploration-exploitation tradeoff at the core of reinforcement learning.
In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function.
Our regret bounds are independent of the number of episodes.
arXiv Detail & Related papers (2020-11-09T18:32:22Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent PAC model.
We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem.
arXiv Detail & Related papers (2020-07-30T04:18:51Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
We present a novel approach to formulate different notions of causal reasoning, over binary acyclic models, as optimization problems.
We show that both notions are efficiently automated. Using models with more than $8000$ variables, checking is computed in a matter of seconds, with MaxSAT outperforming ILP in many cases.
arXiv Detail & Related papers (2020-06-05T10:56:52Z) - Probabilistic Reasoning across the Causal Hierarchy [10.138180861883635]
Our languages are of strictly increasing expressivity.
We show that satisfiability and validity for each language are decidable in space.
arXiv Detail & Related papers (2020-01-09T08:52:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.