Proposta

---

Proposta em PDF

Introdução

---

O modelo gráfico probabilístico é uma representação visual de uma distribuição conjunta de um vetor aleatório. Ele pode ser descrito por um grafo direcionado, como nos modelos de redes Bayesianas, ou não-direcionado, como nos campos aleatórios de Markov. Cada vértice do grafo é uma variável aleatória do vetor e seus arcos ou arestas são definidos conforme a independência condicional entre eles. Suas aplicações se encontram em áreas como a biologia, o aprendizado de máquinas e as ciências sociais, onde os modelos podem possuir um grande número de variáveis.

Um problema recorrente é a reconstrução, a partir de amostras, do grafo que expressa as independências condicionais entre as variáveis, calculando a estimativa de máxima verossimilhança da vizinhança de cada nó do grafo. O problema da estimação é NP-completo, mas em algumas subclasses desses modelos temos boas soluções.

Objetivo

---

O objetivo do trabalho é estudar algoritmos para a estimação da estrutura em algumas configurações de grafos. Inicialmente planejamos o estudo de dois artigos, sendo que um propõe um algoritmo polinomial para a estimação considerando que o grafo é uma árvore, e o outro descreve dois algoritmos, também polinomiais, para a estimação do grafo onde o grau máximo de cada vértice é fixado. Mais algoritmos poderão ser considerados ao longo do trabalho.

Os algoritmos serão estudados de forma teórica e por meio de simulações. Na parte teórica, buscaremos estudar a corretude do programa e a estimação do erro. A parte prática visa implementar os algoritmos na linguagem de programação R, gerar as amostras e verificar empiricamente os resultados de consistência e de velocidade de convergência.

Cronograma

	Abril	Maio	Junho	Julho	Agosto	Setembro	Outubro	Novembro
Estudo dos Algoritmos	X	X	X	X
Estudo da Linguagem R		X	X
Implementação dos Algoritmos		X	X	X
Simulações			X	X	X
Escrita da Monografia					X	X	X	X