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

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

Soit $X =(X i, i \in S)$ une variable de loi $π$ dans l'espace de sites $S =⟦1; n ⟧$ vers l'espace des états $Ω$ . Pour $x = (x 1;\dots; x n)\in Ω$ et les densités conditionnelles $π i (x i | x \neg i)$ où $x \neg i = (x j, j \neq i), i \in S$ , on construit l'échantillonneur de Gibbs sur les noyaux $π$ -invariants : $P i (x, y) = π i (y i | x \neg i) 1 (x \neg i = y \neg i)$ .

Échantillonneur par balayage systématique[modifier | modifier le code]

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

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

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

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)

Portail des probabilités et de la statistique