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

Abstract

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: penalize 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.