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

Brandon Malone and Changhe Yuan

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.

PDF

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}
}