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
Statistician applying Metropolis-Hastings algorithm in a modern research lab.

(Imagem gerada apenas para fins ilustrativos)

O algoritmo de Metropolis-Hastings é um algoritmo proeminente. MCMC método para obter uma sequência de amostras aleatórias de uma distribuição de probabilidade para a qual a amostragem direta é difícil. A cada iteração, gera um candidato para a próxima amostra com base na amostra atual. Esse candidato é então aceito ou rejeitado com uma certa probabilidade, garantindo que a cadeia resultante convirja para a distribuição desejada.

The algorithm works by constructing a Markov chain whose stationary distribution is the target distribution [latex]P(x)[/latex]. Let the current state be [latex]x_t[/latex]. First, a candidate state [latex]x'[/latex] is generated from a proposal distribution [latex]Q(x’|x_t)[/latex], which can be any distribution that is easy to sample from (e.g., a Gaussian centered at [latex]x_t[/latex]). Second, an acceptance probability [latex]\alpha(x’, x_t)[/latex] is calculated: [latex]\alpha(x’, x_t) = \min\left(1, \frac{P(x’)Q(x_t|x’)}{P(x_t)Q(x’|x_t)}\right)[/latex]. A random number [latex]u[/latex] is drawn from a uniform distribution on [latex][0, 1][/latex]. If [latex]u \le \alpha[/latex], the candidate is accepted, and the next state is set to [latex]x_{t+1} = x'[/latex]. Otherwise, the candidate is rejected, and the chain remains at the current state, [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 integration
  • teoria da probabilidade Bayesiana

Aplicações

  • simulating the boltzmann distribution in statistical mechanics
  • 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
  • signal processing and image reconstruction

Patentes:

NA

Ideias de Inovação Potencial

Devido ao tráfego de bots de coleta de dados, atualmente superior a 40 mil por dia, este conteúdo é reservado aos membros da comunidade.
> Login < ou > Registrar < (100% gratuito) para acessar isso, assim como todo o restante do conteúdo e das ferramentas restritas.

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)

Princípios relacionados à invenção, inovação e tecnologia

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