[edit]

# An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning

*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.