Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks

Brandon Malone, Changhe Yuan
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:145-154, 2013.

Abstract

Exact algorithms for learning Bayesian networks guarantee to find provably optimal networks. However, they may fail in difficult learning tasks due to limited time or memory. In this research we adapt several anytime heuristic search-based algorithms to learn Bayesian networks. These algorithms find high-quality solutions quickly, and continually improve the incumbent solution or prove its optimality before resources are ex- hausted. Empirical results show that the any- time window A* algorithm usually finds higher- quality, often optimal, networks more quickly than other approaches. The results also show that, surprisingly, while generating networks with few parents per variable are structurally simpler, they are harder to learn than complex generating net- works with more parents per variable.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-malone13a, title = {Evaluating Anytime Algorithms for Learning Optimal {B}ayesian Networks}, author = {Malone, Brandon and Yuan, Changhe}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {145--154}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/malone13a/malone13a.pdf}, url = {https://proceedings.mlr.press/r11/malone13a.html}, abstract = {Exact algorithms for learning Bayesian networks guarantee to find provably optimal networks. However, they may fail in difficult learning tasks due to limited time or memory. In this research we adapt several anytime heuristic search-based algorithms to learn Bayesian networks. These algorithms find high-quality solutions quickly, and continually improve the incumbent solution or prove its optimality before resources are ex- hausted. Empirical results show that the any- time window A* algorithm usually finds higher- quality, often optimal, networks more quickly than other approaches. The results also show that, surprisingly, while generating networks with few parents per variable are structurally simpler, they are harder to learn than complex generating net- works with more parents per variable.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks %A Brandon Malone %A Changhe Yuan %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-malone13a %I PMLR %P 145--154 %U https://proceedings.mlr.press/r11/malone13a.html %V R11 %X Exact algorithms for learning Bayesian networks guarantee to find provably optimal networks. However, they may fail in difficult learning tasks due to limited time or memory. In this research we adapt several anytime heuristic search-based algorithms to learn Bayesian networks. These algorithms find high-quality solutions quickly, and continually improve the incumbent solution or prove its optimality before resources are ex- hausted. Empirical results show that the any- time window A* algorithm usually finds higher- quality, often optimal, networks more quickly than other approaches. The results also show that, surprisingly, while generating networks with few parents per variable are structurally simpler, they are harder to learn than complex generating net- works with more parents per variable. %Z Reissued by PMLR on 04 October 2026.
APA
Malone, B. & Yuan, C.. (2013). Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:145-154 Available from https://proceedings.mlr.press/r11/malone13a.html. Reissued by PMLR on 04 October 2026.

Related Material