Apprentissage de la structure d'un réseau bayésien par un algorithme génétique

摘要

Combinant les propriétés de la théorie des probabilités et de la théorie des graphes, les réseaux bayésiens ont acquis une popularité certaine durant la dernière décennie. La détermination de la structure d'un modèle à partir d'une base de cas demeure cependant un problème délicat. Nous avons développé un algorithme génétique déterminant une structure tout en s'affranchissant des limitations fréquemment imposées (nombre limité de parents par variable, connaissance d'un ordre total sur les variables). L'algorithme parcourt l'espace des graphes orientés sans circuit et repère un ensemble d'op-tima locaux pour renvoyer le meilleur optimum local trouvé.%Combining the properties of both probability theories and graph theory, bayesian networks have become very popular during the past decade. Determining the network's structure from a database of cases remains, however, a major issue. We have developed a genetical algorithm defining a structure while ignoring the limitations usually imposed upon the search (limited number of parents per node, knowledge of an ordering over the variables). The algorithm searches the space of directed acyclic graphs and defines a set of local optima, eventually returning the best local optimum it has found.