Finding Optimal Bayesian Networks by Dynamic Programming (2005)

Abstract

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.

Full text

Download (application/pdf, 214.0 kB)

Approximate BibTeX Entry

@techreport{singh:04,
    Month = {June},
    Year = {2005},
    Pages = {16},
    School = {School of Computer Science},
    Institution = {Carnegie Mellon University},
    Author = { Ajit Singh, Andrew Moore },
    Title = {Finding Optimal Bayesian Networks by Dynamic Programming}
}