Algorithme espérance-maximisation

L'algorithme espérance-maximisation, proposé par Dempster et al., est une classe d'algorithmes qui permettent de trouver le maximum de vraisemblance des paramètres de modèles probabilistes quand le modèle dépend de variables latentes non observables.

Catégories :

Optimisation - Statistiques - Algorithmique - Apprentissage automatique

Source image : techno-science.net
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

... l'algorithme Espérance-maximisation (Expectation-Maximization) pour l'imputation de données. L'algorithme EM sert à compléter une sé-... (source : desjardinsgestiondactifs)
Les paramètres du mélange sont estimés par l'algorithme Espérance Maximisation (EM). Un critère de mesure d'uniformité de région est utilisé pour comparer... (source : hal.inria)

L'algorithme espérance-maximisation (en anglais Expectation-maximisation algorithm, fréquemment abrégé EM), proposé par Dempster et al. (1977), est une classe d'algorithmes qui permettent de trouver le maximum de vraisemblance des paramètres de modèles probabilistes quand le modèle dépend de variables latentes non observables.

Usage

On utilise fréquemment Espérance-maximisation pour la classification de données, en apprentissage machine, ou en vision artificielle, ainsi qu'en imagerie médicale dans le cadre de la reconstruction tomographique. Espérance-maximisation comporte :

une étape d'évaluation de l'espérance (E), où on calcule l'espérance de la vraisemblance en tenant compte des dernières variables observées,

et une étape de maximisation (M), où 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 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.

Principe de fonctionnement

En considérant un échantillon $\mathbf{x}=(\boldsymbol{x}_1,\dots,\boldsymbol{x}_n)$ d'individus suivant une loi $f(\boldsymbol{x}_i,\theta)$ paramétrée par $\boldsymbol{\theta}$ , on cherche à déterminer le paramètre $\boldsymbol{\theta}$ maximisant la log-vraisemblance donnée par

$L(\mathbf{x};\boldsymbol{\theta})=\sum_{i=1}ˆn\log f(\boldsymbol{x}_i,\boldsymbol{\theta}).$

Cet algorithme est spécifiquement utile quand la maximisation de $L$ est particulièrement complexe mais que, sous réserve de connaître certaines données judicieusement choisies, on peut particulièrement simplement déterminer $\boldsymbol{\theta}$ .

Dans ce cas, on s'appuie sur des données complétées par un vecteur $\mathbf{z}=(z_1,\dots,z_n)$ inconnnu. En notant $f(z_i|\boldsymbol{x}_i;\theta)$ la probabilité de $z i$ sachant $\boldsymbol{x}_i$ et le paramètre $\boldsymbol{\theta}$ , on peut définir la log-vraisemblance complétée comme la quantité

$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 par conséquent,

$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 $\boldsymbol{\theta}ˆ{(c)}$ ce paramètre, on peut écrire

$E\left[L(\mathbf{x};\boldsymbol{\theta})|\boldsymbol{\theta}ˆ{(c)}\right]=E\left[L\left(\mathbf{(x,z)};\boldsymbol{\theta}\right))|\boldsymbol{\theta}ˆ{(c)}\right]-E\left[\sum_{i=1}ˆn\log f(z_i|\boldsymbol{x}_i,\boldsymbol{\theta}))|\boldsymbol{\theta}ˆ{(c)}\right],$

ou encore

$L(\mathbf{x};\boldsymbol{\theta})=Q\left(\boldsymbol{\theta};\boldsymbol{\theta}ˆ{(c)}\right)-H\left(\boldsymbol{\theta};\boldsymbol{\theta}ˆ{(c)}\right)$

avec $Q\left(\boldsymbol{\theta};\boldsymbol{\theta}ˆ{(c)}\right)=E\left[L\left(\mathbf{(x,z)};\boldsymbol{\theta}\right))|\boldsymbol{\theta}ˆ{(c)}\right]$ et $H\left(\boldsymbol{\theta};\boldsymbol{\theta}ˆ{(c)}\right)=E\left[\sum_{i=1}ˆn\log f(z_i|\boldsymbol{x}_i,\boldsymbol{\theta}))|\boldsymbol{\theta}ˆ{(c)}\right]$ .

On montre que la suite définie par

$\boldsymbol{\theta}ˆ{(c+1)}=\arg\max_{\boldsymbol{\theta}}\left(Q\left(\boldsymbol{\theta},\boldsymbol{\theta}ˆ{(c)}\right)\right)$

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

On peut par conséquent définir l'algorithme EM de la manière suivante :

Initialisation au hasard de $\boldsymbol{\theta}ˆ{(0)}$
c=0
Tant que l'algorithme n'a pas convergé, faire

Evaluation de l'espérance (étape E) : $Q\left(\boldsymbol{\theta};\boldsymbol{\theta}ˆ{(c)}\right)=E\left[L\left(\mathbf{(x,z)};\boldsymbol{\theta}\right))|\boldsymbol{\theta}ˆ{(c)}\right]$
Maximisation (étape M) : $\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 la plupart de fois à partir de valeurs initiales différentes de façon à 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 $\left(x_1,\dots,x_n\right)$ de $\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 $(\pi_1,\dots,\pi_g)$ . En notant $\Phi=\left(\pi_1,\dots,\pi_g,\theta_1,\dots,\theta_g\right)$ le paramètre du mélange, la fonction de densité que suit l'échantillon est donnée par

$g(x,\Phi)=\sum_{k=1}ˆg\pi_kf(x,\theta_k),$

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

$L(x,\Phi)=\sum_{i=1}ˆn\log\left(\sum_{k=1}ˆg\pi_kf(x_i,\theta_k)\right).$

La maximisation de cette fonction selon $Φ$ est particulièrement complexe. A titre d'exemple, si on souhaite déterminer les paramètres correspondant à 2 groupes suivant une loi normale dans un espace de dimension 3 (ce qui est peu), on doit optimiser une fonction non linéaire de $\mathbb{R}ˆ{26}$ !!!

Parallèlement, si on connaissait les groupes auxquels appartient chacun des individus, alors le problème serait un problème d'estimation particulièrement simple et particulièrement classique.

La force de l'algorithme EM est précisément de s'appuyer sur ces données pour réaliser l'estimation. En notant $z i k$ 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

$L(x,z,\Phi)=\sum_{i=1}ˆn\sum_{k=1}ˆgz_{ik}\log\left(\pi_kf(x_i,\theta_k)\right).$

On obtient alors rapidement

$Q\left(\Phi,\Phiˆ{(c)}\right)=\sum_{i=1}ˆn\sum_{k=1}ˆgE\left(z_{ik}|x,\Phiˆ{(c)}\right)\log\left(\pi_kf(x_i,\theta_k)\right)$

En notant $t i k$ la quantité donnée par $t_{ik}=E\left(z_{ik}|x,\Phiˆ{(c)}\right)$ , on peut séparer l'algorithme EM en deux étapes, qu'on nomme 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.

Etape E : calcul de $t i k$ par la règle d'inversion de Bayes :

$t_{ik}=\frac{\pi_kf(x_i,\theta_k)}{\sum_{\ell=1}ˆg\pi_\ell f(x_i,\theta_\ell)}$

Etape M : détermination de $Φ$ maximisant

$Q\left(\Phi,\Phiˆ{(c)}\right)=\sum_{i=1}ˆn\sum_{k=1}ˆgt_{ik}\log\left(\pi_kf(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 , généralement assez simple. Dans l'ensemble des cas, les proportions optimales sont données par

$\pi_k=\frac{1}{n}\sum_{i=1}ˆnt_{ik}$

L'estimation des $θ$ dépend d'autre part 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ée par

$\mu_k=\frac{\sum_{i=1}ˆnt_{ik}x_i}{\sum_{i=1}ˆnt_{ik}}$

$\Sigma_k=\frac{\sum_{i=1}ˆnt_{ik}(x_i-\mu_k)(x_i-\mu_k)'}{\sum_{i=1}ˆnt_{ik}}$

Avec M' la matrice transposée de M et en supposant que les $μ k$ sont des vecteurs colonnes.

Variantes usuelles d'EM

L'algorithme EM, quoique particulièrement performant et fréquemment simple à mettre en œuvre, pose quand même quelquefois quelques problèmes qui ont donné lieu à des développements complémentaires. Parmi ceux-ci, nous évoquerons un développement nommé GEM (Generalized EM) qui sert à simplifier le problème de l'étape maximisation, un autre, nommé CEM (Classification EM) servant à prendre en compte l'aspect classification lors de l'estimation, et un dernier, SEM (Stochastic EM) dont l'objectif est de diminuer le risque de tomber dans un optimum local de vaisemblance.

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 indispensable de maximiser Q à chaque étape mais qu'une simple amélioration de Q est suffisante.

GEM peut par conséquent 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 $<img class=$

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 Govært (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}ˆgz_{ik}\log\left(\pi_kf(x,\theta_k)\right)$

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\max_{z}\left(L\left(x,z;\thetaˆ{(c)}\right)\right)$
$\thetaˆ{(c+1)}=\arg\max_{\theta}\left(L\left(x,zˆ{(c+1)};\theta\right)\right)$
$c=c+1\,$

Algorithme SEM

Pour diminuer 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 $\mathcal{M}\left(1,t_{i1}ˆ{(q)},\dots,t_{ig}ˆ{(q)}\right)$ .

Au contraire de ce qui se produit dans l'algorithme CEM, on ne peut considérer que l'algorithme a convergé quand les individus ne changent plus de classes. En effet, celles-ci étant tirées aléatoirement, la suite $\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 $\theta\,$ .

Voir aussi

Partitionnement de données

Références

Celeux, G. et Diebolt, D. (1985). The sem algorithm : a probabilistic teacher algorithm derived from the em algorithm for the mixture problem. Computational Statistics Quarterly, 2 (1) :73–82.

Celeux, G. et Govært, G. (1991). A classification EM algorithm for clustering and two stochastic versions. Rapport de recherche RR-1364, Inria, Institut National de Recherche en Informatique et en Automatique.

Dempster, A. P., Laird, N. M. et Rubin, D. B. (1977). Maximum likelihood from incomplete data via the em algorithm (with discussion). Journal of the Royal Statistical Society, B 39 :1–38.

Recherche sur Amazone (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithme_esp%C3%A9rance-maximisation.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.