Zum Inhalt springen
Zurück zu den Suchergebnissen

EM-Algorithmus

Eingeführt von
Dempster, Laird & Rubin
Jahr
1977
Typ
Iterative optimization algorithm
Familie
Estimation

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Der Erwartungs-Maximierungs-Algorithmus (EM-Algorithmus) ist ein iteratives Optimierungsverfahren zur Ermittlung von Maximum-Likelihood- oder Maximum-A-posteriori-Schätzungen von Parametern in statistischen Modellen mit latenten Variablen oder fehlenden Daten.

Eingeführt von Dempster, Laird und Rubin in ihrer wegweisenden Arbeit von 1977, wechselt EM zwischen der Berechnung der erwarteten Log-Likelihood vollständiger Daten (E-Schritt) und deren Maximierung bezüglich der Parameter (M-Schritt), was bei jeder Iteration eine monoton nicht abnehmende Likelihood garantiert.

Die Intuition hinter der Methode

Stellen Sie sich vor, Sie versuchen, die Regeln eines Spiels zu lernen, indem Sie Spieler beobachten, deren Karten Sie nicht sehen können. In jeder Runde raten Sie, welche Karten sie wahrscheinlich halten, basierend auf dem, was Sie beobachten, und aktualisieren dann Ihr Modell der Regeln unter der Annahme, dass diese Vermutungen korrekt sind. EM macht genau das: Der E-Schritt füllt die fehlenden Informationen probabilistisch unter Verwendung aktueller Parameterschätzungen auf, und der M-Schritt passt das Modell neu an, als ob diese aufgefüllten Werte reale Beobachtungen wären.

Geschichte

Der Algorithmus wurde 1977 von Arthur Dempster, Nan Laird und Donald Rubin in ihrer JRSS-B-Arbeit formal vereinheitlicht und benannt, die bis heute eine der meistzitierten statistischen Publikationen ist. Die Arbeit verallgemeinerte frühere Sonderfallverfahren, die unabhängig für spezifische Probleme mit fehlenden Daten entwickelt wurden. In den folgenden Jahrzehnten entstanden zahlreiche Erweiterungen, darunter die Algorithmen ECM, ECME, AECM und SEM, die die Anwendbarkeit erweiterten und die Konvergenz in vielen praktischen Situationen beschleunigten.

Wann wird sie eingesetzt?

Verwenden Sie den EM-Algorithmus, wenn die Daten fehlende Werte, versteckte Zustände oder latente Variablen enthalten und Sie Maximum-Likelihood-Schätzungen benötigen. Er eignet sich gut für Gaußsche Mischmodelle, versteckte Markov-Modelle, Faktorenanalyse und die Imputation fehlender Daten. Wichtige Annahmen sind, dass fehlende Daten zufällig fehlen (MAR) und dass das Modell für vollständige Daten handhabbar ist. Einschränkungen sind die Sensitivität gegenüber der Initialisierung, die mögliche Konvergenz zu lokalen Maxima und die langsame Konvergenz in der Nähe von Sattelpunkten. Alternativen umfassen gradientenbasierte Optimierung mit numerischer Integration, variationale Inferenz oder MCMC-Methoden.

Grenzen und Hinweise

  • Konvergenz zu einem lokalen Maximum statt zum globalen Maximum, wenn die Likelihood-Oberfläche multimodal ist
  • Kann eine sehr langsame (lineare) Konvergenz aufweisen, wenn der Anteil der fehlenden Informationen groß ist
  • Erfordert, dass der Analyst das Modell für vollständige Daten und die Verteilung der latenten Variablen spezifiziert
  • Der Standard-EM liefert nicht direkt die Kovarianzmatrix der Schätzungen für beobachtete Daten; ein ergänzender Schritt (z. B. Louis' Methode oder der SEM-Algorithmus) ist für Standardfehler erforderlich

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Garantierte monotone Erhöhung der Likelihood beobachteter Daten bei jeder Iteration, was eine stabile Konvergenz gewährleistet
  • Wandelt ein schwieriges Problem mit fehlenden Daten in eine Folge von handhabbaren Optimierungen vollständiger Daten um
  • Breit anwendbar auf Modelle der Exponentialfamilie, Mischmodelle und latente Variablen-Frameworks
  • Geschlossene M-Schritt-Updates sind für viele Standardmodelle verfügbar, was die Implementierung effizient macht

Anwendungen

  • Anpassung von Gaußschen Mischmodellen zur Clusterbildung und Dichteschätzung
  • Training von versteckten Markov-Modellen für Spracherkennung und Analyse biologischer Sequenzen
  • Multiple Imputation und Analyse fehlender Daten in der klinischen und sozialwissenschaftlichen Forschung
  • Parameterschätzung in der Faktorenanalyse und latenten Klassenanalyse
  • Bildsegmentierung und -rekonstruktion in der medizinischen Bildgebung

So funktioniert es

So funktioniert es

1

Vor Beginn der Iteration wählt der Analyst Startwerte für die unbekannten Parameter, bezeichnet als theta-0. Diese können zufällig, aus einer vereinfachten Anpassung oder durch Domänenwissen gewählt werden. Die Qualität der Initialisierung kann beeinflussen, zu welchem lokalen Maximum der Algorithmus konvergiert, was mehrfache zufällige Neustarts zu einer gängigen Praxis macht.

Formel
\text{Choose initial parameter estimates } \theta^{(0)}
2

Gegeben die aktuelle Parameterschätzung theta-t, berechnet der E-Schritt Q, den Erwartungswert der Log-Likelihood vollständiger Daten über die Verteilung der unbeobachteten latenten Variablen Z, bedingt auf die beobachteten Daten X. Diese Erwartung ersetzt effektiv unbekannte Mengen durch ihre probabilistischen Schätzungen, ohne sich auf einen einzelnen imputierten Wert festzulegen.

Formel
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

Der M-Schritt maximiert die Q-Funktion aus dem E-Schritt bezüglich theta und liefert eine aktualisierte Schätzung theta-(t+1). Da die Log-Likelihood vollständiger Daten oft einfacher zu maximieren ist als die marginale Log-Likelihood beobachteter Daten, ist dieser Schritt häufig handhabbar, selbst wenn die direkte Maximum-Likelihood-Schätzung nicht handhabbar ist.

Formel
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

Die E- und M-Schritte werden abwechselnd wiederholt. Nach jedem vollständigen Zyklus wird die Log-Likelihood der beobachteten Daten ausgewertet. Die Iteration stoppt, wenn die Änderung der Log-Likelihood (oder des Parametervektors) unter eine vom Benutzer definierte Toleranz epsilon fällt. Dempster et al. bewiesen, dass jeder Zyklus die Likelihood der beobachteten Daten nicht verringern kann, was eine stabile Konvergenz gewährleistet.

Formel
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

Häufige Fallstricke

  • Die Verwendung einer einzigen zufälligen Initialisierung birgt das Risiko, bei einem schlechten lokalen Maximum zu enden; führen Sie immer mehrere Neustarts durch und wählen Sie die Lösung mit der höchsten endgültigen Log-Likelihood
  • Zu frühe Konvergenzerklärung durch Überwachung nur der Parameteränderung statt der Log-Likelihood beobachteter Daten kann zu ungenauen Schätzungen führen
  • Die Anwendung von EM, wenn Daten Missing Not At Random (MNAR) sind, ohne Modellanpassung, kann systematische Verzerrungen in den Schätzungen einführen
  • Das Ignorieren des Label-Switching-Problems bei Mischmodellen führt zu uninterpretierbaren Komponenten-Zuweisungen, selbst nach korrekter Konvergenz

Häufig gestellte Fragen

Konvergiert der EM-Algorithmus immer zum globalen Maximum?

Nein. EM garantiert nur, ein lokales Maximum (oder Sattelpunkt) der Likelihood beobachteter Daten zu finden. Wenn die Likelihood-Oberfläche mehrere Maxima aufweist, hängt die endgültige Lösung von der Initialisierung ab. Die Ausführung des Algorithmus von mehreren verschiedenen Startpunkten aus und die Beibehaltung der Lösung mit der höchsten Log-Likelihood ist die übliche praktische Abhilfe.

Wie unterscheidet sich EM von der direkten Maximum-Likelihood-Optimierung?

Die direkte MLE maximiert die Log-Likelihood beobachteter Daten, was möglicherweise nicht handhabbare Integrale über latente Variablen beinhaltet. EM umgeht dies, indem es iterativ die erwartete Log-Likelihood vollständiger Daten maximiert, die oft analytisch handhabbar ist. Der Kompromiss ist, dass EM langsam konvergieren kann, während gradientenbasierte Methoden schneller sein können, wenn Gradienten der marginalen Likelihood verfügbar sind.

Wann sollte ich MICE-Imputation dem EM-Algorithmus vorziehen?

MICE (Multiple Imputation by Chained Equations) ist vorzuziehen, wenn die Daten Variablen unterschiedlicher Typen, nichtlineare Beziehungen oder komplexe Interaktionsstrukturen enthalten, die sich schwer in einem einzigen parametrischen Modell für vollständige Daten kodieren lassen. EM ist natürlicher, wenn ein gut spezifiziertes gemeinsames Modell für alle Variablen existiert und die Inferenz auf die Modellparameter und nicht auf imputierte Datensätze abzielt.

Verwandte Methoden

Quellen

  1. 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.

    DOI-Referenz öffnen
    Kopiert.