|
Cadeias de Markov
PESC/COPPE/UFRJ |
The Epic 20,000 Roll Dice Randomness Test |
|
Cadeias de Markov
PESC/COPPE/UFRJ |
The Epic 20,000 Roll Dice Randomness Test |
Desde da sua concepção na década de 40 algoritmos de Monte Carlo vem sendo utilizados para resolver diversos tipos de problemas, tais como problemas de amostragem e estimação, encontrando aplicações na Física, Biologia e Engenharia. Dentre suas muitas variações, algoritmos de Monte Carlo acoplados a cadeias de Markov (MCMC) estão entre os mais poderosos, tais como Metropolis-Hastings e simulated annealing. Com a crescente quantidade de dados e demanda por eficiência computacional, tais algoritmos vem sendo usados como base de técnicas emergentes em Ciências dos Dados e Inteligência Artificial. Nesta disciplina iremos explorar algoritmos de Monte Carlo com um enfoque teórico e fundamental, cobrindo probabilidade e teoria de cadeias de Markov, e também algumas aplicações práticas.
Algoritmo de Metropolis para Monte Carlo foi nomeado pela revista IEEE Computing in Science & Engineering como sendo um dos 10 algoritmos que mais influenciaram o desenvolvimento e a prática da ciência e engenharia no século 20!
Revisão de probabilidade, lei dos grandes números, algoritmos de amostragem, integração de Monte Carlo, cadeias de Markov, estado estacionário, tempo de mistura, passeios aleatórios, Metropolis-Hastings, amostragem de Gibbs, simulated annealing.
Pré-requisito: Probabilidade e estatística
Se inscrever no Moodle da discilina, cujo código de acesso para auto-inscrição é codigo767. Iremos utilizar esta plataforma para troca de mensagens e avisos, e entrega de tarefas (listas).
| Encontro | Data | Comentário | Slides | Vídeos | Tarefa |
| 1 | 22/03 | Logística, programação e regras do jogo. Três (tipos de) problemas resolvidos por Monte Carlo, história das origens, Monte Carlo na Computação |
aula_0.pdf aula_1.pdf |
Aula 0 Aula 1 |
Saiu lista 1 |
| 2 | 24/03 | Revisão de probabilidade: espaço amostral, probabilidade, eventos, independência, exclusão mútua, probabilidade total, regra de Bayes, variável aleatória, função de distribuição, distribuição de Bernoulli | aula_2.pdf | Aula 2 | Fazer lista 1 |
| 3 | 29/03 | Revisão de probabilidade: distribuição Binomial, Geometrica, Zeta, valor esperado, variância, função de v.a., distribuição conjunta, independência de v.a., valor esperado conditional, espaço amostral contínuo, função densidade | aula_3.pdf | Aula 3
Discussão |
Fazer lista 1 |
| 4 | 31/03 | Limitantes para probabilidade, desigualdades de Markov, Chebyshev, Chernoff, with high probability (whp), limitante da União | aula_4.pdf | Aula 4
Discussão |
Fazer lista 1 |
| 5 | 5/04 | Lei dos grandes números (fraca e forte), erro e confiança, margem de erro, falácia do apostador | aula_5.pdf | Aula 5
Discussão |
Saiu lista 2 |
| 6 | 7/04 | Método de Monte Carlo, estimando somatórios, calculando o erro, estimando pi, integração de Monte Carlo, Monte Carlo Ray Tracing | aula_6.pdf | Aula 6
Discussão |
Entregar lista 1 |
| 7 | 12/04 | Gerando amostras de v.a. discretas (eficientemente), gerando geométrica, método da transformada inversa, gerando Binomial, gerando permutações | aula_7.pdf | Aula 7
Discussão |
Fazer lista 2 |
| 8 | 14/04 | Método da rejeição (rejection sampling), exemplos, Importance Sampling, exemplos, generalização | aula_8.pdf | Aula 8
Discussão |
Fazer lista 2 |
| 9 | 19/04 | Algoritmos randomizados, exemplos, algoritmos de monte carlo, algoritmos de las vegas, comparação | aula_6_1.pdf | Aula 6_1
Discussão |
Fazer lista 2 |
| - | 21/04 | Feriado: Dia de Tiradentes | Fazer lista 2 | ||
| 10 | 26/04 | Cadeias de Markov, definição e exemplos, modelo On-Off, sem memória, distribuição no tempo, irredutibilidade, aperiodicidade | aula_9.pdf | Aula 9
Discussão |
Fazer lista 2 |
| 11 | 28/04 | Distribuição estacionária, tempo de chegada, distância de variação total, convergência, calculando distribuição estacionária, reversibilidade, passeio aleatório, processo de nascimento e morte | aula_10.pdf | Aula 10
Discussão |
Entregar lista 2 |
| 12 | 3/05 | Autovalores, autovetores, e decomposição, convergência para estacionaridade, tempo de mistura, spectral gap, tempo de mistura de passeios aleatórios | aula_11.pdf | Aula 11
Discussão |
Saiu lista 3 |
| 13 | 5/05 | Caminho amostral, teorema Ergódico, estimando pi, simulação de CM (eficiente), gerando amostras, simulando cadeias enormes | aula_12.pdf | Aula 12
Discussão |
Fazer lista 3 |
| 14 | 10/05 | Amostrando espaços complicados, Markov Chain Monte Carlo, caso simétrico, exemplo, Metropolis-Hasting, amostrando vértices (sem conhecer a rede) | aula_13.pdf | Aula 13
Discussão |
Fazer lista 3 |
| 15 | 12/05 | Modelo Hardcore via Metropolis-Hastings, Gibbs Sampling, exemplo, modelo Hardcore via Gibbs Sampling, q-coloração via Gibbs Sampling, tempo de mistura | aula_14.pdf | Aula 14
Discussão |
Projeto para disciplina |
| 16 | 17/05 | Otimização, caixeiro viajante, Hill Climbing, distribuição de Boltzman, simulated Annealing, de volta ao caixeiro | aula_15.pdf | Aula 15
Discussão |
Projeto para disciplina |
| 17 | 19/05 | Aula de dicas para sua proposta de projeto para a disciplina | Discussão | Projeto para disciplina | |
| 18 | 24/05 | Entrega e apresentação da proposta de projeto para a disciplina (início às 15h) | Discussão | Entregar proposta, Lista 3 | |
| 19 | 26/05 | Os três problemas, Monte Carlo to the rescue, caminho trilhado, Monte Carlo como building block, desafios. Avaliação da disciplina. | aula_16.pdf | Aula 16
Discussão |
Saiu Lista 4 |
| 20 | 09/06 | Dúvidas e discussão sobre projeto, listas, e conteúdo da disciplina | Discussão | ||
| 21 | 14/06 | Prova única (início às 15h, 2h de duração). Rever todas as listas em preparação para a prova. | Entregar Lista 4 | ||
| 22 | 23/06 | Apresentação dos projetos da disciplina (início às 15h, 3h de duração). Presença obrigatória.
Iremos votar no melhor trabalho! Ver resultado abaixo. |
As listas devem ser submetidas no Moodle da disciplina, até o final do dia de entrega. Listas entregues com atraso serão penalizadas em 10% ao dia.
Você deve preparar uma apresentação de no máximo 10 minutos sobre seu projeto. A apresentação deve ter três blocos: a descrição do problema sendo estudado (e rápida motivação); a metodologia que você construiu para atacar o problema; os resultados empíricos obtivos em diferentes cenários. Cada bloco deve estar bem explicado, deixando claro os aspectos importantes.
Você também deve entregar um relatório com no máximo 8 páginas, utilizando o modelo de artigos (template) da SBC, de preferência usando Latex (use o Overleaf, que é muito bom).
Seu relatório deve ter uma introdução, onde você apresenta uma motivação e discute o problema que será investigado; uma seção onde você define mais preisamente o problema e a metodologia que você está utilizando, assim como os dados usados nos experimentos; uma breve discussão de trabalhos relacionados; uma apresentação e discussão dos resultados (o que você encontrou).
Resultado da votação dos alunos no melhor trabalho (até dois votos por aluno, total 26 votos). Parabéns ao Thadeu Santos Lima pelo trabalho mais votado (7 votos)!
Livros texto de referência para as notas de aula: