Almost Optimal Intervention Sets for Causal Discovery

By Frederick Eberhardt. 2008

68 citations recorded by the source corpus.

We conjecture that the worst case number of experiments necessary and sufficient to discover a causal graph uniquely given its observational Markov equivalence class can be specified as a function of the largest clique in the Markov equivalence class. We provide an algorithm that computes intervention sets that we believe are optimal for the above task. The algorithm builds on insights gained from the worst case analysis in Eberhardt et al. (2005) for sequences of experiments when all possible directed acyclic graphs over N variables are considered. A simulation suggests that our conjecture is correct. We also show that a generalization of our conjecture to other classes of possible graph hypotheses cannot be given easily, and in what sense the algorithm is then no longer optimal.

Subfields: Artificial Intelligence, Causal Inference & Discovery

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 Causal Inference & Discovery

Citations in the corpus

Differentiable Causal Discovery from Interventional Data (2020, background): “In this case, the DAG is identifiable up to an interventional Markov equivalence class, which is a subset of the Markov equivalence class [48, 15], and, when observing enough interventions [9, 11], the DAG is exactly identifiable.”
Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, methodology): “Eberhardt et al. (2005) and Eberhardt (2008) provide algorithms for choosing intervention targets that completely identify all causal models of p variables uniformly, but neither address the question of partial identiﬁability under a limited number of interventions nor provide an algorithm for…”
Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions (2018, background): “Eberhardt & Scheines (2007) and Eberhardt (2008) provided results on the number of single-target interventions required for full identiﬁability of the causal DAG.”
Experiment selection for causal discovery (2013, background): “Meganck et al. (2005), He and Geng (2008), Eberhardt (2008) and Hauser and Bühlmann (2012), in their different ways, also try to find the best next experiment given background knowledge, typically knowledge of the (interventional) Markov equivalence class.”
Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networks (2019, background): “A different line of work approaches the experimental design problem from a theoretical perspective on the graph-level [26–30].”
Identifying Best Interventions through Online Importance Sampling (2017, background): “There has been a lot of work [27, 16, 12, 15, 35, 29, 24, 33] on learning casual models from data and/or experiments and using it to estimate causal strength questions of the counterfactual nature.”