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

• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  Large language models (LLMs) can solve arithmetic word problems with high accuracy, but little is known about how well they generalize to problems that are more complex than the ones on which they have been trained. We present a framework for evaluating LLMs on problems with arbitrarily complex arithmetic proofs, called MathGAP.
  arXiv  Detail & Related papers  (2024-10-17T12:48:14Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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 unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving [0.3441021278275805]
  Probabilistic programming combines general computer programming, statistical inference, and formal semantics. ProbURel is based on Hehner's predicative probabilistic programming, but there are several obstacles to the broader adoption of his work. Our contributions include the formalisation of relations using Unifying Theories of Programming (UTP) and probabilities outside the brackets. 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)
• 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)
• 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.