Échantillonnage de Gibbs

Échantillonnage de Gibbs

Type	Algorithme
Inventeurs	Stuart Geman (en), Donald Geman (en)
Date d'invention	1984
Nommé en référence à	Josiah Willard Gibbs
Aspect de	Méthode de Monte-Carlo par chaînes de Markov

L'échantillonnage de Gibbs est une méthode MCMC. Étant donné 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).

Introduction

Comme pour toutes les méthodes de Monte-Carlo à chaîne de Markov,

• on se place dans un espace vectoriel Ɛ de dimension finie n ;
• on veut générer aléatoirement N vecteurs x⁽ⁱ⁾ suivant une distribution de probabilité π ;
• pour simplifier le problème, on détermine une distribution q_x⁽ⁱ⁾ permettant de générer aléatoirement x^{(i + 1)} à partir de x⁽ⁱ⁾.

La spécificité de l'échantillonnage de Gibbs consiste à « découper » q_x⁽ⁱ⁾ en n probabilités conditionnelles :

• la première composante du vecteur, x^{(i + 1)}₁, est générée à partir de la probabilité conditionnelle π(x₁|x⁽ⁱ⁾₂, x⁽ⁱ⁾₃, …, x⁽ⁱ⁾_n) ;
• la seconde composante du vecteur, x^{(i + 1)}₂, est générée à partir de la probabilité conditionnelle π(x₂|x^{(i + 1)}₁, x⁽ⁱ⁾₃, …, x⁽ⁱ⁾_n) ;
• la composante j du vecteur, x^{(i + 1)}_j, est générée à partir de la probabilité conditionnelle π(x_j|x^{(i + 1)}₁, x^{(i + 1)}₂, …, x^{(i + 1)}_{j - 1}, x⁽ⁱ⁾_{j + 1}, …, x⁽ⁱ⁾_n).

On remplace donc le problème de génération aléatoire de x^{(i + 1)} par n problèmes que l'on espère plus simples.

Principe

Soit X=(X_i, i∈S) une variable de loi π dans l'espace de sites S=⟦1;n⟧ vers l'espace des états Ω. Pour x = (x₁;…;x_n)∈Ω et les densités conditionnelles π_i(x_i|x_¬i) où x_¬i = (x_j, j≠i), i∈S, on construit l'échantillonneur de Gibbs sur les noyaux π-invariants : P_i(x,y) = π_i(y_i|x_¬i)1(x_¬i = y_¬i).

Échantillonneur par balayage systématique

On visite S séquentiellement, en relaxant à chaque pas i la valeur suivant la loi π_i conditionnelle à l'état courant. La transition de x à y s'écrit: $P\left(x;y\right)=\prod _{i=1}^{n}\pi _{i}\left(y_{i}|y_{1},\dotsc ,y_{i-1},x_{i+1},\dotsc ,x_{n}\right)$

Échantillonneur par balayage aléatoire

Soit ν une probabilité jamais nulle sur S. À chaque pas, un site i est choisi avec la probabilité ν_i>0 et la valeur y est relaxée selon la loi conditionnelle π_i à l'état courant. La transition s'écrit: $P\left(x;y\right)=\sum _{i=1}^{n}\nu _{i}\pi _{i}\left(y_{i}|x_{\neg {i}}\right)\mathbf {1} \left(x_{\neg i}=y_{\neg i}\right)$

Propriétés

• Si Ω est fini, la transition P est positive strictement et la vitesse de convergence de νP_k est exponentielle.
• π peut être connu à un facteur multiplicatif près.

Bibliographie

C. Gaetan et X. Guyon, chap. 9 « Simulation des modèles spatiaux », dans Jean-Jacques Droesbeke, Michel Lejeune et Gilbert Saporta, Analyse statistique des données spatiales : 10^e Journées d'étude en statistique, 4-8 novembre 2002, Marseille, Société française de statistique, Paris, Technip, 2006, 468 p. (ISBN 978-2-7108-0873-2, BNF 40225776)