On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables

By Frederick Eberhardt, Clark Glymour, Richard Scheines. 2005

171 citations recorded by the source corpus.

We show that if any number of variables are allowed to be simultaneously and independently randomized in any one experiment, log2(N) + 1 experiments are sufficient and in the worst case necessary to determine the causal relations among N >= 2 variables when no latent variables, no sample selection bias and no feedback cycles are present. For all K, 0 < K < 1/(2N) we provide an upper bound on the number experiments required to determine causal structure when each experiment simultaneously randomizes K variables. For large N, these bounds are significantly lower than the N - 1 bound required when each experiment randomizes at most one variable. For kmax < N/2, we show that (N/kmax-1)+N/(2kmax)log2(kmax) experiments aresufficient and in the worst case necessary. We over a conjecture as to the minimal number of experiments that are in the worst case sufficient to identify all causal relations among N observed variables that are a subset of the vertices of a DAG.

Subfields: Artificial Intelligence, Statistics and Probability, 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 Statistics and Probability

In Causal Inference & Discovery

Citations in the corpus

Differentiable Causal Discovery from Interventional Data (2020, background): “In this case, the DAG is identiﬁable up to an interventional Markov equivalence class , which is a subset of the Markov equivalence class [40, 12], and, when observing enough interventions [7, 9], the DAG is exactly identiﬁable.”
Learning Neural Causal Models from Unknown Interventions (2019, background): “In order to identify the true causal graph structure, intervention data is needed [17].”
Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, background): “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…”
Inductive biases for deep learning of higher-level cognition (2020, background): “In order to identify the true causal graph, the learner needs to perform interventions or experiments i.e., interventional data is needed (Eberhardt et al., 2012).”
Causal Discovery with General Non-Linear Relationships using Non-Linear ICA (2019, background): “Even when it is possible to run randomized control trials, the number of experiments required may raise practical challenges (Eberhardt et al., 2005).”
Causal Discovery from Soft Interventions with Unknown Targets: Characterization and Learning (2020, background): “This operation is also known as a mechanism change [31] or a parameter change [5], and it presents in many settings a more realistic model than hard or perfect interventions, where variables are forced to a fixed value (see also [2, 3, 33, 22, Sec.”
Causal Network Learning from Multiple Interventions of Unknown Manipulated Targets (2016, background): “In general, interventions with known targets are informative to identify the causal network in a Markov equivalence class (Eberhardt et al., 2005; He and Geng, 2008).”
Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions (2018, background): “Copyright 2018 by the author(s). their causes are known as perfect (or hard ) interventions (Eberhardt et al., 2005).”
Learning linear cyclic causal models with latent variables (2012, background): “Eberhardt et al., 2005; Meganck et al., 2005; Nyberg and Korb, 2006; Eberhardt and Scheines, 2007; Eaton and Murphy, 2007).”
Causal Bandits: Learning Good Interventions via Causal Inference (2016, background): “Work on the problem of selecting experiments to discover the correct causal graph from within a Markov equivalence class Eberhardt et al. (2005); Eberhardt (2010); Hauser and Bühlmann (2014); Hu et al. (2014) could potentially be incorporated into a causal bandit algorithm.”
Causal Graphical Models with Latent Variables: Learning and Inference (2007, background): “See Eberhardt et al. (2005); Meganck et al. (2006) for that type of results for Bayesian networks without latent variables.”
Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part I: Algorithms and Empirical Evaluation (2010, methodology): “Recent work has also provided theoretical bounds and related algorithms to minimize the number of experiments needed to infer causal structure (Eberhardt et al., 2006, 2005).”
Permutation-Based Causal Structure Learning with Unknown Intervention Targets (2019, methodology): “In practice, interventions often cannot fully remove the causal dependencies between an intervened target and its causes, but rather modify their causal relationship (Eberhardt et al., 2005).”
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].”
Belief net structure learning from uncertain interventions (2007, background): “To distinguish between such models, we need interventional (experimental) data (Cooper and Yoo, 1999; Pearl, 2000; Spirtes et al., 2000; Eberhardt et al., 2005; Korb and Nyberg, 2006).”
Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs (2013, background): “Xj, Xk/ one of the following two conditions holds (Eberhardt et al., 2005): (a) there is an intervention target I ∈I with j ∈ I and k ∈ I and another intervention target J ∈I with j ∈J and k∈J , or (b) there is an intervention target I ∈I with |I ∩ {j, k}|= 1 and another intervention target J ∈I wit”