Algorithme de Metropolis-Hastings
1970
- Nicholas Metropolis
- Arianna W. Rosenbluth
- Marshall N. Rosenbluth
- Augusta H. Teller
- Edward Teller
- W. Keith Hastings
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
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
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.