Timezone: »

 
Poster
Sample Efficient Active Learning of Causal Trees
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric Boix-Adsera · Guy Bresler

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #138
in Probabilistic Methods -- Causal Inference »
We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If infinite interventional data is available, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples. Several extensions are also presented, to the case where a specified set of nodes cannot be intervened on, to the case where $K$ interventions are scheduled at once, and to the fully adaptive case where each experiment yields only one sample. In the case of finite interventional data, through simulated experiments we show that our algorithms outperform different adaptive baseline algorithms.
Keywords: Causal Inference · Probabilistic Methods
[ Paper]  [ Poster] 

Author Information

Kristjan Greenewald (IBM Research)
Dmitriy Katz (IBM Research)
Karthikeyan Shanmugam (IBM Research, NY)
Sara Magliacane (MIT-IBM Watson AI Lab)
Murat Kocaoglu (MIT-IBM Watson AI Lab IBM Research, MA)
Enric Boix-Adsera (MIT)
Guy Bresler (MIT)

More from the Same Authors