Causal Effect Identification in Uncertain Causal Networks
- URL: http://arxiv.org/abs/2208.04627v3
- Date: Fri, 27 Oct 2023 15:58:19 GMT
- Title: Causal Effect Identification in Uncertain Causal Networks
- Authors: Sina Akbari, Fateme Jamshidi, Ehsan Mokhtarian, Matthew J. Vowels,
Jalal Etesami, Negar Kiyavash
- Abstract summary: Causal identification is at the core of the causal inference literature.
We show that the edges in a causal graph exist with uncertainties which may, for example, represent degree of belief from domain experts.
We propose efficient algorithms to approximate this problem evaluate them against both real-world networks and randomly generated graphs.
- Score: 30.239874638041904
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Causal identification is at the core of the causal inference literature,
where complete algorithms have been proposed to identify causal queries of
interest. The validity of these algorithms hinges on the restrictive assumption
of having access to a correctly specified causal structure. In this work, we
study the setting where a probabilistic model of the causal structure is
available. Specifically, the edges in a causal graph exist with uncertainties
which may, for example, represent degree of belief from domain experts.
Alternatively, the uncertainty about an edge may reflect the confidence of a
particular statistical test. The question that naturally arises in this setting
is: Given such a probabilistic graph and a specific causal effect of interest,
what is the subgraph which has the highest plausibility and for which the
causal effect is identifiable? We show that answering this question reduces to
solving an NP-complete combinatorial optimization problem which we call the
edge ID problem. We propose efficient algorithms to approximate this problem
and evaluate them against both real-world networks and randomly generated
graphs.
Related papers
- On the Complexity of Identification in Linear Structural Causal Models [3.44747819522562]
We give a new sound and complete algorithm for generic identification which runs in space.
The paper also presents evidence that identification is computationally hard in general.
arXiv Detail & Related papers (2024-07-17T13:11:26Z) - Detecting and Identifying Selection Structure in Sequential Data [53.24493902162797]
We argue that the selective inclusion of data points based on latent objectives is common in practical situations, such as music sequences.
We show that selection structure is identifiable without any parametric assumptions or interventional experiments.
We also propose a provably correct algorithm to detect and identify selection structures as well as other types of dependencies.
arXiv Detail & Related papers (2024-06-29T20:56:34Z) - Root Cause Explanation of Outliers under Noisy Mechanisms [50.59446568076628]
Causal processes are often modelled as graphs with entities being nodes and their paths/interconnections as edge.
Existing work only consider the contribution of nodes in the generative process.
We consider both individual edge and node of each mechanism when identifying the root causes.
arXiv Detail & Related papers (2023-12-19T03:24:26Z) - Subset verification and search algorithms for causal DAGs [13.108039226223793]
We study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges)
We prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.
arXiv Detail & Related papers (2023-01-09T06:25:44Z) - Bounding Counterfactuals under Selection Bias [60.55840896782637]
We propose a first algorithm to address both identifiable and unidentifiable queries.
We prove that, in spite of the missingness induced by the selection bias, the likelihood of the available data is unimodal.
arXiv Detail & Related papers (2022-07-26T10:33:10Z) - Experimental Design for Causal Effect Identification [31.23071073904698]
We consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect.
First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic approximation of it.
Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs.
arXiv Detail & Related papers (2022-05-04T13:19:04Z) - Typing assumptions improve identification in causal discovery [123.06886784834471]
Causal discovery from observational data is a challenging task to which an exact solution cannot always be identified.
We propose a new set of assumptions that constrain possible causal relationships based on the nature of the variables.
arXiv Detail & Related papers (2021-07-22T14:23:08Z) - 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) - Identifying Causal Effects via Context-specific Independence Relations [9.51801023527378]
Causal effect identification considers whether an interventional probability distribution can be uniquely determined from a passively observed distribution.
We show that deciding causal effect non-identifiability is NP-hard in the presence of context-specific independence relations.
Motivated by this, we design a calculus and an automated search procedure for identifying causal effects in the presence of CSIs.
arXiv Detail & Related papers (2020-09-21T11:38:15Z) - Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
Causal inferences can be obtained by standard algorithms for the updating of credal nets.
This contribution should be regarded as a systematic approach to represent structural causal models by credal networks.
Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
arXiv Detail & Related papers (2020-08-02T11:19:36Z)
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.