Chaîne de Markov Monte Carlo - Markov chain Monte Carlo

En statistique , les méthodes de Markov Chain Monte Carlo ( MCMC ) comprennent une classe d' algorithmes pour l'échantillonnage à partir d'une distribution de probabilité . En construisant une chaîne de Markov qui a la distribution souhaitée comme distribution d' équilibre , on peut obtenir un échantillon de la distribution souhaitée en enregistrant les états de la chaîne. Plus il y a d'étapes, plus la distribution de l'échantillon correspond à la distribution réelle souhaitée. Divers algorithmes existent pour construire des chaînes, dont l' algorithme de Metropolis-Hastings .

Domaines d'application

Méthodes MCCM sont principalement utilisés pour le calcul des approximations numériques de intégrales multidimensionnelles , par exemple dans la statistique bayésienne , physique numérique , la biologie computationnelle et linguistique informatique .

En statistiques bayésiennes, le développement récent des méthodes MCMC a permis de calculer de grands modèles hiérarchiques qui nécessitent des intégrations sur des centaines à des milliers de paramètres inconnus.

Dans l' échantillonnage d'événements rares , ils sont également utilisés pour générer des échantillons qui peuplent progressivement la région de défaillance rare.

Explication générale

Convergence de l' algorithme de Metropolis–Hastings . La chaîne de Markov Monte Carlo tente d'approcher la distribution bleue avec la distribution orange.

Les méthodes de Monte Carlo à chaîne de Markov créent des échantillons à partir d'une variable aléatoire continue , avec une densité de probabilité proportionnelle à une fonction connue. Ces échantillons peuvent être utilisés pour évaluer une intégrale sur cette variable, comme sa valeur attendue ou sa variance .

Pratiquement, on élabore généralement un ensemble de chaînes, à partir d'un ensemble de points choisis arbitrairement et suffisamment éloignés les uns des autres. Ces chaînes sont des processus stochastiques de « marcheurs » qui se déplacent de manière aléatoire selon un algorithme qui recherche des endroits avec une contribution raisonnablement élevée à l'intégrale pour se déplacer ensuite, en leur attribuant des probabilités plus élevées.

Les méthodes de Monte Carlo à marche aléatoire sont une sorte de simulation aléatoire ou méthode de Monte Carlo . Cependant, alors que les échantillons aléatoires de l'intégrande utilisés dans une intégration Monte Carlo conventionnelle sont statistiquement indépendants , ceux utilisés dans MCMC sont autocorrélés . Les corrélations d'échantillons introduisent la nécessité d'utiliser le théorème central limite de la chaîne de Markov lors de l'estimation de l'erreur des valeurs moyennes.

Ces algorithmes créent des chaînes de Markov telles qu'elles ont une distribution d'équilibre qui est proportionnelle à la fonction donnée.

Réduire la corrélation

Alors que les méthodes MCMC ont été créées pour mieux traiter les problèmes multidimensionnels que les algorithmes génériques de Monte Carlo, lorsque le nombre de dimensions augmente, elles ont également tendance à subir la malédiction de la dimensionnalité : les régions de probabilité plus élevée ont tendance à s'étirer et à se perdre dans un volume croissant d'espace. qui contribue peu à l'intégrale. Une façon de résoudre ce problème pourrait être de raccourcir les étapes du marcheur, de sorte qu'il n'essaie pas en permanence de sortir de la région de probabilité la plus élevée, bien que de cette façon, le processus serait hautement autocorrélé et coûteux (c'est-à-dire que de nombreuses étapes seraient nécessaires pour un résultat précis). Des méthodes plus sophistiquées telles que l' hamiltonien Monte Carlo et l' algorithme de Wang et Landau utilisent diverses manières de réduire cette autocorrélation, tout en réussissant à maintenir le processus dans les régions qui contribuent le plus à l'intégrale. Ces algorithmes reposent généralement sur une théorie plus compliquée et sont plus difficiles à mettre en œuvre, mais ils convergent généralement plus rapidement.

Exemples

Marche aléatoire

Algorithme de Metropolis–Hastings : Cette méthode génère une chaîne de Markov en utilisant une densité de proposition pour les nouvelles étapes et une méthode pour rejeter certains des mouvements proposés. Il s'agit en fait d'un cadre général qui inclut comme cas particuliers le tout premier et plus simple MCMC (algorithme Metropolis) et de nombreuses alternatives plus récentes listées ci-dessous.
- Échantillonnage de Gibbs : Cette méthode nécessite que toutes les distributions conditionnelles de la distribution cible soient échantillonnées exactement. Lorsque tirer des distributions conditionnelles complètes n'est pas simple, d'autres échantillonneurs au sein de Gibbs sont utilisés (par exemple, voir ). L'échantillonnage de Gibbs est populaire en partie parce qu'il ne nécessite aucun « réglage ». La structure de l'algorithme de l' échantillonnage de Gibbs ressemble fortement à celle de l'inférence variationnelle de l'ascension des coordonnées dans la mesure où les deux algorithmes utilisent les distributions conditionnelles complètes dans la procédure de mise à jour.
- Algorithme de Langevin ajusté par Metropolis et d'autres méthodes qui s'appuient sur le gradient (et éventuellement la dérivée seconde) du logarithme de la densité cible pour proposer des étapes plus susceptibles d'aller dans le sens d'une densité de probabilité plus élevée.
- Métropole pseudo-marginale–Hastings : Cette méthode remplace l'évaluation de la densité de la distribution cible par une estimation non biaisée et est utile lorsque la densité cible n'est pas disponible analytiquement, par exemple les modèles à variables latentes .
Échantillonnage en tranches : Cette méthode repose sur le principe que l'on peut échantillonner à partir d'une distribution en échantillonnant uniformément à partir de la région sous le tracé de sa fonction de densité. Il alterne un échantillonnage uniforme dans la direction verticale avec un échantillonnage uniforme à partir de la « tranche » horizontale définie par la position verticale actuelle.
Metropolis à essais multiples : Cette méthode est une variante de l'algorithme Metropolis-Hastings qui permet plusieurs essais à chaque point. En permettant de faire des pas plus importants à chaque itération, il aide à lutter contre la malédiction de la dimensionnalité.
Reversible-jump : Cette méthode est une variante de l'algorithme de Metropolis-Hastings qui permet des propositions qui changent la dimensionnalité de l'espace. Les méthodes de Monte Carlo à chaîne de Markov qui changent la dimensionnalité sont utilisées depuis longtemps dans les applications de physique statistique , où pour certains problèmes une distribution qui est un grand ensemble canonique est utilisée (par exemple, lorsque le nombre de molécules dans une boîte est variable). Mais la variante à saut réversible est utile lors de l'échantillonnage par chaîne de Markov de Monte Carlo ou de Gibbs sur des modèles bayésiens non paramétriques tels que ceux impliquant le processus de Dirichlet ou le processus de restaurant chinois , où le nombre de composants/clusters/etc. est automatiquement déduit des données.
Monte Carlo hamiltonien (ou hybride) (HMC) : essaie d'éviter le comportement de marche aléatoire en introduisant un vecteur de quantité de mouvement auxiliaire et en mettant en œuvre la dynamique hamiltonienne , de sorte que la fonction d'énergie potentielle est la densité cible. Les échantillons de quantité de mouvement sont rejetés après l'échantillonnage. Le résultat final de Hybrid Monte Carlo est que les propositions se déplacent à travers l'espace d'échantillonnage par étapes plus importantes ; ils sont donc moins corrélés et convergent plus rapidement vers la distribution cible.

Méthodes de particules en interaction

Les méthodologies MCMC interactives sont une classe de méthodes de particules à champ moyen pour obtenir des échantillons aléatoires à partir d'une séquence de distributions de probabilité avec un niveau croissant de complexité d'échantillonnage. Ces modèles probabilistes comprennent des modèles d'état de l'espace de chemin avec un horizon temporel croissant, des distributions postérieures par rapport à une séquence d'observations partielles, des ensembles de niveaux de contraintes croissants pour les distributions conditionnelles, des programmes de température décroissants associés à certaines distributions de Boltzmann-Gibbs, et bien d'autres. En principe, tout échantillonneur Monte Carlo à chaîne de Markov peut être transformé en un échantillonneur Monte Carlo à chaîne de Markov en interaction. Ces échantillonneurs Monte Carlo à chaîne de Markov en interaction peuvent être interprétés comme un moyen d'exécuter en parallèle une séquence d'échantillonneurs Monte Carlo à chaîne de Markov. Par exemple, les algorithmes de recuit simulé en interaction sont basés sur des mouvements indépendants de Metropolis-Hastings interagissant séquentiellement avec un mécanisme de type sélection-rééchantillonnage. Contrairement aux méthodes traditionnelles de Monte Carlo à chaîne de Markov, le paramètre de précision de cette classe d'échantillonneurs Monte Carlo à chaîne de Markov en interaction est uniquement lié au nombre d'échantillonneurs Monte Carlo à chaîne de Markov en interaction. Ces méthodologies de particules avancées appartiennent à la classe des modèles de particules Feynman-Kac, également appelés méthodes de Monte Carlo séquentiel ou de filtrage de particules dans les communautés d' inférence bayésienne et de traitement du signal . Les méthodes de Monte Carlo à chaîne de Markov en interaction peuvent également être interprétées comme un algorithme de particules génétiques de sélection de mutation avec des mutations de Monte Carlo à chaîne de Markov.

Chaîne de Markov quasi-Monte Carlo (MCQMC).

L'avantage des séquences à faible discordance au lieu des nombres aléatoires pour un simple échantillonnage Monte Carlo indépendant est bien connu. Cette procédure, connue sous le nom de méthode Quasi-Monte Carlo (QMC), donne une erreur d'intégration qui décroît à un taux supérieur à celui obtenu par l'échantillonnage IID, par l' inégalité de Koksma-Hlawka . Empiriquement, il permet de réduire à la fois l'erreur d'estimation et le temps de convergence d'un ordre de grandeur. La méthode Array-RQMC combine une simulation de chaîne quasi-Monte Carlo et de Markov aléatoire en simulant des chaînes simultanément de manière à ce que la distribution empirique des états à une étape donnée soit une meilleure approximation de la vraie distribution de la chaîne qu'avec le MCMC ordinaire. Dans les expériences empiriques, la variance de la moyenne d'une fonction de l'état converge parfois à un taux ou même plus rapide, au lieu du taux de Monte Carlo. ${\style d'affichage n}$ ${\style d'affichage n}$ ${\style d'affichage O(n^{-2})}$ ${\style d'affichage O(n^{-1})}$

Convergence

Habituellement, il n'est pas difficile de construire une chaîne de Markov avec les propriétés souhaitées. Le problème le plus difficile est de déterminer combien d'étapes sont nécessaires pour converger vers la distribution stationnaire avec une erreur acceptable. Une bonne chaîne aura un mélange rapide : la distribution stationnaire est atteinte rapidement à partir d'une position arbitraire. Une méthode empirique standard pour évaluer la convergence consiste à exécuter plusieurs chaînes de Markov simulées indépendantes et à vérifier que le rapport des variances inter-chaîne sur intra-chaîne pour tous les paramètres échantillonnés est proche de 1.

En règle générale, l'échantillonnage Monte Carlo par chaîne de Markov ne peut qu'approximer la distribution cible, car il y a toujours un effet résiduel de la position de départ. Des algorithmes de chaîne de Markov plus sophistiqués basés sur Monte Carlo, tels que le couplage du passé, peuvent produire des échantillons exacts, au prix de calculs supplémentaires et d'un temps d'exécution illimité (bien que fini en espérance) .

De nombreuses méthodes de Monte Carlo à marche aléatoire se déplacent autour de la distribution d'équilibre en étapes relativement petites, sans tendance à ce que les étapes se déroulent dans la même direction. Ces méthodes sont faciles à mettre en œuvre et à analyser, mais malheureusement cela peut prendre beaucoup de temps au promeneur pour explorer tout l'espace. Le marcheur doublera souvent le dos et couvrira le terrain déjà couvert.

Une autre considération de la convergence est au théorème central limite de la chaîne de Markov . Voir pour une discussion de la théorie liée à la convergence et à la stationnarité de l'algorithme de Metropolis-Hastings.

Logiciel

Plusieurs logiciels offrent des capacités d'échantillonnage MCMC, par exemple :

ParaMonte , un logiciel série/parallèle hautes performances pour les simulations de Monte Carlo, y compris le MCMC de Metropolis-Hastings adaptatif à rejet différé, disponible en
- Python ,
- MATLAB ,
- C/C++/Fortran sur Windows , Linux et macOS .
Vandal , le package Vandal offre plusieurs options de simulation Monte Carlo, telles que la mesure du risque et l'histogramme de règle empirique et bien d'autres, disponibles dans
- Python
Packages qui utilisent des dialectes du langage de modèle BUGS :
- WinBUGS / OpenBUGS / MultiBUGS
- JAGS
- AGILE
greta , un langage de modélisation statistique bayésien / package R qui utilise TensorFlow dans les coulisses, similaire à l'utilisation de Theano par PyMC3 comme back-end de calcul
MCSim
PyMC3
pymcmcstat
R (langage de programmation) avec les packages adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan, etc.
Stan
TensorFlow Probability ( bibliothèque de programmation probabiliste construite sur TensorFlow )
MCL (un algorithme de cluster pour les graphes) et HipMCL (une version parallélisée)
maître de cérémonie (implémentation Python pure sous licence MIT de l'échantillonneur Monte Carlo Ensemble de chaîne de Markov Affine Invariant de Goodman & Weare)
Keanu une bibliothèque de programmation probabiliste à usage général construite en Java
Zeus est une implémentation Python pure de la méthode Ensemble Slice Sampling
Turing.jl , un package pour la programmation probabiliste à usage général dans Julia
Mamba.jl , une plateforme pour la méthode MCMC dans Julia

Voir également

Les références

Citations

Sources

Christophe Andrieu, Nando De Freitas, Arnaud Doucet et Michael I. Jordan Une introduction à MCMC pour l'apprentissage automatique , 2003
Asmussen, Søren ; Glynn, Peter W. (2007). Simulation stochastique : algorithmes et analyse . Modélisation stochastique et probabilité appliquée. 57 . Springer.
Atzberger, P. "Une introduction aux méthodes de Monte-Carlo" (PDF) .
Berg, Bernd A. (2004). Simulations de Monte Carlo par chaîne de Markov et leur analyse statistique . Scientifique mondial .
Bolstad, William M. (2010). Comprendre les statistiques bayésiennes computationnelles . Wiley. ISBN 978-0-470-04609-8.
Casella, Georges; George, Edouard I. (1992). "Expliquer l'échantillonneur Gibbs". Le statisticien américain . 46 (3) : 167-174. CiteSeerX 10.1.1.554.3993 . doi : 10.2307/2685208 . JSTOR 2685208 .
Gelfand, AE ; Smith, AFM (1990). "Approches basées sur l'échantillonnage pour calculer les densités marginales". Journal de l'Association statistique américaine . 85 (410): 398-409. CiteSeerX 10.1.1.512.2330 . doi : 10.1080/01621459.1990.10476213 .
Gelman, André ; Carlin, John B. ; Stern, Hal S.; Rubin, Donald B. (1995). Analyse de données bayésienne (1ère éd.). Chapman et Hall . (Voir chapitre 11.)
Geman, S.; Geman, D. (1984). "La relaxation stochastique, les distributions de Gibbs et la restauration bayésienne des images". Transactions IEEE sur l'analyse des modèles et l'intelligence machine . 6 (6) : 721-741. doi : 10.1109/TPAMI.1984.4767596 . PMID 22499653 .
Gilks, WR; Richardson, S.; Spiegelhalter, DJ (1996). La chaîne de Markov Monte Carlo en pratique . Chapman et Hall /CRC.
Gill, Jeff (2008). Méthodes bayésiennes : une approche des sciences sociales et comportementales (2e éd.). Chapman et Hall /CRC. ISBN 978-1-58488-562-7.
Vert, PJ (1995). « Calcul de Monte Carlo par chaîne de Markov à saut réversible et détermination du modèle bayésien ». Biometrika . 82 (4) : 711-732. CiteSeerX 10.1.1.407.8942 . doi : 10.1093/biomet/82.4.711 .
Neal, Radford M. (2003). "Échantillonnage de tranches" . Annales de statistiques . 31 (3) : 705-767. doi : 10.1214/aos/1056562461 . JSTOR 3448413 .
Neal, Radford M. (1993). " Inférence probabiliste utilisant les méthodes de Monte Carlo par chaîne de Markov " .
Robert, Christian P. ; Casella, G. (2004). Méthodes statistiques de Monte Carlo (2e éd.). Springer. ISBN 978-0-387-21239-5.
Rubinstein, RY; Kroese, DP (2007). Simulation et méthode de Monte Carlo (2e éd.). Wiley . ISBN 978-0-470-17794-5.
Smith, RL (1984). « Procédures de Monte Carlo efficaces pour générer des points uniformément répartis sur des régions délimitées ». Recherche opérationnelle . 32 (6) : 1296-1308. doi : 10.1287/opre.32.6.1296 . hdl : 2027,42/7681 .
Spall, JC (avril 2003). "Estimation via Markov Chain Monte Carlo". Magazine des systèmes de contrôle IEEE . 23 (2) : 34-45. doi : 10.1109/mcs.2003.1188770 .
Stramer, O.; Tweedie, R. (1999). « Modèles de type Langevin II : candidats auto-ciblés pour les algorithmes MCMC ». Méthodologie et calcul en probabilités appliquées . 1 (3) : 307-328. doi : 10.1023/A:101090512027 .

Lectures complémentaires

Diaconis, Perse (avril 2009). « La révolution de la chaîne de Markov Monte Carlo » (PDF) . Taureau. Amer. Math. Soc. 46 (2) : 179-205. doi : 10.1090/s0273-0979-08-01238-x . S 0273-0979(08)01238-X.
Appuyez sur, WH ; Teukolsky, SA ; Vetterling, WT ; Flannery, BP (2007), "Section 15.8. Markov Chain Monte Carlo" , Recettes numériques: L'art de l'informatique scientifique (3e éd.), Cambridge University Press , ISBN 978-0-521-88068-8
Richey, Matthew (mai 2010). « L'évolution des méthodes de Monte Carlo de la chaîne de Markov » (PDF) . Le mensuel mathématique américain . 117 (5) : 383-413. CiteSeerX 10.1.1.295.4478 . doi : 10.4169/000298910x485923 .

Languages

In other projects