Computing Posterior Probabilities of Structural Features in Bayesian Networks

Jin Tian, Ru He
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:546-555, 2009.

Abstract

We study the problem of learning Bayesian network structures from data. Koivisto and Sood (2004) and Koivisto (2006) presented algorithms that can compute the exact marginal posterior probability of a subnetwork, e.g., a single edge, in O(n2n) time and the posterior probabilities for all n(n-1) potential edges in O(n2n) total time, assuming that the number of parents per node or the indegree is bounded by a constant. One main drawback of their algorithms is the requirement of a special structure prior that is non uniform and does not respect Markov equivalence. In this paper, we develop an algorithm that can compute the exact posterior probability of a subnetwork in O(3n) time and the posterior probabilities for all n(n-1) potential edges in O(n3n) total time. Our algorithm also assumes a bounded indegree but allows general structure priors. We demonstrate the applicability of the algorithm on several data sets with up to 20 variables.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-tian09a, title = {Computing Posterior Probabilities of Structural Features in {B}ayesian Networks}, author = {Tian, Jin and He, Ru}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {546--555}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/tian09a/tian09a.pdf}, url = {https://proceedings.mlr.press/r7/tian09a.html}, abstract = {We study the problem of learning Bayesian network structures from data. Koivisto and Sood (2004) and Koivisto (2006) presented algorithms that can compute the exact marginal posterior probability of a subnetwork, e.g., a single edge, in O(n2n) time and the posterior probabilities for all n(n-1) potential edges in O(n2n) total time, assuming that the number of parents per node or the indegree is bounded by a constant. One main drawback of their algorithms is the requirement of a special structure prior that is non uniform and does not respect Markov equivalence. In this paper, we develop an algorithm that can compute the exact posterior probability of a subnetwork in O(3n) time and the posterior probabilities for all n(n-1) potential edges in O(n3n) total time. Our algorithm also assumes a bounded indegree but allows general structure priors. We demonstrate the applicability of the algorithm on several data sets with up to 20 variables.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Computing Posterior Probabilities of Structural Features in Bayesian Networks %A Jin Tian %A Ru He %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-tian09a %I PMLR %P 546--555 %U https://proceedings.mlr.press/r7/tian09a.html %V R7 %X We study the problem of learning Bayesian network structures from data. Koivisto and Sood (2004) and Koivisto (2006) presented algorithms that can compute the exact marginal posterior probability of a subnetwork, e.g., a single edge, in O(n2n) time and the posterior probabilities for all n(n-1) potential edges in O(n2n) total time, assuming that the number of parents per node or the indegree is bounded by a constant. One main drawback of their algorithms is the requirement of a special structure prior that is non uniform and does not respect Markov equivalence. In this paper, we develop an algorithm that can compute the exact posterior probability of a subnetwork in O(3n) time and the posterior probabilities for all n(n-1) potential edges in O(n3n) total time. Our algorithm also assumes a bounded indegree but allows general structure priors. We demonstrate the applicability of the algorithm on several data sets with up to 20 variables. %Z Reissued by PMLR on 04 October 2026.
APA
Tian, J. & He, R.. (2009). Computing Posterior Probabilities of Structural Features in Bayesian Networks. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:546-555 Available from https://proceedings.mlr.press/r7/tian09a.html. Reissued by PMLR on 04 October 2026.

Related Material