Redes Bayesianas são modelos gráficos amplamente utilizados para automatizar o raciocínio probabilístico em domínios complexos. Uma rede Bayesiana é um grafo direcionado acíclico no qual os nós representam variáveis aleatórias e os arcos representam relações de dependência entre variáveis. Especificar manualmente uma rede Bayesiana sobre um domínio grande e complexo é uma tarefa altamente custosa e propensa a erros. Isto justifica o desenvolvimento de métodos para aprender estruturas de redes Bayesianas a partir de observações. Uma abordagem bem sucedida para aprendizado de redes Bayesianas é especificar uma função de pontuação (score), que associa cada estrutura a um número que representa a adequação do modelo aos dados e ao conhecimento prévio. O aprendizado então consiste em selecionar uma estrutura com alta pontuação. A aprendizagem estrutural baseada em pontuação é uma tarefa computacionalmente custosa (NP-difícil), o que cria a necessidade de desenvolvimento de técnicas aproximadas. Embora existam muitas técnicas com alguma garantia de qualidade (convergência, consistência ou estimativa de erro), elas possuem um custo computacional alto e não são aplicáveis em domínios muito grandes (centenas ou milhares de variáveis). Uma técnica simples e eficaz para a aprendizagem aproximada de estruturas de redes Bayesianas consiste em realizar uma busca local no espaço de ordenações topológicas de variáveis utilizando um espaço restrito de conjuntos de pais. Embora essa abordagem não possua garantias de desempenho, ela é computacionalmente eficiente, e empiricamente superior a outros métodos, especial- mente quando o número de variáveis é grande. Geralmente, a busca local é inicializada com uma ordenação das variáveis gerada uniformemente no espaço de ordenações. Isso pode levar a busca a obter soluções de baixa qualidade e a requerer um número alto de iterações, o que prejudica o desempenho do método. Esse trabalho tem como objetivo estudar e aprimorar as técnicas de aprendizagem de redes Bayesianas em domínios muito grandes. Em particular, pretende-se melhorar a qualidade das soluções encontradas pelo algoritmo de busca por geração de ordenações topológicas, empregando técnicas do estado-da-arte na geração de conjuntos de pais e desenvolvendo heurísticas informadas para geração de ordenações topológicas. A qualidade das soluções encontradas foi avaliada pela pon- tuação. Os resultados mostram que as novas heurísticas de inicialização melhoram as redes obtidas com uma diferencia significativa.

Bayesian networks are widely used graphical models for reasoning under uncertainty on complex domains. A Bayesian network is a directed acyclic graph where nodes represent random variables and the arcs represent (in)dependence relationships. Manually specifying a Bayesian network over a large and complex domain is a time-consuming and error-prone task. This justifies the development of methods for learning Bayesian network structures from data. A successful approach to Bayesian network structure learning is to use a score function which assigns a value for each structure based on how well the structure represents the data. This way the problem of learning a Bayesian network becomes a combinatorial optimization of finding structures. Score-based structure learning is a computationally demanding task (in fact, NP-Hard), which justifies the development of approximate methods. Even though there are some methods which provide quality guarantees (convergence, consistence or error estimative), they scale poorly to large domains (hundreds and thousands of variables). An effective approach for learning Bayesian network structures is to perform a local search on the space of topological orderings using a restricted space of parent sets. While this approach has no performance guarantee, it is computationally efficient and performs empirically better than other approaches, especially on large domains. Typically, the search is initialized with a randomly generated ordering. This can lead to poor local optima, slow convergence and ultimately degrade the performance of the method as the number of variables increases. This work aims at studying and improving order-based local search methods for score-based Bayesian network structure learning on large domains. Specifically, we aim at improving solutions obtained by order-based local searches using state-of-the-art parent set selection methods, and at developing new informed heuristics that allow for learning better large Bayesian networks. The new heuristics were evaluated on the scores obtained from real-world data sets. Results show that the new initialization heuristics improve the obtained Bayesian networks significantly.