Geração uniforme de $k$-trees para aprendizado de redes bayesianas

Trabalho de conclusão de curso do Bacharelado em Ciência da Computação do IME-USP

Aluno: Tiago Madeira
Supervisor: Prof. Dr. Denis Deratani Mauá

Resumo

$k$-trees são estruturas que generalizam árvores para grafos cíclicos mantendo seu aspecto recursivo. Há interesse considerável em desenvolver ferramentas eficientes para manipular essa classe de grafos, porque muitos problemas NP-difíceis são resolvidos em tempo polinomial em $k$-trees e subgrafos de $k$-trees.

Este trabalho de conclusão de curso consiste num estudo sobre amostragem uniforme de $k$-trees e seu uso no aprendizado da estrutura de redes bayesianas com treewidth limitado. Foi implementado um algoritmo para codificar e decodificar $k$-trees de forma bijetiva em tempo linear. O trabalho mostra como aprender grafos acíclicos dirigidos cujo grafo moral é um subgrafo das $k$-trees geradas. Experimentos comparam esse método para aprender estruturas com o estado da arte.

Trabalho final

  1. Monografia
  2. Repositório no GitHub (códigos, etc.)
  3. Apresentação
  4. Pôster

Última atualização: Dom Nov 20 21:54:57 BRST 2016