A cadeia de Metropolis do capítulo anterior andava numa grade e propunha o vizinho da esquerda ou da direita com chance ½ cada. Esse equilíbrio era essencial sem chamar atenção: o capítulo avisava que propor de forma desigual, por exemplo sempre propor o ponto de dentro nas pontas da grade, faria a cadeia se acomodar na distribuição errada. Problemas reais precisam de propostas desiguais o tempo todo, e de parâmetros contínuos em vez de grades. Em 1970, W. K. Hastings mostrou que um único fator extra na chance de aceitação conserta qualquer proposta. Com ele, o algoritmo, Metropolis-Hastings, tira amostras de quase qualquer posteriori que você consiga escrever a menos de uma constante.
Ao final você vai conseguir
- Escrever a chance de aceitação de Metropolis-Hastings e dizer o que cada fator faz.
- Provar com o balanço detalhado que ela tem g como alvo para qualquer proposta, e mostrar o que dá errado sem a correção.
- Rodar à mão o Metropolis de passeio aleatório num p contínuo, trabalhando com logaritmos.
- Usar propostas tiradas da priori, e explicar por que aí só a razão de verossimilhanças decide.
- Ler um traço, escolher o aquecimento e o tamanho do passo pela taxa de aceitação, e estimar a partir das amostras.
O alvo é uma posteriori conhecida só a menos de uma constante: g(x) = priori × verossimilhança, sem nenhum fator que não contenha x. A cadeia está em x. Um passo:
- Proponha um valor novo x′ sorteando-o de uma distribuição de proposta q(x′ | x), que pode depender de onde você está.
- Calcule a chance de aceitação α (abaixo).
- Sorteie u uniforme em [0, 1]. Se u < α, vá para x′. Senão fique em x, e registre x de novo: uma proposta rejeitada também conta como passo.
Por que o movimento inverso vai em cima: se x′ é fácil de propor a partir de x mas x é difícil de propor a partir de x′, a cadeia chegaria em x′ com frequência e sairia raramente, acumulando ali por motivos que nada têm a ver com g. O fator q(x | x′)/q(x′ | x) é menor que 1 exatamente nesse caso, e aceita esses movimentos menos vezes, na medida certa.
Numa grade, a chance de ir de i para j ≠ i é P_ij = q(j | i) · α_ij: propor j, depois aceitar. A prova do capítulo anterior funciona com q dentro do min:
A grade dos lances livres com uma proposta desigual
Pegue o exemplo do capítulo anterior: priori Beta(2, 2), 3 acertos em 4, grade {1/4, 1/2, 3/4}, então g ∝ (9, 64, 81). Agora use a proposta que aquele capítulo proibiu: de uma ponta, sempre propor o meio; do meio, propor qualquer ponta com chance ½. A proposta é desigual, q(2 | 1) = 1 mas q(1 | 2) = ½, então o fator de Hastings importa.
| de ↓ para → | 1/4 | 1/2 | 3/4 |
|---|---|---|---|
| 1/4 | 0 | 1 | 0 |
| 1/2 | 9/64 | 23/64 | 1/2 |
| 3/4 | 0 | 32/81 | 49/81 |
Balanço nas arestas: π₁ · 1 = π₂ · 9/64 dá π₂ = (64/9) π₁, e π₂ · ½ = π₃ · 32/81 dá π₃ = 9 π₁. Então π ∝ (9, 64, 81), a posteriori, como prometido. Agora tire a correção e aceite com min(1, gⱼ/gᵢ), como o Metropolis simples faria. As arestas viram P₂₁ = ½ · 9/64 = 9/128 e P₃₂ = 1 · 64/81, e o mesmo balanço dá π ∝ (9, 128, 81): o meio recebe o dobro do peso, porque é proposto com o dobro da vontade com que propõe. A média a posteriori sai 127/218 ≈ 0,583 em vez do correto 95/154 ≈ 0,617.
| cadeia | distribuição estacionária | média de p |
|---|---|---|
| com o fator de Hastings | (9, 64, 81) / 154 | 95/154 ≈ 0.617 |
| sem ele | (9, 128, 81) / 218 | 127/218 ≈ 0,583, errada |
Sem grade, p pode ser qualquer número em [0, 1]. A proposta mais simples é um passo aleatório: p′ = p + s·Z, em que Z é um número normal padrão e s, o tamanho do passo, é um número que você escolhe. A chance de propor p′ a partir de p depende só da distância |p′ − p|, então é a mesma nos dois sentidos: a proposta é simétrica, o fator de Hastings vale 1, e α = min(1, g(p′)/g(p)). Uma proposta fora de [0, 1] tem g(p′) = 0 e é simplesmente rejeitada.
Para a jogadora o alvo é o núcleo da Beta(5, 3), g(p) = p⁴(1 − p)². Cinco passos à mão a partir de p = 0,5, com os passos aleatórios e os números uniformes u já sorteados:
| passo | p | p′ | g(p′) / g(p) | u | resultado |
|---|---|---|---|---|---|
| 1 | 0.50 | 0.62 | 0.02134 / 0.01563 = 1.366 | — | razão ≥ 1: aceita, p = 0,62 |
| 2 | 0.62 | 0.90 | 0.00656 / 0.02134 = 0.308 | 0.52 | u > α: rejeita, p continua 0,62 |
| 3 | 0.62 | 0.55 | 0.01853 / 0.02134 = 0.868 | 0.31 | u < α: aceita, p = 0,55 |
| 4 | 0.55 | 1.06 | 0 (fora de [0, 1]) | — | rejeita, p continua 0,55 |
| 5 | 0.55 | 0.71 | 0.02137 / 0.01853 = 1.153 | — | aceita, p = 0,71 |
A cadeia registrada é 0,50; 0,62; 0,62; 0,55; 0,55; 0,71. Os valores repetidos não são um erro: ficar parada é como a cadeia passa mais tempo nas regiões plausíveis. Se os passos rejeitados ficassem de fora do registro, as amostras seguiriam a distribuição errada.
Trabalhe com logaritmos
Com dados reais o próprio núcleo é inutilizável. Para 7500 acertos em 10 000 lances, g(0,75) contém 0,75⁷⁵⁰⁰ = e^(7500 · ln 0,75) ≈ e^(−2158), muito abaixo do menor número que um computador consegue guardar (cerca de 10⁻³⁰⁸), então os dois valores de g saem 0 e a razão sai 0/0. Compare logaritmos em vez disso: ln g(p) = (a′ − 1) ln p + (b′ − 1) ln(1 − p), e aceite quando ln u < ln g(p′) − ln g(p) (mais ln q(p | p′) − ln q(p′ | p) para uma proposta desigual). As diferenças são números comuns.
Uma proposta não precisa ser um passo pequeno. Uma ideia é ignorar onde você está e sortear p′ da priori: q(p′ | p) = f(p′). Isso é bem desigual (a chance de propor p′ nem depende de p), então o fator de Hastings é essencial. Ele se simplifica de um jeito bonito:
Esqueça a correção e aceite com min(1, g(p′)/g(p)), e a cadeia passa a ter como alvo g · f em vez de g, a priori multiplicada duas vezes: o balanço detalhado vale, mas para a distribuição errada. Com uma priori leve o erro é pequeno; com uma forte ele salta aos olhos. A figura abaixo deixa você desligar a correção. Um cuidado prático: sortear da priori só funciona bem quando a priori não é muito mais larga que a posteriori. Com muitos dados a posteriori é estreita, quase todo sorteio da priori cai onde a verossimilhança é minúscula, e quase tudo é rejeitado.
A teoria promete a distribuição certa a longo prazo; a prática decide quanto tempo é isso. Três coisas para observar, todas visíveis na figura:
| o quê | problema | o que fazer |
|---|---|---|
| aquecimento (burn-in) | os primeiros passos ainda lembram o ponto de partida; começando em p₀ = 0,05, o traço leva um tempo para subir até onde a posteriori está | descarte a primeira parte da corrida, até o traço parar de derivar |
| passo pequeno demais | quase toda proposta é aceita, mas cada uma anda só um pouco; o traço vagueia devagar e valores sucessivos são quase iguais | aumente s |
| passo grande demais | a maioria das propostas cai fora de [0, 1] ou muito morro abaixo e é rejeitada; o traço mostra longos trechos planos | diminua s |
| taxa de aceitação | a fração de propostas aceitas resume os dois problemas | para um parâmetro mire em algo entre 20 % e 50 % (cerca de 44 % é o melhor clássico para um alvo em forma de sino); com muitos parâmetros, menos, por volta de 25 % |
Valores sucessivos de uma cadeia são correlacionados, então 10 000 passos carregam menos informação que 10 000 sorteios independentes, às vezes só tanto quanto algumas centenas. Um traço bem ajustado parece um ruído denso e uniforme em volta de um nível fixo, sem derivas lentas nem trechos planos. Uma conferência útil: rode a cadeia de novo a partir de um ponto de partida bem diferente; depois do aquecimento as duas corridas devem concordar.
Aperte play. Em cima: o valor de p em cada passo, começando em p₀; os primeiros passos ainda lembram o início e são descartados (a faixa vermelha, o aquecimento). Embaixo: o histograma dos passos guardados contra a posteriori exata (verde). No passeio aleatório, experimente um passo minúsculo (s = 0,01: quase tudo é aceito, mas a cadeia se arrasta) e um enorme (s = 1: a maioria das propostas cai fora de [0, 1] ou muito morro abaixo e é rejeitada); algo entre 20 % e 50 % de aceitação mistura melhor. Depois troque para sortear as propostas da priori e desligue a correção de Hastings: o histograma escorrega para a curva vermelha, porque sem o fator q(p)/q(p′) a priori é contada duas vezes. A priori forte Beta(8, 8) deixa o erro fácil de ver.
Estimando a partir das amostras
Depois do aquecimento, os valores guardados se comportam como sorteios (correlacionados) da posteriori, então qualquer pergunta sobre p vira contar ou tirar médias. A média a posteriori é a média dos valores guardados. P(p > ½) é a fração dos valores guardados acima de ½. Um intervalo de credibilidade de 95 % vai do valor com 2,5 % das amostras abaixo dele até o valor com 97,5 % abaixo. Para a jogadora, as respostas exatas pela posteriori Beta(5, 3) são 0,625 e 99/128 ≈ 0,773, e uma corrida longa da cadeia chega tão perto delas quanto se queira.
| passo | o que fazer |
|---|---|
| 1 | Escreva o núcleo alvo g = priori × verossimilhança, sem constantes (em logs, num programa). |
| 2 | Escreva a proposta q(x′ | x). Ela é simétrica? Então o fator de Hastings vale 1. |
| 3 | α = min(1, g(x′) q(x | x′) / (g(x) q(x′ | x))): a proposta inversa em cima. |
| 4 | Grade: P_ij = q(j | i) α_ij para j ≠ i, e P_ii = 1 menos o resto da linha. |
| 5 | Simulação: aceite se u < α; senão registre o valor atual de novo. |
| 6 | Descarte o aquecimento, confira o traço e a taxa de aceitação, depois tire médias, conte ou pegue quantis. |
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Cada exercício é criado na hora, então uma rodada nova nunca é igual. O computador escolhe a resposta primeiro e monta a pergunta em volta dela, trabalhando com frações exatas, por isso o gabarito está sempre certo. As respostas são lidas de forma exata: 0,75, 3/4 e 6/8 contam como o mesmo número (quando a forma irredutível é pedida, 6/8 só recebe um lembrete). Uma resposta errada mostra a resolução linha por linha, na ordem em que a lição faz; o número novo de cada linha aparece colorido.
| Errado | Certo | Por quê |
|---|---|---|
| min(1, g′/g) com uma proposta desigual | multiplique por q(x | x′)/q(x′ | x) | sem isso a cadeia tem o alvo errado, (9, 128, 81) em vez de (9, 64, 81) |
| q(x′ | x)/q(x | x′) | q(x | x′)/q(x′ | x) | o movimento inverso vai em cima |
| pular os passos rejeitados no registro | registre o valor atual de novo | as repetições é que dão peso aos valores plausíveis |
| empurrar uma proposta fora de [0, 1] de volta para a borda | rejeite-a (g = 0 ali) | movê-la muda q, e as bordas seriam propostas demais |
| aceitação perto de 100 % quer dizer que a cadeia funciona bem | quer dizer que os passos são pequenos demais | a cadeia se arrasta; mire em 20–50 % com um parâmetro |
| usar todos os passos, desde o primeiro | descarte o aquecimento | o começo pode estar longe da posteriori |
| calcular g(p) diretamente com muitos dados | compare ln g | as potências viram 0 por falta de precisão, e 0/0 não significa nada |
Ideias-chave
- Metropolis-Hastings: proponha x′ de q(x′ | x), aceite com α = min(1, g(x′) q(x | x′) / (g(x) q(x′ | x))), senão fique.
- A proposta inversa vai em cima; para uma proposta simétrica o fator vale 1 e é o Metropolis simples.
- g_i q(j | i) α_ij = min(g_i q(j | i), g_j q(i | j)) é simétrico: balanço detalhado, então o alvo é estacionário para qualquer proposta.
- Sem o fator uma proposta desigual enviesa a cadeia: na grade dos lances livres, (9, 128, 81) em vez de (9, 64, 81).
- Passeio aleatório p′ = p + s·Z: simétrico; rejeite propostas fora de [0, 1]; compare logaritmos.
- Propostas tiradas da priori deixam só a razão de verossimilhanças, min(1, L(p′)/L(p)).
- Descarte o aquecimento, ajuste s para cerca de 20–50 % de aceitação, lembre que as amostras são correlacionadas.
- Estime tirando médias, contando e pegando quantis dos valores guardados.