Algorithme espérance-maximisation

Modèle:Infobox Méthode scientifiqueL'algorithme espérance-maximisation (en anglais Modèle:Lang, souvent abrégé EM) est un algorithme itératif qui permet de trouver les paramètres du maximum de vraisemblance d'un modèle probabiliste lorsque ce dernier dépend de variables latentes non observables. Il a été proposé par Dempster et al. en 1977. De nombreuses variantes ont par la suite été proposées, formant une classe entière d'algorithmes.

Usage

On utilise souvent l'algorithme EM pour la classification de données (clustering, ou partitionnement de données), l'apprentissage automatique, ou la vision artificielle. On peut également citer son utilisation en imagerie médicale dans le cadre de la reconstruction tomographique.

Principe général

L'algorithme d'espérance-maximisation consiste à itérer les deux étapes suivantes :

• étape E : une étape d'évaluation de l'espérance, où l'on calcule l'espérance de la vraisemblance en tenant compte des dernières variables observées,
• étape M : une étape de maximisation, où l'on estime le maximum de vraisemblance des paramètres en maximisant la vraisemblance trouvée à l'étape E.

On utilise à chaque fois les paramètres trouvés en l'étape M comme point de départ d'une nouvelle étape E d'évaluation de l'espérance.

Pour résoudre le problème d'apprentissage des modèles de Markov cachés (HMM), c’est-à-dire la détermination des paramètres du modèle markovien, on utilise l'algorithme de Baum-Welch.

Principe détaillé

Considérons un échantillon Modèle:Math d'individus suivant une loi Modèle:Math paramétrée par Modèle:Mvar. On cherche à déterminer le paramètre Modèle:Mvar maximisant la log-vraisemblance donnée par

$L(𝐱;\mathit{\theta })=\sum _{i=1}^n\log f({𝒙}_i,\mathit{\theta }).$

Introduction des variables cachées

Cet algorithme est particulièrement utile lorsque la maximisation de Modèle:Mvar est très complexe mais que, sous réserve de connaître certaines données judicieusement choisies, on peut très simplement déterminer Modèle:Mvar. Dans ce cas, on s'appuie sur des données complétées par un vecteur Modèle:Math inconnu. En notant Modèle:Math la probabilité de Modèle:Mvar sachant Modèle:Mvar et le paramètre Modèle:Mvar, on peut définir la log-vraisemblance complétée comme la quantité

$L((𝐱,𝐳);\mathit{\theta })=\sum _{i=1}^n(\log f(z_i|{𝒙}_i,\mathit{\theta })+\log f({𝒙}_i;\mathit{\theta })).$

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

$L(𝐱;\mathit{\theta })=L(\mathbf{(}𝐱,𝐳\mathbf{)};\mathit{\theta })-\sum _{i=1}^n\log f(z_i|{𝒙}_i,\mathit{\theta }).$

Étape E

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 Modèle:Math ce paramètre, on peut écrire

$𝔼[L(𝐱;\mathit{\theta })|{\mathit{\theta }}^{(c)}]=𝔼\left[L(\mathbf{(}𝐱,𝐳\mathbf{)};\mathit{\theta })\right|{\mathit{\theta }}^{(c)}]-𝔼[\sum _{i=1}^n\log f(z_i|{𝒙}_i,\mathit{\theta })\left|{\mathit{\theta }}^{(c)}\right],$ où l'espérance est prise sur Modèle:Math.

ou encore

$L(𝐱;\mathit{\theta })=Q(\mathit{\theta };{\mathit{\theta }}^{(c)})-H(\mathit{\theta };{\mathit{\theta }}^{(c)})$, car Modèle:Math ne dépend pas de Modèle:Math,

avec $Q(\mathit{\theta };{\mathit{\theta }}^{(c)})=𝔼\left[L(\mathbf{(}𝐱,𝐳\mathbf{)};\mathit{\theta })\right|{\mathit{\theta }}^{(c)}]$ et $H(\mathit{\theta };{\mathit{\theta }}^{(c)})=𝔼[\sum _{i=1}^n\log f(z_i|{𝒙}_i,\mathit{\theta })\left|{\mathit{\theta }}^{(c)}\right]$.

Étape M

On montre que la suite définie par

${\mathit{\theta }}^{(c+1)}=\arg \underset{\mathit{\theta }}{\max }\left(Q(\mathit{\theta },{\mathit{\theta }}^{(c)})\right)$

fait tendre $L(𝐱;{\mathit{\theta }}^{(c+1)})$ vers un maximum local.

Pseudo-code général

L'algorithme EM est défini par :

• Initialisation au hasard de Modèle:Math
• Modèle:Math
• Tant que l'algorithme n'a pas convergéModèle:Quoi, faire
  • Étape E. Évaluation de l'espérance  : $Q(\mathit{\theta };{\mathit{\theta }}^{(c)})=𝔼[L(\mathbf{(}𝐱,𝐳\mathbf{)};\mathit{\theta }))|{\mathit{\theta }}^{(c)}]$
  • Étape M. Maximisation  : ${\mathit{\theta }}^{(c+1)}=\arg \underset{\mathit{\theta }}{\max }\left(Q(\mathit{\theta },{\mathit{\theta }}^{\mathit{(}𝒄\mathit{)}})\right)$
  • Modèle:Math

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.

Exemple détaillé : application en classification automatique

Une des applications phares d'EM est l'estimation des paramètres d'une densité mélange en classification automatique dans le cadre des modèles de mélanges gaussiens. Dans ce problème, on considère qu'un échantillon Modèle:Math de ${ℝ}^p$, ie caractérisé par Modèle:Mvar variables continues, est en réalité issu de Modèle:Mvar différents groupes. En considérant que chacun de ces groupes Modèle:Mvar suit une loi Modèle:Mvar de paramètre Modèle:Mvar, et dont les proportions sont données par un vecteur Modèle:Math. En notant Modèle:Math le paramètre du mélange, la fonction de densité que suit l'échantillon est donnée par

$g(x,\mathrm{\Phi })=\sum _{k=1}^g{\pi }_{k}f(x,{\theta }_k),$

et donc, la log-vraisemblance du paramètre Modèle:Math est donnée par

$L(x,\mathrm{\Phi })=\sum _{i=1}^n\log (\sum _{k=1}^g{\pi }_{k}f(x_i,{\theta }_k)).$

La maximisation de cette fonction selon Modèle:Math est très complexe. Par exemple, si on souhaite déterminer les paramètres correspondant à deux groupes suivant une loi normale dans un espace de dimension 3, il faut optimiser une fonction non-linéaire de ${ℝ}^{19}$(9 variables par normale plus la proportion entre les deux).

Parallèlement, si on connaissait les groupes auxquels appartient chacun des individus, alors le problème serait un problème d'estimation tout à fait simple et très classique.

La force de l'algorithme EM est justement de s'appuyer sur ces données pour réaliser l'estimation. En notant Modèle:Mvar la grandeur qui vaut 1 si l'individu Modèle:Mvar appartient au groupe Modèle:Mvar et 0 sinon, la log-vraisemblance des données complétée s'écrit

$L(x,z,\mathrm{\Phi })=\sum _{i=1}^n\sum _{k=1}^g{z}_{ik}\log ({\pi }_{k}f(x_i,{\theta }_k)).$

On obtient alors rapidement

$Q(\mathrm{\Phi },{\mathrm{\Phi }}^{(c)})=\sum _{i=1}^n\sum _{k=1}^g𝔼\left(z_{ik}\right|x,{\mathrm{\Phi }}^{(c)})\log ({\pi }_{k}f(x_i,{\theta }_k))$

En notant Modèle:Mvar la quantité donnée par $t_{ik}=𝔼\left(z_{ik}\right|x,{\mathrm{\Phi }}^{(c)})$, on peut séparer l'algorithme EM en deux étapes, qu'on appelle classiquement, dans le cas des modèles de mélanges, l'étape Estimation et l'étape Maximisation. Ces deux étapes sont itérées jusqu'à la convergence.

• Étape E : calcul de Modèle:Mvar par la règle d'inversion de Bayes :

$t_{ik}=\frac{{\pi }_k^{(c)}f(x_i,{\theta }_k^{(c)})}{\sum _{\ell =1}^g{\pi }_{\ell }^{(c)}f(x_i,{\theta }_{\ell }^{(c)})}$

• Étape M : détermination de Modèle:Math maximisant

$Q(\mathrm{\Phi },{\mathrm{\Phi }}^{(c)})=\sum _{i=1}^n\sum _{k=1}^g{t}_{ik}\log ({\pi }_{k}f(x_i,{\theta }_k))$

L'avantage de cette méthode est qu'on peut séparer le problème en Modèle:Mvar problèmes élémentaires qui sont, en général relativement simples. Dans tous les cas, les proportions optimales sont données par

${\pi }_k=\frac{1}{n}\sum _{i=1}^n{t}_{ik}$

L'estimation des Modèle:Mvar dépend par ailleurs de la fonction de probabilité Modèle:Mvar choisie. Dans le cas normal, il s'agit des moyennes Modèle:Mvar et des matrices de variance-covariance Modèle:Math. Les estimateurs optimaux sont alors donnés par

${\mu }_k=\frac{\sum _{i=1}^n{t}_{ik}{x}_i}{\sum _{i=1}^n{t}_{ik}}$

${\mathrm{\Sigma }}_k=\frac{\sum _{i=1}^n{t}_{ik}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T}{\sum _{i=1}^n{t}_{ik}}$

Avec Modèle:Math la matrice transposée de Modèle:Mvar et en supposant que les Modèle:Mvar sont des vecteurs colonnes.

Variantes usuelles d'EM

L'algorithme EM allie, dans la plupart des cas, simplicité de mise en œuvre et efficacité. Néanmoins quelques cas problématiques ont donné lieu à des développements complémentaires. Parmi les variantes existantes de cet algorithme nous évoquerons l'algorithme GEM (generalized EM) qui permet de simplifier le problème de l'étape maximisation; l'algorithme CEM (classification EM) permettant de prendre en compte l'aspect classification lors de l'estimation, ainsi que l'algorithme SEM (stochastic EM) dont l'objectif est de réduire le risque de tomber dans un optimum local de vraisemblance.

Algorithme GEM

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 ${\theta }^{(0)}$
• $c=0$
• Tant que l'algorithme n'a pas convergé, faire
  • choisir ${\theta }^{(c+1)}$ tel que $Q({\theta }^{(c+1)},{\theta }^{(c)})>Q({\theta }^{(c)},{\theta }^{(c)})$
  • $c=c+1$
• Fin

Algorithme CEM

L'algorithme EM se positionne dans une optique estimation, c'est-à-dire qu'on cherche à maximiser la vraisemblance du paramètre $\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) 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

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

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

• Initialisation au hasard de ${\theta }^{(0)}$
• $c=0$
• Tant que l'algorithme n'a pas convergé, faire
  • $z^{(c+1)}=\arg \underset{z}{\max }\left(L(x,z;{\theta }^{(c)})\right)$
  • ${\theta }^{(c+1)}=\arg \underset{\theta }{\max }\left(L(x,z^{(c+1)};\theta )\right)$
  • $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.

Algorithme SEM

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

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 $(z^{(q)},{\theta }^{(q)})$ 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 $\theta$.

Voir aussi

• Partitionnement de données