Faster Perfect Sampling of Bayesian Network Structures

Juha Harviainen, Mikko Koivisto
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:1558-1568, 2024.

Abstract

Bayesian inference of a Bayesian network structure amounts to averaging over directed acyclic graphs (DAGs) on a given set of n variables, each DAG weighted by its posterior probability. In practice, save some special inference tasks, one averages over a sample of DAGs generated perfectly or approximately from the posterior. For the hard problem of perfect sampling, we give an algorithm that runs in O(2.829n) expected time, getting below O(3n) for the first time. Our algorithm reduces the problem into two smaller sampling problems whose outputs are combined; followed by a simple rejection step, perfect samples are obtained. Subsequent samples can be generated considerably faster. Empirically, we observe speedups of several orders of magnitude over the state of the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-harviainen24a, title = {Faster Perfect Sampling of Bayesian Network Structures}, author = {Harviainen, Juha and Koivisto, Mikko}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {1558--1568}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/harviainen24a/harviainen24a.pdf}, url = {https://proceedings.mlr.press/v244/harviainen24a.html}, abstract = {Bayesian inference of a Bayesian network structure amounts to averaging over directed acyclic graphs (DAGs) on a given set of $n$ variables, each DAG weighted by its posterior probability. In practice, save some special inference tasks, one averages over a sample of DAGs generated perfectly or approximately from the posterior. For the hard problem of perfect sampling, we give an algorithm that runs in $O(2.829^n)$ expected time, getting below $O(3^n)$ for the first time. Our algorithm reduces the problem into two smaller sampling problems whose outputs are combined; followed by a simple rejection step, perfect samples are obtained. Subsequent samples can be generated considerably faster. Empirically, we observe speedups of several orders of magnitude over the state of the art.} }
Endnote
%0 Conference Paper %T Faster Perfect Sampling of Bayesian Network Structures %A Juha Harviainen %A Mikko Koivisto %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-harviainen24a %I PMLR %P 1558--1568 %U https://proceedings.mlr.press/v244/harviainen24a.html %V 244 %X Bayesian inference of a Bayesian network structure amounts to averaging over directed acyclic graphs (DAGs) on a given set of $n$ variables, each DAG weighted by its posterior probability. In practice, save some special inference tasks, one averages over a sample of DAGs generated perfectly or approximately from the posterior. For the hard problem of perfect sampling, we give an algorithm that runs in $O(2.829^n)$ expected time, getting below $O(3^n)$ for the first time. Our algorithm reduces the problem into two smaller sampling problems whose outputs are combined; followed by a simple rejection step, perfect samples are obtained. Subsequent samples can be generated considerably faster. Empirically, we observe speedups of several orders of magnitude over the state of the art.
APA
Harviainen, J. & Koivisto, M.. (2024). Faster Perfect Sampling of Bayesian Network Structures. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:1558-1568 Available from https://proceedings.mlr.press/v244/harviainen24a.html.

Related Material