Timezone: »

 
Oral
Budgeted Experiment Design for Causal Structure Learning
AmirEmad Ghassami · Saber Salehkaleybar · Negar Kiyavash · Elias Bareinboim

Fri Jul 13 07:40 AM -- 07:50 AM (PDT) @ A5
in Causal Inference 1 »
We study the problem of causal structure learning when the experimenter is limited to perform at most $k$ non-adaptive experiments of size $1$. We formulate the problem of finding the best intervention target set as an optimization problem, which aims to maximize the average number of edges whose directions are resolved. We prove that the corresponding objective function is submodular and a greedy algorithm suffices to achieve $(1-\frac{1}{e})$-approximation of the optimal value. We further present an accelerated variant of the greedy algorithm, which can lead to orders of magnitude performance speedup. We validate our proposed approach on synthetic and real graphs. The results show that compared to the purely observational setting, our algorithm orients the majority of the edges through a considerably small number of interventions.
[ PDF] 

Author Information

AmirEmad Ghassami (UIUC)
Saber Salehkaleybar (Sharif University of Technology)
Negar Kiyavash (University of Illinois at Urbana-Champaign)
Elias Bareinboim (Purdue)
Elias Bareinboim

Elias Bareinboim is an associate professor in the Department of Computer Science and the director of the Causal Artificial Intelligence (CausalAI) Laboratory at Columbia University. His research focuses on causal and counterfactual inference and their applications to artificial intelligence and machine learning as well as data-driven fields in the health and social sciences. His work was the first to propose a general solution to the problem of "causal data-fusion," providing practical methods for combining datasets generated under different experimental conditions and plagued with various biases. In the last years, Bareinboim has been exploring the intersection of causal inference with decision-making (including reinforcement learning) and explainability (including fairness analysis). Before joining Columbia, he was an assistant professor at Purdue University and received his Ph.D. in Computer Science from the University of California, Los Angeles. Bareinboim was named one of ``AI's 10 to Watch'' by IEEE, and is a recipient of an NSF CAREER Award, the Dan David Prize Scholarship, the 2014 AAAI Outstanding Paper Award, and the 2019 UAI Best Paper Award.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors