Timezone: »

 
Poster
Learning and Testing Causal Models with Interventions
Jayadev Acharya · Arnab Bhattacharyya · Constantinos Daskalakis · Saravanan Kandasamy

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 210 #8
in Thu Poster Session A »

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/epsilon^2) samples per intervention, suffice to efficiently distinguish whether X=M or whether there exists some intervention under which X and 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.

Keywords: Model Selection and Structure Learning · Graphical Models · Causal Inference
[ Paper] 

Author Information

Jayadev Acharya (Cornell University)
Arnab Bhattacharyya (National University of Singapore & Indian Institute of Science)
Constantinos Daskalakis (MIT)
Saravanan Kandasamy (Tata Institute of Fundamental Research)

More from the Same Authors