### A Bounded Error, Anytime, Parallel Algorithm for Exact Bayesian Network Structure Learning

## Abstract

Bayesian network structure learning is NP-hard. Several anytime structure learning algorithms have been proposed which guarantee to learn optimal networks if given enough resources. In this paper, we describe a general purpose, anytime search algorithm with bounded error that also guarantees optimality. We give an efficient, sparse representation of a key data structure for structure learning. Empirical results show our algorithm often finds better networks more quickly than state of the art methods. They also highlight accepting a small, bounded amount of suboptimality can reduce the memory and runtime requirements of structure learning by several orders of magnitude.## Bibtex

@INPROCEEDINGS{Malone12parallel,author = {Brandon Malone and Changhe Yuan},

title = {A Bounded Error, Anytime, Parallel Algorithm for Exact Bayesian Network Structure Learning},

booktitle = {Proceedings of the Sixth European Workshop on Probabilistic Graphical Models (PGM-12)},

address = {Granada, Spain},

year = {2012}

}