Une méthode d'échantillonnage «d'importance Gibbs» fonctionnerait-elle?

8

Je soupçonne que c'est une question assez inhabituelle et exploratoire, alors soyez indulgent avec moi.

Je me demande si l'on pourrait appliquer l'idée de l'échantillonnage d'importance à l'échantillonnage de Gibbs. Voici ce que je veux dire: dans l'échantillonnage de Gibbs, nous modifions la valeur d'une variable (ou d'un bloc de variables) à la fois, en échantillonnant à partir de la probabilité conditionnelle étant donné les variables restantes.

Cependant, il peut ne pas être possible ou facile d'échantillonner à partir de la probabilité conditionnelle exacte. Au lieu de cela, nous échantillonnons à partir d'une distribution de proposition et utilisons, par exemple, Metropolis-Hastings (MH).q

Jusqu'ici tout va bien. Mais voici une voie divergente: que se passe-t-il si nous, au lieu d'utiliser MH, utilisons la même idée utilisée dans l'échantillonnage d'importance, à savoir que nous échantillonnons à partir de et gardons un poids d'importance de l'échantillon actuel?qp/q

Plus en détail: supposons que nous ayons des variables et une distribution factorisée sorte que . Nous conservons la probabilité de proposition utilisée pour échantillonner la valeur actuelle de chaque variable . À chaque étape, nous modifions un sous-ensemble des variables et mettons à jour (seuls les facteurs de et qui sont affectés). Nous prenons les échantillons et leur poids d'importance pour calculer les statistiques qui nous intéressent.x1,,xnϕ1,,ϕmpi=1mϕiqixip(x)/q(x)pq

Cet algorithme serait-il correct? Si non, des raisons claires pourquoi? Intuitivement, cela a du sens pour moi car il semble faire la même chose que l'échantillonnage d'importance, mais avec des échantillons dépendants à la place.

J'ai mis en œuvre cela pour un modèle de marche aléatoire gaussien et j'ai observé que les poids deviennent de plus en plus petits (mais pas monotones), de sorte que les échantillons initiaux finissent par avoir trop d'importance et dominent la statistique. Je suis assez certain que l'implémentation n'est pas boguée, car à chaque étape, je compare le poids mis à jour à un calcul explicite en force brute de celui-ci. Notez que les poids ne descendent pas indéfiniment à zéro, car ils sont où et sont tous deux des produits d'un nombre fini de densités, et chaque échantillon est obtenu à partir d'une distribution normale qui ne sera que rarement nulle.p/qpq

J'essaie donc de comprendre pourquoi les poids baissent comme ça, et si c'est une conséquence du fait que cette méthode n'est pas correcte.


Voici une définition plus précise de l'algorithme, appliqué à une marche aléatoire gaussienne sur les variables . Le code suit ci-dessous.X1,,Xn

Le modèle est simplement , avec fixé à .XiN(Xi1,σ2),i=1,,nX00

Le poids de l'échantillon actuel est , où sont les densités gaussiennes et sont les distributions à partir desquelles les valeurs actuelles ont été échantillonnées. Initialement, nous échantillonnons simplement les valeurs de manière directe, donc et le poids initial est .ip(xi)iq(xi)pqq=p1

Ensuite, à chaque étape, je choisis pour changer. une nouvelle valeur pour partir de , donc cette densité devient la nouvelle distribution de proposition utilisée pour .j{1,,n}xjXjN(Xj1,σ2)Xj

Pour mettre à jour le poids, je le divise par les densités et de l'ancienne valeur selon et , et multipliez par les densités et de nouvelle valeur selon et . Cela met à jour le numérateur du poids.p(xj|xj1)p(xj+1|xj)xjxj1xj+1p(xj|xj1)p(xj+1|xj)xjxj1xj+1p

Pour mettre à jour le dénominateur , je multiplie le poids par l'ancienne proposition (le supprimant ainsi du dénominateur) et je le divise par .qq(xj)q(xj)

(Parce que partir de la normale centrée sur , est toujours égal à donc ils annulent et l'implémentation ne pas vraiment les utiliser).xjxj1q(xj)p(xj|xj1)

Comme je l'ai mentionné précédemment, dans le code, je compare ce calcul de poids incrémentiel au calcul explicite réel juste pour être sûr.


Voici le code de référence.

println("Original sample: " + currentSample);
int flippedVariablesIndex = 1 + getRandom().nextInt(getVariables().size() - 1);
println("Flipping: " + flippedVariablesIndex);
double oldValue = getValue(currentSample, flippedVariablesIndex);
NormalDistribution normalFromBack = getNormalDistribution(getValue(currentSample, flippedVariablesIndex - 1));
double previousP = normalFromBack.density(oldValue);
double newValue = normalFromBack.sample();
currentSample.set(getVariable(flippedVariablesIndex), newValue);
double previousQ = fromVariableToQ.get(getVariable(flippedVariablesIndex));
fromVariableToQ.put(getVariable(flippedVariablesIndex), normalFromBack.density(newValue));
if (flippedVariablesIndex < length - 1) {
    NormalDistribution normal = getNormalDistribution(getValue(currentSample, flippedVariablesIndex + 1));
    double oldForwardPotential = normal.density(oldValue);
    double newForwardPotential = normal.density(newValue);
    // println("Removing old forward potential " + oldForwardPotential);
    currentSample.removePotential(new DoublePotential(oldForwardPotential));
    // println("Multiplying new forward potential " + newForwardPotential);
    currentSample.updatePotential(new DoublePotential(newForwardPotential));
}

// println("Removing old backward potential " + previousP);
currentSample.removePotential(new DoublePotential(previousP));
// println("Multiplying (removing from divisor) old q " + previousQ);
currentSample.updatePotential(new DoublePotential(previousQ));

println("Final sample: " + currentSample);
println();

// check by comparison to brute force calculation of weight:
double productOfPs = 1.0;
for (int i = 1; i != length; i++) {
    productOfPs *= getNormalDistribution(getValue(currentSample, i - 1)).density(getValue(currentSample, i));
}
double productOfQs = Util.fold(fromVariableToQ.values(), (p1, p2) -> p1*p2, 1.0);
double weight = productOfPs/productOfQs;
if (Math.abs(weight - currentSample.getPotential().doubleValue()) > 0.0000001) {
    println("Error in weight calculation");
    System.exit(0);
}
user118967
la source
L'échantillonnage d'importance ne fournit pas d'échantillons de la distribution cible (dans ce cas, les conditions complètes de ). Ainsi, la dynamique du noyau de Markov qui produit une convergence MCMC ne tient pas. Sans regarder votre code, je ne vois pas pourquoi les poids vont à 0.ϕi
Greenparker
Merci. Je suppose que je devrai me plonger dans les théorèmes de la convergence MCMC. J'ai inclus le code au cas où, c'est assez simple. Merci.
user118967
1
Au lieu d'inclure le code brut (ou en plus), pouvez-vous expliquer comment vous implémentez l'algorithme? Quelle est la distribution cible, quelles sont les conditions complètes, quelle est la distribution de la proposition, comment combinez-vous les poids, etc. etc.
Greenparker
Je vous remercie. Je l'ai fait, faites-le moi savoir si cela prête à confusion quelque part.
user118967
@ Xi'an: ici, l'échantillonnage d'importance est appliqué au retournement d'une seule variable. Au lieu d'accepter la proposition ou non comme dans Metropolis Hastings, nous l'acceptons toujours mais gardons une mesure d'importance de ce retournement en divisant la probabilité p par la proposition q pour la variable retournée.
user118967

Réponses:

4

C'est une idée intéressante, mais j'y vois plusieurs difficultés:

  1. contrairement à l'échantillonnage d'importance standard, ou même à l'échantillonnage d'importance métropolisée, la proposition n'agit pas dans le même espace que la distribution cible, mais dans un espace de plus petite dimension, de sorte que la validation n'est pas claire [et peut imposer de maintenir les pondérations entre les itérations, ce qui fait face à la dégénérescence]
  2. les constantes de normalisation manquantes dans les conditionnelles complètes changent à chaque itération mais ne sont pas prises en compte [voir ci-dessous]
  3. les poids ne sont pas limités, en ce sens que le long des itérations, il y aura éventuellement des simulations avec un poids très important, à moins que l'on garde une trace de la dernière occurrence d'une mise à jour pour le même indice , ce qui peut entrer en conflit avec la validation markovienne de l'échantillonneur Gibbs . L'exécution d'une expérience modeste avec et itérations montre une gamme de poids de à .jn=2T=1037.656397e-073.699364e+04

Pour entrer dans les détails, considérons une cible bidimensionnelle , y compris la constante de normalisation appropriée, et implémentons l'importance de l'échantillonneur Gibbs avec les propositions et . Les poids d'importance appropriés [dans le sens de produire l'espérance correcte, c'est-à-dire un estimateur sans biais, pour une fonction arbitraire de ] pour les simulations successives sont soit où et sont les marginaux de . Ou équivalent p(,)qX(|y)qY(|x)(X,Y)

p(xt,yt1)qX(xt|yt1)mY(yt1)orp(xt1,yt)qY(yt|xt1)mX(xt1)
mX()mY()p(,)
pX(xt|yt1)qX(xt|yt1)orpY(yt|xt1)qY(yt|xt1)
Dans les deux cas, cela nécessite les densités marginales [insolubles] de et sous la cible .XYp(,)

Il vaut la peine de comparer ce qui se passe ici avec l' algorithme Metropolis pondéré en parallèle . (Voir par exemple Schuster und Klebanov, 2018. ) Si la cible est à nouveau et que la proposition est , le poids d'importance est correct [pour produire une estimation non biaisée] et ne met pas à jour le poids précédent mais recommence à zéro à chaque itération.p(,)q(,|x,y)

p(x,y)q(x,y|x,y)

(C.) Une correction de l'importance d'origine proposée par Gibbs consiste à proposer une nouvelle valeur pour le vecteur entier, par exemple, , à partir de la proposition de Gibbs , car alors l'importance poids est correcte [manque une éventuelle normalisation constante qui est maintenant vraiment constante et ne porte pas sur les précédentes itérations de Gibbs] .(x,y)qX(xt|yt1)qY(yt|xt)

p(xt,yt)qX(xt|yt1)qY(yt|xt)

Une dernière note: pour la cible de marche aléatoire considérée dans le code, la simulation directe est réalisable en cascade: simulez , puis étant donné , & tc.X1X2X1

Xi'an
la source