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)

Inventions, innovations et principes techniques connexes

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