Learning Bayesian Network Structure using LP Relaxations

Abstract

We propose to solve the combinatorial problem
\nof finding the highest scoring Bayesian
\nnetwork structure from data. This structure
\nlearning problem can be viewed as an inference
\nproblem where the variables specify the
\nchoice of parents for each node in the graph.
\nThe key combinatorial difficulty arises from
\nthe global constraint that the graph structure
\nhas to be acyclic. We cast the structure
\nlearning problem as a linear program over
\nthe polytope defined by valid acyclic structures.
\nIn relaxing this problem, we maintain
\nan outer bound approximation to the polytope
\nand iteratively tighten it by searching
\nover a new class of valid constraints. If an
\nintegral solution is found, it is guaranteed
\nto be the optimal Bayesian network. When
\nthe relaxation is not tight, the fast dual algorithms
\nwe develop remain useful in combination
\nwith a branch and bound method.
\nEmpirical results suggest that the method is
\ncompetitive or faster than alternative exact
\nmethods based on dynamic programming.