CMU-CALD-05-106
Center for Automated Learning and Discovery
School of Computer Science, Carnegie Mellon University



CMU-CALD-05-106

Ajit P. Singh, Andrew W. Moore

June 2005

CMU-CALD-05-106.pdf


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 reports@cs.cmu.edu