Probabilistic and Causal Satisfiability: the Impact of Marginalization

• URL: http://arxiv.org/abs/2405.07373v2
• Date: Fri, 7 Jun 2024 12:35:11 GMT
• Title: Probabilistic and Causal Satisfiability: the Impact of Marginalization
• Authors: Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz,
• Abstract summary: 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.
• Score: 3.44747819522562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: 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? The resulting complexity changes depending on the level of the hierarchy as well as the operators allowed in the formulas (addition, multiplication, or marginalization). We focus on formulas involving marginalization that are widely used in probabilistic and causal inference, but whose complexity issues are still little explored. Our main contribution are the exact computational complexity results showing that linear languages (allowing addition and marginalization) yield NP^PP-, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. Moreover, we prove that the problem for the full language (allowing additionally multiplication) is complete for the class succ$\exists$R for languages on the highest, counterfactual level, which extends previous results for the lower levels of the PCH. Finally, we consider constrained models that are restricted to a given Bayesian network, a Directed Acyclic Graph structure, or a small polynomial size. The complexity of languages on the interventional level is increased to the complexity of counterfactual languages without such a constraint, that is, linear languages become NEXP-complete. On the other hand, the complexity on the counterfactual level does not change. The constraint on the size reduces the complexity of the interventional and counterfactual languages to NEXP-complete.

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.