Algorithme de Metropolis-Hastings

Algorithme de Metropolis-Hastings

Type	Algorithme
Inventeurs	Nicholas Metropolis, Marshall Rosenbluth, Edward Teller, W. K. Hastings (en), Enrico Fermi, Stanisław Ulam
Date d'invention	1953
Nommé en référence à	Nicholas Metropolis, W. K. Hastings (en)
Aspect de	Méthode de Monte-Carlo par chaînes de Markov

En statistique, l'algorithme de Metropolis-Hastings est une méthode MCMC dont le but est d'obtenir un échantillonnage aléatoire d'une distribution de probabilité quand l'échantillonnage direct en est difficile.

Plus formellement, étant donné une distribution de probabilité $\pi$ sur un univers $\Omega$, cet algorithme définit une chaîne de Markov dont la distribution stationnaire est $\pi$. Il permet ainsi de tirer aléatoirement un élément de $\Omega$ selon la loi $\pi$.

Un point essentiel de l'algorithme de Metropolis-Hastings est qu'il ne nécessite que la connaissance de $\pi$ à une constante multiplicative près. En particulier, il n'est pas nécessaire de calculer la fonction de partition de $\pi$, tâche souvent difficile. Pour cette raison, cette méthode est très utilisée en physique statistique.

On peut noter que l'algorithme de Metropolis–Hastings (comme d'autres méthodes MCMC) est généralement utilisé pour l'échantillonnage de distributions multi-dimensionnelles, en particulier lorsque le nombre de dimensions est élevé. Pour les distributions unidimensionnelles, il existe habituellement d'autres méthodes pour générer des échantillons indépendants (par exemple les méthodes de rejet) qui permettent d'éviter les corrélations entre échantillons générés, problème inhérent aux méthodes MCMC.

Historique

Une première version de l'algorithme a été publiée en 1949 dans un article de Nicholas Metropolis et Stanisław Ulam et sera décrite plus en détails en 1953 par Nicholas Metropolis, Arianna W. Rosenbluth, Marshall Rosenbluth, Augusta H. Teller, et Edward Teller. Cette première version considérait le cas particulier de la distribution de Boltzmann, une des distributions les plus utilisées en physique statistique. En 1970, W. K. Hastings (1930-2016) a étendu l'algorithme au cas d'une distribution quelconque.

Il y a controverse sur la question de la paternité de l'algorithme. Metropolis connaissait les aspects computationnels de la méthode et avait introduit le terme Monte Carlo dans son article de 1949 avec Stanisław Ulam. Il a d'ailleurs dirigé le groupe qui a conçu l'ordinateur MANIAC I utilisé pour les expériences de 1952. Cependant, il n'existait pas de compte-rendu précis du développement de l'algorithme avant 2003. Peu avant sa mort, Marshall Rosenbluth décrivit le développement de l'algorithme au cours d'une présentation intitulée Genesis of the Monte Carlo Algorithm for Statistical Mechanics à l'occasion d'une conférence au LANL qui célébrait le 50ème anniversaire de la publication de 1953. Gubernatis apporta de nouvelles clarifications dans un article de 2005 relatant cette conférence. Rosenbluth y déclare qu'il avait réalisé le travail avec sa femme Arianna, et que Metropolis n'avait pas participé au développement de l'algorithme excepté pour leur accorder du temps de calcul.

Cela contredit le récit d'Edward Teller, qui relate dans ses mémoires que les cinq auteurs de l'article de 1953 y ont travaillé jour et nuit ensemble. Le récit de Rosenbluth crédite Teller d'une suggestion cruciale: tirer avantage des moyennes d'ensemble utilisées en mécanique statistique plutôt que suivre une cinématique détaillée. C'est cette suggestion, dit Rosenbluth, qui l'a amené à réfléchir à une approche Monte Carlo généralisée, un sujet dont il aurait beaucoup discuté avec Von Neumann. Arianna Rosenbluth raconte à Gubernatis en 2003 qu'Augusta Teller avait commencé le code, mais qu'elle l'avait repris depuis le début. Dans un récit oral enregistré peu de temps avant sa mort, Rosenbluth déclare à nouveau que Teller avait proposé l'idée initiale, que lui (Rosenbluth) a résolu le problème et que sa femme Arianna l'a programmé.

Les compétences scientifiques reconnues de Rosenbluth apportent un certain crédit à son récit. Ainsi, Freeman Dyson écrit dans un texte biographique sur Rosenbluth: « Many times I came to Rosenbluth, asking him a question [...] and receiving an answer in two minutes. Then it would usually take me a week of hard work to understand in detail why Rosenbluth's answer was right. He had an amazing ability to see through a complicated physical situation and reach the right answer by physical arguments. Enrico Fermi was the only other physicist I have known who was equal to Rosenbluth in his intuitive grasp of physics. » ce que l'on peut traduire par: « Souvent je posais une question à Rosenbluth à laquelle il répondait en deux minutes. Puis il me fallait une semaine de dur travail pour comprendre pourquoi la réponse de Rosenbluth était juste. Il avait une capacité extraordinaire à comprendre une situation physique complexe et à trouver la bonne réponse par des arguments physiques. Le seul autre physicien que j'ai connu qui avait une intuition physique équivalente était Enrico Fermi. »

Description intuitive

Nous voulons obtenir des tirages aléatoires d'un vecteur $x$, ayant un grand nombre de dimensions (pour une distribution à une dimension, on utilise d'autres algorithmes plus directs comme la méthode de rejet) selon une distribution de probabilité $\pi$. Nous sommes dans le cas où il n'est pas simple de générer directement une suite de vecteurs suivant cette distribution $\pi$. Par ailleurs, il n'est pas nécessaire de connaître cette distribution, il suffit de connaître une fonction $f$ telle que $f(x)$ est proportionnelle à $\pi (x)$. Cette propriété est particulièrement utile, car en pratique, il est souvent difficile de déterminer le facteur de normalisation.

L'algorithme de Metropolis–Hastings génère des valeurs d'échantillon de manière que plus on produit de valeurs, plus la distribution de ces valeurs se rapproche de la distribution recherchée $\pi$. Ces valeurs sont produites de manière itérative, la probabilité de l'échantillon à l'étape suivante ne dépend que de l'échantillon à l'étape considérée, la suite d'échantillons est donc une chaîne de Markov. Plus précisément, à chaque itération, l'algorithme choisit un candidat pour le prochain échantillon qui n'est basé que sur l'échantillon courant. Ensuite, le candidat est soit accepté avec une certaine probabilité (et dans ce cas il sera utilisé à l'étape suivante), soit rejeté avec la probabilité complémentaire (et dans ce cas l'échantillon actuel sera réutilisé à l'étape suivante). La probabilité d'acceptation est déterminée en comparant les valeurs de la fonction $f$ pour l'échantillon actuel à la valeur de $f$ pour l'échantillon candidat. Après un « grand nombre » d'itérations, la valeur des échantillons « perdent la mémoire » de l'état initial et suivent la distribution $\pi$.

Algorithme de Metropolis

On considère d'abord le cas de l'algorithme de Metropolis, qui est un cas particulier de l'algorithme de Metropolis–Hastings, où la probabilité de transition est symétrique. Hastings a généralisé cet algorithme à une probabilité de transition dissymétrique.

Pseudo-code

Soit $f$ une fonction proportionnelle à la distribution-cible, c'est-à-dire à la distribution de probabilité recherchée $\pi$.

1. Initialisation: choisir un point arbitraire $x_{0}$ pour être le premier échantillon et une probabilité de transition $g$ qui suggère un échantillon candidat $x'$ pour la valeur de l'échantillon suivant, connaissant la valeur de l'échantillon précédent $x$. On suppose ici que cette distribution de probabilité est symétrique, c'est-à-dire que $g$ doit vérifier $g(x'\mid x)=g(x\mid x')$. Un choix usuel pour une telle distribution est la distribution gaussienne centrée sur $x$, de manière que les points proches de $x$ aient une plus grande probabilité d'être visités à l'itération suivante.
2. A chaque itération t (échantillon courant $x_{t}$):
   • tirer aléatoirement un candidat $x'$ pour l'échantillon suivant selon la distribution $g(x'\mid x_{t})$.
   • Calculer le taux d'acceptation $\alpha ={\frac {f(x')}{f(x_{t})}}$, qui sera utilisé pour déterminer si le candidat est accepté ou rejeté. Comme $f$ est proportionnelle à la densité $\pi$, on a $\alpha ={\frac {f(x')}{f(x_{t})}}={\frac {\pi (x')}{\pi (x_{t})}}$.
   • Accepter ou rejeter:
     • Tirer un nombre uniformément aléatoire $u\in [0,1]$.
     • Si $u\leq \alpha$, alors accepter le candidat en effectuant $x_{t+1}=x'$ (donc si $\alpha \geq 1$, on accepte nécessairement),
     • Si $u>\alpha$, alors rejeter le candidat en effectuant $x_{t+1}=x_{t}$.

Interprétation

L'algorithme peut être interprété intuitivement de la manière suivante : à chaque itération, on tente de se déplacer dans l'espace des états possibles, le déplacement peut être accepté ou rejeté. Le taux d'acceptation $\alpha$ indique à quel point le nouvel état est probable étant donné l'état actuel, et selon la distribution $\pi$. Si l'on cherche à se déplacer vers un état plus probable que l'état actuel (si $\alpha \geq 1\geq u$), le déplacement est toujours accepté. Cependant, si l'on cherche à se déplacer vers un état moins probable que l'état actuel, alors le déplacement peut être rejeté et le rejet est d'autant plus probable que la chute de densité de probabilité $\pi$ est élevée. Par conséquent, la marche tend à visiter préférentiellement les régions de l'espace des états où la densité $\pi$ est élevée mais visite occasionnellement des régions de moindre densité.

Cas général

Généralités sur les processus de Markov

Un processus markovien est défini de manière unique par la distribution des probabilités de transition $g$. $g(x,y)=g(x|y)$ désigne la probabilité d'aller d'un état donné $y$ vers un autre état donné $x$. Un processus markovien admet une unique distribution stationnaire $\pi (x)$ si la chaîne de Markov est ergodique (ou irréductible, c'est-à-dire que tout état de l'espace est accessible depuis tout autre état), apériodique (le système ne revient pas dans le même état à intervalles réguliers) et récurrente positive (le nombre de pas pour revenir dans un même état est fini). On doit vérifier ces conditions pour pouvoir appliquer l'algorithme de Metropolis–Hastings.

Pseudo-code

Partiellement adapté de.

Soit $f$ une fonction proportionnelle à la distribution-cible, c'est-à-dire à la distribution de probabilité recherchée $\pi$.

1. Initialisation: choisir un point arbitraire $x_{0}$ pour être le premier échantillon et une probabilité de transition $g$ qui suggère un échantillon candidat $x$ pour la valeur de l'échantillon suivant, connaissant la valeur de l'échantillon précédent $y$. La condition de réversibilité de la chaîne de Markov implique que $g(x\mid y)\pi (y)=g(y\mid x)\pi (x)$.
2. A chaque itération t (échantillon courant $x_{t}$):
   • tirer aléatoirement un candidat $x'$ pour l'échantillon suivant selon la distribution $g(x',x_{t})=g(x'\mid x_{t})$.
   • Calculer le taux d'acceptation $\alpha ={\frac {f(x')g(x_{t},x')}{f(x_{t})g(x',x_{t})}}$, qui sera utilisé pour déterminer si le candidat est accepté ou rejeté. Comme $f$ est proportionnelle à la densité $\pi$, on a $\alpha ={\frac {f(x')g(x_{t},x')}{f(x_{t})g(x',x_{t})}}={\frac {\pi (x')g(x_{t},x')}{\pi (x_{t})g(x',x_{t})}}$.
   • Accepter ou rejeter:
     • Tirer un nombre uniformément aléatoire $u\in [0,1]$.
     • Si $u\leq \alpha$, alors accepter le candidat en effectuant $x_{t+1}=x'$ (donc si $\alpha \geq 1$, on accepte nécessairement),
     • Si $u>\alpha$, alors rejeter le candidat en effectuant $x_{t+1}=x_{t}$.

Il est important de noter que dans le cas général, le choix de la distribution $g$ et du nombre d'itérations à réaliser sont des paramètres libres de la méthode et doivent être adaptés au problème considéré. Dans le cas d'un espace discret, le nombre d'itérations doit être de l'ordre du temps d'autocorrélation du processus de Markov.

Analyse et comparaison à d'autres méthodes

L'algorithme de Metropolis–Hastings est une des méthodes les plus générales dans la famille des méthodes MCMC, dans le sens où il impose très peu de conditions sur la densité cible. À partir de la densité cible $\pi (x)$ (qui peut être en grandes dimensions), on choisit une densité instrumentale conditionnelle $g$ à partir de laquelle il est relativement facile de simuler.

Par comparaison avec d'autres algorithmes d'échantillonnage tel que la méthode de rejet et sa variante adaptative qui génère directement des échantillons indépendants depuis la distribution, l'algorithme de Metropolis–Hastings (et les méthodes MCMC en général) présentent des désavantages:

• Les échantillons sont corrélés. Un ensemble de points proches au cours du processus seront corrélés entre eux et ne reflète donc pas correctement la distribution. Par conséquent, si l'on souhaite avoir des échantillons indépendants, on doit éliminer la majorité des échantillons pour ne conserver qu'un échantillon tous les n pas, avec n « suffisamment grand ». On peut déterminer n par exemple en mesurant l'autocorrélation entre échantillons proches. L'autocorrélation peut être réduite en augmentant la largeur des sauts entre deux échantillons, mais augmenter la taille des sauts augmente aussi la probabilité de rejet du nouvel échantillon. Dans le cas où le processus nécessite un grand nombre de sauts pour éliminer l'autocorrélation, on dit que la chaîne de Markov a un long temps de mélange.
• Bien que la chaîne de Markov converge vers la distribution souhaitée, les échantillons initiaux peuvent suivre une distribution très différente, en particulier s'ils se trouvent dans une région de faible densité de probabilité. Par conséquent, une période de rodage est souvent nécessaire, et les premiers échantillons seront éliminés.

En revanche, les méthodes de rejet les plus simples peuvent souffrir du « fléau de la dimension », qui se traduit ici par le fait que la probabilité de rejet augmente exponentiellement avec le nombre de dimensions. Les méthodes MCMC n'ont pas ce problème jusqu'à un certain point et sont donc souvent les seules solutions disponibles lorsque le nombre de dimensions de la distribution à échantillonner est élevé.

Dans le cas des distributions multivariées, l'algorithme de Metropolis–Hastings tel que décrit plus haut suppose de choisir à chaque itération un nouvel échantillon dans l'espace multi-dimensionnel. Quand le nombre de dimensions est élevé, trouver le pas du déplacement peut être difficile, car chaque dimension peut se comporter très différemment, or le pas du saut doit être adapté à chaque dimension pour éviter un mélange trop lent. Une approche alternative qui peut mieux fonctionner dans de telles situations est l'échantillonnage de Gibbs. Cette approche consiste à choisir un nouvel échantillon pour chaque dimension séparément des autres. Elle est utilisable en particulier lorsque la distribution multivariée est composée d'un ensemble de variables aléatoires conditionnées par un petit ensemble d'autres variables, ce qui est typiquement le cas dans les modèles bayésiens hiérarchiques. Les variables individuelles sont échantillonnées une à une et chaque variable est conditionnée sur la valeur la plus récente de celles dont elle dépend. Plusieurs algorithmes peuvent être utilisés pour choisir ces échantillons individuels, en fonction de la forme précise de la distribution multivariée (par exemple l'algorithme adaptatif d'acceptation-rejet, l'algorithme adaptatif d'acceptation-rejet de Metropolis, l'algorithme Metropolis–Hastings à 1 dimension, etc).

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Metropolis–Hastings algorithm » (voir la liste des auteurs).

Voir aussi

Articles connexes

• Chaîne de Markov
• Recuit simulé
• Optimisation combinatoire
• Méthode de Monte-Carlo par chaînes de Markov
• Méthode de Monte-Carlo
• Échantillonnage
• Algorithme de Metropolis-Hastings à sauts réversibles