Algorithme espérance-maximisation
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

l'Algorithme espérance-maximisation (en anglais "Expectation-maximisation algorithm", souvent 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 lorsque le modèle dépend de variables latentes non observables.

On utilise souvent Espérance-maximisation pour la classification de données, en apprentissage (L’apprentissage est l'acquisition de savoir-faire, c'est-à-dire le processus d’acquisition de pratiques, de connaissances,...) machine, ou en vision artificielle. Espérance-maximisation alterne (Les organes d'une plante sont dits alternes lorsqu'ils sont insérés isolément et à des niveaux différents sur une tige ou un rameau.) des étapes 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, et 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 (Graphie) de départ d'une nouvelle phase (Le mot phase peut avoir plusieurs significations, il employé dans plusieurs domaines et principalement en physique :) 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.

Principe de fonctionnement

En considérant un échantillon (De manière générale, un échantillon est une petite quantité d'une matière, d'information, ou d'une solution. Le mot est utilisé dans différents domaines :) \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 (Un paramètre est au sens large un élément d'information à prendre en compte pour prendre une décision ou pour effectuer un calcul.) \boldsymbol{\theta} maximisant la log-vraisemblance donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) par

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 \boldsymbol{\theta}.

Dans ce cas, on s'appuie sur des données complétées par un vecteur (En mathématiques, un vecteur est un élément d'un espace vectoriel, ce qui permet d'effectuer des opérations d'addition et de multiplication par un scalaire. Un...) \mathbf{z}=(z_1,\dots,z_n) inconnnu. En notant f(z_i|\boldsymbol{x}_i;\theta) la probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des...) de zi sachant \boldsymbol{x}_i et le paramètre \boldsymbol{\theta}, on peut définir la log-vraisemblance complétée comme la quantité (La quantité est un terme générique de la métrologie (compte, montant) ; un scalaire, vecteur, nombre d’objets ou d’une autre manière de dénommer la...)

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,

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 donc définir l'algorithme EM de la manière suivante:

  • Initialisation au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.) 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
  • Fin

En pratique, pour s'affranchir du caractère local du maximum atteint, on fait tourner l'algorithme EM un grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques....)

Une des applications phares d'EM est l'estimation des paramètres d'une densité (La densité ou densité relative d'un corps est le rapport de sa masse volumique à la masse volumique d'un corps pris comme référence. Le corps de...) mélange (Un mélange est une association de deux ou plusieurs substances solides, liquides ou gazeuses qui n'interagissent pas chimiquement. Le...) 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 Gk 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) par

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

et donc, 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 très complexe. Par exemple, si on souhaite déterminer les paramètres correspondant à 2 groupes suivant une loi normale dans un espace de dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de...) 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 tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) à fait simple et très classique.

La force (Le mot force peut désigner un pouvoir mécanique sur les choses, et aussi, métaphoriquement, un pouvoir de la volonté ou encore une vertu morale...) de l'algorithme EM est justement de s'appuyer sur ces données pour réaliser l'estimation. En notant zik la grandeur qui vaut 1 si l'individu (Le Wiktionnaire est un projet de dictionnaire libre et gratuit similaire à Wikipédia (tous deux sont soutenus par la fondation Wikimedia).) xi appartient au groupe Gk 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 tik 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 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 (Le terme de convergence est utilisé dans de nombreux domaines :).

  • Etape E: calcul de tik 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, en général relativement simple. Dans tous les cas, les proportions optimales sont données par

\pi_k=\frac{1}{n}\sum_{i=1}^nt_{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é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

Variantes usuelles d'EM

L'algorithme EM, bien que très performant et souvent simple à mettre en œuvre, pose quand même parfois quelques problèmes qui ont donné lieu à des développements complémentaires. Parmi ceux-ci, nous évoquerons un développement appelé GEM (Generalized EM) qui permet de simplifier le problème de l'étape maximisation, un autre, appelé CEM (Classification EM) permettant de prendre en compte l'aspect classification lors de l'estimation, et un dernier, SEM (Stocastic EM) dont l'objectif est de réduire le risque de tomber dans un optimum local de vaisemblance.

Algorithme GEM

GEM a été proposé en même temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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\left(\theta,\theta^{(c+1)}\right)>Q\left(\theta,\theta^{(c)}\right)
  • c=c+1\,
  • Fin

Algorithme CEM

L'algorithme EM se positionne dans une optique (L'optique est la branche de la physique qui traite de la lumière, du rayonnement électromagnétique et de ses relations avec la vision.) 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}^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\,
  • 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 t_{ik}^{(c)}, l’appartenance z_{ik}^{(c)} des individus aux classes est tirée aléatoirement selon une loi multinomiale de paramètre \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 \left(z^{(q)},\theta^{(q)}\right) ne converge pas au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant...) 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ètres \theta\,.

Page générée en 0.134 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique