Learning Bayesian networks in the space of structures by estimation of distribution algorithms

The induction of the optimal Bayesian network structure is NP-hard, justifying the use of search heuristics. Two novel population-based stochastic search approaches, univariate marginal distribution algorithm (UMDA) and population-based incremental learning (PBIL), are used to learn a Bayesian network structure from a database of cases in a score + search framework. A comparison with a genetic algorithm (GA) approach is performed using three different scores: penalized maximum likelihood, marginal likelihood, and information-theory-based entropy. Experimental results show the interesting capabilities of both novel approaches with respect to the score value and the number of generations needed to converge. (C) 2003 Wiley Periodicals, Inc.