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

Abstract

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.

arXiv commentAppears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

Cited by in corpus (18)

• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• Causal Bandits: Learning Good Interventions via Causal Inference
• Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs
• Learning Neural Causal Models from Unknown Interventions
• Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions
• Learning and Testing Causal Models with Interventions
• Learning Causal Graphs with Small Interventions
• Differentiable Causal Discovery from Interventional Data
• Learning Neural Causal Models with Active Interventions
• High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
• Permutation-Based Causal Structure Learning with Unknown Intervention Targets
• Experimental Design for Cost-Aware Learning of Causal Graphs
• Amortized learning of neural causal representations
• Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning
• Perturbation graphs, invariant prediction and causal relations in psychology
• Efficient Neural Causal Discovery without Acyclicity Constraints
• Distributional Invariances and Interventional Markov Equivalence for Mixed Graph Models
• A Topological Perspective on Causal Inference