Learning and Testing Causal Models with Interventions

Abstract

We consider testing and learning problems on causal Bayesian networks as defined by Pearl (Pearl, 2009). Given a causal Bayesian network $\mathcal{M}$ on a graph with $n$ discrete variables and bounded in-degree and bounded `confounded components', we show that $O(\log n)$ interventions on an unknown causal Bayesian network $\mathcal{X}$ on the same graph, and $\tilde{O}(n/{\epsilon }^2)$ samples per intervention, suffice to efficiently distinguish whether $\mathcal{X}=\mathcal{M}$ or whether there exists some intervention under which $\mathcal{X}$ and $\mathcal{M}$ are farther than $\epsilon$ in total variation distance. We also obtain sample/time/intervention efficient algorithms for: (i) testing the identity of two unknown causal Bayesian networks on the same graph; and (ii) learning a causal Bayesian network on a given graph. Although our algorithms are non-adaptive, we show that adaptivity does not help in general: $\Omega (\log n)$ interventions are necessary for testing the identity of two unknown causal Bayesian networks on the same graph, even adaptively. Our algorithms are enabled by a new subadditivity inequality for the squared Hellinger distance between two causal Bayesian networks.

References in corpus (7)

• Kernel-based Conditional Independence Test and Application in Causal Discovery
• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• Optimal Testing for Properties of Distributions
• Permutation-based Causal Inference Algorithms with Interventions
• Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions
• On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables
• Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

Cited by in corpus (6)

• Interventional Sum-Product Networks: Causal Inference with Tractable Probabilistic Models
• Private Identity Testing for High-Dimensional Distributions
• Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning
• On the Sample Complexity of Causal Discovery and the Value of Domain Expertise
• On Distribution Testing in the Conditional Sampling Model
• A Ladder of Causal Distances