Les méthodes de Monte-Carlo par chaînes de Markov, ou méthodes MCMC pour Markov chain Monte Carlo en anglais, sont une classe de méthodes d'échantillonnage à partir de distributions de probabilité. Ces méthodes de Monte-Carlo se basent sur le parcours de chaînes de Markov qui ont pour lois stationnaires les distributions à échantillonner.

Certaines méthodes utilisent des marches aléatoires sur les chaînes de Markov (algorithme de Metropolis-Hastings, échantillonnage de Gibbs), alors que d'autres algorithmes, plus complexes, introduisent des contraintes sur les parcours pour essayer d'accélérer la convergence (Monte Carlo Hybride, Surrelaxation successive).

Ces méthodes sont notamment appliquées dans le cadre de l'inférence bayésienne.

Approche intuitive

On se place dans un espace vectoriel de dimension finie n. On veut générer aléatoirement des vecteurs suivant une distribution de probabilité . On veut donc avoir une suite de vecteurs telle que la distribution des approche .

Les méthodes de Monte-Carlo par chaînes de Markov consistent à générer un vecteur uniquement à partir de la donnée du vecteur ; c'est donc un processus « sans mémoire », ce qui caractérise les chaînes de Markov. Il faut donc trouver un générateur aléatoire avec une distribution de probabilité qui permette de générer à partir de . On remplace ainsi le problème de génération avec une distribution par problèmes de génération avec des distributions , que l'on espère plus simples.

Principe

On veut simuler une loi sur un espace d'états général . Une transition sur est une application telle que pour tout est mesurable et pour tout est une probabilité sur . Soit une chaîne de Markov homogène de transition et de loi initiale , on note la loi de la chaîne .

Pour simuler , on veut savoir construire une transition telle que , avec convergence en norme en variation totale . La chaîne de transition est ergodique.

La dernière condition, délicate, est satisfaite dans les cas de l'échantillonnage de Gibbs et de l'algorithme de Metropolis-Hastings.

Histoire Les méthodes MCMC plongent leurs racines dans les premières explorations des techniques de Monte Carlo (MC) au milieu du XXᵉ siècle, en particulier en physique. Un tournant survient en 1953 avec l'algorithme Metropolis proposé par Nicholas Metropolis, Arianna W. Rosenbluth, Marshall Rosenbluth, Augusta H. Teller et Edward Teller, conçu pour résoudre les problèmes d'intégration de grande dimension à l'aide des premiers ordinateurs. En 1970, W.K. Hastings généralise cet algorithme et, sans le chercher, introduit l’idée de mises à jour composante par composante, plus tard connue sous le nom d'échantillonnage de Gibbs. Parallèlement, les fondements théoriques de l'échantillonnage de Gibbs se mettent en place, comme le théorème de Hammersley-Clifford évoqué dans l'article de Julian Besag de 1974. Bien que les germes du MCMC aient été semés plus tôt - notamment avec la dénomination formelle de l’échantillonnage de Gibbs en traitement d’images par Stuart Geman et Donald Geman (1984) et la méthode d'augmentation des données par Martin A. Tanner et Wing Hung Wong (1987) - leur « révolution » dans les statistiques grand public a largement suivi les démonstrations de l’universalité et de la simplicité de mise en œuvre des méthodes d’échantillonnage (en particulier l’échantillonnage de Gibbs) pour des problèmes statistiques complexes, notamment bayésiens. L’essor de la puissance de calcul et de logiciels comme BUGS accélère cette adoption. Cette transformation s'accompagne d'avancées théoriques majeures, telles que le traitement rigoureux de la convergence du MCMC par Luke Tierney (1994) et l'analyse de la structure de l'échantillonneur de Gibbs par Jun S. Liu, Wong et Augustine Kong (1994, 1995). Par la suite, l’outillage MCMC s’élargit encore : filtres particulaires (Monte-Carlo séquentiel) pour les problèmes séquentiels, échantillonnage parfait visant la simulation exacte (Jim Propp et David B. Wilson, 1996), RJMCMC « Reversible Jump » (Peter J. Green, 1995) pour le traitement des modèles à dimension variable, et des recherches plus approfondies sur les diagnostics de convergence et le théorème central limite. Globalement, l'évolution du MCMC représente un changement de paradigme dans le calcul statistique, permettant l'analyse de nombreux modèles complexes auparavant intraitables et élargissant continuellement la portée et l'impact des statistiques. Méthodes d'échantillonnage Les méthodes d’échantillonnage sont utilisées pour estimer la distribution (complète) postérieure des paramètres d’un modèle. Parmi elles, les méthodes de Monte-Carlo sont très précises. Néanmoins, elles sont coûteuses en calculs et prennent beaucoup de temps à converger. Elles sont également limitées par la taille de l’échantillon, puisqu’elles deviennent insolubles lorsque ceux-ci sont trop grands. Même sur de petits échantillons, le calcul d'une distribution de probabilité peut s’avérer difficile. Il existe plusieurs approches à ce problème, utilisées pour obtenir un ensemble de bons réseaux d'échantillonnage à partir de la distribution postérieure.

Algorithme de Metropolis : l'algorithme de Metropolis consiste en une marche aléatoire avec une correction afin que chaque nouvelle valeur extraite puisse être rejetée si elle correspond à une valeur de la fonction d'intégration plus petite que le point précédent, avec une probabilité égale à un moins le rapport entre ces valeurs. Le processus aléatoire se concentre ainsi dans les zones où la fonction d'intégration a des valeurs plus élevées, d'où l'efficacité. Toutefois, contrairement aux méthodes de Monte-Carlo simples, où les valeurs échantillonnées sont statistiquement indépendantes, dans l'algorithme de Metropolis (et les chaînes de Monte-Carlo de Markov en général), elles sont auto-corrélées.

Algorithme de Metropolis–Hastings : Hastings a publié une généralisation de l'algorithme Metropolis (qui a valu le nom d'algorithme Metropolis-Hastings) qui utilise un processus aléatoire de base (distribution des propositions) qui n'est pas nécessairement du type marche aléatoire.

Echantillonnage de Gibbs : exige que toutes les distributions conditionnelles de la distribution cible soient connues correctement et puissent être utilisées pour les échantillonner. Cette méthode est devenue populaire car, si elle peut être appliquée, elle ne nécessite pas de paramètres d'algorithme prédéfinis.

Échantillonnage par tranches : dépend du principe selon lequel il est possible d'échantillonner une distribution uniformément à partir de la région située sous la courbe de sa fonction de densité. Cette méthode alterne entre l'échantillonnage uniforme dans la direction verticale et l'échantillonnage de la couche identifiée par la position verticale actuelle.

Metropolis à tentatives multiples : il s'agit d'une variante de l'algorithme de Metropolis-Hastings qui permet des tentatives multiples à chaque point. Cela permet à l'algorithme de définir des étapes plus importantes sous une forme systématique, ce qui permet de s'attaquer à des problèmes présentant des dimensions intrinsèquement importantes.

Méthode de sur-relaxation : une version Monte Carlo de cette technique peut être considérée comme une variation de l'échantillonnage Gibbs ; elle évite parfois les répétitions de parcours.

Méthode hybride/Hamiltonienne de Monte Carlo (HMC) : Implante la dynamique Hamiltonienne dans la chaîne de Markov en augmentant l'espace étudié avec un espace auxiliaire de temps. La densité cible devient alors la fonction d'énergie potentielle et le temps est graduellement tiré d'une distribution prédéterminée conditionnée au point xi , où une trajectoire d'énergie constante est calculée et arrêtée après un temps arbitraire. À la fin de l'échantillonnage, les données sont rejetées. Le résultat final est d'allonger les étapes proposées tout en les maintenant dans les régions à haute densité.

No U-Turn Sampling (NUTS) : Variante de la méthode HMC qui permet d'éviter les répétitions en chaîne en calculant de manière adaptative le temps des trajectoires.

La méthode MCMC de Langevin : La méthode MCMC de Langevin et d'autres méthodes basées sur la méthode du gradient (éventuellement en dérivée seconde) du logarithme de la distribution objective, proposent des chemins qui sont de préférence dans la direction de la densité de probabilité la plus élevée.

Méthodes basées sur le changement de dimension : La méthode du saut réversible est une variante de la méthode de Metropolis-Hastings qui permet de proposer des pas qui modifient la dimension de l'espace paramétrique sur lequel la marche aléatoire opère. Cette méthode a été proposée en 1995 par le statisticien Peter Green de l'Université de Bristol. Les méthodes MCMC qui modifient la dimensionnalité sont utilisées depuis longtemps dans les applications de physique statistique, où les distributions basées sur l'ensemble grand-canonique (par exemple, lorsque le nombre de molécules dans une boîte est variable) ont été utilisées pour divers problèmes. Une certaine variation de la méthode du saut réversible est nécessaire dans le cas de l'échantillonnage MCMC ou Gibbs sur des modèles bayésiens non paramétriques tels que ceux impliqués dans le processus de Dirichlet (un processus stochastique qui peut être considéré comme une distribution de probabilités dont le domaine est lui-même une distribution aléatoire) ou celui du processus du restaurant chinois, où le nombre de composants, de grappes, etc. est automatiquement déduit des données.

Construction de réseaux aléatoires et recherche de motifs La méthode de Monte Carlo par chaines de Markov est souvent utilisée dans les algorithmes traitant les réseaux (biologiques ou non). Plusieurs applications sont possibles dont 2 principales : la génération de réseaux aléatoires et la classification d’éléments dans les graphes. Les exemples choisis pour illustrer l'utilisation des MCMC par la suite seront basées sur la biologie.

Réseaux aléatoires La MCMC est très souvent utilisée pour générer des réseaux aléatoires servant comme modèles nuls, le plus proche possible du hasard, tout en gardant les caractéristiques de base d’un réseau étudié afin de rester comparable. Ces modèles nuls permettent ensuite de déterminer si des caractéristiques d’un réseau étudié sont statistiquement significatives ou non.

Le déroulement de la méthode est simple : 2 arêtes sont prises en compte (A -> B ; C -> D) et un échange des nœuds de ces arêtes (A -> D ; C -> B) est ensuite considéré et accepté seulement si les nouvelles arêtes n’existent pas déjà et qu’il n’y a pas d’arête cyclique (A -> A). Le nombre d’échanges considérés suit souvent la formule Q x E, où E est le nombre d’arêtes d’un réseau réel (souvent le réseau étudié) et Q est un nombre suffisamment élevé pour s’assurer de l’aspect aléatoire du réseau produit, souvent mis à 100.

L’utilisation de la méthode de Monte Carlo par chaînes de Markov pour générer un modèle nul contre lequel on détermine la significativité d’un (ou plusieurs) caractère(s) peut être rencontré sous le nom de «switching algorithm», avec le «matching algorithm» étant l’alternatif dans la génération des réseaux aléatoires. Ce dernier, qui n’emploie pas le MCMC, présente aussi comme désavantage la présence d’un biais dans les réseaux produits. Ces algorithmes sont le plus souvent utilisés dans la biologie pour rechercher des motifs dans les réseaux, des sous-graphes composés d’un nombre limité de nœuds et qui se retrouvent dans un très grand nombre de réseaux. Parmi les outils qui utilisent le MCMC pour générer des réseaux aléatoires sont mfinder, FANMOD, KAVOSH et NetMODE.

Recherche de motifs