On Probabilistic and Causal Reasoning with Summation Operators

• URL: http://arxiv.org/abs/2405.03069v2
• Date: Sat, 18 May 2024 20:14:42 GMT
• Title: On Probabilistic and Causal Reasoning with Summation Operators
• Authors: Duligur Ibeling, Thomas F. Icard, Milan Mossé,
• Abstract summary: 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.
• Score: 3.1133049660590615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ibeling et al. (2023). axiomatize increasingly expressive languages of causation and probability, and Mosse et al. (2024) show that reasoning (specifically the satisfiability problem) in each causal language is as difficult, from a computational complexity perspective, as reasoning in its merely probabilistic or "correlational" counterpart. Introducing a summation operator to capture common devices that appear in applications -- such as the $do$-calculus of Pearl (2009) for causal inference, which makes ample use of marginalization -- van der Zander et al. (2023) partially extend these earlier complexity results to causal and probabilistic languages with marginalization. We complete this extension, fully characterizing the complexity of probabilistic and causal reasoning with summation, demonstrating that these again remain equally difficult. 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. We finally axiomatize these languages featuring marginalization (or more generally summation), resolving open questions posed by Ibeling et al. (2023).

Related papers

• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAP generates problem statements and chain-of-thought reasoning traces according to specifications about their arithmetic proof structure. Using MathGAP, we find that LLMs show a significant decrease in performance as proofs get deeper and wider.
  arXiv  Detail & Related papers  (2024-10-17T12:48:14Z)
• QUITE: Quantifying Uncertainty in Natural Language Text in Bayesian Reasoning Scenarios [15.193544498311603]
  We present QUITE, a dataset of real-world Bayesian reasoning scenarios with categorical random variables and complex relationships. We conduct an extensive set of experiments, finding that logic-based models outperform out-of-the-box large language models on all reasoning types. Our results provide evidence that neuro-symbolic models are a promising direction for improving complex reasoning.
  arXiv  Detail & Related papers  (2024-10-14T12:44:59Z)
• 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)
• To Believe or Not to Believe Your LLM [51.2579827761899]
  We explore uncertainty quantification in large language models (LLMs) We derive an information-theoretic metric that allows to reliably detect when only epistemic uncertainty is large. We conduct a series of experiments which demonstrate the advantage of our formulation.
  arXiv  Detail & Related papers  (2024-06-04T17:58:18Z)
• From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
  We show that languages allowing addition and marginalization yield NPPP, PSPACE, and NEXP-complete satisfiability problems, depending on the level of the PCH. On the other hand, in the case of full languages, i.e. allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels.
  arXiv  Detail & Related papers  (2024-05-12T20:25:36Z)
• The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
  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.
  arXiv  Detail & Related papers  (2023-05-16T15:01:22Z)
• Interpolation can hurt robust generalization even when there is no noise [76.3492338989419]
  We show that avoiding generalization through ridge regularization can significantly improve generalization even in the absence of noise. We prove this phenomenon for the robust risk of both linear regression and classification and hence provide the first theoretical result on robust overfitting.
  arXiv  Detail & Related papers  (2021-08-05T23:04:15Z)
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding [101.35070661471124]
  We show that unobserved confounding leaves a characteristic footprint in the observed data distribution that allows for disentangling spurious and causal effects. We propose an adjusted score-based causal discovery algorithm that may be implemented with general-purpose solvers and scales to high-dimensional problems.
  arXiv  Detail & Related papers  (2021-03-28T11:07:59Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• 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.