Fitness Landscape Analysis of Bayesian Network Structure Learning

Algorithms for learning the structure of Bayesian Networks (BN) from data are the focus of intense research interest. Search-and-score algorithms using nature-inspired metaheuristics are an important strand of this research; however performance is variable and strongly problem-dependent. In this paper we use fitness landscape analysis to explain empirically-observed performance differences between particular search-and-score algorithms on two well-studied benchmark problems. We investigate the average landscape discovered by random walks around optimal points in the space of BN node orderings. Differences in algorithm performance are explained in terms of these landscapes, which in turn are related to properties of the BN structures. These initial findings suggest that fitness landscape analysis is a promising approach for explaining existing empirical performance comparisons with further potential for understanding the relative difficulty of benchmark problems and the robustness of particular algorithms.