|
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 | 03/05 | 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 | 05/05 | 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 | 10/05 | 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 | Fazer lista 1 |
| 4 | 12/05 | Limitantes para probabilidade, desigualdades de Markov, Chebyshev, Chernoff, with high probability (whp), limitante da União | aula_4.pdf | Aula 4 | Fazer lista 1 |
| 5 | 17/05 | Lei dos grandes números (fraca e forte), erro e confiança, margem de erro, falácia do apostador | aula_5.pdf | Aula 5 | Fazer lista 1 |
| 6 | 19/05 | 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 | 24/05 | 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 | Saiu lista 2 |
| 8 | 26/05 | Método da rejeição (rejection sampling), exemplos, Importance Sampling, exemplos, generalização | aula_8.pdf | Aula 8 Discussão | Fazer lista 2 |
| 9 | 31/05 | 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 |
| 10 | 02/06 | 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 | Fazer lista 2 |
| 11 | 07/06 | 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 |
| 12 | 09/06 | 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 |
| 13 | 14/06 | 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 |
| 14 | 16/06 | 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 |
| 15 | 21/06 | 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 |
| 16 | 23/06 | Aula de dicas para sua proposta de projeto para a disciplina | Discussão | Entregar Lista 3 | |
| 17 | 28/06 | Entrega e apresentação da proposta de projeto para a disciplina (início às 15h) | Discussão | Entregar proposta | |
| 18 | 30/06 | Os três problemas, Monte Carlo to the rescue, caminho trilhado, Monte Carlo como building block, desafios | aula_16.pdf | Aula 16 Discussão | Saiu Lista 4 |
| 19 | 05/07 | Dúvidas e discussão sobre projeto ou conteúdo da disciplina, avaliação da disciplina | Discussão | Fazer lista 4 | |
| 20 | 14/07 | Prova única (início às 15h, 2h de duração). Rever todas as listas em preparação para a prova. | |||
| 21 | 21/07 | Dúvidas e discussão sobre projeto ou conteúdo da disciplina | Discussão | ||
| 22 | 26/07 | Apresentação dos projetos da disciplina (início às 15h, 4h de duração). Presença obrigatória.
Iremos votar no melhor trabalho! Ver resultado abaixo. |
Discussão | ||
| 23 | 28/07 | Discussão das questões da prova (opcional), às 16h | Discussão |
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 31 votos). Parabéns ao Cleiton Almeida pelo trabalho mais votado!
Livros texto de referência para as notas de aula: