Learning Bayesian Network Structures with Non-Decomposable Scores

Bayesian networks learned from data and background knowledge have been broadly used to reason under uncertainty, and to determine associations and dependencies between random variables in the data, in various fields such as artificial intelligence, machine learning, and bioinformatics. The problem of learning the structure of a Bayesian network is typically formulated as an optimization problem, by scoring each network structure with respect to data and background knowledge. Modern approaches to the structure learning problem assume the scores to be decomposable, so that the optimization problem can be decomposed into a number of smaller and easier subproblems that can be optimized independently. These approaches include those based on dynamic programming, heuristic search, and integer linear programming methods.In this thesis, we break away from this tradition, and consider non-decomposable scores, that provide a richer expression for scoring the network structures. More specifically, we generalize the heuristic search approach for learning with decomposable scores, by using a more expressive search space, that accommodates non-decomposable scores. The search can be guided effectively by a heuristic function evaluated by existing structure learning approaches for decomposable scores. We show that our framework can learn an optimal Bayesian network structure with ancestral constraints and order-modular priors. Both are non-decomposable scores. Our framework can also enumerate the k-best Bayesian network structures and the k-best Markov-equivalent Bayesian network structures, using decomposable scores, and is empirically orders of magnitude more efficient than the previous state of the art