From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy

• URL: http://arxiv.org/abs/2405.07373v3
• Date: Thu, 06 Feb 2025 18:53:16 GMT
• Title: From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
• Authors: Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz,
• Abstract summary: 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.
• Score: 3.44747819522562
• License:
• Abstract: The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the progressive sophistication of human thought regarding causation. We investigate the computational complexity aspects of reasoning in this framework focusing mainly on satisfiability problems expressed in probabilistic and causal languages across the PCH. That is, given a system of formulas in the standard probabilistic and causal languages, does there exist a model satisfying the formulas? Our main contribution is to prove the exact computational complexities showing that languages allowing addition and marginalization (via the summation operator) yield NP^PP, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. These are the first results to demonstrate a strictly increasing complexity across the PCH: from probabilistic to causal and counterfactual reasoning. 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, solving an open problem in the field.

Related papers

• Algorithmic causal structure emerging through compression [53.52699766206808]
  We explore the relationship between causality, symmetry, and compression. We build on and generalize the known connection between learning and compression to a setting where causal models are not identifiable. We define algorithmic causality as an alternative definition of causality when traditional assumptions for causal identifiability do not hold.
  arXiv  Detail & Related papers  (2025-02-06T16:50:57Z)
• 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)
• 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)
• 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)
• MetaLogic: Logical Reasoning Explanations with Fine-Grained Structure [129.8481568648651]
  We propose a benchmark to investigate models' logical reasoning capabilities in complex real-life scenarios. Based on the multi-hop chain of reasoning, the explanation form includes three main components. We evaluate the current best models' performance on this new explanation form.
  arXiv  Detail & Related papers  (2022-10-22T16:01:13Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  This paper introduces a simple efficient learning algorithms for general sequential decision making. We prove that OMLE learns near-optimal policies of an enormously rich class of sequential decision making problems.
  arXiv  Detail & Related papers  (2022-09-29T17:56:25Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• 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)
• Algorithms for Causal Reasoning in Probability Trees [13.572630988699572]
  We present concrete algorithms for causal reasoning in discrete probability trees. Our work expands the domain of causal reasoning to a very general class of discrete processes.
  arXiv  Detail & Related papers  (2020-10-23T08:51:52Z)
• 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.