An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning

Colin Lee, Peter van Beek
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:69-80, 2017.

Abstract

Bayesian networks are a widely used graphical model with diverse applications in knowledge discovery, classification, and decision making. Learning a Bayesian network from discrete data can be cast as a combinatorial optimization problem and thus solved using optimization techniques---the well-known \emph{score-and-search} approach. An important consideration when applying a score-and-search method for Bayesian network structure learning (BNSL) is its anytime behavior; i.e., how does the quality of the solution found improve as a function of the amount of time given to the algorithm. Previous studies of the anytime behavior of methods for BNSL are limited by the scale of the instances used in the evaluation and evaluate only algorithms that do not scale to larger instances. In this paper, we perform an extensive evaluation of the anytime behavior of the current state-of-the-art algorithms for BNSL. Our benchmark instances range from small (instances with fewer than 20 random variables) to massive (instances with more than 1,500 random variables). We find that a local search algorithm based on memetic search dominates the performance of other state-of-the-art algorithms when considering anytime behavior.

Cite this Paper

BibTeX
@InProceedings{pmlr-v73-lee17a, title = {An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning}, author = {Lee, Colin and van Beek, Peter}, booktitle = {Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks}, pages = {69--80}, year = {2017}, editor = {Hyttinen, Antti and Suzuki, Joe and Malone, Brandon}, volume = {73}, series = {Proceedings of Machine Learning Research}, month = {20--22 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v73/lee17a/lee17a.pdf}, url = {https://proceedings.mlr.press/v73/lee17a.html}, abstract = {Bayesian networks are a widely used graphical model with diverse applications in knowledge discovery, classification, and decision making. Learning a Bayesian network from discrete data can be cast as a combinatorial optimization problem and thus solved using optimization techniques---the well-known \emph{score-and-search} approach. An important consideration when applying a score-and-search method for Bayesian network structure learning (BNSL) is its anytime behavior; i.e., how does the quality of the solution found improve as a function of the amount of time given to the algorithm. Previous studies of the anytime behavior of methods for BNSL are limited by the scale of the instances used in the evaluation and evaluate only algorithms that do not scale to larger instances. In this paper, we perform an extensive evaluation of the anytime behavior of the current state-of-the-art algorithms for BNSL. Our benchmark instances range from small (instances with fewer than 20 random variables) to massive (instances with more than 1,500 random variables). We find that a local search algorithm based on memetic search dominates the performance of other state-of-the-art algorithms when considering anytime behavior.} }
Endnote
%0 Conference Paper %T An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning %A Colin Lee %A Peter van Beek %B Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks %C Proceedings of Machine Learning Research %D 2017 %E Antti Hyttinen %E Joe Suzuki %E Brandon Malone %F pmlr-v73-lee17a %I PMLR %P 69--80 %U https://proceedings.mlr.press/v73/lee17a.html %V 73 %X Bayesian networks are a widely used graphical model with diverse applications in knowledge discovery, classification, and decision making. Learning a Bayesian network from discrete data can be cast as a combinatorial optimization problem and thus solved using optimization techniques---the well-known \emph{score-and-search} approach. An important consideration when applying a score-and-search method for Bayesian network structure learning (BNSL) is its anytime behavior; i.e., how does the quality of the solution found improve as a function of the amount of time given to the algorithm. Previous studies of the anytime behavior of methods for BNSL are limited by the scale of the instances used in the evaluation and evaluate only algorithms that do not scale to larger instances. In this paper, we perform an extensive evaluation of the anytime behavior of the current state-of-the-art algorithms for BNSL. Our benchmark instances range from small (instances with fewer than 20 random variables) to massive (instances with more than 1,500 random variables). We find that a local search algorithm based on memetic search dominates the performance of other state-of-the-art algorithms when considering anytime behavior.
APA
Lee, C. & van Beek, P.. (2017). An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning. Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, in Proceedings of Machine Learning Research 73:69-80 Available from https://proceedings.mlr.press/v73/lee17a.html.

Related Material