Algorithme espérance-maximisation

Cet algorithme est particulièrement utile lorsque la maximisation de L est très complexe mais que, sous réserve de connaître certaines données judicieusement choisies, on peut très simplement déterminer θ. Dans ce cas, on s'appuie sur des données complétées par un vecteur z = (z₁ , ... , z_n) inconnu. En notant f(z_i | x_i,θ) la probabilité de z_i sachant x_i et le paramètre θ, on peut définir la log-vraisemblance complétée comme la quantité

${\displaystyle L\left((\mathbf {x,z} );{\boldsymbol {\theta }}\right)=\sum _{i=1}^{n}\left(\log f(z_{i}|{\boldsymbol {x}}_{i},{\boldsymbol {\theta }})+\log f({\boldsymbol {x}}_{i};{\boldsymbol {\theta }})\right).}$

Ainsi, on écrit la log-vraisemblance initiale comme :

${\displaystyle L(\mathbf {x}$ ;{\boldsymbol {\theta }})=L\left(\mathbf {(x,z)} ;{\boldsymbol {\theta }}\right)-\sum _{i=1}^{n}\log f(z_{i}|{\boldsymbol {x}}_{i},{\boldsymbol {\theta }}).}

L'algorithme EM est une procédure itérative basée sur l'espérance des données complétées conditionnellement au paramètre courant. En notant θ^(c) ce paramètre, on peut écrire

${\displaystyle \mathbb {E} \left[L(\mathbf {x}$ ;{\boldsymbol {\theta }}){\Bigg |}{\boldsymbol {\theta }}^{(c)}\right]=\mathbb {E} \left[L\left(\mathbf {(x,z)} ;{\boldsymbol {\theta }}\right){\Bigg |}{\boldsymbol {\theta }}^{(c)}\right]-\mathbb {E} \left[\sum _{i=1}^{n}\log f(z_{i}|{\boldsymbol {x}}_{i},{\boldsymbol {\theta }}){\Bigg |}{\boldsymbol {\theta }}^{(c)}\right],} où l'espérance est prise sur z.

ou encore

${\displaystyle L(\mathbf {x}$ ;{\boldsymbol {\theta }})=Q\left({\boldsymbol {\theta }};{\boldsymbol {\theta }}^{(c)}\right)-H\left({\boldsymbol {\theta }};{\boldsymbol {\theta }}^{(c)}\right)} , car L(x ; θ) ne dépend pas de z,

avec ${\displaystyle Q\left({\boldsymbol {\theta }};{\boldsymbol {\theta }}^{(c)}\right)=\mathbb {E} \left[L\left(\mathbf {(x,z)}$ ;{\boldsymbol {\theta }}\right){\Bigg |}{\boldsymbol {\theta }}^{(c)}\right]} et ${\displaystyle H\left({\boldsymbol {\theta }};{\boldsymbol {\theta }}^{(c)}\right)=\mathbb {E} \left[\sum _{i=1}^{n}\log f(z_{i}|{\boldsymbol {x}}_{i},{\boldsymbol {\theta }}){\Bigg |}{\boldsymbol {\theta }}^{(c)}\right]}$.

On montre que la suite définie par

${\displaystyle {\boldsymbol {\theta }}^{(c+1)}=\arg \max _{\boldsymbol {\theta }}\left(Q\left({\boldsymbol {\theta }},{\boldsymbol {\theta }}^{(c)}\right)\right)}$

fait tendre ${\displaystyle L\left(\mathbf {x}$ ;{\boldsymbol {\theta }}^{(c+1)}\right)} vers un maximum local.

L'algorithme EM est défini par :

• Initialisation au hasard de θ⁽⁰⁾
• c = 0
• Tant que l'algorithme n'a pas convergé, faire
  • Étape E. Évaluation de l'espérance : ${\displaystyle Q\left({\boldsymbol {\theta }};{\boldsymbol {\theta }}^{(c)}\right)=\mathbb {E} \left[L\left(\mathbf {(x,z)}$ ;{\boldsymbol {\theta }}\right))|{\boldsymbol {\theta }}^{(c)}\right]}
  • Étape M. Maximisation : ${\displaystyle {\boldsymbol {\theta }}^{(c+1)}=\arg \max _{\boldsymbol {\theta }}\left(Q\left({\boldsymbol {\theta }},{\boldsymbol {\theta ^{(c)}}}\right)\right)}$
  • c = c+1

En pratique, pour s'affranchir du caractère local du maximum atteint, on fait tourner l'algorithme EM un grand nombre de fois à partir de valeurs initiales différentes de manière à avoir de plus grandes chances d'atteindre le maximum global de vraisemblance.

GEM a été proposé en même temps qu'EM par Dempster et al. (1977) qui ont prouvé que pour assurer la convergence vers un maximum local de vraisemblance, il n'est pas nécessaire de maximiser Q à chaque étape mais qu'une simple amélioration de Q est suffisante.

GEM peut donc s'écrire de la manière suivante:

• Initialisation au hasard de ${\displaystyle \theta ^{(0)}\,}$
• ${\displaystyle c=0\,}$
• Tant que l'algorithme n'a pas convergé, faire
  • choisir ${\displaystyle \theta ^{(c+1)}\,}$ tel que ${\displaystyle Q\left(\theta ^{(c+1)},\theta ^{(c)}\right)>Q\left(\theta ^{(c)},\theta ^{(c)}\right)}$
  • ${\displaystyle c=c+1\,}$
• Fin

L'algorithme EM se positionne dans une optique estimation, c'est-à-dire qu'on cherche à maximiser la vraisemblance du paramètre ${\displaystyle \theta \,}$, sans considération de la classification faite a posteriori en utilisant la règle de Bayes.

L'approche classification, proposée par Celeux et Govaert (1991)[2] consiste à optimiser, non pas la vraisemblance du paramètre, mais directement la vraisemblance complétée, donnée, dans le cas des modèles de mélange, par

${\displaystyle L(x,z;\theta )=\sum _{i=1}^{n}\sum _{k=1}^{g}z_{ik}\log \left(\pi _{k}f(x,\theta _{k})\right)}$

Pour cela, il suffit de procéder de la manière suivante:

• Initialisation au hasard de ${\displaystyle \theta ^{(0)}\,}$
• ${\displaystyle c=0\,}$
• Tant que l'algorithme n'a pas convergé, faire
  • ${\displaystyle z^{(c+1)}=\arg \max _{z}\left(L\left(x,z;\theta ^{(c)}\right)\right)}$
  • ${\displaystyle \theta ^{(c+1)}=\arg \max _{\theta }\left(L\left(x,z^{(c+1)};\theta \right)\right)}$
  • ${\displaystyle c=c+1\,}$
• Fin

Lorsque les composantes du mélange appartiennent à la même famille exponentielle, en utilisant la bijection entre les divergences de Bregman et les familles exponentielles, on obtient l'algorithme k-MLE[3].

Afin de réduire le risque de tomber dans un maximum local de vraisemblance, Celeux et Diebolt (1985)[4] proposent d’intercaler une étape stochastique de classification entre les étapes E et M. Après le calcul des probabilités ${\displaystyle t_{ik}^{(c)}}$, l’appartenance ${\displaystyle z_{ik}^{(c)}}$ des individus aux classes est tirée aléatoirement selon une loi multinomiale de paramètres ${\displaystyle {\mathcal {M}}\left(1,t_{i1}^{(q)},\dots ,t_{ig}^{(q)}\right)}$.

Contrairement à ce qui se produit dans l’algorithme CEM, on ne peut considérer que l’algorithme a convergé lorsque les individus ne changent plus de classes. En effet, celles-ci étant tirées aléatoirement, la suite ${\displaystyle \left(z^{(q)},\theta ^{(q)}\right)}$ ne converge pas au sens strict. En pratique, Celeux et Diebolt (1985) proposent de lancer l’algorithme SEM un nombre de fois donné puis d’utiliser l’algorithme CEM pour obtenir une partition et une estimation du paramètre ${\displaystyle \theta \,}$.