Product Design, Manufacturing & Innovation Resources
Maison » Algorithme de Metropolis-Hastings

Algorithme de Metropolis-Hastings

1970
  • Nicholas Metropolis
  • Arianna W. Rosenbluth
  • Marshall N. Rosenbluth
  • Augusta H. Teller
  • Edward Teller
  • W. Keith Hastings
Statisticien appliquant l'algorithme Metropolis-Hastings dans un laboratoire de recherche moderne.

(Image générée à titre d'illustration uniquement)

The Metropolis-Hastings algorithm is a prominent MCMC méthode 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.

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].

The brilliance of this acceptance ratio is that it only requires knowing [latex]P(x)[/latex] up to a constant of proportionality, since any normalization constant cancels out in the fraction [latex]frac{P(x’)}{P(x_t)}[/latex]. This is crucial in Bayesian statistics, where the posterior distribution is often known only up to the intractable marginal likelihood. The original Metropolis algorithm (1953) is a special case where the proposal distribution [latex]Q[/latex] is symmetric, i.e., [latex]Q(x’|x_t) = Q(x_t|x’)[/latex], simplifying the acceptance probability to [latex]minleft(1, frac{P(x’)}{P(x_t)}right)[/latex]. Hastings’ 1970 generalization allowed for asymmetric proposal distributions, significantly broadening the algorithm’s applicability and efficiency.

UNESCO Nomenclature: 1209
- Statistiques

Taper

Logiciel/Algorithme

Perturbation

Substantiel

Usage

Utilisation généralisée

Précurseurs

  • Algorithme de Metropolis (1953)
  • théorie de l'équilibre détaillé dans les chaînes de Markov
  • Intégration de Monte Carlo
  • théorie des probabilités bayésiennes

Applications

  • simulation de la distribution de Boltzmann en mécanique statistique
  • inférence bayésienne en apprentissage automatique
  • résolution de problèmes d'optimisation complexes par recuit simulé
  • finance computationnelle pour la modélisation des risques
  • traitement du signal et reconstruction d'images

Brevets:

NA

Idées d'innovations potentielles

En raison du trafic généré par les robots de scraping, actuellement supérieur à 40 000 par jour, ce contenu est réservé aux membres de la communauté.
> Connexion < ou > Registre < (100% gratuit) pour y accéder, ainsi qu'à tous les autres contenus et outils à accès restreint.

Related to: Metropolis-Hastings, MCMC, Bayesian statistics, acceptance-rejection, proposal distribution, stationary distribution, Markov chain, sampling, statistical mechanics, simulated annealing.

Contexte historique

Algorithme de Metropolis-Hastings

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

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Les images en pleine résolution et les téléchargements sont uniquement disponibles, et 100% gratuits, pour les membres inscrits.