Product Design, Manufacturing & Innovation Resources
Lar » Algoritmo de Metropolis-Hastings

Algoritmo de Metropolis-Hastings

1970
  • Nicholas Metropolis
  • Arianna W. Rosenbluth
  • Marshall N. Rosenbluth
  • Augusta H. Teller
  • Edward Teller
  • W. Keith Hastings
Estatístico aplicando o algoritmo de Metropolis-Hastings em um laboratório de pesquisa moderno.

(Imagem gerada apenas para fins ilustrativos)

O algoritmo de Metropolis-Hastings é um algoritmo proeminente. MCMC method for obtaining a sequence of random samples from a probability distribution for which direct sampling is difficult. At each iteration, it generates a candidate for the next sample based on the current sample. This candidate is then accepted or rejected with a certain probability, ensuring the resulting chain converges to the desired distribution.

O algoritmo funciona construindo um Cadeia de Markov cuja distribuição estacionária é a distribuição alvo [latex]P(x)[/latex]. Seja o estado atual [latex]x_t[/latex]. Primeiro, um estado candidato [latex]x'[/latex] é gerado a partir de uma distribuição de proposta [latex]Q(x’|x_t)[/latex], que pode ser qualquer distribuição da qual seja fácil amostrar (por exemplo, uma Gaussiana centrada em [latex]x_t[/latex]). Segundo, uma probabilidade de aceitação [latex]alpha(x’, x_t)[/latex] é calculada: [latex]alpha(x’, x_t) = minleft(1, frac{P(x’)Q(x_t|x’)}{P(x_t)Q(x’|x_t)}right)[/latex]. Um número aleatório [latex]u[/latex] é extraído de uma distribuição uniforme em [latex][0, 1][/latex]. Se [latex]u le alpha[/latex], o candidato é aceito e o próximo estado é definido como [latex]x_{t+1} = x'[/latex]. Caso contrário, o candidato é rejeitado e a cadeia permanece no estado atual, [latex]x_{t+1} = x_t[/latex].

A genialidade dessa taxa de aceitação reside no fato de que ela requer apenas o conhecimento de [latex]P(x)[/latex] até uma constante de proporcionalidade, visto que qualquer constante de normalização se cancela na fração [latex]frac{P(x’)}{P(x_t)}[/latex]. Isso é crucial na estatística Bayesiana, onde a distribuição posterior é frequentemente conhecida apenas até a intratável verossimilhança marginal. O algoritmo de Metropolis original (1953) é um caso especial em que a distribuição de proposta [latex]Q[/latex] é simétrica, ou seja, [latex]Q(x’|x_t) = Q(x_t|x’)[/latex], simplificando a probabilidade de aceitação para [latex]minleft(1, frac{P(x’)}{P(x_t)}right)[/latex]. Hastings’ A generalização de 1970 permitiu distribuições de propostas assimétricas, ampliando significativamente a aplicabilidade e a eficiência do algoritmo.

UNESCO Nomenclature: 1209
Estatísticas

Tipo

Software/Algoritmo

Interrupção

Substancial

Uso

Uso generalizado

Precursores

  • Algoritmo de Metropolis (1953)
  • teoria do balanço detalhado em cadeias de Markov
  • Monte Carlo integração
  • teoria da probabilidade Bayesiana

Aplicações

  • simulando o distribuição de Boltzmann em mecânica estatística
  • inferência bayesiana em aprendizado de máquina
  • resolução de problemas complexos de otimização por meio de recozimento simulado
  • finanças computacionais para modelagem de risco
  • processamento de sinais e reconstrução de imagem

Patentes:

NA

Ideias de Inovação Potencial

  • adaptive MCMC algorithms that tune the proposal distribution on the fly
  • hamiltonian monte carlo for more efficient exploration of the state space
  • reversible-jump MCMC for models with a varying number of parameters
  • pseudo-marginal MCMC for models with intractable likelihoods
  • parallel tempering to overcome getting stuck in local modes of a distribution
  • automated model selection in complex statistical problems
  • inference in deep generative models like variational autoencoders
  • probabilistic robotics for robot localization and mapping (SLAM)
  • cryptanalysis by sampling from distributions of possible keys
  • algorithmic trading strategies based on bayesian forecasting
Relacionado a: Metropolis-Hastings, MCMC, estatística Bayesiana, aceitação-rejeição, distribuição de proposta, distribuição estacionária, cadeia de Markov, amostragem, mecânica estatística, recozimento simulado.

Contexto histórico

Algoritmo de Metropolis-Hastings

1960
1967
1967
1970
1970
1970
1970-01-01
1960
1960
1967
1970
1970
1970
1970
1973

(Caso a data seja desconhecida ou irrelevante, por exemplo, "mecânica dos fluidos", é fornecida uma estimativa aproximada de seu surgimento notável)

10º ano aniversário

Imagens em tamanho real e downloads estão disponíveis apenas, 100% gratuitos, para membros registrados.