From Checking to Inference: Actual Causality Computations as
Optimization Problems
- URL: http://arxiv.org/abs/2006.03363v2
- Date: Mon, 6 Jul 2020 11:28:01 GMT
- Title: From Checking to Inference: Actual Causality Computations as
Optimization Problems
- Authors: Amjad Ibrahim and Alexander Pretschner
- Abstract summary: 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.
- Score: 79.87179017975235
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Actual causality is increasingly well understood. Recent formal approaches,
proposed by Halpern and Pearl, have made this concept mature enough to be
amenable to automated reasoning. Actual causality is especially vital for
building accountable, explainable systems. Among other reasons, causality
reasoning is computationally hard due to the requirements of counterfactuality
and the minimality of causes. Previous approaches presented either inefficient
or restricted, and domain-specific, solutions to the problem of automating
causality reasoning. In this paper, we present a novel approach to formulate
different notions of causal reasoning, over binary acyclic models, as
optimization problems, based on quantifiable notions within counterfactual
computations. We contribute and compare two compact, non-trivial, and sound
integer linear programming (ILP) and Maximum Satisfiability (MaxSAT) encodings
to check causality. Given a candidate cause, both approaches identify what a
minimal cause is. Also, we present an ILP encoding to infer causality without
requiring a candidate cause. 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. In
contrast, inference is computed in a matter of minutes.
Related papers
- Causal Discovery and Prediction: Methods and Algorithms [0.0]
In this thesis we introduce a generic a-priori assessment of each possible intervention.
We propose an active learning algorithm that identifies the causal relations in any given causal model.
arXiv Detail & Related papers (2023-09-18T01:19:37Z) - A Framework for Data-Driven Explainability in Mathematical Optimization [0.0]
provably optimal solutions may not be accepted due to the perception of optimization software as a black box.
We advocate for introducing the explainability of a solution as another evaluation criterion, next to its objective value.
It turns out the cost of enforcing explainability can be very small.
arXiv Detail & Related papers (2023-08-16T12:12:24Z) - Complex Query Answering on Eventuality Knowledge Graph with Implicit
Logical Constraints [48.831178420807646]
We propose a new framework to leverage neural methods to answer complex logical queries based on an EVentuality-centric KG.
Complex Eventuality Query Answering (CEQA) considers the implicit logical constraints governing the temporal order and occurrence of eventualities.
We also propose a Memory-Enhanced Query (MEQE) to significantly improve the performance of state-of-the-art neural query encoders on the CEQA task.
arXiv Detail & Related papers (2023-05-30T14:29:24Z) - Chaining Simultaneous Thoughts for Numerical Reasoning [92.2007997126144]
numerical reasoning over text should be an essential skill of AI systems.
Previous work focused on modeling the structures of equations, and has proposed various structured decoders.
We propose CANTOR, a numerical reasoner that models reasoning steps using a directed acyclic graph.
arXiv Detail & Related papers (2022-11-29T18:52:06Z) - Active Bayesian Causal Inference [72.70593653185078]
We propose Active Bayesian Causal Inference (ABCI), a fully-Bayesian active learning framework for integrated causal discovery and reasoning.
ABCI jointly infers a posterior over causal models and queries of interest.
We show that our approach is more data-efficient than several baselines that only focus on learning the full causal graph.
arXiv Detail & Related papers (2022-06-04T22:38:57Z) - Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems.
First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints.
We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect.
arXiv Detail & Related papers (2022-05-16T08:10:40Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems.
In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
arXiv Detail & Related papers (2021-07-15T04:47:35Z) - Efficient Solution of Boolean Satisfiability Problems with Digital
MemComputing [0.0]
We show that a memory-assisted physical system can efficiently solve the SAT problem in continuous time.
The efficiency of the simulations is related to the collective dynamical properties of the original physical system.
We anticipate our results to broaden research directions in physics-inspired computing paradigms.
arXiv Detail & Related papers (2020-11-12T18:13:46Z) - 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)
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.