Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models

Raj Agrawal, Caroline Uhler, Tamara Broderick
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:89-98, 2018.

Abstract

Learning a Bayesian network (BN) from data can be useful for decision-making or discovering causal relationships. However, traditional methods often fail in modern applications, which exhibit a larger number of observed variables than data points. The resulting uncertainty about the underlying network as well as the desire to incorporate prior information recommend a Bayesian approach to learning the BN, but the highly combinatorial structure of BNs poses a striking challenge for inference. The current state-of-the-art methods such as order MCMC are faster than previous methods but prevent the use of many natural structural priors and still have running time exponential in the maximum indegree of the true directed acyclic graph (DAG) of the BN. We here propose an alternative posterior approximation based on the observation that, if we incorporate empirical conditional independence tests, we can focus on a high-probability DAG associated with each order of the vertices. We show that our method allows the desired flexibility in prior specification, removes timing dependence on the maximum indegree, and yields provably good posterior approximations; in addition, we show that it achieves superior accuracy, scalability, and sampler mixing on several datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-agrawal18a, title = {Minimal I-{MAP} {MCMC} for Scalable Structure Discovery in Causal {DAG} Models}, author = {Agrawal, Raj and Uhler, Caroline and Broderick, Tamara}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {89--98}, 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/agrawal18a/agrawal18a.pdf}, url = {https://proceedings.mlr.press/v80/agrawal18a.html}, abstract = {Learning a Bayesian network (BN) from data can be useful for decision-making or discovering causal relationships. However, traditional methods often fail in modern applications, which exhibit a larger number of observed variables than data points. The resulting uncertainty about the underlying network as well as the desire to incorporate prior information recommend a Bayesian approach to learning the BN, but the highly combinatorial structure of BNs poses a striking challenge for inference. The current state-of-the-art methods such as order MCMC are faster than previous methods but prevent the use of many natural structural priors and still have running time exponential in the maximum indegree of the true directed acyclic graph (DAG) of the BN. We here propose an alternative posterior approximation based on the observation that, if we incorporate empirical conditional independence tests, we can focus on a high-probability DAG associated with each order of the vertices. We show that our method allows the desired flexibility in prior specification, removes timing dependence on the maximum indegree, and yields provably good posterior approximations; in addition, we show that it achieves superior accuracy, scalability, and sampler mixing on several datasets.} }
Endnote
%0 Conference Paper %T Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models %A Raj Agrawal %A Caroline Uhler %A Tamara Broderick %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-agrawal18a %I PMLR %P 89--98 %U https://proceedings.mlr.press/v80/agrawal18a.html %V 80 %X Learning a Bayesian network (BN) from data can be useful for decision-making or discovering causal relationships. However, traditional methods often fail in modern applications, which exhibit a larger number of observed variables than data points. The resulting uncertainty about the underlying network as well as the desire to incorporate prior information recommend a Bayesian approach to learning the BN, but the highly combinatorial structure of BNs poses a striking challenge for inference. The current state-of-the-art methods such as order MCMC are faster than previous methods but prevent the use of many natural structural priors and still have running time exponential in the maximum indegree of the true directed acyclic graph (DAG) of the BN. We here propose an alternative posterior approximation based on the observation that, if we incorporate empirical conditional independence tests, we can focus on a high-probability DAG associated with each order of the vertices. We show that our method allows the desired flexibility in prior specification, removes timing dependence on the maximum indegree, and yields provably good posterior approximations; in addition, we show that it achieves superior accuracy, scalability, and sampler mixing on several datasets.
APA
Agrawal, R., Uhler, C. & Broderick, T.. (2018). Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:89-98 Available from https://proceedings.mlr.press/v80/agrawal18a.html.

Related Material