Algorithme de Metropolis-Hastings

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 à 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[modifier | modifier le code]

La première version de l'algorithme est décrite dans un article de 1953 par Nicholas Metropolis, Arianna W. Rosenbluth, Marshall Rosenbluth (en), Augusta H. Teller, et Edward Teller[1].

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[2].

Approche intuitive[modifier | modifier le code]

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 par exemple la méthode de rejet —, avec une distribution de probabilité π. Nous sommes dans le cas où il n'est pas simple de générer directement une suite de vecteurs suivant cette distribution π. Par ailleurs, on ne connaît pas nécessairement cette distribution π, il suffit de connaître une fonction ƒ(x) qui est proportionnelle à π(x).

On part d'une valeur x0. À 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 x0) ; Hastings a généralisé cet algorithme à une distribution q dissymétrique.

Puis, on calcule le rapport de probabilité α entre x' et x0 :

α = ƒ(x')/ƒ(x0) = P(x')/P(x0).

Alors :

  • si α ≥ 1, on prend x1 = x' ;
  • si α < 1, on prend x1 = x0.

Et l'on recommence de manière récursive.

On a donc une chaîne de Markov, puisque l'état de xi ne dépend que de xi - 1 ; et après un « grand nombre » d'itérations, les xi suivent la distribution π.

Cas général[modifier | modifier le code]

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(y|x) à 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(y_{t+1},x_t)}{\pi(x_t)q(x_t,y_{t+1})},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[3].

Cas symétrique[modifier | modifier le code]

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[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (en) N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller et E. Teller, « Equations of State Calculations by Fast Computing Machines », Journal of Chemical Physics, vol. 21, no 6,‎ 1953, p. 1087–1092.
  2. W.K. Hastings, « Monte Carlo Sampling Methods Using Markov Chains and Their Applications », Biometrika, vol. 57, no 1,‎ 1970, p. 97–109.
  3. Vanessa Bergeron Laperrière (Été 2010), (supervisée par Mylène Bédard), L’Algorithme Metropolis-Hastings Projet de recherche CRSNG, Département de Mathématiques et Statistique Université de Montréal.