Algorithme EM

L'algorithme d'espérance-maximisation (EM) permet d'estimer les paramètres par maximum de vraisemblance dans des modèles comportant des données manquantes ou des variables latentes, en alternant l'imputation des informations manquantes et la maximisation de la log-vraisemblance attendue qui en résulte.

Definition

L'algorithme d'espérance-maximisation est une procédure itérative qui maximise une vraisemblance avec des données incomplètes en formant de manière répétée la log-vraisemblance attendue des données complètes étant donné les paramètres actuels (l'étape E) et en la maximisant pour mettre à jour les paramètres (l'étape M).

Scope

Ce sujet aborde l'étape E et l'étape M qui définissent l'algorithme, la propriété de montée monotone qui garantit que la vraisemblance ne diminue jamais, son comportement et sa vitesse de convergence, ses applications canoniques aux modèles de mélange et aux données manquantes, ainsi que ses extensions telles que les variantes EM généralisées et de Monte Carlo. Sa relation avec d'autres méthodes d'ascension est également notée.

Core questions

• Comment l'étape E et l'étape M augmentent-elles conjointement la vraisemblance des données observées ?
• Pourquoi l'algorithme garantit-il une augmentation monotone de la vraisemblance ?
• Comment l'algorithme est-il appliqué aux modèles de mélange et aux problèmes de données manquantes ?
• Qu'est-ce qui régit sa vitesse de convergence, et comment les variantes accélérées abordent-elles la convergence lente ?

Key concepts

• Vraisemblance des données complètes
• Étape E
• Étape M
• Variables latentes
• Convergence monotone
• Maxima locaux

Key theories

Alternance des étapes E et M

L'étape E calcule l'espérance de la log-vraisemblance des données complètes sous les paramètres actuels, et l'étape M maximise cette espérance ; l'itération conduit les paramètres vers un point stationnaire de la vraisemblance des données observées.

Propriété de montée monotone

Chaque itération ne diminue pas de manière prouvée la vraisemblance des données observées, ce qui confère à l'algorithme sa stabilité, bien qu'il puisse converger lentement et uniquement vers un maximum local en fonction de l'initialisation.

Clinical relevance

L'algorithme d'espérance-maximisation est le moteur standard pour l'ajustement des modèles de mélange finis, des modèles de Markov cachés, des modèles factoriels et de classes latentes, ainsi que pour la gestion des données manquantes, ce qui en fait un outil fondamental en statistique, en apprentissage automatique, en génétique et en traitement du signal.

History

Dempster, Laird et Rubin ont unifié de nombreux algorithmes de cas particuliers antérieurs au sein du cadre général d'espérance-maximisation en 1977 ; les travaux ultérieurs ont développé la théorie de la convergence, les schémas d'accélération, et les variantes de Monte Carlo et généralisées pour les étapes intraitables.

Key figures

• Arthur Dempster
• Nan Laird
• Donald Rubin
• Geoffrey McLachlan

Seminal works

• dempster1977
• mclachlan2008

Frequently asked questions

Pourquoi utiliser l'algorithme d'espérance-maximisation plutôt qu'une maximisation directe ?

Lorsque les données sont incomplètes ou qu'un modèle comporte des variables latentes, la vraisemblance des données observées peut être difficile à maximiser directement. L'algorithme utilise la vraisemblance des données complètes, plus simple, et converge de manière fiable avec une non-diminution garantie à chaque étape.

L'algorithme trouve-t-il toujours le maximum global ?

Non. Il converge vers un point stationnaire qui dépend des valeurs initiales, lequel peut être un maximum local ou un point selle. L'exécuter à partir de plusieurs initialisations est la précaution habituelle.