An Improved Admissible Heuristic for Learning Optimal Bayesian Networks

Changhe Yuan, Brandon Malone
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:923-932, 2012.

Abstract

Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-yuan12a, title = {An Improved Admissible Heuristic for Learning Optimal {B}ayesian Networks}, author = {Yuan, Changhe and Malone, Brandon}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {923--932}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/yuan12a/yuan12a.pdf}, url = {https://proceedings.mlr.press/r10/yuan12a.html}, abstract = {Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T An Improved Admissible Heuristic for Learning Optimal Bayesian Networks %A Changhe Yuan %A Brandon Malone %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-yuan12a %I PMLR %P 923--932 %U https://proceedings.mlr.press/r10/yuan12a.html %V R10 %X Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper. %Z Reissued by PMLR on 04 October 2026.
APA
Yuan, C. & Malone, B.. (2012). An Improved Admissible Heuristic for Learning Optimal Bayesian Networks. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:923-932 Available from https://proceedings.mlr.press/r10/yuan12a.html. Reissued by PMLR on 04 October 2026.

Related Material