Averaging of Decomposable Graphs by Dynamic Programming and Sampling

Kustaa Kangas, Teppo Niinimäki, Mikko Koivisto Helsinki Institute for Information Technology
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:870-879, 2015.

Abstract

We give algorithms for Bayesian learning of decomposable graphical models from complete data. We build on a recently proposed dynamic programming algorithm that finds optimal graphs of $n$ nodes in $O(4^n)$ time and $O(3^n)$ space (Kangas et al., NIPS 2014), and show how it can be turned into accurate averaging algorithms. Specifically, we show that certain marginals of the posterior distribution, like the posterior probability of an edge, can be computed in $O(n^3 3^n)$ time, provided that the prior over the graphs is of an appropriate form. To overcome some limitations of the exact approach, we also give sampling schemes that—using essentially no extra space—can draw up to $3^n$ independent graphs from the posterior in $O(n 4^n)$ time. Through importance sampling, this enables accurate Bayesian inference with a broader class of priors. Using benchmark datasets, we demonstrate the method’s performance and the advantage of averaging over optimization when learning from little data.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-kangas15a, title = {Averaging of Decomposable Graphs by Dynamic Programming and Sampling}, author = {Kangas, Kustaa and Niinim{\"a}ki, Teppo and Technology, Mikko Koivisto Helsinki Institute for Information}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {870--879}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/kangas15a/kangas15a.pdf}, url = {https://proceedings.mlr.press/r13/kangas15a.html}, abstract = {We give algorithms for Bayesian learning of decomposable graphical models from complete data. We build on a recently proposed dynamic programming algorithm that finds optimal graphs of $n$ nodes in $O(4^n)$ time and $O(3^n)$ space (Kangas et al., NIPS 2014), and show how it can be turned into accurate averaging algorithms. Specifically, we show that certain marginals of the posterior distribution, like the posterior probability of an edge, can be computed in $O(n^3 3^n)$ time, provided that the prior over the graphs is of an appropriate form. To overcome some limitations of the exact approach, we also give sampling schemes that—using essentially no extra space—can draw up to $3^n$ independent graphs from the posterior in $O(n 4^n)$ time. Through importance sampling, this enables accurate Bayesian inference with a broader class of priors. Using benchmark datasets, we demonstrate the method’s performance and the advantage of averaging over optimization when learning from little data.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Averaging of Decomposable Graphs by Dynamic Programming and Sampling %A Kustaa Kangas %A Teppo Niinimäki %A Mikko Koivisto Helsinki Institute for Information Technology %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-kangas15a %I PMLR %P 870--879 %U https://proceedings.mlr.press/r13/kangas15a.html %V R13 %X We give algorithms for Bayesian learning of decomposable graphical models from complete data. We build on a recently proposed dynamic programming algorithm that finds optimal graphs of $n$ nodes in $O(4^n)$ time and $O(3^n)$ space (Kangas et al., NIPS 2014), and show how it can be turned into accurate averaging algorithms. Specifically, we show that certain marginals of the posterior distribution, like the posterior probability of an edge, can be computed in $O(n^3 3^n)$ time, provided that the prior over the graphs is of an appropriate form. To overcome some limitations of the exact approach, we also give sampling schemes that—using essentially no extra space—can draw up to $3^n$ independent graphs from the posterior in $O(n 4^n)$ time. Through importance sampling, this enables accurate Bayesian inference with a broader class of priors. Using benchmark datasets, we demonstrate the method’s performance and the advantage of averaging over optimization when learning from little data. %Z Reissued by PMLR on 04 October 2026.
APA
Kangas, K., Niinimäki, T. & Technology, M.K.H.I.f.I.. (2015). Averaging of Decomposable Graphs by Dynamic Programming and Sampling. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:870-879 Available from https://proceedings.mlr.press/r13/kangas15a.html. Reissued by PMLR on 04 October 2026.

Related Material