### Abstract

We propose to solve the combinatorial problem of finding the highest scoring Bayesian network structure from data. This structure learning problem can be viewed as an inference problem where the variables specify the choice of parents for each node in the graph. The key combinatorial difficulty arises from the global constraint that the graph structure has to be acyclic. We cast the structure learning problem as a linear program over the polytope defined by valid acyclic structures. In relaxing this problem, we maintain an outer bound approximation to the polytope and iteratively tighten it by searching over a new class of valid constraints. If an integral solution is found, it is guaranteed to be the optimal Bayesian network. When the relaxation is not tight, the fast dual algorithms we develop remain useful in combination with a branch and bound method. Empirical results suggest that the method is competitive or faster than alternative exact methods based on dynamic programming.

Original language | English (US) |
---|---|

Pages (from-to) | 358-365 |

Number of pages | 8 |

Journal | Journal of Machine Learning Research |

Volume | 9 |

State | Published - 2010 |

Event | 13th International Conference on Artificial Intelligence and Statistics, AISTATS 2010 - Sardinia, Italy Duration: May 13 2010 → May 15 2010 |

### ASJC Scopus subject areas

- Software
- Control and Systems Engineering
- Statistics and Probability
- Artificial Intelligence

## Fingerprint Dive into the research topics of 'Learning Bayesian network structure using LP relaxations'. Together they form a unique fingerprint.

## Cite this

*Journal of Machine Learning Research*,

*9*, 358-365.