Der Expectation-Maximization-Algorithmus (EM-Algorithmus) ist ein iteratives Verfahren, das in der Statistik verwendet wird, um lokale Maximum-Likelihood- oder Maximum-a-posteriori-Schätzungen (MAP) von Parametern in statistischen Modellen zu finden, die von unbeobachteten latenten Variablen abhängen. Der Algorithmus wechselt zwischen einem Expectation-Schritt (E-Schritt), in dem die erwartete Log-Likelihood-Funktion basierend auf den aktuellen Parameterschätzungen berechnet wird, und einem Maximization-Schritt (M-Schritt), in dem die Parameter aktualisiert werden, um diese erwartete Log-Likelihood zu maximieren. Diese aktualisierten Parameter fließen dann in den nächsten E-Schritt ein, und der Prozess wird wiederholt, bis Konvergenz erreicht ist. EM wird häufig in Bereichen wie Machine learning eingesetzt, beispielsweise zur Schätzung von Mischmodellen, zur Behandlung fehlender Daten und zum Training von Hidden-Markov-Modellen.
Die zentrale Herausforderung, die EM adressiert, entsteht, wenn eine Likelihood-Funktion sowohl beobachtete Daten als auch unbeobachtete latente Variablen umfasst. Eine direkte Maximierung der Likelihood durch Ableitungen nach allen Unbekannten führt typischerweise zu verschränkten Gleichungen, die nicht analytisch lösbar sind. EM umgeht dieses Problem, indem es iterativ eine Gruppe von Unbekannten löst, während die andere fixiert bleibt, und wechselt, bis beide zu einem Fixpunkt konvergieren. Dieser Ansatz erhöht die Likelihood bei jeder Iteration garantiert, kann jedoch zu einem lokalen Maximum oder Sattelpunkt konvergieren, anstatt zum globalen Optimum.
Geschichte
Der EM-Algorithmus wurde in einem klassischen Artikel von Arthur Dempster, Nan Laird und Donald Rubin aus dem Jahr 1977 formal benannt und erklärt. Die Methode wurde jedoch bereits in Spezialfällen von früheren Autoren vorgeschlagen. Cedric Smith führte eine Genzählmethode zur Schätzung von Allelfrequenzen ein, und H.O. Hartley schlug 1958 einen verwandten Ansatz vor, mit weiteren Entwicklungen durch Hartley und Hocking im Jahr 1977. Rolf Sundberg lieferte in seiner Dissertation und in späteren Arbeiten eine detaillierte Behandlung für exponentielle Familien, basierend auf einer Zusammenarbeit mit Per Martin-Löf und Anders Martin-Löf. Der Artikel von Dempster, Laird und Rubin aus dem Jahr 1977 verallgemeinerte diese Ideen und skizzierte eine Konvergenzanalyse, wodurch EM zu einem wichtigen statistischen Werkzeug wurde. Ein korrekter Konvergenzbeweis wurde später 1983 von C. F. Jeff Wu veröffentlicht, der Fehler in der ursprünglichen Analyse behob und die Konvergenzgarantien über exponentielle Familien hinaus erweiterte.
Algorithmusbeschreibung
Gegeben seien beobachtete Daten X, latente Daten Z und unbekannte Parameter θ. Das Ziel ist es, die marginale Likelihood-Funktion L(θ; X) = ∫ p(X, Z | θ) dZ zu maximieren. Die EM-Iteration besteht aus zwei Schritten:
- E-Schritt: Berechne den Erwartungswert der Log-Likelihood-Funktion, Q(θ | θ^(t)), bezüglich der bedingten Verteilung von Z gegeben X und der aktuellen Parameterschätzung θ^(t).
- M-Schritt: Finde die Parameter θ^(t+1), die Q(θ | θ^(t)) maximieren.
Die aktualisierten Parameter werden dann im nächsten E-Schritt verwendet, und der Prozess wird wiederholt, bis die Änderung der Parameter oder der Likelihood unter einen Schwellenwert fällt. Dieses Verfahren erhöht die Likelihood monoton und gewährleistet die Konvergenz zu einem stationären Punkt.
Anwendungen
EM wird häufig zur Schätzung von Parametern in Mischmodellen verwendet, wie beispielsweise Gaußschen Mischmodellen, bei denen angenommen wird, dass jeder beobachtete Datenpunkt aus einer von mehreren zugrunde liegenden Komponenten stammt. Es behandelt auch Probleme mit fehlenden Daten, bei denen einige Beobachtungen unvollständig sind. In Artificial intelligence bildet EM die Grundlage für Trainingsalgorithmen von Hidden-Markov-Modellen, die in der Spracherkennung und Bioinformatik eingesetzt werden. Darüber hinaus kann EM multiple lineare Regressionsprobleme mit latenten Variablen lösen und wird in der Faktorenanalyse und beim Clustering angewendet.
Eigenschaften und Einschränkungen
EM ist rechnerisch effizient und für viele Modelle einfach zu implementieren, hat jedoch Einschränkungen. Es kann zu lokalen Maxima konvergieren, und die endgültige Lösung hängt von der Initialisierung ab. Bei Mischmodellen kann EM singuläre Lösungen finden, bei denen eine Komponente eine Varianz von null aufweist, was unsinnige Maxima darstellt. Der Algorithmus erfordert außerdem die Angabe der Anzahl latenter Komponenten oder Zustände, die oft unbekannt ist. Varianten wie der generalisierte EM-Algorithmus und der stochastische EM-Algorithmus adressieren einige dieser Probleme, aber die grundlegende Methode bleibt ein fundamentales Werkzeug in der statistischen Datenanalyse.
Verwandte Konzepte
Der EM-Algorithmus ist eng mit anderen iterativen Optimierungstechniken im Bereich Machine learning verwandt, wie gradientenbasierten Methoden wie Stochastic Gradient Descent Variants und Adam (Optimizer). Er ist auch mit der variationalen Inferenz in Deep learning verbunden, wo approximative Posterior-Verteilungen optimiert werden. In Generative AI finden EM-ähnliche Ansätze Anwendung beim Training latenter Variablenmodelle, und seine Prinzipien sind grundlegend für das Verständnis fortgeschrittenerer Algorithmen wie Reinforcement Learning from AI Feedback (RLAIF) und Curriculum Learning.