Algorithme espérance-maximisation

On utilise souvent l'algorithme EM pour la classification 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.

L'algorithme d'espérance-maximisation comporte :

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

On utilise ensuite les paramètres trouvés en M comme point de départ d'une nouvelle phase d'évaluation de l'espérance, et l'on itère ainsi.

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.

En considérant un échantillon x = (x₁ , ... , x_n) d'individus suivant une loi f(x_i,θ) paramétrée par θ, on cherche à déterminer le paramètre θ maximisant la log-vraisemblance donnée par

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

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).}$

et donc,

${\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 peut être défini par :

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

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.

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 (x₁ , ... , x_n) de ${\displaystyle \mathbb {R} ^{p}}$, ie caractérisé par p variables continues, est en réalité issu de g différents groupes. En considérant que chacun de ces groupes G_k suit une loi f de paramètre θ_k, et dont les proportions sont données par un vecteur (π₁ , ... , π_g). En notant Φ = (π₁ , ... , π_g , θ₁ , ... , θ_g) le paramètre du mélange, la fonction de densité que suit l'échantillon est donnée par

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

et donc, la log-vraisemblance du paramètre Φ est donnée par

${\displaystyle L(x,\Phi )=\sum _{i=1}^{n}\log \left(\sum _{k=1}^{g}\pi _{k}f(x_{i},\theta _{k})\right).}$

La maximisation de cette fonction selon Φ 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 ${\displaystyle \mathbb {R} ^{19}}$.

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 z_ik la grandeur qui vaut 1 si l'individu x_i appartient au groupe G_k et 0 sinon, la log-vraisemblance des données complétée s'écrit

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

On obtient alors rapidement

${\displaystyle Q\left(\Phi ,\Phi ^{(c)}\right)=\sum _{i=1}^{n}\sum _{k=1}^{g}\mathbb {E} \left(z_{ik}{\Bigg |}x,\Phi ^{(c)}\right)\log \left(\pi _{k}f(x_{i},\theta _{k})\right)}$

En notant t_ik la quantité donnée par ${\displaystyle t_{ik}=\mathbb {E} \left(z_{ik}{\Bigg |}x,\Phi ^{(c)}\right)}$, 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 t_ik par la règle d'inversion de Bayes :

${\displaystyle 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 Φ maximisant

${\displaystyle Q\left(\Phi ,\Phi ^{(c)}\right)=\sum _{i=1}^{n}\sum _{k=1}^{g}t_{ik}\log \left(\pi _{k}f(x_{i},\theta _{k})\right)}$

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

${\displaystyle \pi _{k}={\frac {1}{n}}\sum _{i=1}^{n}t_{ik}}$

L'estimation des θ dépend par ailleurs de la fonction de probabilité f choisie. Dans le cas normal, il s'agit des moyennes μ_k et des matrices de variance-covariance Σ_k. Les estimateurs optimaux sont alors donnés par

${\displaystyle \mu _{k}={\frac {\sum _{i=1}^{n}t_{ik}x_{i}}{\sum _{i=1}^{n}t_{ik}}}}$

${\displaystyle \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 M^T la matrice transposée de M et en supposant que les μ_k sont des vecteurs colonnes.

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.

• Partitionnement de données

• Portail des probabilités et de la statistique
• Portail de l'informatique théorique