Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University


Ajit P. Singh, Andrew W. Moore

June 2005


Keywords: Bayesian networks, structure learning, dynamic programming, P-cache

Finding the Bayesian network that maximizes a score function is known as structure learning or structure discovery. Most approaches use local search in the space of acyclic digraphs, which is prone to local maxima. Exhaustive enumeration requires super-exponential time. In this paper we describe a "merely" exponential space/time algorithm for finding a Bayesian network that corresponds to a global maxima of a decomposable scoring function, such as BDeu or BIC.

16 pages

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by