2024-09-12-harviainen24a.md

title	abstract	openreview	section	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Faster Perfect Sampling of Bayesian Network Structures	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.	eq2rjvKbaG	Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	harviainen24a	0	Faster Perfect Sampling of Bayesian Network Structures	1558	1568	1558-1568	1558	false	Harviainen, Juha and Koivisto, Mikko	given family Juha Harviainen given family Mikko Koivisto	2024-09-12		Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence	244	inproceedings	date-parts 2024 9 12	https://raw.githubusercontent.com/mlresearch/v244/main/assets/harviainen24a/harviainen24a.pdf