Revistes Catalanes amb Accés Obert (RACO)

Learning bayesian networks by ant colony optimisation: searching in two different spaces

Luís Miguel De Campos, José Antonio Gámez Martín, José Miguel Puerta Castellón

Resum


The most common way of automatically learning Bayesian networks
from data is the combination of a scoring metric, the evaluation of the
fitness of any given candidate network to the data base, and a
search procedure to explore the search space. Usually, the search
is carried out by greedy hill-climbing algorithms, although other techniques
such as genetic algorithms, have also been used.

A recent metaheuristic, Ant Colony Optimisation (ACO), has
been successfully applied to solve a great variety of problems,
being remarkable the performance achieved in
those problems related to path (permutation) searching in
graphs, such as the Traveling Salesman Problem.
In two previous works [13,12], the authors have approached the problem of learning
Bayesian networks by means of the search+score methodology using
ACO as the search engine.

As in these articles the search was performed in different search spaces,
in the space of orderings [13] and in the space of directed acyclic graphs [12].
In this paper we compare both approaches
by analysing the results obtained and the differences in the design and
implementation of both algorithms.

Text complet: HTML