110
8 Algorithme EM et mélanges
Le théorème 8.3 ne vaut que si nous savons estimer ˜
θ. Dans l’algorithme
EM, ceci est fait numériquement. Le résultat suivant montre que la logvraisemblance L obs est croissante le long de l’algorithme.
Théorème 8.4 (Croissance de la vraisemblance). La suite (θ k ) k0 construite
par l’algorithme EM vérifie la propriété de stabilité numérique suivante :
L obs (θ k+1 , X) L obs (θ k , X),
où L obs (θ, X) est la log-vraisemblance des observations.
Démonstration. Posons
H(θ, θ k ) = E θ k (log g θ (Z | X)) =
n
i=1
E θ k (log g θ (Z i | X i )).
Puisque h θ (x, z) = f θ (x)g θ (z|X = x), la vraisemblance conditionnelle s’écrit
L c (θ, θ k , X) = L obs (θ, X) + H(θ, θ k ).
Lors de l’étape M, la fonction θ → L c (θ, θ k , X) est maximisée en θ, d’où
L c (θ k+1 , θ k , X) L c (θ k , θ k , X).
On en déduit que
L obs (θ k+1 , X) − L obs (θ k , X) H(θ k , θ k ) − H(θ k+1 , θ k ).
Par définition de H,
H(θ k , θ k ) − H(θ k+1 , θ k ) = E θ k log
g θ k (Z | X)
g θ k+1 (Z | X)
.
En notant μ θ la loi de Z sachant X sous P θ , on remarque que la quantité
ci-dessus n’est rien d’autre que l’entropie relative de μ θ k par rapport à μ θ k+1 :
H(θ k , θ k ) − H(θ k+1 , θ k ) =
log
dμ θ k
dμ θ k+1
dμ θ k =
dμ θ k
dμ θ k+1
log
dμ θ k
dμ θ k+1
dμ θ k+1 .
L’inégalité de Jensen assure que cette quantité est positive.
Le théorème 8.4 montre que la suite (L obs (θ k , X)) k0 est croissante. Elle
converge donc vers un point critique (maximum local ou point selle) de la vraisemblance L obs (·, X). Contrairement au cas où l’on observe en même temps
X et Z, il peut exister des maxima locaux qui vont piéger l’algorithme, ce
qui rend le résultat sensible au point de départ. On peut améliorer le comportement de l’algorithme en incorporant un peu d’aléa, comme par exemple
dans l’algorithme du recuit simulé du chapitre 4, mais cela est un peu illusoire. De plus on ne sait pas combien d’itérations sont requises pour approcher
suffisamment un maximum local. Il n’y a pas de critère d’arrêt performant.
La figure 8.1 donne l’estimation du mélange de trois gaussiennes par l’algorithme EM avec 1000 itérations et les paramètres
α = (0.4 0.4 0.2), m = (−2 0 2), v = (0.3 0.2 0.2), n = 1000.
8 Algorithme EM et mélanges
Le théorème 8.3 ne vaut que si nous savons estimer ˜
θ. Dans l’algorithme
EM, ceci est fait numériquement. Le résultat suivant montre que la logvraisemblance L obs est croissante le long de l’algorithme.
Théorème 8.4 (Croissance de la vraisemblance). La suite (θ k ) k0 construite
par l’algorithme EM vérifie la propriété de stabilité numérique suivante :
L obs (θ k+1 , X) L obs (θ k , X),
où L obs (θ, X) est la log-vraisemblance des observations.
Démonstration. Posons
H(θ, θ k ) = E θ k (log g θ (Z | X)) =
n
i=1
E θ k (log g θ (Z i | X i )).
Puisque h θ (x, z) = f θ (x)g θ (z|X = x), la vraisemblance conditionnelle s’écrit
L c (θ, θ k , X) = L obs (θ, X) + H(θ, θ k ).
Lors de l’étape M, la fonction θ → L c (θ, θ k , X) est maximisée en θ, d’où
L c (θ k+1 , θ k , X) L c (θ k , θ k , X).
On en déduit que
L obs (θ k+1 , X) − L obs (θ k , X) H(θ k , θ k ) − H(θ k+1 , θ k ).
Par définition de H,
H(θ k , θ k ) − H(θ k+1 , θ k ) = E θ k log
g θ k (Z | X)
g θ k+1 (Z | X)
.
En notant μ θ la loi de Z sachant X sous P θ , on remarque que la quantité
ci-dessus n’est rien d’autre que l’entropie relative de μ θ k par rapport à μ θ k+1 :
H(θ k , θ k ) − H(θ k+1 , θ k ) =
log
dμ θ k
dμ θ k+1
dμ θ k =
dμ θ k
dμ θ k+1
log
dμ θ k
dμ θ k+1
dμ θ k+1 .
L’inégalité de Jensen assure que cette quantité est positive.
Le théorème 8.4 montre que la suite (L obs (θ k , X)) k0 est croissante. Elle
converge donc vers un point critique (maximum local ou point selle) de la vraisemblance L obs (·, X). Contrairement au cas où l’on observe en même temps
X et Z, il peut exister des maxima locaux qui vont piéger l’algorithme, ce
qui rend le résultat sensible au point de départ. On peut améliorer le comportement de l’algorithme en incorporant un peu d’aléa, comme par exemple
dans l’algorithme du recuit simulé du chapitre 4, mais cela est un peu illusoire. De plus on ne sait pas combien d’itérations sont requises pour approcher
suffisamment un maximum local. Il n’y a pas de critère d’arrêt performant.
La figure 8.1 donne l’estimation du mélange de trois gaussiennes par l’algorithme EM avec 1000 itérations et les paramètres
α = (0.4 0.4 0.2), m = (−2 0 2), v = (0.3 0.2 0.2), n = 1000.