Efficient Intervention Design for Causal Discovery with Latents

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.

arXiv commentInternational Conference on Machine Learning 2020

References in corpus (5)

• Kernel-based Conditional Independence Test and Application in Causal Discovery
• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Two Optimal Strategies for Active Learning of Causal Models from Interventional Data

Cited by in corpus (1)

• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments