Algorithme de Metropolis-Hastings

En statistique, l'algorithme de Métropolis-Hastings est une méthode MCMC. Étant donnée 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$ (on parle d'échantillonnage).

Un point essentiel de l'algorithme de Métropolis-Hasting 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.

Historique

La première version de l'algorithme a été initiée dans un article de 1949 par Nicholas Metropolis et Stan Ulam puis décrite quelques années plus tard 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. Keith Hastings (1930-) a étendu l'algorithme au cas de n'importe quelle distribution.

Approche 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 —, avec 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, on ne connaît pas nécessairement cette distribution $\pi$, il suffit de connaître une fonction $f(x)$ qui est proportionnelle à $\pi (x)$.

On part d'une valeur $x_{0}$. À partir de cette valeur, on détermine une valeur $x'$ avec un générateur pseudo-aléatoire utilisant une distribution de probabilité $q$. Dans le cas de l'algorithme original de Metropolis, $q$ est symétrique (on prend par exemple une distribution normale centrée sur $x_{0}$) ; Hastings a généralisé cet algorithme à une distribution $q$ dissymétrique.

Puis, on calcule le rapport de probabilité $\alpha$ entre $x'$ et $x_{0}$ :

$\alpha ={\frac {f(x')}{f(x_{0})}}={\frac {\pi (x')}{\pi (x_{0})}}$

Alors :

• si $\alpha \geq 1$, on prend $x_{1}=x'$
• si $\alpha <1$, alors avec probabilité $1-\alpha$, on prend $x_{1}=x_{0}$

Et l'on recommence de manière itérative.

On a donc une chaîne de Markov, puisque l'état de $x_{i}$ ne dépend que de $x_{i-1}$, et après un « grand nombre » d'itérations, les $x_{i}$ suivent la distribution $\pi$.

Cas général

De toutes les familles de méthodes MCMC, la plus générale est sans doute l'algorithme Metropolis-Hastings, dans le sens qu’il impose le moins de conditions sur la densité cible. À partir de la densité cible $\pi (x)$ (possiblement en grandes dimensions), on choisit une densité instrumentale conditionnelle $q(x,y)=q(x|y)$ à partir de laquelle il est assez facile de simuler. Commençant avec une valeur (possiblement vectorielle) $x_{0}$, l’algorithme passe au travers des étapes suivantes à chaque itération. Sachant que la chaîne est à l’état $x_{t}$ à la $t^{e}$ itération,

• générer $y_{t+1}$ $\sim$ $q(.,x_{t})$

• Calculer la probabilité d’acceptation $\alpha (x_{t},y_{t+1})=\min \left\{{\frac {\pi (y_{t+1})q(x_{t},y_{t+1})}{\pi (x_{t})q(y_{t+1},x_{t})}},1\right\}\,\!.$

• prendre $x_{t+1}={\begin{cases}y_{t+1},&{\text{avec probabilité}}\,\,\alpha \\x_{t},&{\text{avec probabilité}}\,\,1-\alpha \end{cases}}$

En recommençant ces étapes pour $t$ allant de $0$ à $N$.

Cas symétrique

Un cas particulier courant de l'algorithme est celui où $q$ est symétrique (i.e., $q(x,y)=q(y,x)$). Dans ce cas, l'algorithme se déplace de $x_{t}$ en $x$

• avec probabilité $1$ si $\pi (x)\geq \pi (x_{t})$ ;
• avec probabilité ${\frac {\pi (x)}{\pi (x_{t})}}$ sinon (et reste en $x_{t}$ avec la probabilité restante).

Voir aussi

• 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