|
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
Todos devem se inscrever no Moodle da discilina. Iremos utilizar esta plataforma para troca de mensagens e avisos, e entrega de tarefas (listas). O código de acesso para inscrição na disciplina no Moodle é mcmc2019.
| Aula | Data | Comentário | Slides | Tarefa |
| 1 | 12/03 | Logística, programação e regras do jogo. Três problemas, Monte Carlo to the rescue, História das origens, Monte Carlo na Computação | aula_0.pdf aula_1.pdf |
Saiu lista 1 |
| 2 | 14/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 | aula_2.pdf | Fazer lista 1 |
| 3 | 19/03 | Revisão de probabilidade: Bernoulli, sequência iid, binomial, geometrica, zeta, valor esperado, variância, função de v.a., distribuição conjunta, independência de v.a. | aula_3.pdf | Fazer lista 1 |
| 4 | 21/03 | Valor esperado conditional, espaço amostral contínuo, função densidade, limitantes para cauda e cabeça, desigualdade de Markov, desigualdade de Chebyshev, desigualdade de Chernoff, with high probability, exemplos | aula_4.pdf | Fazer lista 1 |
| 5 | 26/03 | Limitante da união, método do primeiro momento, Lei dos grandes números (fraca e forte), erro e confiança | aula_5.pdf | Entregar lista 1 |
| 6 | 28/03 | Método de Monte Carlo, estimando somatórios, calculando erro, estimando pi | aula_6.pdf | Saiu lista 2 |
| 7 | 2/04 | Calculando o erro de pi, integração de Monte Carlo, Monte Carlo Ray Tracing | aula_6.pdf | Fazer lista 2 |
| 8 | 4/04 | Gerando amostras de v.a. discretas, gerando Geométrica, método da transformada inversa, gerando Binomial, gerando permutações | aula_7.pdf | Entregar 2, saiu lista 3 |
| - | 9/04 | Aula cancelada por conta da chuva! COPPE/UFRJ suspendeu suas atividades | Fazer lista 3 | |
| 9 | 11/04 | Método da rejeição (rejection sampling), exemplos, importance sampling, generalização | aula_8.pdf | Fazer lista 3 |
| 10 | 16/04 | Self-normalized importance sampling, gerando amostras complicadas, variância amostral, simulação | aula_9.pdf | Fazer lista 3 |
| - | 18/04 | Não teremos aula. Trabalhar na lista 3. | Fazer lista 3 | |
| - | 23/4 | Não teremos aula, feriado Estadual: Dia de São Jorge | Fazer lista 3 | |
| 11 | 25/04 | Cadeias de Markov, definição e exemplos, modelo On-Off, sem memória, distribuição no tempo, irredutibilidade, aperiodicidade | aula_11.pdf | Fazer lista 3 |
| 12 | 30/04 | Distribuição estacionária, tempo de chegada, distância de variação total, convergência, calculando distribuição estacionária, reversibilidade, passeios aleatórios, modelo de nascimento e morte | aula_12.pdf | Entregar lista 3 |
| 13 | 2/05 | Discussão sobre projetos para disciplina. Tragam suas ideias para projetos e dúvidas! | Definir projeto | |
| 14 | 7/05 | Autovalores, autovetores, e decomposição, convergência para estacionaridade, tempo de mistura, spectral gap, tempo de mistura de passeios aleatórios | aula_14.pdf | Definir projeto |
| 15 | 9/5 | Caminho amostral, teorema Ergódico, estimando pi, simulação de CM, gerando amostras, Markov Chain Monte Carlo (caso simétrico), exemplo | aula_15.pdf | Saiu lista 4 |
| 16 | 14/05 | Revisando MCMC, Metropolis-Hasting, amostrando vértices em redes | aula_16.pdf | Fazer lista 4, projeto |
| - | 16/05 | Não teremos aula. Trabalhar na lista 4 e no projeto da disciplina | Fazer lista 4, projeto | |
| 17 | 21/05 | Modelo Hardcore, Gibbs Sampling (ou Glauber Dynamics), gerando q-colorações | aula_16.pdf | Terminar lista 4, projeto |
| 18 | 23/05 | Otimização, caixeiro viajante, Hill Climbing, distribuição de Boltzman, simulated Annealing, de volta ao caixeiro | aula_18.pdf | Saiu lista 5 |
| 19 | 28/05 | Problemas iniciais, Monte Carlo na moda, caminho trilhado, desafios, encerramento, avaliação | aula_19.pdf | |
| - | 30/05 | Não teremos aula. Trabalhar na lista e projeto! | ||
| 20 | 4/06 | Prova única (início às 15h, 2h de duração). Rever todas as listas em preparação para a prova | ||
| - | 6/06 | Não teremos aula. Trabalhar no projeto! | Fazer projeto | |
| - | 11/06 | Não teremos aula. Trabalhar no projeto! | Fazer projeto | |
| 21 | 13/06 | Entrega de relatório e apresentação do trabalho. Presença obrigatória.
Ver resultado da votação abaixo. |
As listas devem ser submetidas no Moodle da disciplina, até o final do dia de entrega.
Você deve entregar um relatório descrevendo seu projeto com no máximo 8 páginas, utilizando o modelo de artigos (template) da SBC em Latex (preferencialmente).
Seu relatório deve ter uma seção de introdução e motivação, uma seção descrevendo o problema sendo atacado, uma seção descrevendo como Monte Carlo está sendo usado na sua solução, uma seção com avaliação numérica e discussão dos resultados, e uma seção com trabalhos relacionados e bibliografia.
Você pode usar o Overleaf que é um ambiente online e colaborativo para produzir documentos em Latex (gratuitos, de forma limitada).
Além do relatório, você deve preparar uma apresentação de 12 minutos (no máximo) sobre seu projeto. A apresentação deve ter slides (em Latex, Powerpoint, LibreOffice, ou outro) mas o formato é livre, então utilize sua criatividade para expor em forma oral o seu trabalho.
A turma irá votar no melhor trabalho (júri popular).
Resultado da votação dos alunos no melhor trabalho. Parabéns a Jessica Nascimento pelo trabalho mais votado!
As notas de aulas serão tiradas principalmente dos seguintes livros: