ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery

Raj Agrawal, Chandler Squires, Karren Yang, Karthikeyan Shanmugam, Caroline Uhler
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:3400-3409, 2019.

Abstract

Determining the causal structure of a set of variables is critical for both scientific inquiry and decision-making. However, this is often challenging in practice due to limited interventional data. Given that randomized experiments are usually expensive to perform, we propose a general framework and theory based on optimal Bayesian experimental design to select experiments for targeted causal discovery. That is, we assume the experimenter is interested in learning some function of the unknown graph (e.g., all descendants of a target node) subject to design constraints such as limits on the number of samples and rounds of experimentation. While it is in general computationally intractable to select an optimal experimental design strategy, we provide a tractable implementation with provable guarantees on both approximation and optimization quality based on submodularity. We evaluate the efficacy of our proposed method on both synthetic and real datasets, thereby demonstrating that our method realizes considerable performance gains over baseline strategies such as random sampling.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-agrawal19b, title = {ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery}, author = {Agrawal, Raj and Squires, Chandler and Yang, Karren and Shanmugam, Karthikeyan and Uhler, Caroline}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {3400--3409}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/agrawal19b/agrawal19b.pdf}, url = {https://proceedings.mlr.press/v89/agrawal19b.html}, abstract = {Determining the causal structure of a set of variables is critical for both scientific inquiry and decision-making. However, this is often challenging in practice due to limited interventional data. Given that randomized experiments are usually expensive to perform, we propose a general framework and theory based on optimal Bayesian experimental design to select experiments for targeted causal discovery. That is, we assume the experimenter is interested in learning some function of the unknown graph (e.g., all descendants of a target node) subject to design constraints such as limits on the number of samples and rounds of experimentation. While it is in general computationally intractable to select an optimal experimental design strategy, we provide a tractable implementation with provable guarantees on both approximation and optimization quality based on submodularity. We evaluate the efficacy of our proposed method on both synthetic and real datasets, thereby demonstrating that our method realizes considerable performance gains over baseline strategies such as random sampling.} }
Endnote
%0 Conference Paper %T ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery %A Raj Agrawal %A Chandler Squires %A Karren Yang %A Karthikeyan Shanmugam %A Caroline Uhler %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-agrawal19b %I PMLR %P 3400--3409 %U https://proceedings.mlr.press/v89/agrawal19b.html %V 89 %X Determining the causal structure of a set of variables is critical for both scientific inquiry and decision-making. However, this is often challenging in practice due to limited interventional data. Given that randomized experiments are usually expensive to perform, we propose a general framework and theory based on optimal Bayesian experimental design to select experiments for targeted causal discovery. That is, we assume the experimenter is interested in learning some function of the unknown graph (e.g., all descendants of a target node) subject to design constraints such as limits on the number of samples and rounds of experimentation. While it is in general computationally intractable to select an optimal experimental design strategy, we provide a tractable implementation with provable guarantees on both approximation and optimization quality based on submodularity. We evaluate the efficacy of our proposed method on both synthetic and real datasets, thereby demonstrating that our method realizes considerable performance gains over baseline strategies such as random sampling.
APA
Agrawal, R., Squires, C., Yang, K., Shanmugam, K. & Uhler, C.. (2019). ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:3400-3409 Available from https://proceedings.mlr.press/v89/agrawal19b.html.

Related Material