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. / 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.

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. / 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.

Made available in DSpace on 2014-12-17T14:56:21Z (GMT). No. of bitstreams: 1 AdersonCP.pdf: 441948 bytes, checksum: 3ac355b4df6f67d2c5c0a9bb8f35c95a (MD5) Previous issue date: 2006-08-30 / Bayesian networks are powerful tools as they represent probability distributions as graphs. They work with uncertainties of real systems. Since last decade there is a special interest in learning network structures from data. However learning the best network structure is a NP-Hard problem, so many heuristics algorithms to generate network structures from data were created. Many of these algorithms use score metrics to generate the network model. This thesis compare three of most used score metrics. The K-2 algorithm and two pattern benchmarks, ASIA and ALARM, were used to carry out the comparison. Results show that score metrics with hyperparameters that strength the tendency to select simpler network structures are better than score metrics with weaker tendency to select simpler network structures for both metrics (Heckerman-Geiger and modified MDL). Heckerman-Geiger Bayesian score metric works better than MDL with large datasets and MDL works better than Heckerman-Geiger with small datasets. The modified MDL gives similar results to Heckerman-Geiger for large datasets and close results to MDL for small datasets with stronger tendency to select simpler network structures / Redes Bayesianas s?o poderosas ferramentas de representa??o gr?fica de distribui??es de probabilidade. Tais redes manipulam incertezas existentes em sistemas do mundo real. A partir da ?ltima d?cada, especial interesse no aprendizado de sua estrutura a partir de um conjunto de dados. Entretanto, o aprendizado da estrutura ? um problema NP-Dif?cil, o que gerou a cria??o de Algoritmos heur?sticos de busca. Muitos desses Algoritmos s?o baseados em m?tricas de pontua??o para estimar o modelo. Este trabalho procura comparar tr?s das m?tricas mais utilizadas. Para gerar os resul tados foram utilizadas as redes ASIA e ALARM, que s?o dois dos benchmarks padr?es e o Algoritmo de busca K-2. A m?trica Bayesiana Heckerman-Geiger com hiperpar?metros que dificultam a gera??o de arestas apresentam melhores resultados que ?quelas que flexibilizam a gera??o de arestas, acontecendo o mesmo com a m?trica MDL modificada. A compara??o das duas m?tricas mostrou que a m?trica Bayesiana ? superior ? m?trica MDL com grandes conjuntos de dados e inferior, caso contr?rio. A modifica??o na m?trica MDL resultou em estruturas mais pr?ximas ?s apresentadas pela MDL para um conjunto reduzido de dados e mais pr?ximas ? Heckerman-Geiger para um grande conjunto de dados, quando seus par?metros restrigem a cria??o de arestas