On Probabilistic and Causal Reasoning with Summation Operators
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).
Code (0)
등록된 구현이 없습니다.
Tasks
Causal InferenceSimilar Papers 제목 키워드 기반
From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
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 tho…
Causal InferencecounterfactualCounterfactual ReasoningT-CPDL: A Temporal Causal Probabilistic Description Logic for Developing Logic-RAG Agent
Large language models excel at generating fluent text but frequently struggle with structured reasoning involving temporal constraints, causal relationships, and probabilistic reasoning. To address these limitations, we …
Causal InferenceDecision MakingRAGRetrieval-augmented GenerationCausal Temporal Reasoning for Markov Decision Processes
We introduce $\textit{PCFTL (Probabilistic CounterFactual Temporal Logic)}$, a new probabilistic temporal logic for the verification of Markov Decision Processes (MDP). PCFTL is the first to include operators for causal …
counterfactualCounterfactual ReasoningSafe Reinforcement LearningMultiVerse: Causal Reasoning using Importance Sampling in Probabilistic Programming
We elaborate on using importance sampling for causal reasoning, in particular for counterfactual inference. We show how this can be implemented natively in probabilistic programming. By considering the structure of the c…
counterfactualCounterfactual InferenceProbabilistic ProgrammingProbabilistic Reasoning across the Causal Hierarchy
We propose a formalization of the three-tier causal hierarchy of association, intervention, and counterfactuals as a series of probabilistic logical languages. Our languages are of strictly increasing expressivity, the f…
Bayesian Inferencecounterfactual