Learning and Testing Causal Models with Interventions

2018/05/24 by Acharya, Jayadev, Bhattacharyya, Arnab, Daskalakis, Constantinos +1 · 1 citation
#Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1805.09697

Abstract

We consider testing and learning problems on causal Bayesian networks as defined by Pearl (Pearl, 2009). Given a causal Bayesian network 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 X on the same graph, and O(n/ε²) samples per intervention, suffice to efficiently distinguish whether X=M or whether there exists some intervention under which X and M are farther than ε 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: Ω(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.

Cited by

• Probably Approximately Correct Causal Discovery

Related

• Efficient inference of interventional distributions
• Sample Efficient Bayesian Learning of Causal Graphs from Interventions
• Causal Network Learning from Multiple Interventions of Unknown Manipulated Targets
• Variational Causal Networks: Approximate Bayesian Inference over Causal Structures
• Learning and Sampling of Atomic Interventions from Observations