Cost-Optimal Learning of Causal Graphs

Murat Kocaoglu, Alex Dimakis, Sriram Vishwanath
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1875-1884, 2017.

Abstract

We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-kocaoglu17a, title = {Cost-Optimal Learning of Causal Graphs}, author = {Murat Kocaoglu and Alex Dimakis and Sriram Vishwanath}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1875--1884}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/kocaoglu17a/kocaoglu17a.pdf}, url = {https://proceedings.mlr.press/v70/kocaoglu17a.html}, abstract = {We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.} }
Endnote
%0 Conference Paper %T Cost-Optimal Learning of Causal Graphs %A Murat Kocaoglu %A Alex Dimakis %A Sriram Vishwanath %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-kocaoglu17a %I PMLR %P 1875--1884 %U https://proceedings.mlr.press/v70/kocaoglu17a.html %V 70 %X We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.
APA
Kocaoglu, M., Dimakis, A. & Vishwanath, S.. (2017). Cost-Optimal Learning of Causal Graphs. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1875-1884 Available from https://proceedings.mlr.press/v70/kocaoglu17a.html.

Related Material