Learning Causal Graphs with Small Interventions

By Karthikeyan Shanmugam, Murat Kocaoglu, A. Dimakis, Sriram Vishwanath. 2015

124 citations recorded by the source corpus.

We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previous work has focused on the use of separating systems for complete graphs for this task. We prove that any deterministic adaptive algorithm needs to be a separating system in order to learn complete graphs in the worst case. In addition, we present a novel separating system construction, whose size is close to optimal and is arguably simpler than previous work in combinatorics. We also develop a novel information theoretic lower bound on the number of interventions that applies in full generality, including for randomized adaptive learning algorithms. For general chordal graphs, we derive worst case lower bounds on the number of interventions. Building on observations about induced trees, we give a new deterministic adaptive algorithm to learn directions on any chordal skeleton completely. In the worst case, our achievable scheme is an $\alpha$-approximation algorithm where $\alpha$ is the independence number of the graph. We also show that there exist graph classes for which the sufficient number of experiments is close to the lower bound. In the other extreme, there are graph classes for which the required number of experiments is multiplicatively $\alpha$ away from our lower bound. In simulations, our algorithm almost always performs very close to the lower bound, while the approach based on separating systems for complete graphs is significantly worse for random chordal graphs.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Causal Reasoning from Meta-reinforcement Learning (2019, background): “We chose to focus on the RL approach because we are interested in agents that can learn about causes and effects not only from passive observations but also from active interactions with the environment (Hyttinen et al., 2013; Shanmugam et al., 2015).”
Identifying Best Interventions through Online Importance Sampling (2017, background): “There has been a lot of work (Mooij et al., 2016; Hyttinen et al., 2013; Eberhardt, 2008; Hauser & Bühlmann, 2012; Spirtes et al., 2001; Pearl, 2009a; Loh & Bühlmann, 2014; Shanmugam et al., 2015) on learning casual models from data and/or experiments and using it to estimate causal strength questio”
Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions (2019, background): “Related Work: Learning causal graphs from a combination of observational and interventional data has been studied in the literature [3, 11, 7, 20, 8, 12, 23].”
Causal Confusion in Imitation Learning (2019, methodology): “We operate in the interventional regime [55, 11, 49, 48] where a user may “experiment” to discover causal structures by assigning values to some subset of the variables of interest and observing the effects on the rest of the system.”
Learning Causal Structures Using Regression Invariance (2017, background): “In recent works, bounds on the required number of interventions for complete discovery of causal relationships as well as passive and adaptive algorithms for minimizing the number of experiments were derived [5, 9, 10, 11, 31].”