• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
10.11606/T.18.2012.tde-30102012-103112
Documento
Autor
Nombre completo
Edwin Rafael Villanueva Talavera
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2012
Director
Tribunal
Maciel, Carlos Dias (Presidente)
Fernandez, Francisco Javier Ramirez
Hruschka Júnior, Estevam Rafael
Ribeiro, Carlos Henrique Costa
Vêncio, Ricardo Zorzetto Nicoliello
Título en portugués
Sistema evolutivo eficiente para aprendizagem estrutural de redes Bayesianas
Palabras clave en portugués
Aprendizagem estrutural
Computação evolutiva
Redes Bayesianas
Resumen en portugués
Redes Bayesianas (RB) são ferramentas probabilísticas amplamente aceitas para modelar e fazer inferências em domínios sob incertezas. Uma das maiores dificuldades na construção de uma RB é determinar a sua estrutura de modelo, a qual representa a estrutura de interdependências entre as variáveis modeladas. A estimativa exata da estrutura de modelo a partir de dados observados é, de forma geral, impraticável já que o número de estruturas possíveis cresce de forma super-exponencial com o número de variáveis. Métodos eficientes de aprendizagem aproximada tornam-se, portanto, essenciais para a construção de RBs verossímeis. O presente trabalho apresenta o Sistema Evolutivo Eficiente para Aprendizagem Estrutural de RBs, ou abreviadamente, EES-BN. Duas etapas de aprendizagem compõem EES-BN. A primeira etapa é encarregada de reduzir o espaço de busca mediante a aprendizagem de uma superestrutura. Para tal fim foram desenvolvidos dois métodos efetivos: Opt01SS e OptHPC, ambos baseados em testes de independência. A segunda etapa de EES-BN é um esquema de busca evolutiva que aproxima a estrutura do modelo respeitando as restrições estruturais aprendidas na superestrutura. Três blocos principais integram esta etapa: recombinação, mutação e injeção de diversidade. Para recombinação foi desenvolvido um novo operador (MergePop) visando ganhar eficiência de busca, o qual melhora o operador Merge de Wong e Leung (2004). Os operadores nos blocos de mutação e injeção de diversidade foram também escolhidos procurando um adequado equilíbrio entre exploração e utilização de soluções. Todos os blocos de EES-BN foram estruturados para operar colaborativamente e de forma auto-ajustável. Em uma serie de avaliações experimentais em RBs conhecidas de variado tamanho foi encontrado que EES-BN consegue aprender estruturas de RBs significativamente mais próximas às estruturas verdadeiras do que vários outros métodos representativos estudados (dois evolutivos: CCGA e GAK2, e dois não evolutivos: GS e MMHC). EES-BN tem mostrado também tempos computacionais competitivos, melhorando marcadamente os tempos dos outros métodos evolutivos e superando também ao GS nas redes de grande porte. A efetividade de EES-BN foi também comprovada em dois problemas relevantes em Bioinformática: i) reconstrução da rede deinterações intergênicas a partir de dados de expressão gênica, e ii) modelagem do chamado desequilíbrio de ligação a partir de dados genotipados de marcadores genéticos de populações humanas. Em ambas as aplicações, EES-BN mostrou-se capaz de capturar relações interessantes de significância biológica estabelecida.
Título en inglés
Efficient evolutionary system for learning BN structures
Palabras clave en inglés
Bayesian networks
Evolutionary computation
Structure learning
Resumen en inglés
Bayesian networks (BN) are probabilistic tools widely accepted for modeling and reasoning in domains under uncertainty. One of the most difficult tasks in the construction of a BN is the determination of its model structure, which is the inter-dependence structure of the problem variables. The exact estimation of the model structure from observed data is generally infeasible, since the number of possible structures grows super-exponentially with the number of variables. Efficient approximate methods are therefore essential for the construction of credible BN. In this work we present the Efficient Evolutionary System for learning BN structures (EES-BN). This system is composed by two learning phases. The first phase is responsible for the reduction of the search space by estimating a superstructure. For this task were developed two methods (Opt01SS and OptHPC), both based in independence tests. The second phase of EES-BN is an evolutionary design for finding the optimal model structure using the superstructure as the search space. Three main blocks compose this phase: recombination, mutation and diversity injection. With the aim to gain search efficiency was developed a new recombination operator (MergePop), which improves the Merge operator of Wong e Leung (2004). The operators for mutation and recombination blocks were also selected aiming to have an appropriate balance between exploitation and exploration of the solutions. All blocks in EES-BN were structured to operate in a collaborative and self-regulated fashion. Through a series of experiments and comparisons on benchmark BNs of varied dimensionality was found that EES-BN is able to learn BN structures markedly closer to the gold standard networks than various other representative methods (two evolutionary: CCGA and GAK2, and two non-evolutionary methods: GS and MMHC). The computational times of EES-BN were also found competitive, improving notably the times of the evolutionary methods and also the GS in the larger networks. The effectiveness of EES-BN was also verified in two real problems in bioinformatics: i) the reconstruction of a gene regulatory network from gene-expression data, and ii) the modeling of the linkage disequilibrium structures from genetic marker genotyped data of human populations. In both applications EES-BN proved to be able to recover interesting relationships with proven biological meaning.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Edwin.pdf (4.38 Mbytes)
Fecha de Publicación
2012-11-07
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2019. Todos los derechos reservados.