Branch and Bound for Regular Bayesian Network Structure Learning

Joe Suzuki, Jun Kawahara
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:141-150, 2017.

Abstract

We consider efficient Bayesian network structure learning (BNSL) based on scores using branch and bound. Thus far, as a BNSL score, the Bayesian Dirichlet equiva- lent uniform (BDeu) has been used most of- ten, but it is recently proved that the BDeu does not choose the simplest model even when the likelihood is maximized whereas Jeffreys’ prior and MDL satisfy such regu- larity. Although the BDeu has been pre- ferred because it gives Markov equivalent models the same score, in this paper, we introduce another class of scores (quotient scores) that satisfies the property, and pro- pose a pruning rule for the quotient score based on Jeffreys’ prior. We find that the quotient score based on Jeffreys’ prior is regular, and that the proposed pruning rule utilizes the regularity, and is applied much more often than that of the BDeu, so that much less computation is required in BNSL. Finally, our experiments support the hypothesis that the regular scores out- perform the non-regular ones in the sense of computational efficiency as well as cor- rectness of BNSL.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-suzuki17a, title = {Branch and Bound for Regular {B}ayesian Network Structure Learning}, author = {Suzuki, Joe and Kawahara, Jun}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {141--150}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/suzuki17a/suzuki17a.pdf}, url = {https://proceedings.mlr.press/r15/suzuki17a.html}, abstract = {We consider efficient Bayesian network structure learning (BNSL) based on scores using branch and bound. Thus far, as a BNSL score, the Bayesian Dirichlet equiva- lent uniform (BDeu) has been used most of- ten, but it is recently proved that the BDeu does not choose the simplest model even when the likelihood is maximized whereas Jeffreys’ prior and MDL satisfy such regu- larity. Although the BDeu has been pre- ferred because it gives Markov equivalent models the same score, in this paper, we introduce another class of scores (quotient scores) that satisfies the property, and pro- pose a pruning rule for the quotient score based on Jeffreys’ prior. We find that the quotient score based on Jeffreys’ prior is regular, and that the proposed pruning rule utilizes the regularity, and is applied much more often than that of the BDeu, so that much less computation is required in BNSL. Finally, our experiments support the hypothesis that the regular scores out- perform the non-regular ones in the sense of computational efficiency as well as cor- rectness of BNSL.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Branch and Bound for Regular Bayesian Network Structure Learning %A Joe Suzuki %A Jun Kawahara %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-suzuki17a %I PMLR %P 141--150 %U https://proceedings.mlr.press/r15/suzuki17a.html %V R15 %X We consider efficient Bayesian network structure learning (BNSL) based on scores using branch and bound. Thus far, as a BNSL score, the Bayesian Dirichlet equiva- lent uniform (BDeu) has been used most of- ten, but it is recently proved that the BDeu does not choose the simplest model even when the likelihood is maximized whereas Jeffreys’ prior and MDL satisfy such regu- larity. Although the BDeu has been pre- ferred because it gives Markov equivalent models the same score, in this paper, we introduce another class of scores (quotient scores) that satisfies the property, and pro- pose a pruning rule for the quotient score based on Jeffreys’ prior. We find that the quotient score based on Jeffreys’ prior is regular, and that the proposed pruning rule utilizes the regularity, and is applied much more often than that of the BDeu, so that much less computation is required in BNSL. Finally, our experiments support the hypothesis that the regular scores out- perform the non-regular ones in the sense of computational efficiency as well as cor- rectness of BNSL. %Z Reissued by PMLR on 04 October 2026.
APA
Suzuki, J. & Kawahara, J.. (2017). Branch and Bound for Regular Bayesian Network Structure Learning. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:141-150 Available from https://proceedings.mlr.press/r15/suzuki17a.html. Reissued by PMLR on 04 October 2026.

Related Material