Algoritmo de Metropolis–Hastings

A distribuição da proposta Q propõe o próximo ponto para o qual a caminhada aleatória pode (ou não) se mover dependendo de um parâmetro probabilístico.

Em estatística e física estatística, o algoritmo Metropolis-Hastings é um método de Cadeia de Markov Monte Carlo (MCMC) para obter amostras aleatórias a partir de uma distribuição de probabilidade da qual a amostragem direta é difícil. Essa sequência pode ser usada para aproximar a distribuição (por exemplo, para gerar um histograma) ou para calcular uma integral (por exemplo, um valor esperado). Metropolis – Hastings e outros algoritmos MCMC são geralmente usados para amostragem de distribuições multidimensionais, especialmente quando o número de dimensões é alto. Para distribuições unidimensionais, existem outros métodos (por exemplo, amostragem por rejeição adaptativa) que podem retornar amostras independentes, fugindo do problema de amostras autocorrelacionadas inerente aos métodos MCMC.

História

O algoritmo recebeu o nome de Nicholas Metropolis, autor do artigo de 1953 sobre Equação de Cálculos Estatais por Máquinas de Computação Rápida, juntamente com Arianna W. Rosenbluth, Marshall Rosenbluth, Marshall Rosenbluth, Augusta H. Teller e Edward Teller. Este artigo propôs o algoritmo para o caso de distribuições simétricas de propostas, e WK Hastings o estendeu ao caso mais geral em 1970.

Existe alguma controvérsia no que diz respeito ao crédito pelo desenvolvimento do algoritmo. Metropolis cunhou o termo "Monte Carlo" em um artigo anterior com Stanislav Ulam, estava familiarizado com os aspectos computacionais do método e liderou o grupo na Divisão Teórica que projetou e construiu o computador MANIAC I usado nos experimentos em 1952. No entanto, antes de 2003, não havia uma descrição detalhada do desenvolvimento do algoritmo. Então, pouco antes de sua morte, Marshall Rosenbluth participou de uma conferência de 2003 na LANL, comemorando o 50º aniversário da publicação de 1953. Nesta conferência, Rosenbluth descreveu o algoritmo e seu desenvolvimento em uma apresentação intitulada "Gênese do algoritmo de Monte Carlo para mecânica estatística". Esclarecimentos históricos adicionais são feitos por Gubernatis em um artigo de jornal de 2005 recontando a conferência do 50º aniversário. Rosenbluth deixa claro que ele e sua esposa Arianna fizeram o trabalho e que Metropolis não teve nenhum papel no desenvolvimento além de fornecer tempo ao computador.

Intuição

O algoritmo Metropolis–Hastings pode coletar amostras de qualquer distribuição de probabilidade ${\displaystyle P(x)}$, desde que conheçamos uma função ${\displaystyle f(x)}$ proporcional à densidade de ${\displaystyle P}$ e os valores de ${\displaystyle f(x)}$ possam ser calculados. A exigência de que ${\displaystyle f(x)}$ deve ser apenas proporcional à densidade, e não exatamente igual a ela, torna o algoritmo Metropolis-Hastings particularmente útil, porque calcular na prática o fator de normalização necessário costuma ser extremamente difícil.

O algoritmo Metropolis-Hastings funciona gerando uma sequência de valores de tal maneira que, à medida que mais e mais valores de amostra são produzidos, a distribuição de valores se aproxima mais da distribuição desejada ${\displaystyle P(x)}$. Esses valores de amostra são produzidos iterativamente, com a distribuição da próxima amostra dependendo apenas do valor atual da amostra (transformando a sequência de amostras em uma cadeia de Markov). Especificamente, a cada iteração, o algoritmo escolhe um candidato para o próximo valor de amostra com base no valor atual da amostra. Então, com alguma probabilidade, o candidato é aceito ou rejeitado. Caso seja rejeitado, o valor do candidato é descartado e o valor atual é reutilizado na próxima iteração. A probabilidade de aceitação é determinado comparando os valores da função ${\displaystyle f(x)}$ dos valores de amostra atuais e candidatos em relação à distribuição desejada ${\displaystyle P(x)}$.

Para fins de ilustração, o algoritmo Metropolis, um caso especial do algoritmo Metropolis-Hastings, em que a função da proposta é simétrica, é descrito abaixo.

Algoritmo de Metropolis (distribuição simétrica de propostas)

Deixe ${\displaystyle f(x)}$ ser uma função proporcional à distribuição de probabilidade desejada ${\displaystyle P(x)}$ (também conhecida como distribuição de destino).

1. Inicialização: escolha um ponto arbitrário ${\displaystyle x_{t}}$ para ser a primeira amostra e escolher uma densidade de probabilidade arbitrária ${\displaystyle g(x\mid y)}$ (às vezes escrito ${\displaystyle Q(x\mid y)}$) que sugere um candidato para o próximo valor da amostra ${\displaystyle x}$, dado o valor da amostra anterior ${\displaystyle y}$. Nesta secção, ${\displaystyle g}$ é assumido como simétrico; em outras palavras, ele deve satisfazer ${\displaystyle g(x\mid y)=g(y\mid x)}$. Uma escolha usual é deixar ${\displaystyle g(x\mid y)}$ ser uma distribuição gaussiana centrada em ${\displaystyle y}$, para que aponte para mais perto ${\displaystyle y}$ são mais propensos a serem visitados a seguir, transformando a sequência de amostras em uma caminhada aleatória . A função ${\displaystyle g}$ é chamado de densidade da proposta ou distribuição de salto .
2. Para cada iteração t :
   • Gere um candidato ${\displaystyle x'}$ para a próxima amostra, escolhendo na distribuição ${\displaystyle g(x'\mid x_{t})}$ .
   • Calcule a taxa de aceitação ${\displaystyle \alpha =f(x')/f(x_{t})}$, que será usado para decidir se aceita ou rejeita o candidato. Como f é proporcional à densidade de P, temos que ${\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}$ .
   • Aceite ou rejeite :
     • Gere um número aleatório uniforme ${\displaystyle u\in [0,1]}$ .
     • E se ${\displaystyle u\leq \alpha }$, aceite o candidato definindo ${\displaystyle x_{t+1}=x'}$ ,
     • E se ${\displaystyle u>\alpha }$, rejeite o candidato e defina ${\displaystyle x_{t+1}=x_{t}}$ em vez de.

Esse algoritmo prossegue ao tentar mover-se aleatoriamente no espaço da amostra, às vezes aceitando as movimentações e às vezes permanecendo no local. Observe que a taxa de aceitação ${\displaystyle \alpha }$ indica a probabilidade da nova amostra proposta em relação à amostra atual, de acordo com a distribuição ${\displaystyle P(x)}$ . Se tentarmos avançar para um ponto mais provável que o ponto existente (isto é, um ponto em uma região de maior densidade de ${\displaystyle P(x)}$), sempre aceitaremos a mudança. No entanto, se tentarmos avançar para um ponto menos provável, às vezes rejeitaremos a mudança e, quanto mais a queda relativa na probabilidade, maior a probabilidade de rejeitarmos o novo ponto. Assim, tenderemos a permanecer (e retornar um grande número de amostras de) regiões de alta densidade de ${\displaystyle P(x)}$, enquanto visitam apenas ocasionalmente regiões de baixa densidade. Intuitivamente, é por isso que esse algoritmo funciona e retorna amostras que seguem a distribuição desejada ${\displaystyle P(x)}$.

Comparado com um algoritmo como a amostragem por rejeição adaptativa^[1] que gera diretamente amostras independentes de uma distribuição, o Metropolis – Hastings e outros algoritmos do MCMC têm algumas desvantagens:

• As amostras estão correlacionadas. Embora, a longo prazo, sigam corretamente ${\displaystyle P(x)}$, um conjunto de amostras próximas será correlacionado entre si e não refletirá corretamente a distribuição. Isso significa que, se queremos um conjunto de amostras independentes, temos que jogar fora a maioria das amostras e coletar apenas a n- amostra, por algum valor de n (geralmente determinado examinando a autocorrelação entre amostras adjacentes). A autocorrelação pode ser reduzida aumentando a largura do salto (o tamanho médio de um salto, que está relacionado à variância da distribuição do salto), mas isso também aumentará a probabilidade de rejeição do salto proposto. Um tamanho de salto muito grande ou muito pequeno levará a uma cadeia de Markov de mistura lenta, ou seja, um conjunto de amostras altamente correlacionado, de modo que um número muito grande de amostras será necessário para obter uma estimativa razoável de qualquer propriedade desejada da distribuição.
• Embora a cadeia de Markov eventualmente converja para a distribuição desejada, as amostras iniciais podem seguir uma distribuição muito diferente, especialmente se o ponto de partida estiver em uma região de baixa densidade. Como resultado, normalmente é necessário um período de queima,^[2] onde um número inicial de amostras (por exemplo, as primeiras 1000) são jogadas fora.

Por outro lado, os métodos mais simples de amostragem de rejeição sofrem com a " maldição da dimensionalidade ", onde a probabilidade de rejeição aumenta exponencialmente em função do número de dimensões. Metropolis – Hastings, juntamente com outros métodos MCMC, não têm esse problema a esse grau e, portanto, são frequentemente as únicas soluções disponíveis quando o número de dimensões da distribuição a ser amostrada é alto. Como resultado, os métodos MCMC são frequentemente escolhidos para produzir amostras a partir de modelos hierárquicos bayesianos e demais modelos estatísticos de alta dimensionalidade.

Nas distribuições multivariadas, o algoritmo clássico Metropolis-Hastings, conforme descrito acima, envolve a escolha de um novo ponto de amostra multidimensional. Quando o número de dimensões é alto, é difícil encontrar a distribuição de salto adequada a ser usada, pois as diferentes dimensões individuais se comportam de maneiras muito diferentes, e a largura do salto (veja acima) deve ser "perfeita" para todas as dimensões de uma só vez para evitar misturas excessivamente lentas. Uma abordagem alternativa que geralmente funciona melhor nessas situações, conhecida como amostragem de Gibbs, envolve a escolha de uma nova amostra para cada dimensão separadamente das outras, em vez de escolher uma amostra para todas as dimensões de uma só vez. Isso é especialmente aplicável quando a distribuição multivariada é composta por um conjunto de variáveis aleatórias individuais , nas quais cada variável é condicionada apenas a um pequeno número de outras variáveis, como é o caso dos modelos hierárquicos mais comuns. As variáveis individuais são então amostradas uma de cada vez, com cada variável condicionada aos valores mais recentes de todas as outras. Vários algoritmos podem ser usados para escolher essas amostras individuais, dependendo da forma exata da distribuição multivariada: algumas possibilidades são os métodos de amostragem por rejeição adaptativa,^[1][3][4][5] o algoritmo de amostragem por metrópole de rejeição adaptativa^[6] ou suas melhorias^[7][8] (consulte o código do matlab), uma etapa unidimensional simples de Metropolis – Hastings ou amostragem de fatias.

Derivação formal

O objetivo do algoritmo Metropolis – Hastings é gerar uma coleção de estados conforme uma distribuição desejada ${\displaystyle P(x)}$ . Para conseguir isso, o algoritmo usa um processo de Markov, que atinge assintoticamente uma distribuição estacionária exclusiva ${\displaystyle \pi (x)}$ de tal modo que ${\displaystyle \pi (x)=P(x)}$ .

Um processo de Markov é definido exclusivamente por suas probabilidades de transição ${\displaystyle P(x'\mid x)}$, a probabilidade de fazer a transição de qualquer estado ${\displaystyle x}$ para qualquer outro estado ${\displaystyle x'}$ . O processo possui uma distribuição estacionária única ${\displaystyle \pi (x)}$ quando as duas condições a seguir são atendidas:

1. Existência de distribuição estacionária : deve existir uma distribuição estacionária ${\displaystyle \pi (x)}$. Uma condição suficiente (mas não necessária) é o equilíbrio detalhado, que exige que cada transição ${\displaystyle x\to x'}$ seja reversível: para cada par de estados ${\displaystyle x,x'}$, a probabilidade de estar no estado ${\displaystyle x}$ e transitar para o estado ${\displaystyle x'}$ deve ser igual à probabilidade de estar no estado ${\displaystyle x'}$ e transitar para o estado ${\displaystyle x}$, ${\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}$ .
2. Exclusividade da distribuição estacionária : a distribuição estacionária ${\displaystyle \pi (x)}$ deve ser única. Isso é garantido pela ergodicidade do processo de Markov, que exige que todo estado (1) seja aperiódico (o sistema não retorna ao mesmo estado em intervalos fixos); e (2) seja positivo recorrente (o número esperado de etapas para retornar ao mesmo estado é finito).

O algoritmo Metropolis-Hastings envolve o desenho de uma cadeia de Markov (construindo probabilidades de transição) que atenda às duas condições acima, de modo que sua distribuição estacionária ${\displaystyle \pi (x)}$ seja ${\displaystyle P(x)}$ . A derivação do algoritmo começa com a condição de equilíbrio detalhado :

${\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}$

que é reescrita como

${\displaystyle {\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.}$

A abordagem é separar a transição em duas sub-etapas; a proposta e a aceitação-rejeição. A distribuição da proposta ${\displaystyle g(x'\mid x)}$ é a probabilidade condicional de caminhar para um estado ${\displaystyle x'}$ dado ${\displaystyle x}$ e a distribuição de aceitação ${\displaystyle A(x',x)}$ é a probabilidade de aceitar o estado proposto ${\displaystyle x'}$ e, de fato, permanecer neste. A probabilidade de transição pode ser escrita como o produto deles:

${\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x).}$

Inserindo essa relação na equação anterior, temos

${\displaystyle {\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.}$

O próximo passo na derivação é escolher uma taxa de aceitação que atenda à condição acima. Uma escolha comum é a escolha de Metropolis:

${\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).}$

Para essa taxa de aceitação do Metropolis ${\displaystyle A}$, ou ${\displaystyle A(x',x)=1}$ ou ${\displaystyle A(x,x')=1}$ e, de qualquer forma, a condição é satisfeita.

O algoritmo Metropolis – Hastings consiste, portanto, no seguinte:

1. Inicialize
   1. Escolha um estado inicial ${\displaystyle x_{0}}$ .
   2. Coloque ${\displaystyle t=0}$ .
2. Itere
   1. Gere um estado candidato aleatório ${\displaystyle x'}$ de acordo com ${\displaystyle g(x'\mid x_{t})}$ .
   2. Calcule a probabilidade de aceitação ${\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}$ .
   3. Aceite ou rejeite :
      1. gere um número aleatório uniforme ${\displaystyle u\in [0,1]}$ ;
      2. E se ${\displaystyle u\leq A(x',x_{t})}$, aceite o novo estado e defina ${\displaystyle x_{t+1}=x'}$ ;
      3. E se ${\displaystyle u>A(x',x_{t})}$, rejeite o novo estado e copie o estado antigo para a frente ${\displaystyle x_{t+1}=x_{t}}$ .
   4. Incremente : coloque ${\displaystyle t=t+1}$ .

Desde que as condições especificadas sejam atendidas, a distribuição empírica dos estados salvos ${\displaystyle x_{0},\ldots ,x_{T}}$ vai se aproximar de ${\displaystyle P(x)}$ . O número de iterações (${\displaystyle T}$) necessário para estimar efetivamente ${\displaystyle P(x)}$ depende de vários fatores, como a relação entre ${\displaystyle P(x)}$ e a distribuição da proposta e a precisão desejada.^[9] Para distribuição em espaços de estado discretos, deve ser da ordem do tempo de autocorrelação do processo de Markov.

É importante notar que, em um problema geral, não é óbvio qual distribuição ${\displaystyle g(x'\mid x)}$ deve-se usar ou o número de iterações necessárias para uma estimativa adequada; ambos são parâmetros livres do método, que devem ser ajustados ao problema específico em questão.

Uso na integração numérica

Um uso comum do algoritmo Metropolis-Hastings é calcular uma integral. Especificamente, considere um espaço ${\displaystyle \Omega \subset \mathbb {R} }$ e uma distribuição de probabilidade ${\displaystyle P(x)}$ sobre ${\displaystyle \Omega }$, ${\displaystyle x\in \Omega }$ . Metropolis-Hastings pode estimar uma integral da forma de

${\displaystyle P(E)=\int _{\Omega }A(x)P(x)\,dx,}$

Onde ${\displaystyle A(x)}$ é uma função (mensurável) de interesse.

Por exemplo, considere uma estatística ${\displaystyle E(x)}$ e sua distribuição de probabilidade ${\displaystyle P(E)}$, que é uma distribuição marginal . Suponha que o objetivo seja estimar ${\displaystyle P(E)}$ para ${\displaystyle E}$ na cauda de ${\displaystyle P(E)}$ . Formalmente, ${\displaystyle P(E)}$ pode ser escrito como

${\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}$

e, assim, pode-se estimar ${\displaystyle P(E)}$ estimando primeiro o valor esperado da função indicadora ${\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}$, que é 1 quando ${\displaystyle E(x)\in [E,E+\Delta E]}$ e 0 caso contrário. Como ${\displaystyle E}$ está na cauda de ${\displaystyle P(E)}$, a probabilidade de tomar um estado ${\displaystyle x}$ com ${\displaystyle E(x)}$ na cauda de ${\displaystyle P(E)}$ é proporcional a ${\displaystyle P(E)}$, que é pequeno por definição. O algoritmo Metropolis-Hastings pode ser usado aqui para amostrar estados (raros) com maior probabilidade e, assim, aumentar o número de amostras usadas para estimar ${\displaystyle P(E)}$ nas caudas. Isso pode ser feito, por exemplo, usando uma distribuição de amostragem ${\displaystyle \pi (x)}$ favorecer esses estados (por exemplo, ${\displaystyle \pi (x)\propto e^{aE}}$ com ${\displaystyle a>0}$)

Instruções passo a passo

Suponha que o valor mais recente amostrado seja ${\displaystyle x_{t}}$ . Para seguir o algoritmo Metropolis-Hastings, pegamos um novo estado proposto ${\displaystyle x'}$ com densidade de probabilidade ${\displaystyle g(x'\mid x_{t})}$ e calculamos um valor

${\displaystyle a=a_{1}a_{2},}$

onde

${\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}$

é a razão de probabilidade (por exemplo, a distribuição posterior bayesiana) entre a amostra proposta ${\displaystyle x'}$ e a amostra anterior ${\displaystyle x_{t}}$ e

${\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}}$

é a razão da densidade da proposta em duas direções (de ${\displaystyle x_{t}}$ para ${\displaystyle x'}$ e vice-versa). Isso é igual a 1 se a densidade da proposta for simétrica. Então o novo estado ${\displaystyle x_{t+1}}$ é escolhido de acordo com as seguintes regras.

Se ${\displaystyle a\geq 1{:}}$

${\displaystyle x_{t+1}=x',}$

De outro modo:

${\displaystyle x_{t+1}={\begin{cases}x'&{\text{com probabilidade }}a,\\x_{t}&{\text{com probabilidade }}1-a.\end{cases}}}$

A cadeia de Markov é iniciada a partir de um valor inicial arbitrário ${\displaystyle x_{0}}$, e o algoritmo é executado para muitas iterações até que esse estado inicial seja "esquecido". Essas amostras, que são descartadas, são conhecidas como burn-in . O conjunto restante de valores aceitos de ${\displaystyle x}$ representam uma amostra de valores da distribuição ${\displaystyle P(x)}$ .

O algoritmo funciona melhor se a densidade da proposta corresponder à forma da distribuição de destino ${\displaystyle P(x)}$, da qual a amostragem direta é difícil (ou seja, ${\displaystyle g(x'\mid x_{t})\approx P(x')}$) . Se uma densidade de proposta gaussiana ${\displaystyle g}$ é usado, o parâmetro de variância ${\displaystyle \sigma ^{2}}$ precisa ser ajustado durante o período de queima. Isso geralmente é feito calculando a taxa de aceitação, que é a fração de amostras propostas que é aceita em uma janela da última ${\displaystyle N}$ amostras. A taxa de aceitação desejada depende da distribuição de destino. No entanto, foi demonstrado teoricamente que a taxa de aceitação ideal para uma distribuição Gaussiana unidimensional é de cerca de 50%, diminuindo para cerca de 23% para uma distribuição Gaussiana ${\displaystyle N}$-dimensional.

Se ${\displaystyle \sigma ^{2}}$ for muito pequeno, a cadeia se misturará lentamente (ou seja, a taxa de aceitação será alta, mas amostras sucessivas se moverão lentamente pelo espaço, e a cadeia convergirá apenas lentamente para ${\displaystyle P(x)}$ ) Por outro lado, se ${\displaystyle \sigma ^{2}}$ for muito grande, a taxa de aceitação será muito baixa porque é provável que as propostas cheguem a regiões com uma densidade de probabilidade muito menor. ${\displaystyle a_{1}}$ será muito pequena e, novamente, a cadeia convergirá muito lentamente. Geralmente, a distribuição da proposta é ajustada para que os algoritmos aceitem na ordem de 30% de todas as amostras - de acordo com as estimativas teóricas mencionadas no parágrafo anterior.

O resultado de três cadeias de Markov em execução na função Rosenbrock 3D usando o algoritmo Metropolis–Hastings. O algoritmo coleta amostras de regiões onde a probabilidade posterior é alta e as cadeias começam a se misturar nessas regiões. A posição aproximada do máximo foi iluminada. Observe que os pontos vermelhos são os que permanecem após o processo de gravação. Os anteriores foram descartados.

Ver também

• Algorítmos genéticos
• Amostragem de Gibbs
• Simulated annealing

Referências

1. Gilks. «Adaptive Rejection Sampling for Gibbs Sampling». Journal of the Royal Statistical Society. Series C (Applied Statistics). 41: 337–348. JSTOR 2347565. doi:10.2307/2347565 
2. Bayesian data analysis. Chapman & Hall / CRC 2nd ed. Boca Raton, Fla.: [s.n.] 2004. ISBN 978-1584883883. OCLC 51991499 
3. Görür. «Concave-Convex Adaptive Rejection Sampling». Journal of Computational and Graphical Statistics. 20: 670–691. ISSN 1061-8600. doi:10.1198/jcgs.2011.09058 
4. Hörmann. «A Rejection Technique for Sampling from T-concave Distributions». ACM Trans. Math. Softw. 21: 182–193. CiteSeerX 10.1.1.56.6055. ISSN 0098-3500. doi:10.1145/203082.203089 
5. Martino. «A generalization of the adaptive rejection sampling algorithm». Statistics and Computing. 21: 633–647. ISSN 0960-3174. doi:10.1007/s11222-010-9197-9 
6. Gilks. «Adaptive Rejection Metropolis Sampling within Gibbs Sampling». Journal of the Royal Statistical Society. Series C (Applied Statistics). 44: 455–472. JSTOR 2986138. doi:10.2307/2986138 
7. Martino. «Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling». IEEE Transactions on Signal Processing. 63: 3123–3138. Bibcode:2015ITSP...63.3123M. ISSN 1053-587X. arXiv:1205.5494. doi:10.1109/TSP.2015.2420537 
8. Meyer. «Adaptive rejection Metropolis sampling using Lagrange interpolation polynomials of degree 2». Computational Statistics & Data Analysis. 52: 3408–3423. doi:10.1016/j.csda.2008.01.005 
9. Raftery, Adrian E., and Steven Lewis. "How Many Iterations in the Gibbs Sampler?" In Bayesian Statistics 4. 1992.

• Portal da matemática