EM-Algorithmus

Der Erwartungs-Maximierungs-Algorithmus (EM-Algorithmus) findet Maximum-Likelihood-Schätzungen in Modellen mit fehlenden Daten oder latenten Variablen, indem er zwischen der Imputation der fehlenden Informationen und der Maximierung der resultierenden erwarteten Log-Likelihood alterniert.

Definition

Der Erwartungs-Maximierungs-Algorithmus ist ein iteratives Verfahren, das eine Likelihood mit unvollständigen Daten maximiert, indem es wiederholt die erwartete Log-Likelihood der vollständigen Daten unter Berücksichtigung der aktuellen Parameter bildet (der E-Schritt) und diese maximiert, um die Parameter zu aktualisieren (der M-Schritt).

Scope

Dieses Thema behandelt den E-Schritt und den M-Schritt, die den Algorithmus definieren, die monotone Aufstiegseigenschaft, die garantiert, dass die Likelihood niemals abnimmt, sein Konvergenzverhalten und seine Konvergenzrate, kanonische Anwendungen auf Mischmodelle und fehlende Daten sowie Erweiterungen wie die verallgemeinerten und Monte-Carlo-EM-Varianten. Seine Beziehung zu anderen Aufstiegsmethoden wird ebenfalls beleuchtet.

Core questions

• Wie erhöhen der E-Schritt und der M-Schritt gemeinsam die Likelihood der beobachteten Daten?
• Warum garantiert der Algorithmus einen monotonen Anstieg der Likelihood?
• Wie wird der Algorithmus auf Mischmodelle und Probleme mit fehlenden Daten angewendet?
• Was bestimmt seine Konvergenzrate, und wie begegnen beschleunigte Varianten einer langsamen Konvergenz?

Key concepts

• Likelihood der vollständigen Daten
• E-Schritt
• M-Schritt
• Latente Variablen
• Monotone Konvergenz
• Lokale Maxima

Key theories

Alternation von E-Schritt und M-Schritt

Der E-Schritt berechnet die Erwartung der Log-Likelihood der vollständigen Daten unter den aktuellen Parametern, und der M-Schritt maximiert diese Erwartung; die Iteration treibt die Parameter zu einem stationären Punkt der Likelihood der beobachteten Daten.

Monotone Aufstiegseigenschaft

Jede Iteration verringert nachweislich nicht die Likelihood der beobachteten Daten, was dem Algorithmus seine Stabilität verleiht, obwohl er je nach Initialisierung langsam und nur zu einem lokalen Maximum konvergieren kann.

Clinical relevance

Der Erwartungs-Maximierungs-Algorithmus ist der Standardmotor für die Anpassung von endlichen Mischmodellen, Hidden-Markov-Modellen, Faktor- und Latent-Class-Modellen sowie für den Umgang mit fehlenden Daten, was ihn zu einer grundlegenden Methode in Statistik, maschinellem Lernen, Genetik und Signalverarbeitung macht.

History

Dempster, Laird und Rubin vereinigten 1977 viele frühere Spezialfallalgorithmen zu dem allgemeinen Erwartungs-Maximierungs-Framework; nachfolgende Arbeiten entwickelten die Konvergenztheorie, Beschleunigungsschemata sowie Monte-Carlo- und verallgemeinerte Varianten für unlösbare Schritte.

Key figures

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

Seminal works

• dempster1977
• mclachlan2008

Frequently asked questions

Warum sollte man den Erwartungs-Maximierungs-Algorithmus anstelle einer direkten Maximierung verwenden?

Wenn Daten unvollständig sind oder ein Modell latente Variablen aufweist, kann die Maximierung der Likelihood der beobachteten Daten direkt schwierig sein. Der Algorithmus arbeitet mit der einfacheren Likelihood der vollständigen Daten und konvergiert zuverlässig mit einer garantierten Nicht-Abnahme bei jedem Schritt.

Findet der Algorithmus immer das globale Maximum?

Nein. Er konvergiert zu einem stationären Punkt, der von den Startwerten abhängt und ein lokales Maximum oder ein Sattelpunkt sein kann. Das Ausführen von mehreren Initialisierungen ist die übliche Vorsichtsmaßnahme.