Upload
bigmc
View
531
Download
1
Embed Size (px)
DESCRIPTION
Olivier Féron's talk at BigMC March 2011 (French)
Citation preview
Échantillonnage de champs gaussiens de grandedimension
Olivier Féron1 & François Orieux2 & Jean-François Giovannelli3
1 EDF R&D et Laboratoire de Finance des Marchés de l’Énergie, UniversitéParis-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris,
2 Laboratoire des Signaux et Systèmes (CNRS – SUPELEC – Univ. Paris-Sud 11) SUPELEC,Plateau de Moulon, 91192 Gif-sur-Yvette Cedex,
3 Laboratoire d’Intégration du Matériau au Système, Équipe Signal-Image,Université de Bordeaux 1, 33405 Talence, France,
Séminaire BigMC, mars 2011 1 / 26
Sommaire
Introduction : contexte applicatif
Algorithme de Perturbation-Optimisation
Illustration en super-résolution d’image
Travaux en cours
Conclusions et perspectives
Séminaire BigMC, mars 2011 2 / 26
Résolution de problèmes inverses dans un cadrebayésien
Contexte :
Modèle direct linéaire y = Hx+ bH dépend de θ éventuellement inconnu
Lois a priori sur b et x gaussiennes conditionnellement θ
Inversion :
Estimer conjointement x et θ à partir de p(x,θ|y)
p(x,θ|y) difficile à manipuler
Approche possible : échantillonneur de Gibbs=⇒ problème d’échantillonnage de p(x|θ,y)
Séminaire BigMC, mars 2011 3 / 26
Échantillonnage de champ gaussien
p(x|θ,y) est gaussienne de matrice de covariancedépendant de θ et Hnon creuse en généralde très grande dimension (le nombre de pixel de x)
Méthodes d’échantillonnage existantes :Échantillonnage pixel par pixelAlgorithme de Hastings-MetropolisÉchantillonnage par FFT (si H est circulant)
ContributionMéthode d’échantillonnage par un algorithme de typePerturbation-Optimisation, valable quel que soit H.
Séminaire BigMC, mars 2011 4 / 26
Loi a posteriori conditionnelle
Modèle direct : y = Hx+ b
Hypothèses :H linéaire (dépendant de θ)b|θ ∼ N (0,Rb)x|θ ∼ N (mx,Rx)
Loi a posteriori p(x|θ,y) ∼ N (mpostx ,Rpost
x )
Rpostx =
(H tR−1
b H +R−1x
)−1
mpostx = Rpost
x
(H tR−1
b y +R−1x mx
)
mpostx est le minimum d’un critère quadratique :
mpostx = arg min
x{J(x|y,mx,θ)}
J(x|y,mx,θ) = ‖y −Hx‖2R−1
b
+ ‖x−mx‖2R−1
x
Séminaire BigMC, mars 2011 5 / 26
Perturbation de critère
Tirage aléatoire indépendant suivant les lois a priori
y ∼ N (y,Rb)
mx ∼ N (mx,Rx)
Minimiseur :
x = arg minx{J(x|y, mx,θ)}
J(x|y, mx,θ) = ‖y −Hx‖2R−1
b
+ ‖x− mx‖2R−1
x
x = Rpostx
(H tR−1
b y +R−1x mx
)Proposition
x ∼ N(mpost
x ,Rpostx
)Séminaire BigMC, mars 2011 6 / 26
Preuve
x = Rpostx
(H tR−1
b y +R−1x mx
)Moyenne de x :
E [x] = Rpostx
(H tR−1
b E[y] +R−1x E[mx]
)= mpost
x
Covariance de x :
E[xxt] = Rpostx E
[ (H tR−1
b y +R−1x mx
)(H tR−1
b y +R−1x mx
)t ]Rpost
x
= Rpostx
[H tR−1
b E[yyt]R−1
b H +R−1x E
[mxm
tx
]R−1
x
]Rpost
x
= Rpostx
[H tR−1
b (yyt +Rb)R−1b H +R−1
x (mxmxt +Rx)R−1
x
]Rpost
x
= E [x]E [x]t +Rpostx
[H tR−1
b H +R−1x
]Rpost
x
= E [x]E [x]t +Rpostx
V[x] = Rpostx
Séminaire BigMC, mars 2011 7 / 26
Algorithme de Perturbation - Optimisation
Objectif : tirer un échantillon x ∼ N(mpost
x ,Rpostx
)Algorithme proposé
Étape P (perturbation) : tirage de y et mx indépendamment suivant
y ∼ N (y,Rb)
mx ∼ N (mx,Rx)
Étape O (optimisation) : minimisation du critère
x = arg minx{J(x|y, mx,θ)}
Conditions d’utilisationlois a priori facilement échantillonnableslois a priori gaussiennes conditionnellement à θ (loisgaussiennes, modèles à variable cachée,...)
Séminaire BigMC, mars 2011 8 / 26
Applications
Algorithme simple à mettre en œuvreÉchantillonnage de bruits gaussiensOptimisation d’un critère quadratique
Double intérêt : un seul algorithme pour atteindre la moyenne etla variance cibles
Possibilité de relierles problèmes inverses de reconstruction d’imagesles méthodes MCMC
Possibilité d’accéderà des méthodes d’estimation non-superviséesà la distribution entière des inconnues (pour des écart types, desintervalles de confiance,...)
Séminaire BigMC, mars 2011 9 / 26
Applications : Tomographie micro-onde
Reconstruction d’image en tomographie micro-onde
y = GSw + ε
w = XE inc +XGDw + η
Modèle non linéaire reliant l’image d’intérêt x aux donnéesobservées yModèle bilinéaire par rapport aux inconnues x et w (courantsinduits)
Loi a priori de mélange de gaussiennes pour x
p(x|z) = N (mz ,Σz)
Loi a posteriori conditionnellement gaussiennes pourl’image xles courants induits w
Séminaire BigMC, mars 2011 10 / 26
Illustration en super-résolution d’image
Vraie image Une image basse résolution
Modèle direct : y = PHx+ b
y ∈ RM : images de basse résolution −→ donnéesH : matrice de convolutionP : matrice de sous-échantillonnagex ∈ RN : image originale
Hypothèsesb ∼ N (0, γ−1
b I)x ∼ N (0, γ−1
x DtD), avec D opérateur laplacien.a priori de Jeffreys pour γb et γx
Séminaire BigMC, mars 2011 11 / 26
Illustration en super-résolution
Loi a posteriori jointe :
p(x, γb, γx|y) ∝ γM/2−1b γ(N−1)/2−1
x exp[−γb
2‖y − PHx‖2
]exp
[−γx
2‖Dx‖2
].
Échantillonneur de Gibbs pour l’inversion non supervisée
1 Initialisation avec k = 1 et x(0) = x0
2 Tirage de γ(k)b ∼ G
(1 + M/2,2/
∥∥y − PHx(k−1)∥∥2)
3 Tirage de γ(k)x ∼ G
(1 + (N − 1)/2,2/
∥∥Dx(k−1)∥∥2)
4 Tirage x(k) ∼ N (mpostx ,Rpost
x ) par perturbation-optimisation
5 k = k + 1
6 Retour en 2 ou arrêt si respect d’un critère d’arrêt
Séminaire BigMC, mars 2011 12 / 26
Illustration en super-résolution
Réconstruction d’image
Vraie image Une image basse résolution Image estimée
Séminaire BigMC, mars 2011 13 / 26
Illustration en super-résolution
Comportement de la chaîne des hyperparamètres
γb γx
Séminaire BigMC, mars 2011 14 / 26
Généralisation
Objectif : générer un échantillon x ∼ N(Q−1B,Q−1), avec
Q =K∑
k=1
M tkR
−1k Mk
B =
(K∑
k=1
M tkR
−1k µk
)
Perturbation-Optimization algorithm
1 Step P (Perturbation) : Générer les variables gaussiennes indépendantesζk , k = 1, . . . , K suivant
ζk ∼ N (µk ,Rk ), ∀k = 1, . . . K
2 Step O (Optimisation) : Calculer le minimiseur x du critère
J(x|ζ1, . . . , ζK ) =K∑
k=1
(ζk −Mkx)tR−1k (ζk −Mkx)
Séminaire BigMC, mars 2011 15 / 26
Travaux en cours
Rapprochement avec l’algorithme de Langevin
Idée sous-jacente : alléger l’algorithme d’optimisation par unesimple descente de gradient.
Algorithme de Hastings-MetropolisProcessus discret de diffusion ayant pour loi invariante la loi cible
Étude de convergence en prenant en compte le critère d’arrêt del’algorithme d’optimisation.
Séminaire BigMC, mars 2011 16 / 26
Algorithme de Langevin
Processus de Langevin
dXt = −12∇J(Xt)dt + dBt
Loi stationnaire du processus : π(x) = C exp {−J(x)}En pratique : discrétisation du processus de diffusion
x(t+1) = x(t) − τ2
2∇J(x(t))
+ τεt
Problème : la loi invariante n’est plus π.
Séminaire BigMC, mars 2011 17 / 26
Algorithme de Langevin
Solution : considérer x(t+1) comme candidat dans unalgorithme de Hastings-Metropolis.
x(t+1) ∼ N(x(t) − τ
2∇J(x(t))
; τ2I)
probabilité d’acceptation
ρ(x(t+1),x(t)) =exp
{−J(x(t+1))
}exp
{−J(x(t))
} ...
...exp
{− 1
τ2 ‖x(t) − x(t+1) − τ2∇J(x(t+1))‖2
}exp
{− 1
τ2 ‖x(t+1) − x(t) − τ2∇J(x(t))‖2
}
Séminaire BigMC, mars 2011 18 / 26
Algorithme de Langevin
Cas particulier : générer un échantillon x ∼ N(Q−1B,Q−1),
avec
Q =K∑
k=1
M tkR
−1k Mk , B =
(K∑
k=1
M tkR
−1k µk
)
π(x) ∝ exp {−J(x)}, avec
J(x) =12
K∑k=1
(µk −M t
kx)tR−1
k
(µk −M t
kx)
∇J(x) = Qx−B
Échantillon candidat
xp = xc −τ
2(Qxc −B) + ε, ε ∼ N (0, τ2I)
Séminaire BigMC, mars 2011 19 / 26
Algorithme PO (1 étape de descente)
Critère perturbé
ζk ∼ N (µk ,Rk ), ∀k = 1, . . .K
J(x) =12
K∑k=1
(ζk −Mkx)tR−1k (ζk −Mkx)
∇J(x) = Qx−B + ε
= ∇J(x) + ε
avecε ∼ N (0,Q)
Échantillon candidat
xp = xc − τ(Qxc −B) + ε, ε ∼ N (0, τ2Q)
Séminaire BigMC, mars 2011 20 / 26
Algorithme PO (1 étape de descente)
Probabilité d’acceptation
ρ(xp,xc) = exp{−(xt
pQxp − xtcQxc − 2Bt(xp − xc)
)...
−1τ(xp − xc)
t(xp + xc − 2Q−1B)}
Nécessite le calcul de Q−1B, i.e. la moyenne de la loi cible.Dans le cas particulier où la loi cible est N (0,Q−1), alorsl’algorithme de Hastings Metropolis est utilsable.
Séminaire BigMC, mars 2011 21 / 26
Convergence de la marche aléatoire
Loi ciblex ∼ N (Q−1B,Q−1)
Processus de marche aléatoire
x(t+1) = x(t) − τ(Qx(t) −B) + εt , εt ∼ N (0, τ2Q)
Proposition
La loi invariante du processus précédent est N (µ,R), avec
µ = Q−1B
R = τ(2I − τQ)−1
Un exemple qui montre que la loi invariante du processus deLangevin discrétisé est différente de celle du processus continu.Ce processus peut donner un estimateur de la moyenne cible.
Séminaire BigMC, mars 2011 22 / 26
Convergence de la marche aléatoire
moyenneµ = (I − τQ)µ+ τB ⇒ µ = Q−1B
varianceR telle que R = (I − τQ)R(I − τQ) + τ2QPrenons R = τ(2I − τQ)−1
(I − τQ)R = (2I − τQ)R−R = τI −R⇒ (I − τQ)R(I − τQ) = (τI −R)(I − τQ)
= τ(I − τQ)−R(I − τQ)
= τI − τ2Q−R(2I − τQ) +R
= R− τ2Q
Séminaire BigMC, mars 2011 23 / 26
Marche aléatoire adaptée
Loi ciblex ∼ N (Q−1B,Q−1)
Processus de marche aléatoire
x(t+1) = x(t) − τ(Qx(t) −B) + ε(t),
objectif : trouver la variance de ε(t) telle que la loi invariante dela marche aléatoire soit la loi cible.
Proposition
Si ε(t) ∼ N (0, τ(2I − τQ)), Alors la marche aléatoire définie par
x(t+1) = x(t) − τ(Qx(t) −B) + ε(t)
admet pour loi invariante la loi N (Q−1B,Q−1)
Séminaire BigMC, mars 2011 24 / 26
Marche aléatoire adaptée
moyenneµ = (I − τQ)µ+ τB ⇒ µ = Q−1B
varianceR telle que
R = (I − τQ)R(I − τQ) + 2τI − τ2Q
⇒ τ2QRQ− τQR− τRQ+ 2τI − τ2Q = 0
R = Q−1 est solution.
Séminaire BigMC, mars 2011 25 / 26
Conclusion et perspectives
Communication :
Journées de statistiques (Marseilles 2010)Article court pour IEEE Signal Processing Letter
Perspectives
Étude de convergence du maximum numériquePoursuite vers un algorithme « allégé » et étude de convergenceCommunication vers la communauté statistique
Séminaire BigMC, mars 2011 26 / 26