Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Échantillonnage de Gibbs
Résumé
L' 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).
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(i) suivant une distribution de probabilité π ;
pour simplifier le problème, on détermine une distribution qx(i) permettant de générer aléatoirement x(i + 1) à partir de x(i).
La spécificité de l'échantillonnage de Gibbs consiste à « découper » qx(i) en n probabilités conditionnelles :
la première composante du vecteur, x(i + 1)1, est générée à partir de la probabilité conditionnelle π(x1|x(i)2, x(i)3, ..., x(i)n) ;
la seconde composante du vecteur, x(i + 1)2, est générée à partir de la probabilité conditionnelle π(x2|x(i + 1)1, x(i)3, ..., x(i)n) ;
la composante j du vecteur, x(i + 1)j, est générée à partir de la probabilité conditionnelle π(xj|x(i + 1)1, x(i + 1)2, ..., x(i + 1)j - 1, x(i)j + 1, ..., x(i)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.
Soit une variable de loi dans l'espace de sites vers l'espace des états . Pour et les densités conditionnelles où , on construit l'échantillonneur de Gibbs sur les noyaux -invariants : .
On visite séquentiellement, en relaxant à chaque pas la valeur suivant la loi conditionnelle à l'état courant. La transition de à s'écrit:
Soit une probabilité jamais nulle sur . À chaque pas, un site est choisi avec la probabilité et la valeur y est relaxée selon la loi conditionnelle à l'état courant. La transition s'écrit:
Si est fini, la transition est positive strictement et la vitesse de convergence de est exponentielle.
peut être connu à un facteur multiplicatif près.
Catégorie:Algorithme
Catégorie:Processus stochastique
Catégorie:Physique statistique
Catégorie:Probabilités
Catég
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.