Learning Optimal Causal Graphs with Exact Search

Kari Rantanen, Antti Hyttinen, Matti Järvisalo
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:344-355, 2018.

Abstract

Discovering graphical models over very general model spaces with high accuracy requires optimally combining conflicting (in)dependence constraints in sample data, and thus results in a computationally hard combinatorial optimization problem. Recent advances in exact algorithmic approaches in this constraint-based setting build upon off-the-shelf declarative optimization solvers. In this paper, we propose the first truly specialized exact search algorithm for optimal causal graphs in a general model space, allowing both cycles and latent confounding variables. Our problem-oriented approach enables directly incorporating domain knowledge for developing a wider range of specialized search techniques for the problem, including problem-specific propagators, branching heuristics, and bounding techniques, as well as directly incorporating different constraints on the model space, such as sparsity and acyclicity constraints. We empirically evaluate a first implementation of the approach, showing that it clearly outperforms current state of art in exact constraint-based causal discovery on real-world instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-rantanen18a, title = {Learning Optimal Causal Graphs with Exact Search}, author = {Rantanen, Kari and Hyttinen, Antti and J\"{a}rvisalo, Matti}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {344--355}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/rantanen18a/rantanen18a.pdf}, url = {https://proceedings.mlr.press/v72/rantanen18a.html}, abstract = {Discovering graphical models over very general model spaces with high accuracy requires optimally combining conflicting (in)dependence constraints in sample data, and thus results in a computationally hard combinatorial optimization problem. Recent advances in exact algorithmic approaches in this constraint-based setting build upon off-the-shelf declarative optimization solvers. In this paper, we propose the first truly specialized exact search algorithm for optimal causal graphs in a general model space, allowing both cycles and latent confounding variables. Our problem-oriented approach enables directly incorporating domain knowledge for developing a wider range of specialized search techniques for the problem, including problem-specific propagators, branching heuristics, and bounding techniques, as well as directly incorporating different constraints on the model space, such as sparsity and acyclicity constraints. We empirically evaluate a first implementation of the approach, showing that it clearly outperforms current state of art in exact constraint-based causal discovery on real-world instances.} }
Endnote
%0 Conference Paper %T Learning Optimal Causal Graphs with Exact Search %A Kari Rantanen %A Antti Hyttinen %A Matti Järvisalo %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-rantanen18a %I PMLR %P 344--355 %U https://proceedings.mlr.press/v72/rantanen18a.html %V 72 %X Discovering graphical models over very general model spaces with high accuracy requires optimally combining conflicting (in)dependence constraints in sample data, and thus results in a computationally hard combinatorial optimization problem. Recent advances in exact algorithmic approaches in this constraint-based setting build upon off-the-shelf declarative optimization solvers. In this paper, we propose the first truly specialized exact search algorithm for optimal causal graphs in a general model space, allowing both cycles and latent confounding variables. Our problem-oriented approach enables directly incorporating domain knowledge for developing a wider range of specialized search techniques for the problem, including problem-specific propagators, branching heuristics, and bounding techniques, as well as directly incorporating different constraints on the model space, such as sparsity and acyclicity constraints. We empirically evaluate a first implementation of the approach, showing that it clearly outperforms current state of art in exact constraint-based causal discovery on real-world instances.
APA
Rantanen, K., Hyttinen, A. & Järvisalo, M.. (2018). Learning Optimal Causal Graphs with Exact Search. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:344-355 Available from https://proceedings.mlr.press/v72/rantanen18a.html.

Related Material