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
- 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) - Parrot Mind: Towards Explaining the Complex Task Reasoning of Pretrained Large Language Models with Template-Content Structure [66.33623392497599]
We show that a structure called template-content structure (T-C structure) can reduce the possible space from exponential level to linear level.
We demonstrate that models can achieve task composition, further reducing the space needed to learn from linear to logarithmic.
arXiv Detail & Related papers (2023-10-09T06:57:45Z) - When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities.
Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity.
Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
arXiv Detail & Related papers (2023-08-29T17:22:39Z) - 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) - 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) - Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
We design a predictive layer for structured-output prediction (SOP)
It can be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints.
Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over a structured output space.
arXiv Detail & Related papers (2022-06-01T12:02:38Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs)
We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
arXiv Detail & Related papers (2020-06-22T17:58:54Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data.
In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem.
We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z) - Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP)
We show that central problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth.
We also provide a full dynamic programming algorithm that adheres to these bounds.
arXiv Detail & Related papers (2020-01-13T13:16:13Z) - 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.