Budgeted Experiment Design for Causal Structure Learning

AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, Elias Bareinboim
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1724-1733, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-ghassami18a, title = {Budgeted Experiment Design for Causal Structure Learning}, author = {Ghassami, AmirEmad and Salehkaleybar, Saber and Kiyavash, Negar and Bareinboim, Elias}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1724--1733}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/ghassami18a/ghassami18a.pdf}, url = {https://proceedings.mlr.press/v80/ghassami18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Budgeted Experiment Design for Causal Structure Learning %A AmirEmad Ghassami %A Saber Salehkaleybar %A Negar Kiyavash %A Elias Bareinboim %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-ghassami18a %I PMLR %P 1724--1733 %U https://proceedings.mlr.press/v80/ghassami18a.html %V 80 %X 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.
APA
Ghassami, A., Salehkaleybar, S., Kiyavash, N. & Bareinboim, E.. (2018). Budgeted Experiment Design for Causal Structure Learning. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1724-1733 Available from https://proceedings.mlr.press/v80/ghassami18a.html.

Related Material