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 equivalent uniform (BDeu) has been used most often, 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 regularity. Although the BDeu has been preferred 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 propose 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 outperform the non-regular ones in the sense of computational efficiency as well as correctness 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 equivalent uniform (BDeu) has been used most often, 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 regularity. Although the BDeu has been preferred 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 propose 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 outperform the non-regular ones in the sense of computational efficiency as well as correctness 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 equivalent uniform (BDeu) has been used most often, 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 regularity. Although the BDeu has been preferred 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 propose 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 outperform the non-regular ones in the sense of computational efficiency as well as correctness 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