L'algorithme d'espérance-maximisation (EM) est une méthode itérative utilisée en statistiques pour trouver des estimations du maximum de vraisemblance ou du maximum a posteriori (MAP) des paramètres dans des modèles statistiques qui dépendent de variables latentes non observées. L'algorithme alterne entre une étape d'espérance (E), qui calcule la log-vraisemblance attendue compte tenu des estimations actuelles des paramètres, et une étape de maximisation (M), qui met à jour les paramètres pour maximiser cette log-vraisemblance attendue. Ces paramètres mis à jour informent ensuite l'étape E suivante, et le processus se répète jusqu'à convergence. EM est largement appliqué dans des domaines tels que apprentissage automatique pour des tâches comme l'estimation de modèles de mélange, le traitement de données manquantes et l'entraînement de modèles de Markov cachés.
Le défi central que EM aborde survient lorsqu'une fonction de vraisemblance implique à la fois des données observées et des variables latentes non observées. Maximiser directement la vraisemblance en prenant des dérivées par rapport à toutes les inconnues donne généralement des équations imbriquées qui ne peuvent pas être résolues analytiquement. EM contourne ce problème en résolvant itérativement un ensemble d'inconnues tout en maintenant l'autre fixe, en alternant jusqu'à ce que les deux convergent vers un point fixe. Cette approche garantit une augmentation de la vraisemblance à chaque itération, bien qu'elle puisse converger vers un maximum local ou un point de selle plutôt que vers l'optimum global.
Historique
L'algorithme EM a été formellement nommé et expliqué dans un article classique de 1977 par Arthur Dempster, Nan Laird et Donald Rubin. Cependant, la méthode avait été proposée dans des cas particuliers par des auteurs antérieurs. Cedric Smith a introduit une méthode de comptage de gènes pour estimer les fréquences alléliques, et H.O. Hartley a proposé une approche connexe en 1958, avec des développements supplémentaires par Hartley et Hocking en 1977. Rolf Sundberg a fourni un traitement détaillé pour les familles exponentielles dans sa thèse et ses articles ultérieurs, s'appuyant sur une collaboration avec Per Martin-Löf et Anders Martin-Löf. L'article de 1977 de Dempster-Laird-Rubin a généralisé ces idées et esquissé une analyse de convergence, établissant EM comme un outil statistique majeur. Une preuve de convergence correcte a été publiée plus tard par C. F. Jeff Wu en 1983, corrigeant les défauts de l'analyse originale et étendant les garanties de convergence au-delà des familles exponentielles.
Description de l'algorithme
Étant donné des données observées X, des données latentes Z et des paramètres inconnus θ, l'objectif est de maximiser la vraisemblance marginale L(θ; X) = ∫ p(X, Z | θ) dZ. L'itération EM consiste en deux étapes :
- Étape E : Calculer la valeur attendue de la fonction de log-vraisemblance, Q(θ | θ^(t)), par rapport à la distribution conditionnelle de Z étant donné X et l'estimation actuelle des paramètres θ^(t).
- Étape M : Trouver les paramètres θ^(t+1) qui maximisent Q(θ | θ^(t)).
Les paramètres mis à jour sont ensuite utilisés dans l'étape E suivante, et le processus se répète jusqu'à ce que le changement dans les paramètres ou la vraisemblance tombe en dessous d'un seuil. Cette procédure augmente de manière monotone la vraisemblance, garantissant la convergence vers un point stationnaire.
Applications
EM est couramment utilisé pour estimer les paramètres de modèles de mélange, tels que les mélanges gaussiens, où chaque point de données observé est supposé provenir de l'un des plusieurs composants sous-jacents. Il gère également les problèmes de données manquantes, où certaines observations sont incomplètes. Dans intelligence artificielle, EM sous-tend les algorithmes d'entraînement pour les modèles de Markov cachés, qui sont utilisés dans la reconnaissance vocale et la bioinformatique. De plus, EM peut résoudre des problèmes de régression linéaire multiple avec des variables latentes et est appliqué dans l'analyse factorielle et le regroupement.
Propriétés et limites
EM est efficace sur le plan computationnel et facile à implémenter pour de nombreux modèles, mais il présente des limites. Il peut converger vers des maxima locaux, et la solution finale dépend de l'initialisation. Dans les modèles de mélange, EM peut trouver des solutions singulières où un composant a une variance nulle, ce qui correspond à des maxima non pertinents. L'algorithme nécessite également la spécification du nombre de composants ou d'états latents, qui est souvent inconnu. Des variantes telles que l'algorithme EM généralisé et l'EM stochastique abordent certains de ces problèmes, mais la méthode de base reste un outil fondamental en calcul statistique.
Concepts connexes
L'algorithme EM est étroitement lié à d'autres techniques d'optimisation itératives dans apprentissage automatique, telles que les méthodes basées sur le gradient comme variantes de SGD et optimiseur Adam. Il est également connecté à l'inférence variationnelle dans apprentissage profond, où des distributions postérieures approximatives sont optimisées. Dans IA générative, des approches de type EM apparaissent dans l'entraînement de modèles à variables latentes, et ses principes sont fondamentaux pour comprendre des algorithmes plus avancés comme apprentissage par retour d'IA et apprentissage par curriculum.