Causal Structure Learning With Momentum: Sampling Distributions Over Markov Equivalence Classes

Moritz Schauer, Marcel Wienöbst
Proceedings of The 12th International Conference on Probabilistic Graphical Models, PMLR 246:382-400, 2024.

Abstract

In the context of inferring a Bayesian network structure (directed acyclic graph, DAG for short), we devise a non-reversible continuous time Markov chain, the “Causal Zig-Zag sampler”, that targets a probability distribution over classes of observationally equivalent (Markov equivalent) DAGs. The classes are represented as completed partially directed acyclic graphs (CPDAGs). The non-reversible Markov chain relies on the operators used in Chickering’s Greedy Equivalence Search (GES) and is endowed with a momentum variable, which improves mixing significantly as we show empirically. The possible target distributions include posterior distributions based on a prior over DAGs and a Markov equivalent likelihood. We offer an efficient implementation wherein we develop new algorithms for listing, counting, uniformly sampling, and applying possible moves of the GES operators, all of which significantly improve upon the state-of-the-art run-time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v246-schauer24a, title = {Causal Structure Learning With Momentum: Sampling Distributions Over Markov Equivalence Classes}, author = {Schauer, Moritz and Wien\"{o}bst, Marcel}, booktitle = {Proceedings of The 12th International Conference on Probabilistic Graphical Models}, pages = {382--400}, year = {2024}, editor = {Kwisthout, Johan and Renooij, Silja}, volume = {246}, series = {Proceedings of Machine Learning Research}, month = {11--13 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v246/main/assets/schauer24a/schauer24a.pdf}, url = {https://proceedings.mlr.press/v246/schauer24a.html}, abstract = {In the context of inferring a Bayesian network structure (directed acyclic graph, DAG for short), we devise a non-reversible continuous time Markov chain, the “Causal Zig-Zag sampler”, that targets a probability distribution over classes of observationally equivalent (Markov equivalent) DAGs. The classes are represented as completed partially directed acyclic graphs (CPDAGs). The non-reversible Markov chain relies on the operators used in Chickering’s Greedy Equivalence Search (GES) and is endowed with a momentum variable, which improves mixing significantly as we show empirically. The possible target distributions include posterior distributions based on a prior over DAGs and a Markov equivalent likelihood. We offer an efficient implementation wherein we develop new algorithms for listing, counting, uniformly sampling, and applying possible moves of the GES operators, all of which significantly improve upon the state-of-the-art run-time.} }
Endnote
%0 Conference Paper %T Causal Structure Learning With Momentum: Sampling Distributions Over Markov Equivalence Classes %A Moritz Schauer %A Marcel Wienöbst %B Proceedings of The 12th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2024 %E Johan Kwisthout %E Silja Renooij %F pmlr-v246-schauer24a %I PMLR %P 382--400 %U https://proceedings.mlr.press/v246/schauer24a.html %V 246 %X In the context of inferring a Bayesian network structure (directed acyclic graph, DAG for short), we devise a non-reversible continuous time Markov chain, the “Causal Zig-Zag sampler”, that targets a probability distribution over classes of observationally equivalent (Markov equivalent) DAGs. The classes are represented as completed partially directed acyclic graphs (CPDAGs). The non-reversible Markov chain relies on the operators used in Chickering’s Greedy Equivalence Search (GES) and is endowed with a momentum variable, which improves mixing significantly as we show empirically. The possible target distributions include posterior distributions based on a prior over DAGs and a Markov equivalent likelihood. We offer an efficient implementation wherein we develop new algorithms for listing, counting, uniformly sampling, and applying possible moves of the GES operators, all of which significantly improve upon the state-of-the-art run-time.
APA
Schauer, M. & Wienöbst, M.. (2024). Causal Structure Learning With Momentum: Sampling Distributions Over Markov Equivalence Classes. Proceedings of The 12th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 246:382-400 Available from https://proceedings.mlr.press/v246/schauer24a.html.

Related Material