Efficient Intervention Design for Causal Discovery with Latents
- URL: http://arxiv.org/abs/2005.11736v2
- Date: Sun, 12 Jul 2020 16:53:18 GMT
- Title: Efficient Intervention Design for Causal Discovery with Latents
- Authors: Raghavendra Addanki, Shiva Prasad Kasiviswanathan, Andrew McGregor,
Cameron Musco
- Abstract summary: We consider recovering a causal graph in presence of latent variables, where we seek to minimize the cost of interventions used in the recovery process.
We consider two intervention cost models: (1) a linear cost model where the cost of an intervention on a subset of variables has a linear form, and (2) an identity cost model where the cost of an intervention is the same, regardless of what variables it is on.
- Score: 30.721629140295178
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider recovering a causal graph in presence of latent variables, where
we seek to minimize the cost of interventions used in the recovery process. We
consider two intervention cost models: (1) a linear cost model where the cost
of an intervention on a subset of variables has a linear form, and (2) an
identity cost model where the cost of an intervention is the same, regardless
of what variables it is on, i.e., the goal is just to minimize the number of
interventions. Under the linear cost model, we give an algorithm to identify
the ancestral relations of the underlying causal graph, achieving within a
$2$-factor of the optimal intervention cost. This approximation factor can be
improved to $1+\epsilon$ for any $\epsilon > 0$ under some mild restrictions.
Under the identity cost model, we bound the number of interventions needed to
recover the entire causal graph, including the latent variables, using a
parameterization of the causal graph through a special type of colliders. In
particular, we introduce the notion of $p$-colliders, that are colliders
between pair of nodes arising from a specific type of conditioning in the
causal graph, and provide an upper bound on the number of interventions as a
function of the maximum number of $p$-colliders between any two nodes in the
causal graph.
Related papers
- Causal Discovery under Off-Target Interventions [18.92683981229985]
Causal graph discovery is a significant problem with applications across various disciplines.
This work addresses the causal discovery problem under the setting of interventions with the natural goal of minimizing the number of interventions performed.
arXiv Detail & Related papers (2024-02-13T05:43:49Z) - Adaptivity Complexity for Causal Graph Discovery [7.424262881242935]
We study the problem of $r$-adaptivity, where the algorithm designer recovers the causal graph under a total of $r$ sequential rounds.
We provide a $r$-adaptive algorithm that achieves $O(minr,log n cdot n1/minr,log n)$ approximation with respect to the verification number.
arXiv Detail & Related papers (2023-06-09T09:49:16Z) - Nonparametric Identifiability of Causal Representations from Unknown
Interventions [63.1354734978244]
We study causal representation learning, the task of inferring latent causal variables and their causal relations from mixtures of the variables.
Our goal is to identify both the ground truth latents and their causal graph up to a set of ambiguities which we show to be irresolvable from interventional data.
arXiv Detail & Related papers (2023-06-01T10:51:58Z) - FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
We tackle a novel federated learning (FL) problem for optimizing a family of X-risks, to which no existing algorithms are applicable.
The challenges for designing an FL algorithm for X-risks lie in the non-decomability of the objective over multiple machines and the interdependency between different machines.
arXiv Detail & Related papers (2022-10-26T00:23:36Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model.
It is assumed that the graph's structure is known and has $N$ nodes.
Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
arXiv Detail & Related papers (2022-08-26T16:21:31Z) - Variational Causal Networks: Approximate Bayesian Inference over Causal
Structures [132.74509389517203]
We introduce a parametric variational family modelled by an autoregressive distribution over the space of discrete DAGs.
In experiments, we demonstrate that the proposed variational posterior is able to provide a good approximation of the true posterior.
arXiv Detail & Related papers (2021-06-14T17:52:49Z) - A Twin Neural Model for Uplift [59.38563723706796]
Uplift is a particular case of conditional treatment effect modeling.
We propose a new loss function defined by leveraging a connection with the Bayesian interpretation of the relative risk.
We show our proposed method is competitive with the state-of-the-art in simulation setting and on real data from large scale randomized experiments.
arXiv Detail & Related papers (2021-05-11T16:02:39Z) - Efficient Causal Inference from Combined Observational and
Interventional Data through Causal Reductions [68.6505592770171]
Unobserved confounding is one of the main challenges when estimating causal effects.
We propose a novel causal reduction method that replaces an arbitrary number of possibly high-dimensional latent confounders.
We propose a learning algorithm to estimate the parameterized reduced model jointly from observational and interventional data.
arXiv Detail & Related papers (2021-03-08T14:29:07Z) - Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs [22.401163479802094]
We study the problem of learning the causal relationships between a set of observed variables in the presence of latents.
Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions.
Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems.
arXiv Detail & Related papers (2020-12-27T17:08:46Z) - Synthetic Interventions [20.96904429337912]
We learn the expected potential outcome associated with every intervention on every unit, totaling $N times D$ causal parameters.
We present a causal framework, synthetic interventions (SI), to infer these $N times D$ causal parameters.
We believe our results could have implications for the design of data-efficient randomized experiments.
arXiv Detail & Related papers (2020-06-13T18:15:22Z)
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.