Tópicos Especiais em Algoritmos
de Monte Carlo e Cadeias de Markov

PESC/COPPE/UFRJ
CPS767 - 2018/1



The Epic 20,000 Roll Dice Randomness Test
Professor
Localização / Horário
Resumo/Motivação

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!

Ementa (preliminar)

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

Lista de email
Programação das aulas

Aula Data Comentário Slides Tarefa
1 6/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 8/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 13/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 15/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 15/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, saiu lista 2
- 22/03 Não teremos aula. Trabalhar na Lista 2 Fazer lista 2
6 27/03 Método de Monte Carlo, estimando somatórios, calculando erro, estimando pi, o erro de pi, integração de Monte Carlo, Monte Carlo Ray Tracing aula_6.pdf Fazer lista 2
7 29/03 Gerando amostras de v.a. discretas, gerando Geométrica, método da transformada inversa, gerando Binomial, gerando permutações aula_7.pdf Entregar lista 2
8 3/04 Método da rejeição (rejection sampling), exemplos, importance sampling, generalização aula_8.pdf Saiu Lista 3
- 5/04 Não teremos aula. Trabalhar na Lista 3 Fazer lista 3
9 10/04 Self-normalized importance sampling, gerando amostras complicadas, variância amostral, simulação aula_9.pdf Fazer lista 3
10 12/04 Tudo aquilo que você quis perguntar mas ainda não perguntou. Aula de dúvidas sobre as listas e a matéria. Fazer lista 3
11 17/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 19/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 aula_12.pdf Entregar lista 3
- 24/04 Não teremos aula. Professor participando da Reunião do Comitê de Programa da ACM Sigmetrics 2018, realizada na Columbia University, EUA Pensar em projeto
- 26/04 Não teremos aula. Professor participando da Reunião do Comitê de Programa da ACM Sigmetrics 2018, realizada na Columbia University, EUA Pensar em projeto
- 1/5 Não teremos aula. Feriado nacional: Dia do Trabalhor Pensar em projeto
13 3/05 Autovalores, autovetores, e decomposição, convergência para estacionaridade, tempo de mistura, spectral gap, tempo de mistura de passeios aleatórios aula_13.pdf Saiu lista 4
14 8/05 Caminho amostral, teorema Ergódico, rstimando pi, simulação de CM, gerando amostras, Markov Chain Monte Carlo (caso simétrico), exemplo aula_14.pdf Fazer lista 4, começar projeto
- 9/5 Prof. Jeannette Wing (Data Science Institute, Columbia University), Palestra: Using Data for Good, 10:30, Auditório da COPPE no CT2 (imperdível)
15 10/05 Metropolis-Hasting, amostrando vértices, modelo Hardcore, Gibbs Sampling (ou Glauber Dynamics), gerando q-colorações aula_15.pdf Lista 4
16 15/05 Otimização, caixeiro viajante, Hill Climbing, distribuição de Boltzman, simulated Annealing ,de volta ao caixeiro aula_16.pdf Lista 4
17 17/05 Problemas iniciais, Monte Carlo na moda, caminho trilhado, desafios, encerramento, avaliação aula_17.pdf Saiu lista 5
18 22/05 Prova única (início às 15h, 2h de duração). Rever todas as listas em preparação para a prova Entregar Lista 4 e 5 (opcional)
- 24/05 Não teremos aula. Finalizar trabalho
- 29/05 Aula suspensa pela Reitoria por conta das trapalhadas nacionais.
Aproveitar para finalizar o trabalho.
- 31/05 Não teremos aula. Feriado Nacional: Dia de Corpus Christi
19 5/06 Entrega de relatório e apresentação do trabalho. Presença obrigatória.
Ver resultado da votação abaixo.

Listas de exercícios

As listas devem ser entregue em papel no início da aula na data de entrega. Não serão aceitas listas enviadas por email.


Projeto

Prova


Leitura


Referências

As notas de aulas serão tiradas principalmente dos seguintes livros: