An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning
[edit]
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:6980, 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 techniquesthe wellknown \emph{scoreandsearch} approach. An important consideration
when applying a scoreandsearch 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 stateoftheart 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 stateoftheart algorithms when considering anytime behavior.
Related Material


