Bayesian Network Structure Learning

Abstract—Learning the structure of Bayesian network is useful for a variety of tasks, ranging from density estimation to scien-tific discovery. Unfortunately, learning the structure from data considering all possible structures exhaustively is an NP-hard problem. Hence, structure learning require either sub-optimal heuristic search algorithms or algorithms that are optimal under certain assumptions. In light of these requirements, this paper distills a set of criteria for comparison of structure learning algorithms: time and space complexity, completeness of search space, search optimality, structural correctness and classification accuracy. Based on these criteria, a representative set of existing algorithms are summarized and compared. I