|
Abstract : |
Algorithms for learning Bayesian networks from data have two components: a scoring metric and a search procedure. The scoring metric computes a score reflecting the goodness-of-fit of the structure to the data. The search procedure tries to identify network structures with high scores. Heckerman et al. (1995) introduce a Bayesian metric, called the BDe metric, that computes the relative posterior probability of a network structure given data. In this paper, we show that the search problem of identifying a Bayesian network---among those where each node has at most K parents---that has a relative posterior probability greater than a given constant is NP-complete, when the BDe metric is used. Recently, many researchers have begun to investigate methods for learning Bayesian networks. Many of these approaches have the same basic components: a scoring metric and a search procedure. The scoring metric takes a database of observed cases D and a network, |
