L'algorithme espérance-maximisation (EM) est une méthode itérative en statistiques et en apprentissage automatique pour trouver des estimations locales du maximum de vraisemblance ou du maximum a posteriori des paramètres dans des modèles statistiques qui dépendent de variables latentes non observées. EM alterne entre une étape d'espérance (E), qui calcule une fonction pour la log-vraisemblance attendue en utilisant les estimations actuelles des paramètres, et une étape de maximisation (M), qui met à jour les paramètres pour maximiser cette log-vraisemblance attendue. Ces estimations mises à jour informent ensuite l'étape E suivante, et le processus se répète jusqu'à convergence.
En apprentissage automatique, EM est un outil central pour les modèles où les données sont incomplètes, tels que les modèles de mélange (par exemple, les modèles de mélange gaussiens) et les modèles de Markov cachés. Il a des applications dans le clustering, la segmentation d'images et l'estimation de paramètres pour les modèles graphiques probabilistes, et il sert de fondement à des méthodes plus avancées d'inférence variationnelle utilisées dans les modèles génératifs profonds.
Histoire
L'algorithme EM a été formellement nommé et expliqué dans un article de 1977 par Arthur Dempster, Nan Laird et Donald Rubin, mais la méthode avait été proposée plus tôt pour des cas spécifiques. Cedric Smith a utilisé le comptage de gènes pour estimer les fréquences alléliques, et H.O. Hartley a introduit une approche connexe en 1958, que Hartley a étendue avec Hocking en 1977, fournissant des concepts clés. Rolf Sundberg a développé un traitement détaillé pour les familles exponentielles, influencé par Per Martin-Löf et Anders Martin-Löf. L'article de Dempster-Laird-Rubin a généralisé la méthode et l'a étendue à une classe plus large, bien que sa preuve de convergence ait été imparfaite. C. F. Jeff Wu a proposé une analyse de convergence corrigée en 1983, établissant la validité d'EM au-delà des familles exponentielles. L'algorithme est devenu une norme dans l'analyse statistique, et des travaux ultérieurs, tels que ceux de Meng et van Dyk (1997), l'ont affiné davantage.
Étapes de l'algorithme
L'algorithme EM aborde des problèmes d'optimisation où la fonction de vraisemblance contient des variables latentes, rendant la maximisation directe par dérivées impossible dans de nombreux cas. Au lieu de cela, l'algorithme résout de manière itérative des équations imbriquées : les paramètres dépendent des variables latentes, et les variables latentes dépendent des paramètres, ce qui donne généralement des équations insolubles lorsqu'elles sont substituées directement.
EM brise ce cycle en alternant entre deux étapes :
- Étape E : Étant donné les estimations actuelles des paramètres de l'itération précédente, calculer la valeur attendue de la log-vraisemblance par rapport à la distribution des variables latentes, conditionnée aux données observées.
- Étape M : Maximiser la log-vraisemblance attendue par rapport aux paramètres, produisant de nouvelles estimations qui garantissent d'augmenter la vraisemblance des données observées ou de la maintenir constante (non décroissante). Cela se répète jusqu'à convergence.
Si le modèle a des variables latentes indépendantes, l'étape E se simplifie pour trouver l'estimation du maximum a posteriori des variables latentes, souvent en utilisant des méthodes comme l'algorithme de Viterbi pour les modèles de Markov cachés. Le processus entier atteint finalement un maximum local de la vraisemblance marginale, mais il garantit des maxima locaux, pas l'optimum global. Dans les modèles de mélange, la procédure peut converger vers une solution avec des singularités, comme lorsqu'un composant a une variance nulle et que sa moyenne s'aligne avec un point de données.
Applications
EM est utilisé pour les mélanges de gaussiennes estimées et pour résoudre des problèmes de régression linéaire multiple avec des données manquantes. En apprentissage automatique, il est un composant central dans la sur-attente pour les modèles à variables latentes, y compris les modèles de mélange gaussiens pour le clustering, comme implémenté dans scikit-learn et d'autres bibliothèques. Il sous-tend également des algorithmes pour les chaînes de Markov pour les séquences de texte et pour la segmentation d'images en vision par ordinateur.
La méthode a été adoptée dans des domaines tels que les réseaux bayésiens et les modèles graphiques probabilistes, avec des influenceurs comme Michael Jordan et Daphne Koller l'appliquant à des modèles structurés. Dans les contextes modernes, EM sert de base théorique pour l'optimisation itérative dans les modèles graphcore, bien que les réseaux de neurones profonds utilisent souvent des méthodes basées sur le gradient à la place.
Variantes et extensions
Plusieurs variantes améliorent l'EM de base. L'EM généralisé (GEM) assouplit l'étape M pour trouver des paramètres qui augmentent plutôt que maximisent la log-vraisemblance attendue. La maximisation conditionnelle par espérance (ECM) divise l'étape M en sous-étapes plus simples, ce qui est utile pour les paramètres contraints. L'EM de Monte Carlo utilise un échantillonnage stochastique (par exemple, les chaînes de Markov Monte Carlo) dans l'étape E lorsque la log-vraisemblance attendue ne peut pas être calculée analytiquement. Ces méthodes conservent la robustesse centrale d'EM mais abordent des défis spécifiques en termes de coût computationnel.
Dans l'IA générative, les idées d'EM apparaissent dans l'apprentissage lorsque les modèles ont des représentations latentes, mais les modèles génératifs tels que IA générative reposent désormais sur des approches fréquentistes ou probabilistes adaptées aux réseaux de neurones.
Limites et considérations
EM n'est pas garanti de trouver un maximum global ; il peut s'arrêter à un maximum local ou à un point de selle. Il peut être sensible aux initialisations et, dans certains cas, les solutions présentent une singularité artificielle. De plus, l'étape E suppose que l'on peut calculer la log-vraisemblance attendue, ce qui peut être intraitable pour des modèles complexes. Des variantes comme l'inférence variationnelle (une alternative pour l'inférence approximative) ou des méthodes conjointes peuvent être appropriées. Dans les contextes modernes d'apprentissage automatique, les professionnels s'appuient souvent sur EM pour sa simplicité, mais pour les modèles GP profonds ou les réseaux de neurones, l'optimisation basée sur le gradient est préférée.
Voir aussi
- Apprentissage automatique
- Apprentissage profond
- Intelligence artificielle
- Université Carnegie Mellon (recherche en apprentissage automatique)
Références
- Dempster, A. P.; Laird, N. M.; Rubin, D. B. (1977). "Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society.
- Wu, C. F. J. (1983). On the convergence properties of the EM algorithm. Annals of Statistics.
- Hartley, H. O. (1958). Maximum likelihood estimation from incomplete data. Biometrics.
{, "infobox": {"type": "algorithme", "introduit": "1977", "introduit_par": "Arthur Dempster, Nan Laird et Donald Rubin", "lié": ["machine-learning", "artificial-intelligence", "deep-learning"]}, ", "catégories": ["statistical-algorithms", "machine-learning", "latent-variable-models","optimization-methods"]}