Algorithme espérance-maximisation - Définition

Principe de fonctionnement

En considérant un échantillon d'individus suivant une loi paramétrée par , on cherche à déterminer le paramètre maximisant la log-vraisemblance donnée par

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 inconnnu. En notant la probabilité de z_i sachant et le paramètre , on peut définir la log-vraisemblance complétée comme la quantité

et donc,

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

ou encore

avec et .

On montre que la suite définie par

fait tendre vers un maximum local.

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

• Initialisation au hasard de
• c=0
• Tant que l'algorithme n'a pas convergé, faire

• Evaluation de l'espérance (étape E) :
• Maximisation (étape M) :
• 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.

Variantes usuelles d'EM

L'algorithme EM allie, dans la plupart des cas, simplicité de mise en oeuvre 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
• 
• Tant que l'algorithme n'a pas convergé, faire

• choisir tel que
• 

• Fin

Algorithme CEM

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

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

• Initialisation au hasard de
• 
• Tant que l'algorithme n'a pas convergé, faire

• Fin

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 , l’appartenance des individus aux classes est tirée aléatoirement selon une loi multinomiale de paramètres .

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 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 .