Introduction à la méthode de Chaîne de Markov Monte Carlo

Introduction

Comment générer des nombres aléatoires suivant une distribution complexe, même sans en connaître la forme exacte ni la constante de normalisation ? C’est un défi que peut relever la méthode Chaîne de Markov Monte Carlo (CMMC). Cette approche combine deux concepts fondamentaux : les chaînes de Markov, qui génèrent des suites d’échantillons où chaque valeur dépend de la précédente, et la simulation Monte Carlo, qui utilise le hasard pour explorer un espace probabiliste. Dans cet article, nous expliquons le principe de la méthode CMMC et montrons comment elle permet d’échantillonner efficacement des distributions connues uniquement à une constante près. Nous illustrons son fonctionnement à travers un exemple simple utilisant l’algorithme de Metropolis-Hastings.

À propos de la méthode des chaînes de Markov Monte Carlo (CMMC)

La méthode Chaîne de Markov Monte Carlo (CMMC) est un outil puissant en mathématiques et en sciences des données. Elle permet de générer des échantillons selon une distribution complexe, même lorsque celle-ci n’est connue qu’à une constante multiplicative près, c’est-à-dire sans avoir besoin de son expression normalisée complète. CMMC combine deux concepts fondamentaux :

1. Les chaînes de Markov : un processus aléatoire où la probabilité de passer à un nouvel état dépend uniquement de l’état actuel, et non de l’historique complet. Sous certaines conditions, une chaîne de Markov admet une distribution stationnaire, vers laquelle elle converge au fil du temps.
2. La méthode de Monte Carlo : une technique statistique basée sur des simulations aléatoires, utilisée pour approximer des intégrales, des moyennes ou explorer des distributions complexes lorsqu’une solution analytique est difficile à obtenir.

L’idée clé de la méthode CMMC est de faire évoluer une chaîne de Markov dont la distribution stationnaire est celle que l’on souhaite échantillonner, en s’appuyant sur des tirages aléatoires dans l’esprit de la méthode Monte Carlo. En faisant évoluer cette chaîne suffisamment longtemps, les états générés suivent approximativement la distribution cible. Parmi les algorithmes de la méthode CMMC, Metropolis-Hastings est l’un des plus répandus.

Présentation des méthodes Metropolis simple et Metropolis-Hastings

La méthode Metropolis simple est une technique d’échantillonnage qui permet de générer des valeurs aléatoires suivant une distribution complexe, même lorsque cette distribution n’est connue qu’à une constante près. Autrement dit, elle fonctionne sans avoir besoin de connaître la constante de normalisation de la loi, ce qui est particulièrement utile lorsque celle-ci est difficile à calculer analytiquement.

Elle repose sur un principe simple : à partir d’un point initial, on propose un nouveau point en utilisant une distribution de proposition symétrique, puis on décide d’accepter ou non ce point en fonction de sa probabilité relative dans la distribution cible. Si le nouveau point est plus probable, on l’accepte. S’il est moins probable, on l’accepte avec une certaine probabilité. Cette approche permet, au fil du temps, de construire une chaîne de Markov dont les valeurs sont distribuées selon la loi souhaitée. La méthode Metropolis simple est un cas particulier de l’algorithme plus général appelé Metropolis-Hastings, qui permet d’utiliser des propositions asymétriques.

Voici comment fonctionne l’algorithme Metropolis-Hastings, étape par étape :

Étape 1 : Initialisation

• Choisir une valeur initiale \(x_0\)
• Définir une distribution de proposition \(q(x’ \mid x)\) (exemple : uniforme centrée autour de \(x\), pour notre exemple ci-après)

Étape 2 : Proposer un nouveau point

• À partir du point actuel x, on génère un candidat \(x’\) selon la distribution de proposition : \(x’ \sim q(x’ \mid x)\)

Étape 3 : Calcul du taux d’acceptation

On évalue à quel point \(x’\)est plus ou moins probable que \(x\), selon la distribution cible \(p(x)\), en tenant compte de la proposition \(q\) :

\(
\alpha = \min\left(1,\ \frac{p(x’) \cdot q(x \mid x’)}{p(x) \cdot q(x’ \mid x)}\right)
\)

Étape 4 : Décision d’acceptation

• Tirer un nombre aléatoire \(u \sim \text{Uniform}(0,1)\)
• Si \(u \leq \alpha\), accepter la proposition : \(x_{t+1} = x’\)
• Sinon, rester sur place : \(x_{t+1} = x\)

Étape 5 : Répéter

• Reprendre à l’étape 2 pour plusieurs itérations (souvent des milliers ou millions)
• Après une période de burn-in (début instable), les valeurs suivent la distribution cible \(p(x)\)

Comme évoqué précédemment, l’algorithme de Metropolis simple est un cas particulier de Metropolis-Hastings. Il s’applique lorsque la distribution de proposition \(q(x’ \mid x) \)est symétrique, c’est-à-dire que la probabilité de proposer \(x’\) à partir de \(x\) est la même que celle de proposer \(x\) à partir de \(x’\). Dans ce cas, les termes \(q\) se simplifient, et le taux d’acceptation devient : \( \alpha = \min\left(1,\ \frac{p(x’) }{p(x) }\right) \).

Dans ce cas, la décision d’acceptation repose uniquement sur la comparaison des valeurs \(p(x’)\) et \(p(x)\). Si le point proposé est plus probable selon la distribution cible, il est accepté. Sinon, il peut tout de même être accepté avec une certaine probabilité. Ce mécanisme permet à la chaîne de visiter aussi bien les zones très probables que les zones moins fréquentes, tout en respectant la forme de la distribution cible.

Exemple illustratif : échantillonnage à partir d’une loi normale

Pour comprendre comment fonctionne la méthode Metropolis-Hastings, rien de mieux qu’un exemple simple. Imaginons que nous souhaitons générer des échantillons aléatoires suivant une loi normale standard, c’est-à-dire de moyenne 0 et d’écart-type 1. Dans la réalité, on connaît parfaitement cette densité notée \(N(0,1)\), mais nous allons faire comme si nous ne connaissions que sa forme “non normalisée” :

$$ p(x) \propto \exp\left(-\frac{x^2}{2}\right)$$

L’objectif est de construire une chaîne de Markov dont l’état stationnaire correspond à cette densité \(N(0,1)\). L’algorithme Metropolis-Hastings va nous y aider. On commence par choisir un point de départ, par exemple \(x_0 = 0\) . À chaque étape, on propose un nouveau point \(x’\), tiré selon une distribution de proposition. Ici, on peut choisir une loi uniforme centrée autour du point actuel, comme \(x’ \sim U(x – \delta, x + \delta)\), où \(\delta\) est un paramètre que l’on fixe.

En répétant ce processus selon l’algorithme de Metropolis simple, on obtient finalement un histogramme des valeurs de \(x\). Le graphe ci-dessous montre que ces échantillons reproduisent fidèlement la forme de la densité normale standard. Cela illustre bien la puissance de la méthode Chaîne de Markov Monte Carlo (CMMC).

Conclusion

La méthode Metropolis-Hastings de la famille des techniques Chaîne de Markov Monte Carlo (CMMC) offre une solution pour échantillonner des distributions complexes, même lorsqu’elles sont connues seulement à une constante près. À travers notre exemple simple, nous avons vu comment des tirages successifs, guidés par des règles de probabilité bien définies, permettent de reconstruire fidèlement une distribution cible comme la loi normale standard.