A Depth-first Branch and Bound Algorithm for Learning Optimal Bayesian Networks

Early methods for learning a Bayesian network that optimizes a scoring function for a given dataset are mostly approximation algorithms such as greedy hill climbing approaches. These methods are anytime algorithms as they can be stopped anytime to produce the best solution so far. However, they cannot guarantee the quality of their solution, not even mentioning optimality. In recent years, several exact algorithms have been developed for learning optimal Bayesian network structures. Most of these algorithms only find a solution at the end of the search, so they fail to find any solution if stopped early for some reason, e.g., out of time or memory. We present a new anytime algorithm that finds increasingly better solutions and eventually converges to an optimal Bayesian network upon completion. The algorithm is shown to not only improve the runtime to find optimal network structures up to 100 times compared to some existing methods, but also prove the optimality of these solutions about 10 times faster in some cases