|
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).
| Aula | Data | Comentário | Slides | Vídeos | Tarefa |
| 1 | 11/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 | 13/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 | 18/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 | Fazer lista 1 |
| 4 | 20/03 | 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 | 25/03 | Lei dos grandes números (fraca e forte), erro e confiança, margem de erro, falácia do apostador | aula_5.pdf | Aula 5 | Entregar lista 1 |
| 6 | 27/03 | 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 | Saiu lista 2 |
| 7 | 1/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 | Fazer lista 2 |
| 8 | 3/04 | Método da rejeição (rejection sampling), exemplos, Importance Sampling, exemplos, generalização | aula_8.pdf | Aula 8 | Fazer lista 2 |
| 9 | 8/04 | Algoritmos randomizados, exemplos, algoritmos de monte carlo, algoritmos de las vegas, comparação | aula_6_1.pdf | Aula 6_1 | Fazer lista 2 |
| 10 | 10/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 | Entregar lista 2 |
| 11 | 15/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 | |
| - | 17/04 | Não teremos aula. Feriado enforcado: Sexta-feira Santa | Saiu lista 3 | ||
| - | 22/04 | Não teremos aula. Feriado enforcado: Dia de Tiradentes e Dia de São Jorge | Fazer lista 3 | ||
| 12 | 24/04 | 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 | Fazer lista 3 |
| 13 | 29/04 | Caminho amostral, teorema Ergódico, estimando pi, simulação de CM (eficiente), gerando amostras, simulando cadeias enormes | aula_12.pdf | Aula 12 | Fazer lista 3 |
| - | 1/05 | Não teremos aula. Feriado Nacional: Dia do Trabalho | |||
| 14 | 6/05 | Processo de Decisão de Markov (MDP), estimando valor de política, estimando valor de política com importance sampling | |||
| 15 | 8/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 | Fazer lista 3 |
| 16 | 13/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 | Projeto para disciplina |
| 17 | 15/05 | Otimização, caixeiro viajante, Hill Climbing, distribuição de Boltzman, simulated Annealing, de volta ao caixeiro | aula_15.pdf | Aula 15 | Projeto para disciplina, saiu Lista 4 |
| 18 | 20/05 | Entrega e apresentação da proposta de projeto para a disciplina (início às 15h) | Entregar proposta | ||
| - | 22/05 | Não teremos aula | Fazer projeto | ||
| 19 | 27/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 | Fazer projeto |
| 20 | 29/06 | Dúvidas e discussão sobre projeto, listas, e conteúdo da disciplina | Fazer lista 4 | ||
| 21 | 3/06 | Prova única ((início às 15h, 2h de duração). Rever todas as listas em preparação para a prova. | Entregar Lista 4. | ||
| - | 5/06 | Não teremos aula. | Fazer projeto | ||
| - | 10/06 | Não teremos aula. | Fazer projeto | ||
| 22 | 12/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. |
Apresentar projeto |
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 artigo (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:
Livros texto de referência para as notas de aula: