Algorithme EM
- Introduite par
- Dempster, Laird & Rubin
- Année
- 1977
- Type
- Iterative optimization algorithm
- Famille
- Estimation
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
Imaginez essayer d'apprendre les règles d'un jeu en observant des joueurs dont vous ne pouvez pas voir les cartes.
À chaque tour, vous devinez quelles cartes ils détiennent probablement en fonction de ce que vous observez, puis vous mettez à jour votre modèle des règles en supposant que ces suppositions sont correctes. EM fait exactement cela : l'étape E remplit les informations manquantes de manière probabiliste en utilisant les estimations de paramètres actuelles, et l'étape M réajuste le modèle comme si ces valeurs remplies étaient des observations réelles.
L’intuition derrière la méthode
Avant le début de l'itération, l'analyste sélectionne des valeurs de départ pour les paramètres inconnus, notés $\theta^0$. Celles-ci peuvent être choisies aléatoirement, à partir d'un ajustement simplifié, ou par connaissance du domaine. La qualité de l'initialisation peut affecter le maximum local vers lequel l'algorithme converge, faisant des redémarrages aléatoires multiples une pratique courante.
Histoire
Ajustement de modèles de mélange gaussien pour le clustering et l'estimation de densité
Quand l’utiliser
Augmentation monotone garantie de la vraisemblance des données observées à chaque itération, assurant une convergence stable
Limites et points d’attention
- Peut présenter une convergence très lente (linéaire) lorsque la fraction d'information manquante est importante
- Nécessite que l'analyste spécifie le modèle de données complètes et la distribution des variables latentes
- L'EM standard ne fournit pas directement la matrice de covariance des données observées des estimations ; une étape supplémentaire (par exemple, la méthode de Louis ou l'algorithme SEM) est nécessaire pour les erreurs standard
- L'utilisation d'une seule initialisation aléatoire risque de terminer sur un maximum local médiocre ; exécutez toujours plusieurs redémarrages et sélectionnez la solution avec la log-vraisemblance finale la plus élevée
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Convertit un problème difficile de données manquantes en une séquence d'optimisations traitables de données complètes
- Largement applicable aux modèles de la famille exponentielle, aux modèles de mélange et aux cadres à variables latentes
- Des mises à jour de l'étape M en forme fermée sont disponibles pour de nombreux modèles standards, rendant l'implémentation efficace
- Convergence vers un maximum local plutôt que vers le maximum global lorsque la surface de vraisemblance est multimodale
Applications
- Entraînement de modèles de Markov cachés pour la reconnaissance vocale et l'analyse de séquences biologiques
- Imputation multiple et analyse de données manquantes dans la recherche en sciences cliniques et sociales
- Estimation de paramètres en analyse factorielle et en analyse de classes latentes
- Segmentation et reconstruction d'images en imagerie médicale
- L'algorithme EM converge-t-il toujours vers le maximum global ?
Comment ça marche
Comment ça marche
Étant donné l'estimation du paramètre actuelle $\theta^t$, l'étape E calcule $Q$, la valeur espérée de la log-vraisemblance des données complètes sur la distribution des variables latentes non observées $Z$, conditionnellement aux données observées $X$. Cette espérance remplace effectivement les quantités inconnues par leurs estimations probabilistes sans s'engager sur une seule valeur imputée.
Formule
\text{Choose initial parameter estimates } \theta^{(0)}L'étape M maximise la fonction $Q$ de l'étape E par rapport à $\theta$, produisant une estimation mise à jour $\theta^{(t+1)}$. Parce que la log-vraisemblance des données complètes est souvent plus simple à maximiser que la log-vraisemblance marginale des données observées, cette étape est fréquemment traitable même lorsque le maximum de vraisemblance direct ne l'est pas.
Formule
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]Les étapes E et M sont répétées en alternance. Après chaque cycle complet, la log-vraisemblance des données observées est évaluée. L'itération s'arrête lorsque la variation de la log-vraisemblance (ou du vecteur de paramètres) tombe en dessous d'une tolérance $\epsilon$ définie par l'utilisateur. Dempster et al. ont prouvé que chaque cycle ne peut pas diminuer la vraisemblance des données observées, assurant une convergence stable.
Formule
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})Utilisez l'algorithme EM lorsque les données contiennent des valeurs manquantes, des états cachés ou des variables latentes et que vous avez besoin d'estimations du maximum de vraisemblance. Il est bien adapté aux modèles de mélange gaussien, aux modèles de Markov cachés, à l'analyse factorielle et à l'imputation de données manquantes. Les hypothèses clés incluent que les données manquantes sont manquantes de manière aléatoire (MAR) et que le modèle de données complètes est traitable. Les limites incluent la sensibilité à l'initialisation, la convergence possible vers des maxima locaux et une convergence lente près des points selle. Les alternatives incluent l'optimisation basée sur le gradient avec intégration numérique, l'inférence variationnelle ou les méthodes MCMC.
Formule
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilonPièges courants
- Déclarer une convergence trop précoce en ne surveillant que le changement de paramètre plutôt que la log-vraisemblance des données observées peut produire des estimations inexactes
- Appliquer EM lorsque les données sont Manquantes Non Aléatoirement (MNAR) sans ajustement du modèle peut introduire un biais systématique dans les estimations
- Ignorer le problème de permutation des étiquettes dans les modèles de mélange conduit à des affectations de composantes ininterprétables même après une convergence correcte
- L'algorithme a été formellement unifié et nommé par Arthur Dempster, Nan Laird et Donald Rubin dans leur article de 1977 dans JRSS-B, qui reste l'un des articles de statistiques les plus cités jamais publiés. L'article a généralisé des procédures de cas spéciaux antérieures développées indépendamment pour des problèmes spécifiques de données manquantes. Les décennies suivantes ont vu de nombreuses extensions, y compris les algorithmes ECM, ECME, AECM et SEM, élargissant l'applicabilité et accélérant la convergence dans de nombreux contextes pratiques.
Questions fréquentes
Non. EM est garanti seulement de trouver un maximum local (ou un point selle) de la vraisemblance des données observées. Lorsque la surface de vraisemblance a plusieurs modes, la solution finale dépend de l'initialisation. L'exécution de l'algorithme à partir de plusieurs points de départ différents et la conservation de la solution avec la log-vraisemblance la plus élevée est le remède pratique standard.
En quoi EM diffère-t-il de l'optimisation directe du maximum de vraisemblance ?
Le MLE direct maximise la log-vraisemblance des données observées, ce qui peut impliquer des intégrales incalculables sur les variables latentes. EM évite cela en maximisant itérativement la log-vraisemblance espérée des données complètes, qui est souvent analytiquement traitable. Le compromis est qu'EM peut converger lentement, tandis que les méthodes basées sur le gradient peuvent être plus rapides lorsque les gradients de la vraisemblance marginale sont disponibles.
Quand devrais-je préférer l'imputation MICE à l'algorithme EM ?
MICE (Multiple Imputation by Chained Equations) est préférable lorsque les données incluent des variables de types mixtes, des relations non linéaires ou des structures d'interaction complexes difficiles à encoder dans un seul modèle paramétrique de données complètes. EM est plus naturel lorsqu'un modèle conjoint bien spécifié pour toutes les variables existe et que l'inférence cible les paramètres du modèle plutôt que les jeux de données imputés.
L'algorithme EM est disponible en tant que routine de base dans les principaux kits d'outils statistiques et d'apprentissage automatique, et peut également être implémenté à partir de zéro étant donné un modèle de données complètes traitable et ses statistiques suffisantes.
Méthodes associées
Sources
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: Series B, 39(1), 1–38.
Ouvrir la référence DOICopié.