Algorithme de Metropolis-Hastings

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

En statistique, l'algorithme de Métropolis-Hastings est une méthode MCMC. Étant donnée une distribution de probabilité sur un univers , cet algorithme définit une chaîne de Markov dont la distribution stationnaire est . Il permet ainsi de tirer aléatoirement un élément de selon la loi (on parle d'échantillonnage).

Un point essentiel de l'algorithme de Métropolis-Hasting est qu'il ne nécessite que la connaissance de à constante multiplicative près. En particulier, il n'est pas nécessaire de calculer la fonction de partition de , 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 , 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é . 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 qui est proportionnelle à .

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

Puis, on calcule le rapport de probabilité entre et  :

Alors :

  • si , on prend
  • si , alors avec probabilité , on prend

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

On a donc une chaîne de Markov, puisque l'état de ne dépend que de , et après un « grand nombre » d'itérations, les 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 (possiblement en grandes dimensions), on choisit une densité instrumentale conditionnelle à partir de laquelle il est assez facile de simuler. Commençant avec une valeur (possiblement vectorielle) , l’algorithme passe au travers des étapes suivantes à chaque itération. Sachant que la chaîne est à l’état à la itération,

  • générer
  • Calculer la probabilité d’acceptation
  • prendre

En recommençant ces étapes pour allant de à [3].

Cas symétrique[modifier | modifier le code]

Un cas particulier courant de l'algorithme est celui où est symétrique (i.e., ). Dans ce cas, l'algorithme se déplace de en

  • avec probabilité si  ;
  • avec probabilité sinon (et reste en 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,‎ , p. 1087–1092.
  2. W.K. Hastings, « Monte Carlo Sampling Methods Using Markov Chains and Their Applications », Biometrika, vol. 57, no 1,‎ , 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.