Processus Stochastiques - tourneret.perso.enseeiht.frtourneret.perso.enseeiht.fr/StochasticProcesses/slides_MCMC.pdf · Processus Stochastiques ... Alors, si U est uniforme sur [0,1],

Processus Stochastiques

Jean-Yves Tourneret(1)

(1) Universite of Toulouse, ENSEEIHT-IRIT-TeSA

Theme 1 : Analyse et Synthese de l’Information

[email protected]

Cours Mastere, 2010 – p. 1/41

Méthodes de simulation

Partie 1 : Bayes et Simulation

Partie 2 : Metropolis - Hastings

Partie 3 : L’échantillonneur de Gibbs

Partie 4 : Diagnostic de Convergence

Partie 5 : Segmentation de signaux stationnaires parmorceaux

Pour finir : Livres, Sites Webs, Pages perso, ...


Bibliographie

Christian P. Robert and George Casella, Monte CarloStatistical Methods, Springer-Verlag, New-York, 2ndEdition, 2004.


Cours 1 : Bayes et Simulation

1) Introduction : modèles statistiques

2) Maximum de vraisemblance

3) Méthodes Bayésiennes

4) Méthodes de base de simulation

5) Méthodes de Monte Carlo pour l’intégration

6) Méthodes numériques déterministes


Modèle Statistique (1)

Compromis entre

un modèle compliqué proche de la réalité qui peut induiredes méthodes d’estimation, de détection ou declassification non standards

un modèle simple qui conduit à des hypothèses commelinéarité, Gaussianité, ... mais qui peut être trop éloignédu phénomène physique étudié

Avec le développement de la puissance de calcul, desméthodes comme les méthodes de simulation peuvent êtreenvisagées plus facilement.


Modèle Statistique (2)

Parfois, on choisit un modèle simple mais la suppression decertaines informations rend le problème difficile :

Modèles de censure

yi = min{xi, c}

Modèles de mélanges

yi ∼ p1f1(x) + ... + pkfk(x)

Modèles stationnaires par morceaux

yi ∼ fk(x) si i ∈ [tk, tk+1[


Maximum de Vraisemblance

Définition : Pour un échantillon x = (x1, ..., xn) dedensité f(x|θ), la vraisemblance s’écrit :

L(x|θ) =n∏

i=1

f(xi|θ)

Propriétés asymptotiques : asymptotiquement sansbiais, convergent et efficace

Facile à comprendre et souvent facile à étudier

Mais pose problème pour de nombreux modèlesstatistiques


Exemple1 : loi Gamma, α connu

f(x|α, β) =xα−1e−x/β

Γ(α)βαIR+(x)

Log-vraisemblance :

ln L(x|α, β) = −n ln Γ(α) − nα ln β

+ (α − 1)

n∑

i=1

ln xi −1

β

n∑

i=1

xi

Estimateur du maximum de vraisemblance de β :

β =1

Nα

n∑

i=1

xi


Exemple2 : loi Gamma, α inconnu

Estimateur du maximum de vraisemblance

∂

∂αln L(x|α, β) = 0

∂

∂βln L(x|α, β) = 0

Équations non-linéaires faisant intervenir la fonctiondigamma !!


Exemple3 : loi de Student

f(x|θ, p, σ) ∝ 1

σ

(1 +

(x − θ)2

pσ2

)−p+12

Log-vraisemblance :

ln L(x|θ, p, σ) = −(

p + 1

2

)ln

(σ

2np+1

n∏

i=1

(1 +

(xi − θ)2

pσ2

))

possède n maxima locaux (p et σ2 connus)matlab: student


Modèles de censure

Loi de Weibull

f(x|α, β) = αβxα−1 exp(−βxα)IR+(x)

Données tronquées z = min(x, ω)

f(z|α, β, ω) = αβzαe−βzα

I]−∞,ω](z)+

(∫∞

ωαβzαe−βzα

dz

)δω(z)


Modèles de mélange

DéfinitionSupposons que xi suive la loi de densité fj(xi) avec laprobabilité pj :

f(xi) = p1f1(xi) + ... + pkfk(xi)

Vraisemblance

L(x|θ, p) =n∏

i=1

(p1f1(xi) + ... + pkfk(xi)

)

comporte kn termes. Donc les techniques classiquesd’optimisation sont inappropriées à une telle fonctionmultimodale.


Méthodes Bayésiennes

Vraisemblance

f(x|θ) =n∏

i=1

f(xi|θ)

Loi a priori sur θ

π(θ)

Loi a posteriori

f(θ|x) =f(x|θ)π(θ)∫f(x|θ)π(θ)dθ

où f(x) =∫

f(x|θ)π(θ)dθ est la loi marginale de x.


Inférence Bayésienne

On rencontre deux types de problèmes avec les méthodesd’estimation Bayésiennes

E[C(θ, θ(x)

)]=

∫ [∫C(θ, θ(x))f(θ,x)dx

]dθ

Des problèmes d’optimisation (coût 0 − 1) : estimateur dumaximum a Posteriori

θMAP(x) = arg max f(θ|x) = arg max f(x|θ)π(θ)

Des problèmes d’intégration (coût quadratique) :estimateur MMSE

θMMSE(x) = E[θ|x] =

∫θf(θ|x)dθ


Méthodes Bayésiennes


Exemple1 : le cas Gaussien

Données

f(x|µ, σ2) =

n∏

i=1

1√2πσ2

exp

(−(xi − µ)2

2σ2

)

Loi a priori : µ ∼ N (µ0, σ20)

π(µ) =1√2πσ2

0

exp

(−(µ − µ0)

2

2σ20

)

Loi a posteriori : µ|x ∼ N (µn, σ2n)

µn =

(nσ2

0

nσ20 + σ2

)1

n

n∑

i=1

xi +

(σ2

σ2 + nσ20

)µ0

matlab: BayesCours Mastere, 2010 – p. 16/41

Exemple2 : Loi de Cauchy

Données

f(x|µ, σ) =n∏

i=1

σ−1

[1 +

(xi − µ

σ

)2]

Loi a priori :

π(µ, σ) = σ−1

Loi a posteriori de µ

f(µ|x) ∝∫ ∞

0

σ−n−1

n∏

i=1

[

1 +

(xi − µ

σ

)2]

dσ

Donc, pas d’expression explicite de cette loi a posteriori !


Lois conjuguées

Définition : une loi a priori π(θ) est conjuguée si f(x|θ)et π(θ) appartiennent à la même famille de lois.

Cas Gaussien

f(x|m,σ2) ∝ 1

(σ2)n/2exp

[

− 1

2σ2

n∑

i=1

(xi − m)2

]

☞ loi conjuguée pour m : loi normale

m ∼ N (µ, β2)

☞ loi conjuguée pour σ2 : loi inverse gamma

π(σ2|κ, γ) ∝ 1

(σ2)κ+1exp

(− γ

σ2

)


Lois conjuguées

Motivation : simplifie le calcul de la loi a posteriori

Cas Particulier : lois impropres☞ π(θ) ∝ Cste

☞ Jeffreys prior π(σ2) ∝ 1σ2



Générateur uniformePour une fonction de répartition F définie sur R, on définitson inverse généralisée par

F−1(u) = inf{x;F (x) ≥ u}

Alors, si U est uniforme sur [0, 1], la variable aléatoireF−1(U) est de fonction de répartition F car

P [F−1(U) ≤ x] = P [U ≤ F (x)] = F (x)

Cette méthode nécessite de connaître l’inversegénéralisée de la fonction de répartition.



Certaines méthodes utilisent des propriétés spécifiques de laloi à simuler :

loi Exponentielle

X = −1

λln U, U ∼ U([0, 1])

la méthode de l’inverse généralisée donne X = − 1λ

ln (1 − U).

Loi Gamma et Beta

Y = −ba∑

j=1

ln Uj ∼ Ga(a, b), a ∈ N∗

Y =

∑aj=1 ln Uj

∑a+bj=1 ln Uj

∼ Be(a, b), a, b ∈ N∗



Méthode de Box MüllerSi U1 et U2 sont deux variables indépendantes uniformessur [0, 1], alors

Y1 =√−2 ln U1 cos(2πU2)

Y2 =√−2 ln U1 sin(2πU2)

sont des variables iid distribuées suivant une loi N (0, 1).

Loi de PoissonSi Xi ∼ E(λ) et N ∼ P(λ) alors

P [N = k] = P [X1 + ... + Xk ≤ 1 < X1 + ... + Xk+1]


Méthodes d’acceptation-rejet

Beaucoup de lois sont difficiles à simuler directementavec les méthodes précédentes

Il y a certaines applications où la loi à simuler f estconnue à une constante multiplicative près (méthodesBayésiennes)

☞ Une solution est de simuler à l’aide d’une loi deproposition g plus simple et d’utiliser un algorithmed’acceptation-rejet


Algorithme d’acceptation-rejet

Soit une loi d’intérêt de densité f et une loi de proposition dedensité g telle que

f(x) ≤ Mg(x)

sur le support de f . Alors, on peut simuler suivant f avecl’algorithme suivant

1) Générer X ∼ g et U ∼ U([0, 1])

2) Accepter Y = X si

U ≤ f(X)

Mg(X)

3) Retourner en 1) si rejet


Probabilité d’acceptation

P [X accepté] = P

[U ≤ f(X)

Mg(X)

]= E

[I{U≤ f(X)

Mg(X)}

]

= E

[E

[I{U≤ f(X)

Mg(X)}

]|X]

= E

[f(X)

Mg(X)

]

=

∫f(x)

Mg(x)g(x)dx =

1

M


loi de X

P [X < x|X accepté] =P [X < x,X accepté]

1/M

= MP

[X < x,U <

f(X)

Mg(X)

]

= ME

[I{X<x,U≤ f(X)

Mg(X)}

]

= ME

[E

[I{X<x,U≤ f(X)

Mg(X)}

]|X]

= ME

[I{X<x}

f(X)

Mg(X)

]

=

∫ x

−∞

f(x)

g(x)g(x)dx = F (x)


Remarques

Cet algorithme permet de simuler une densité connue àune const. multiplicative près, e.g. f(θ|x) ∝ f(x|θ)π(θ)

La probabilité d’acceptation est 1/M donc la valeur de M

règle l’efficacité (vitesse) de l’algorithme

Problème pour des densités à queues lourdes. Parexemple, on ne peut simuler une loi de Cauchy avec uneloi de proposition normale (mais on peut faire l’inverse !)

Utilisable pour un grand nombre de lois : N (0, 1), Ga(a, b),lois normales tronquées, ...


Exemple : Cauchy→ Normale

Loi cible

f(x) =1√2π

exp(−x2/2

)

Loi de proposition

g(x) =1

π

1

1 + x2

Choix de M

f(x)

g(x)=

√π

2(1 + x2)e−x2/2 ≤

√2π

e= 1.52

valeur atteinte en ±1. Proba d’acceptation 1/M ≃ 0.66.

matlab: accept-reject pour différentes valeurs de M


Intégration par la méthode de Monte Carlo

On cherche à évaluer

E[h(Θ)] =

∫

Ph(θ)f(θ)dθ,

où P est l’espace des paramètres, f est une densité connue et h est une fonction connue.

Solution : générer un échantillon (θ1, ..., θn) distribuésuivant f pour approcher cette intégrale :

E[h(Θ)] ≃ hm =1

m

m∑

j=1

h(θj),

Justification : loi forte des grands nombres

Erreur : O(

1√n

)(remember, curse of dimensionality!) Cste


Intervalles de confiance

Variance :

vm =1

m2

m∑

j=1

[h(θj) − hm]2

Loi asymptotique :

hm − E[h(Θ)]√vm

∼ N (0, 1)

☞ On peut déterminer des intervalles de confiance surles paramètres inconnus !


Exemple : Fonction de répartition

Définition :

F (θ) =

∫ θ

−∞

1√2π

e−t2/2dt

Approximation :

F (θ) =1

n

n∑

i=1

Iθi<θ,

où (θ1, ..., θn) est un échantillon généré avec l’algorithmede Box-Muller.

Remarque : La variance de F (θ) est F (θ)[1−F (θ)]n

, e.g. 14n

pour θ = 0. Donc, pour avoir une précision de 10−4, il fautun échantillon de taille n = 200 millions !


Échantillonnage d’importance

Définition :

E[h(Θ)] =

∫

P

[h(θ)

f(θ)

g(θ)

]g(θ)dθ,

qui permet de simuler suivant g.

Estimation : générer un échantillon (θ1, ..., θn) distribuésuivant g pour approcher cette intégrale :

E[h(Θ)] ≃ 1

m

m∑

j=1

f(θj)

g(θj)h(θj),


Choix de la loi de proposition

Loi g simple à simuler

Si le support de g contient celui de f , l’estimateurconverge vers ∫

Ph(θ)f(θ)dθ

La variance de l’estimateur est finie si

E

[h2(Θ)

f(Θ)

g(Θ)

]< ∞

Éviter les lois de proposition telles que supθ∈Pf(θ)g(θ)

= ∞1) pb si le support de f n’est pas inclus dans celui de g,

2) il existe une loi optimale minimisant la variance qui dépend de l’intégrale à calculer !


Exemple

Soit f la densité d’une loi de Student à ν degrés de liberté.Calcul de

I =

∫ ∞

a

θ5f(θ)dθ,

Simulation suivant f

Échantillonnage d’importance avec loi de Cauchy

Un changement de variables u = 1/θ permet d’obtenir

I =

∫ 1a

0

a1

au7f

(1

u

)du ≃ 1

a

1

n

n∑

i=1

1

u7j

f

(1

uj

),

où U suit une loi uniforme sur [0, 1a].

matlab : integrale-student, I = 6.54, variance des estimées pour n = 5000


Exemple : ν = 12, a = 2.1

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 104

3.5

4

4.5

5

5.5

6

6.5

7

iterations

inté

gral

e

Simulation suivant fImportance Sampling (Loi de Cauchy avec ν=1)Importance Sampling (Loi uniforme sur [0, 1/2.1])


Méthodes d’accélération

Utiliser la corrélation pour diminuer la varianced’estimation. Soient deux échantillons (θ1, ..., θn) et(η1, ..., ηn) distribués suivant f . On a alors deuxestimateurs non biaisés de I =

∫R

h(θ)f(θ)dθ définis par

I1 =1

n

n∑

i=1

h(θi), I2 =1

n

n∑

i=1

h(ηi)

La variance de la moyenne de ces deux estimateurs est

Var

(I1 + I2

2

)

=1

4

(VarI1 + VarI2

)+

1

2Cov(I1, I2)

☞ diminution de variance si la covariance est négative


Conditionnement - Rao-Blackwellization

Espérances conditionnelles

E[h(Θ)] = E [E[h(Θ)|Λ]]

EstimateursDonc, si on sait calculer g(λ) = E[h(Θ)|λ], on en déduitdeux estimateurs

I1 =1

n

n∑

i=1

h(Θi)

I2 =1

n

n∑

i=1

g(Λi) =1

n

n∑

i=1

E[h(Θ)|Λi]

Réduction de variance


Exemple

Problème

I =

∫ ∞

−∞e−θ2

f(θ)dθ,

où f la densité d’une loi de Student à ν degrés de liberté.

Estimateur usuel

I1 =1

n

n∑

i=1

e−Θ2j

Réduction de variance Θ|Λ ∼ N (µ, σ2Λ) et Λ−1 ∼ χ2ν

I2 =1

n

n∑

i=1

E[e−Θ2|Λi] =1

n

n∑

i=1

1√2σ2Λj + 1

matlab : Raoblack, I = 5373Cours Mastere, 2010 – p. 38/41

Exemple : ν = 4.6, µ = 0, σ2= 1

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 100000.49

0.5

0.51

0.52

0.53

0.54

0.55

0.56

0.57

iterations

inté

gral

e

Estimateur usuelRao BlackwellizationValeur de l’intégrale


Méthodes déterministes d’optimisation

Pour résoudre une équation de la forme

f(θ) = 0,

on peut utiliser des algorithmes comme l’algorithme deNewton-Raphson :

θn+1 = θn +

(∂f

∂θ(θn)

)−1

f(θn),

qui converge vers la solution f(θ) = 0.

convergence lente en O(n2) ou O(n3) alors que pour uneméthode de simulation, on aura classiquement uneconvergence en O(n) !


Méthodes déterministes d’intégration

Pour calculer une intégrale de la forme

∫ b

a

f(θ)dθ,

on peut utiliser des algorithmes basés sur les sommes deRiemann (méthode des trapèzes, méthode de Simpson, ...).

On peut explorer des zones de faibles probabilités

On a en général des problèmes pour des fonctionsmulti-modales.

L’erreur est en O(

1n1/d

), où d est la dimension de

l’espace! (curse of dimensionality).Pour les méthodes de Monte-Carlo, on aura une erreur en O

(1√

n

)!


Cours 2 : Metropolis - Hastings

1) Introduction : méthodes de Monte Carlo par chaînesde Markov (MCMC)

2) L’algorithme de Metropolis-Hastings indépendant

3) L’algorithme de Metropolis-Hastings à marche aléatoire

4) Algorithme de Green à sauts réversibles

– p. 1/34

Introduction

Pour approcher l’intégrale∫

P

h(θ)f(θ)dθ,

il n’est pas nécessaire de simuler suivant f (cf. échant.d’importance). Le principe des méthodes MCMC est deconstruire une chaîne de Markov ergodique dont la loistationnaire est f :

Idée : on part d’une valeur θ(0) et on construit θ(t) àl’aide d’un noyau de transition tel que la loi cible est f

Pour t0 “grand", θ(t0) est distribué suivant f

Remarque : Les valeurs générées θ(t0), θ(t0+1), ... sontdépendantes car θ(t) est une chaîne de Markov

– p. 2/34

Principes des méthodes MCMC

HypothèsesOn connaît la loi cible f à une constantemultiplicative prèsOn définit une loi de proposition (appelée aussi loiinstrumentale) q(y|θ).

Algorithme

Initialisation : choix de θ(0)

À partir de θ(t), on génère y(t) à l’aide de la loi deproposition et on accepte ou rejette cette valeur dey(t) à l’aide d’une procédure d’acceptation-rejet. Lavaleur retenue est notée θ(t+1).Les premières valeurs générées par l’algorithme neseront pas utilisées pour l’inférence (“burn-in")

– p. 3/34

L’algorithme de Metropolis-Hastings

Étant donné θ(t),

1. Générer yt ∼ q(y|θ(t)).

2. Acceptation-Rejet

θ(t+1) =

{yt avec prob. ρ(θ(t), yt),

θ(t) avec prob. 1 − ρ(θ(t), yt),

où

ρ(θ, y) = min

{f(y)

f(θ)

q(θ|y)

q(y|θ) , 1

}.

– p. 4/34

Propriétés et commentaires

Cas symétrique :

ρ(θ(t), yt) = min

{f(yt)

f(θ(t)), 1

}.

On accepte toujours les valeurs de yt augmentant la“vraisemblance"

La loi cible f peut être connue à une constantemultiplicative près

La chaîne (θ(t))t peut prendre plusieurs fois la mêmevaleur ⇒ échantillon non iid

– p. 5/34

Convergence

HypothèsesProbabilité d’acceptation

P

[f(yt) q(θ(t)|yt)

f(θ(t)) q(yt|θ(t))≥ 1

]< 1. (1)

i.e., l’événement {θ(t+1) = θ(t)} est possible.Loi de proposition

q(y|θ) > 0 pour tout (θ, y), (2).

En particulier, le support de la loi de proposition doitinclure le support de la loi cible !

– p. 6/34

Convergence

Conclusions

ErgodicitéPour h tel que Ef [|h(Θ)|] < ∞,

limT→∞

1

T

T∑

t=1

h(θ(t)) =

∫h(θ)f(θ)dθ

Convergence en variation totale

limn→∞

∥∥∥∥∫

Kn(θ, ·)µ(dθ) − f

∥∥∥∥TV

= 0

pour toute loi initiale µ, Kn(θ, ·) est le noyau de la chaîne après n transitions.

En particulier

limt→∞

P [θ(t) ∈ A] =

∫

A

f(θ)dθ

– p. 7/34

Metropolis-Hastings - Cas indépendant

La loi de proposition q(y|θ(t)) est indépendante de θ(t)


1. Générer yt ∼ q(y).


θ(t+1) =

{yt avec prob. min

{f(yt)f(θ(t))

q(θ(t))q(yt)

, 1}

,

θ(t) sinon

PropriétésL’échantillon généré n’est pas iid

Si f(θ) ≤ Mq(θ), ∀θ ∈ supp f , alors ‖.‖T V ≤(1 − 1

M

)n(ergodicité uniforme)

La probabilité d’acceptation est ≥ 1/M (i.e ≥ proba acceptation-rejet)

– p. 8/34

Exemple : Loi Gamma

Soit f la densité d’une loi gamma Ga(α, β). Calcul de

I =

∫ ∞

−∞θ2f(θ)dθ,

Acceptation rejet avec q(θ) ∼ Ga([α], [α]

α

), f(θ) < Mq(θ)

M = exp{α(ln(α) − 1) − [α](ln([α]) − 1)}

Algo de Metropolis-Hastings avec q(θ) ∼ Ga([α], [α]

α

)

ρ(θ(t), yt) = min

{(yt

θ(t)exp

[θ(t) − yt

α

])α−[α]

, 1

}

Matlab : lois-gamma, I = 8.33, TSVP pour exemplesnombre de données aléatoire avec acceptation-rejet

– p. 9/34

Acceptation-Rejet - Loi Gamma

1. Générer y ∼ Ga([α], [α]

α

).


θ(t) = y avec prob.

(ey exp(−y/α)

α

)α−[α]

– p. 10/34

Metropolis-Hastings - Loi Gamma


1. Générer yt ∼ Ga([α], [α]

α

).


θ(t+1) =

yt avec prob. min

{(yt

θ(t) exp{

θ(t)−yt

α

})α−[α], 1

}

θ(t) sinon

– p. 11/34

Exemple : α = 2.43, β = 1

0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000

2

4

6

8

10

12

14

16

18

20

iterations

inté

gral

e

acceptation−rejetvaleur de l’intégraleMetropolis−Hastings

– p. 12/34

Zoom

1000 1500 2000 2500 3000 3500 4000 4500

6.5

7

7.5

8

8.5

9

9.5

10

10.5

11

iterations

inté

gral

e

acceptation−rejetvaleur de l’intégraleMetropolis−Hastings

– p. 13/34

Metropolis-Hastings - Marche Aléatoire

La loi de proposition q est telle que

yt = θ(t) + ǫt,

où ǫt indépendant de θ(t), i.e. q(y|θ) = q(y − θ). Si q estsymétrique, on obtient l’algorithme suivant :


1. Générer yt ∼ q(y − θ(t)).


θ(t+1) =

{yt avec prob. min

{f(yt)f(θ(t))

, 1}

,

θ(t) sinon

– p. 14/34

Propriétés

Pas d’ergodicité uniforme

Conditions suffisantes d’ergodicité géométrique pourdes densités symétriques log-concaves ... (Mengersen& Tweedie, 1996)

∀θ ∈ P ,

∥∥∥∥∫

Kn(θ, ·)µ(dθ) − f

∥∥∥∥TV

≤ M

rn,

avec M < ∞ et r > 1.

Applet 1 : exemple d’algorithme de Metropolis-Hastings àmarche aléatoire, Jeff Rosenthal (Thanks!)Applet 2 : problème de la non-convergence uniforme, JeffRosenthal (Thanks!)

– p. 15/34

Exemple : Loi Normale

Simulation de données suivant la loi normale N (0, 1).

Metropolis-Hastings - Indépendant avec q(y) ∼ U [−3,+3]

Algo de Metropolis-Hastings - Marche Aléatoire avecq(ǫt) ∼ U [−δ,+δ] (Hastings, 1970)


min{exp

{(θ2

(t) − y2t )/2

}, 1}

Matlab : loi-gauss et loi-gauss-delta pour d = 1 et d = 0.01

– p. 16/34

Lois cibles pour δ = 0.01 et δ = 1

−4 −3 −2 −1 0 1 2 3 40

0.1

0.2

0.3

0.4

0.5

0.6

0.7δ = 1

−2.5 −2 −1.5 −1 −0.5 0 0.5 1 1.5 20

0.2

0.4

0.6

0.8

1δ = 0.01

– p. 17/34

Calcul des moyennes pourδ ∈ {0.1, 0.5, 1, 5}

0 5000 10000 15000−0.6

−0.4

−0.2

0

0.2

0.4δ = 0.1

0 5000 10000 15000−1

−0.5

0

0.5δ = 0.5

0 5000 10000 15000−0.5

0

0.5

1

1.5

2δ = 1

0 5000 10000 15000−1

0

1

2

3

4

5

6δ = 5

– p. 18/34

Calcul des variances pourδ ∈ {0.1, 0.5, 1, 5}

0 5000 10000 150000

0.5

1

1.5

2δ = 0.1

0 5000 10000 150000

0.2

0.4

0.6

0.8

1

1.2

1.4δ = 0.5

0 5000 10000 150000

0.2

0.4

0.6

0.8

1

1.2

1.4δ = 1

0 5000 10000 150000

2

4

6

8

10

12δ = 5

– p. 19/34

Extensions

Adaptive Rejection Metropolis Sampling (ARMS)

Algorithme de Metropolis-Hastings à sauts réversibles

Algorithmes de Langevin

...

– p. 20/34

Metropolis-Hastings avec sauts réversibles

“One of the things we do not know is the number of things wedo not know" - Peter Green

Dans quel cas ?Lorsque l’espace des paramètres inconnus est de tailleinconnue

mélanges de lois

modèles de types ARMA

modèles stationnaires par morceaux

Solution

utiliser une loi de proposition qui permet de sedéplacer dans des espaces de différentes dimensions

– p. 21/34

Densités jointe et a posteriori

Loi jointe

f(k, θ(k),x) = f(x|k, θ(k))f(θ(k)|k)f(k), k ∈ K, θ(k) ∈ Θk

f(k) : a priori sur le nombre de paramètres (k ∼ P(λ))

f(θ(k)|k) : loi a priori sur les paramètres sachant k

f(x|k, θ(k)) : vraisemblance

Loi a posteriori

f(k, θ(k)|x) =f(k, θ(k),x)∫ ∫

f(k, θ(k),x)dθ(k)dk∝ f(k, θ(k),x)

(k, θ(k)

)∈ ⋃k∈K Ck, Ck = {k} × R

nk espace de dimensionvariable.

– p. 22/34

Transition de Mk versMk′

Pour se déplacer de Rnk vers R

n′

k , avec k 6= k′, on doitcomplèter ces espaces afin de définir un difféomorphisme gkk′

Transition de Mk vers Mk′

gkk′ =

g1kk′

R

nk+nkk′ → Rnk′

(θ(k), u

)7→ θ(k′)

g2kk′

R

nk+nkk′ → Rnk′k

(θ(k), u

)7→ u′

avec nk + nkk′ = nk′ + nk′k.

– p. 23/34

Transition de Mk′ versMk

Afin d’assurer la réversibilité, il faut aussi définir undifféomorphisme gk′k allant de R

n′

k vers Rnk

Transition de Mk′ vers Mk

gk′k =

g1k′k

R

nk′+nk′k → Rnk

(θ(k′), u′) 7→ θ(k)

g2k′k

R

nk′+nk′k → Rnkk′

(θ(k′), u′) 7→ u

Remarque : on peut avoir u = 0 ou u′ = 0 !

– p. 24/34


Le nouvel état θ(k′) = g1k′k

(θ(k), u

)est accepté avec la

probabilité

ρkk′ = min

{Posterior Mk′

Posterior Mk

pk′k

pkk′

Proposal u′

Proposal u

∣∣∣∣∣∂(θ(k′), u′)

∂ (θ(k), u)

∣∣∣∣∣ , 1

}

avec

pk′k : proba de tenter un déplacement de Rnk′ vers R

nk

pkk′ : proba de tenter un déplacement de Rnk vers R

nk′

∣∣∣∣∂(θ(k′),u′

)

∂(θ(k),u)

∣∣∣∣ : Jacobien de la transformation

– p. 25/34

Exemple scolaire

Modèle M1

xi ∼ N (θ1, 1), i ≤ 50, xi ∼ N (θ2, 1), i > 50, C1 = {2}×R2

Posterior

∝2∏

j=1

exp

−1

2

tj+1−1∑

i=tj

(xi − θj)2

exp

(−1

2(θj − µ)2

)

Modèle M2

xi ∼ N (θ, 1), i = 1, ..., 100, C2 = {1} × R

Posterior

(1

2π

)50

exp

(−1

2

100∑

i=1

(xi − θ)2

)1√2π

exp

(−1

2(θ − µ)2

)1

2

– p. 26/34

Difféomorphismeg12

Passage de M1 à M2

g12

R

2 → R2

(θ1, θ2) 7→ (θ = θ1+θ2

2, u = θ1−θ2

2)


PosteriorM2

PosteriorM1

1/2

1/2

q(u)

1|Jacobien| =

π2

(θ1+θ2

2

)q(

θ1−θ2

2

)

π1(θ1, θ2)

1

2

Proposal u ∼ N (µ, 1)

– p. 27/34

Difféomorphismeg21

Passage de M2 à M1

g21

R

2 → R2

(θ, u) 7→ (θ1 = θ + u, θ2 = θ − u)


PosteriorM1

PosteriorM2

1/2

1/2

1

q(u)|Jacobien| =

π1 (θ + u, θ − u)

π2(θ)q(u)2

Proposal u ∼ N (µ, 1)

Matlab : samplingGreen

– p. 28/34

Optimisation du taux d’acceptation

Un algorithm générique “Adaptive rejection Metropolissampling (ARMS)"

choix d’une loi instrumentale q qui approche f de façon àce que le rapport f/q soit borné, de façon à avoirl’ergodicité uniforme

Algorithme à marche aléatoire

Dans les deux derniers cas, le choix de q est critique !

– p. 29/34

Metropolis-Hastings Indépendant

ρ = E

[min

{f(Y ) q(Θ)

f(Θ) q(Y ), 1

}]

= 2P

(f(Y )

q(Y )≥ f(Θ)

q(Θ)

), Θ ∼ f, Y ∼ q,

Loi de proposition q paramètrée par η et on cherche η quimaximise le taux d’acceptation moyen

ρ(η) =2

m

m∑

i=1

I{f(yi)q(θi)>f(θi)q(yi)} ,

où θ1, . . . , θm échantillon de densité f et y1, . . . , ym échantilloniid de densité q.

– p. 30/34

Metropolis-Hastings à marche aléatoire

Un taux d’acceptation moyen élevé n’indique pasnécessairement que l’algorithme évolue correctement carla marche aléatoire peut évoluer trop lentement (exempletypique des densités multi-modales)

Un taux d’acceptation moyen faible signifie que ledéplacement entre yt et θ(t) est rapide

Règle empirique (Gelman, Gilks et Robert, 1995) : tauxd’acceptation de 50% pour les modèles de dimension 1 et2, et de 25% pour les modèles de dimension supérieure

Applets Laird Breyer + exemples 2 derniers slides

– p. 31/34

Exemple d’une loi bimodale

– p. 32/34

Exemple d’une loi bimodale

– p. 33/34

Mélange de Gaussiennes

Modèle : y1, ..., yn i.i.d., r inconnu

f(y|θr) =r∑

i=1

ωi√2πσ2

i

exp

[−(y − mi)

2

2σ2i

]

1 2 3 4 5 6 7 8 9 100

0.05

0.1

0.15

0.2

0.25

revers

ible jum

p sam

pler

−2 −1 0 1 20

0.5

1

1.5

2

2.5

3

Codes C disponibles sur la page d’Olivier Cappé,http://www.tsi.enst.fr/~cappe/ctrj_mix

– p. 34/34

http://www.tsi.enst.fr/~cappe/ctrj_mix

Cours 3 : L’échantillonneur de Gibbs

1) Principes généraux

2) Complétion

3) Convergence

4) Le théorème de Hammersley-Clifford

5) Modèles hiérarchiques

6) Augmentation de données

7) Algorithme MCMC hybride

8) Dangers

– p. 1/30

Principes généraux

Pour simuler suivant une loi f(θ) avec θ = (θ1, ..., θp), on peututiliser l’idée suivante

Initialisation : générer un vecteur θ = (θ1, ..., θp) suivantune loi de proposition initiale π0

Simuler suivant les lois conditionnelles

Θi|θ1, θ2, . . . , θi−1, θi+1, . . . , θp

∼ fi(θi|θ1, θ2, . . . , θi−1, θi+1, . . . , θp)

for i = 1, 2, . . . , p.

– p. 2/30

L’échantillonneur de Gibbs

Étant donné θ(t) =

(θ(t)1 , ..., θ

(t)p

),

1. Générer θ(t+1)1 ∼ f1(θ1|θ(t)

2 , ..., θ(t)p ),

2. Générer θ(t+1)2 ∼ f2(θ2|θ(t+1)

1 , θ(t)3 , ..., θ

(t)p ),

. . .

p. Générer θ(t+1)p ∼ fp(θp|θ(t+1)

1 , θ(t+1)2 , ..., θ

(t+1)p−1 ),

Seules les lois conditionnelles f1, . . . , fp sont utilisées pourla simulation. Donc, même pour un problème de grandedimension, toutes les simulations sont univariées !

– p. 3/30

Propriétés

Taux d’acceptation égal à 1

Choix de la loi de proposition imposé par la méthode

Nécessite de connaître les lois conditionnelles de f

Ne peut s’appliquer si le vecteur paramètre à simuler estde dimension variable

Algorithme multi-dimensionnel par construction

– p. 4/30

Cas bidimensionnel

Pour simuler suivant

(X,Y ) ∼ f(x, y)

l’échantillonneur de Gibbs se réduit à

Simuler x0 et pour t = 1, 2, ..., générer (xt, yt) comme suit

1. yt ∼ fy|x(·|xt−1),

2. xt ∼ fx|y(·|yt),

où fy|x et fx|y sont les lois conditionnelles du couple (X,Y ).

Remarque : (xt)t, (yt)t et (xt, yt)t sont des chaînes deMarkov.

– p. 5/30

Cas Gaussien :Xi ∼ N (m, σ2)

Vraisemblance

f(x|m,σ2) ∝(σ2)−n/2

exp

(− 1

2σ2

n∑

i=1

(xi − m)2

)

Lois a priori

Moyenne

m ∼ N(m0, σ

20

)

Variance

σ2 ∼ IG (α, β)

– p. 6/30

Lois conditionnelles

moyenne

m|σ2,x ∼ N(M,Σ2

)

avec

M =nσ2

0

nσ20 + σ2

(1

n

n∑

i=1

xi

)+

(σ2

σ2 + nσ20

)m0 et Σ2 =

σ2σ20

σ2 + nσ20

variance

σ2|m,x ∼ IG(

n

2+ α,

1

2

n∑

i=1

(xi − m)2 + β

)

Donc, on peut simuler des couples (m,σ2) avecl’échantillonneur de Gibbs

– p. 7/30

Monte Carlo Statistical Methods

The Gibbs Sampler

General Principles

Example of results with n = 10 observations from theN(0, 1) distribution

Number of Iterations 1

, 2, 3, 4, 5, 10, 25, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2

, 3, 4, 5, 10, 25, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3

, 4, 5, 10, 25, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4

, 5, 10, 25, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4, 5

, 10, 25, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4, 5, 10

, 25, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4, 5, 10, 25

, 50, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4, 5, 10, 25, 50

, 100, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4, 5, 10, 25, 50, 100

, 500


The Gibbs Sampler

General Principles


Number of Iterations 1, 2, 3, 4, 5, 10, 25, 50, 100, 500

A Markov Chain Monte Carlo Primer

MCMC Basics

The Gibbs Sampler

Example of Results with, Left n = 10 Observations; Right,n = 100 Observations from the N(0, 1) Distribution

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 10

1

2

3

4

5

6

7

8

µ

σ2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

µ

σ2

Complétion

Définition : la densité g est une complétion de f si∫

Zg(θ,η)dη = f(θ),

i.e. si f est une loi marginale de g.

Intérêt : les lois conditionnelles de g sont parfois plussimples à simuler que celles de f (e.g. analyseBayésienne hiérarchique).

Notations : pour p > 1, soit Y = (θ,η) de densitég(y) = g(y1, ..., yp) et de lois conditionnelles

Yi|y1, ..., yi−1, yi+1, ..., yp ∼ gi(yi|y1, ..., yi−1, yi+1, ..., yp)

– p. 8/30

Echantillonneur de Gibbs après complétion

Étant donné y(t) =

(y

(t)1 , ..., y

(t)p

),

1. Générer y(t+1)1 ∼ g1(y1|y(t)

2 , ..., y(t)p ),

2. Générer y(t+1)2 ∼ g2(y2|y(t+1)

1 , y(t)3 , ..., y

(t)p ),

. . .

p. Générer y(t+1)p ∼ gp(yp|y(t+1)

1 , y(t+1)2 , ..., y

(t+1)p−1 ),

– p. 9/30

Exemple : loi Cauchy-Normale (1)

Posterior

f(θ|θ0) ∝e−θ2/2

[1 + (θ − θ0)2]ν

ComplétionOn a

f(θ|θ0) ∝∫ ∞

0

e−θ2/2 e−[1+(θ−θ0)2] η/2 ην−1 dη

d’où

g(θ, η) ∝ e−θ2/2 e−[1+(θ−θ0)2] η/2 ην−1

– p. 10/30

Exemple : loi Cauchy-Normale (2)


g1(η|θ) = Ga

(ν,

1 + (θ − θ0)2

2

),

g2(θ|η) = N(

θ0η

1 + η,

1

1 + η

).

Le paramètre η n’a pas d’intérêt physique et sertuniquement à simplifier la simulation d’un échantillon θ(t).

– p. 11/30

Condition de positivité

Positivité

g(i)(yi) > 0, i = 1, · · · , p ⇒ g(y1, ..., yp) > 0

où g(i) est la loi marginale de Yi (ou support de la loicible g égal au produit cartésien des supports des g(i))

Pour montrer la convergence de l’échantillonneur deGibbs, la loi cible doit vérifier la condition de positivité.

Contre-exempleg(y1, y2) =

1

2π[Iǫ(y1, y2) + Iǫ′(y1, y2)] ,

où ǫ et ǫ′ sont deux disques de rayons 1 centrés sur(1, 1) et (−1,−1)(autre exemple : vecteur non Gaussien dont les lois marginales sont Gaussiennes).

– p. 12/30

Illustration de la non-positivité

Initialisation Aléatoire

−1 0 1 2 3 4

−1

01

23

4

µ1

µ2

– p. 13/30

Illustration de la non-positivité

Gibbs coincé autour du mauvais mode

−1 0 1 2 3

−1

01

23

µ1

µ2

– p. 14/30

Convergence de l’échantillonneur de Gibbs

Si la condition de positivité est vérifiée et si le noyau detransition est absolument continu par rapport à g, on a

ErgodicitéSi∫|h(y)|g(y)dy < ∞, alors

limT→∞

1

T

T∑

t=1

h(y(t)) =

∫h(y)g(y)dy

Convergence en variation totale

limn→∞

∥∥∥∥∫

Kn(y, ·)µ(dy) − g

∥∥∥∥TV

= 0

pour toute loi initiale µ.

– p. 15/30

Remarques

L’échantillonneur de Gibbs est la composition de p

algorithmes de Metropolis-Hastings avec des probabilitésd’acceptation uniformément égales à 1.

Échantillonneur de Gibbs à balayage aléatoire

– p. 16/30

Le théorème de Hammersley-Clifford

Une loi jointe est caractérisée par l’ensemble de ses loisconditionnelles.

Dimension 2

Si la densité jointe g(y1, y2) a des lois conditionnellesnotées g1(y1|y2) et g2(y2|y1), alors (Hammersley andClifford, 1970)

g(y1, y2) =g2(y2|y1)∫

g2(v|y1)/g1(y1|v) dv.

– p. 17/30

Généralisation

Sous l’hypothèse de positivité, une loi jointe g peuts’écrire

g(y1, . . . , yp) ∝p∏

j=1

gℓj(yℓj

|yℓ1 , . . . , yℓj−1, y′

ℓj+1, . . . , y′

ℓp)

gℓj(y′

ℓj|yℓ1 , . . . , yℓj−1

, y′ℓj+1

, . . . , y′ℓp

)

pour toute permutation l définie sur {1, ..., p} et touty′ ∈ Y.

Exemple : p = 2 et l1 = 1, l2 = 2

g(y1, y2) ∝g1(y1|y′

2)

g1(y′1|y′

2)

g2(y2|y1)

g1(y′2|y1)

On retrouve Hammersley-Clifford !

– p. 18/30

Modèles hiérarchiques

L’échantillonneur de Gibbs est particulièrement bien adaptéaux modèles hiérarchiques :

Les paramètres inconnus sont munis de lois a priori ainsique les hyperparamètres associés

En général, on introduit des lois non informatives audernier niveau de la hiérarchie

– p. 19/30

Exemple

Données Poissonniennes

Xi ∼ P (λ1) pour i = 1, . . . , l1,

Xi ∼ P (λ2) pour i = l1 + 1, . . . , n,

avec l1 connu.

Lois a priori sur les paramètres

λ1 ∼ Ga (α, β) , λ2 ∼ Ga (α, β) , α = 2.

Loi a priori sur les hyperparamètres

f(β) =1

βIR+(β)

– p. 20/30

Loi jointe

f (x,λ, β) ∝ 1

β

l1∏

i=1

[λxi

1

xi!e−λ1

] n∏

i=l1+1

[λxi

2

xi!e−λ2

] 2∏

i=1

βα

Γ (α)λα−1

i e−βλi

Loi conditionnellespour les paramètres λi

λ1|β,x ∼ Ga

(l1∑

i=1

xi + α, β + l1

)

λ2|β,x ∼ Ga

(n∑

i=l1+1

xi + α, β + n − l1

),

pour β

β|x,λ ∼ Ga (2α, λ1 + λ2)Matlab : simu-Poisson

– p. 21/30

simu-Poisson

Données Poissonniennes cachées

Observations 0 1 2 3 4 ou plus

Nombre 139 128 55 25 13

Données : observations du nombre de données égales à0, 1, 2, 3 et du nombre de données ≥ 4.

Vraisemblance

ℓ(x1, . . . , x5;λ) ∝ e−347λλ128+55×2+25×3

(

1 − e−λ3∑

i=0

λi

i!

)13

,

Idée : on munit λ d’une loi a priori π(λ) = 1/λ et oncomplète ce paramètre par y = (y1, ..., y13).

– p. 22/30

Loi a posteriori

ℓ(λ, y1:13|x1:5) ∝ e−347λλ128+55×2+25×3

(13∏

i=1

λyie−λ

yi!

)1

λ,


yi|λ ∼ P(λ)Iyi≥4, i = 1, ..., 13

λ|y ∼ Ga(313 +

∑13i=1 yi, 360

)

Estimateur de λ

λ =1

360T

T∑

t=1

(313 +

13∑

i=1

y(t)i

)

Rao-Blackwellization

– p. 23/30

Conditionnement - Rao-Blackwellization

Espérances conditionnelles

E[h(Λ)] = E [E[h(Λ)|Y ]]

EstimateursIci on sait calculer g(Y ) = E[h(Λ)|Y ]. On en déduit deuxestimateurs

I1 =1

T

T∑

t=1

h(Λt)

I2 =1

T

T∑

t=1

g(Y t) =1

T

T∑

t=1

E[h(Λ)|Y t]

Réduction de variance

– p. 24/30

Résultats de simulation

0 100 200 300 400 500

1.02

11.

022

1.02

31.

024

1.02

5

0.9 1.0 1.1 1.2

010

2030

40

lambda

– p. 25/30

Algorithme MCMC hybride

Motivations

La convergence de l’échantillonneur de Gibbs peutêtre lente car on simule une seule composante àchaque itération

Pas de problème avec la loi de proposition commeavec l’algorithme de Metropolis-Hastings

Certaines lois conditionnelles peuvent êtreimpossibles à simuler

Définition : un algorithme MCMC hybride est uneméthode MCMC utilisant simultanément des étapesd’échantillonneur de Gibbs et des étapes deMetropolis-Hastings

– p. 26/30

Algorithme MCMC hybride

Remplacer chaque étape i où une simulation suivant la loiconditionnelle gi(yi|)yj, j 6= i est impossible par

1. Simuler yi ∼ qi(yi|y(t+1)1 , ..., y

(t)i , y

(t)i+1, ..., y

(t)p ),

2. Prendre

y(t+1)i =

yi avec probabilité ρ

y(t)i avec probabilité 1 − ρ

ρ = 1∧

gi

(yi|y(t+1)

1 , ..., y(t)i , y

(t)i+1, ..., y

(t)p

)

gi

(y(t)i |y(t+1)

1 , ..., y(t)i , y

(t)i+1, ..., y

(t)p

)qi

(y(t)i |y(t+1)

1 , ..., yi, y(t)i+1, ..., y

(t)p

)

qi

(yi|y(t)

1 , ..., y(t)i , y

(t)i+1, ..., y

(t)p

)

Remarque : l’étape de Metropolis-Hastings n’est utiliséequ’une fois (et la convergence est assurée).Matlab : metropolis_within_Gibbs

– p. 27/30

metropolis_within_Gibbs

Dangers

Modèle à effets aléatoires

Yij = µ + αi + εij, i = 1, . . . , I, j = 1, . . . , J,

avec

αi ∼ N (0, σ2) et εij ∼ N (0, τ 2),

Lois a prioriLa loi a priori de Jeffreys (impropre) pour les paramètresµ, σ et τ est

π(µ, σ2, τ 2) =1

σ2τ 2.

– p. 28/30


Les lois conditionnelles sont définies par

αi|y, µ, σ2, τ 2 ∼ N(

J(yi − µ)

J + τ 2σ−2, (Jτ−2 + σ−2)−1

),

µ|α, y, σ2, τ 2 ∼ N (y − α, τ 2/JI) ,

σ2|α, µ, y, τ 2 ∼ IG(

I

2,1

2

∑

i

α2i

),

τ 2|α, µ, y, σ2 ∼ IG(

IJ

2,1

2

∑

i,j

(yij − αi − µ)2

),

et sont faciles à simuler. Mais la loi jointe n’existe pas !

– p. 29/30

Simulations

Évolution de µ(t) et histogramme pour 1000 itérations

-4 -3 -2 -1 0

05

1015

2025

30

(1000 iterations)

freq.

-8-6

-4-2

0ob

serv

ation

s

– p. 30/30

Documents

Processus Stochastiques - tourneret.perso.enseeiht.frtourneret.perso.enseeiht.fr/StochasticProcesses/slides_MCMC.pdf · Processus Stochastiques ... Alors, si U est uniforme sur [0,1],