Edimilson Batista dos Santos
Resumo
O desenvolvimento de métodos automáticos para aprender estruturas de uma Rede Bayesiana (RB) diretamente a partir de dados é um problema relevante e considerado uma tarefa difícil, porque o número de possíveis estruturas cresce exponencialmente de acordo com o número de variáveis. Geralmente, para reduzir o espaço de busca, algumas restrições podem ser impostas durante o processso de indução da RB. Uma restrição possível é a definição de uma ordenação das variáveis. Definir uma ordenação adequada das variáveis é, contudo, um problema complexo a ser executado, principalmente porque requer conhecimento prévio sobre o domínio. Trabalhos anteriores, na literatura, sugerem o uso de Algoritmos Evolucionários para encontrar uma ordenação de variáveis adequada ao aprendizado de estruturas de redes Bayesianas. No entanto, algoritmos evolucionários podem ser computacionalmente custosos, assim, o uso de operadores genéticos específicos para o problema da ordenação de variáveis pode torná-los mais eficientes. Para os casos onde a busca por uma ordenação de variáveis é adequada, este trabalho apresenta dois novos operadores genéticos e um novo algoritmo adaptativo híbrido que busca tal ordenação para otimizar o aprendizado das redes. Para os casos onde uma ordenação não é indicada, são definidos um método de indução de classificadores Bayesianos, chamado DMBC, e uma versão aproximada, chamada A-DMBC. Os resultados experimentais mostram que os métodos propostos são consistentes e promissores.
Abstract
The development of automatic methods for learning Bayesian network structures directly from data is a relevant problem, and is considered a difficult task because the number of possible structures grows exponentially according to the number of variables. In order to reduce this search space, some constraints can be imposed during the induction process. One possible constraint is the definition of a variable ordering. Defining a suitable variable ordering is, however, a complex problem to be performed mainly because it requires prior knowledge about the model. Previous works in the literature suggest that the use of evolutionary algorithms for dealing with variable ordering, when learning a Bayesian network structure from data, is worth pursuing. However, evolutionary algorithms may be computationally costly and the use of specific genetic operators for variable ordering problem can make them more efficient. To the cases where a variable ordering is suitable, this work presents two new genetic operators and a new hybrid adaptive algorithm which look for such a ordering for optimizing the network learning. To the cases where a variable ordering is not indicated, a method of induction of Bayesian classifiers named DMBC and an approximate version named A-DMBC are defined. The experimental results show that the proposed methods are consistent and promising.
