Der Expectation-Maximization-Algorithmus (EM-Algorithmus) ist ein iteratives Verfahren der Statistik zur Bestimmung von Maximum-Likelihood- oder Maximum-a-posteriori-Schätzungen von Parametern in statistischen Modellen, die von unbeobachteten latenten Variablen abhängen. Er ist besonders nützlich, wenn die Gleichungen für die Parameter nicht direkt gelöst werden können, etwa bei Mischmodellen oder wenn Daten fehlende Werte enthalten.
Die EM-Iteration wechselt zwischen einem Expectation-Schritt (E-Schritt), der die erwartete Log-Likelihood der vollständigen Daten unter den aktuellen Parameterschätzungen berechnet, und einem Maximization-Schritt (M-Schritt), der die Parameter durch Maximierung dieser erwarteten Log-Likelihood aktualisiert. Diese aktualisierten Parameterschätzungen werden dann im nächsten E-Schritt verwendet, und der Prozess wiederholt sich bis zur Konvergenz. Der Algorithmus konvergiert nachweislich zu einem lokalen Maximum oder Sattelpunkt der Likelihood-Funktion, jedoch nicht notwendigerweise zum globalen Maximum.
Historische Entwicklung
Der EM-Algorithmus wurde 1977 in einem Artikel von Arthur Dempster, Nan Laird und Donald Rubin formal benannt und erklärt, der später als DLR-Artikel bekannt wurde. Diese Arbeit etablierte das Verfahren als zentrales Werkzeug der statistischen Analyse. Frühere Autoren hatten die Technik jedoch bereits in spezifischen Fällen vorgeschlagen.
Ein Vorläufer war die Gen-Zählmethode, die von Cedric Smith zur Schätzung von Allelfrequenzen entwickelt wurde. H.O. Hartley schlug 1958 ebenfalls eine frühe Version vor, und Hartley und Hocking erweiterten diese 1977. Rolf Sundberg lieferte in seiner Dissertation und in nachfolgenden Arbeiten eine detaillierte Behandlung für exponentielle Familien, nach einer Zusammenarbeit mit Per Martin-Löf und Anders Martin-Löf.
Der DLR-Artikel von 1977 verallgemeinerte diese früheren Methoden und skizzierte eine Konvergenzanalyse für eine breite Klasse von Problemen. Diese Analyse wies jedoch Mängel auf, und ein korrekter Konvergenzbeweis wurde 1983 von C. F. Jeff Wu veröffentlicht, der die Konvergenz auch außerhalb der exponentiellen Familie etablierte.
Kernidee und verschränkte Gleichungen
In statistischen Modellen mit latenten Variablen erfordert die Maximum-Likelihood-Schätzung typischerweise die Lösung von Gleichungen, die beide Ketten betreffen. Die Lösung für die Parameter erfordert die Werte der latenten Variablen, und diese wiederum erfordern die Parameter, was zu einem wechselseitig abhängigen System führt, das nicht analytisch gelöst werden kann.
Der EM-Algorithmus löst dies, indem er einen Satz von Werten initialisiert (oft willkürliche Schätzungen für die Parameter) und zwischen den Schätzschritten wechselt. Beispielsweise kann er latente Variablen basierend auf aktuellen Parametern schätzen, dann diese latenten Variablen verwenden, um die Parameter zu aktualisieren, und den Zyklus wiederholen, bis beide Sätze zu einem Fixpunkt konvergieren. Obwohl intuitiv einfach, hat das Verfahren eine bewiesene Konvergenzeigenschaft: Die Ableitung der Likelihood nähert sich am Endpunkt Null.
Anwendungen und Einschränkungen
Eine häufige Anwendung ist die Schätzung der Parameter einer Mischung von Gauß-Verteilungen, bei der jeder beobachtete Datenpunkt zu einer unbeobachteten Mischungskomponente gehört. EM kann auch für multiple lineare Regression mit fehlenden Daten verwendet werden, wird jedoch oft in Bereichen wie maschinellem Lernen, künstlicher Intelligenz und anderen Feldern mit latenten Strukturen angewendet.
Eine Einschränkung ist, dass EM zu einem lokalen Maximum statt zum globalen Maximum konvergieren kann, und einige Likelihoods können Singularitäten aufweisen. Bei Mischmodellen kann beispielsweise eine Lösung mit unsinnigen Maxima auftreten, wenn einer Komponente eine Varianz von Null zugewiesen wird, was problematisch ist, aber ein bekanntes Ergebnis des iterativen Verfahrens darstellt.
Erweiterungen und praktische Hinweise
Erweiterungen von EM, wie der Expectation-Conditional-Maximization-Algorithmus (ECM) oder Monte-Carlo-EM, adressieren potenzielle Konvergenzprobleme oder Rechenkomplexität. In der Praxis wird EM gewählt, wenn die Log-Likelihood der vollständigen Daten einfacher zu optimieren ist als die marginale Likelihood, selbst wenn die beobachteten Daten unvollständig sind. Es bleibt eine grundlegende Methode zur Parameterschätzung mit latenten Variablen mit breiter Relevanz in der Statistik.
Referenzen
Der Name des DLR-Artikels und die Konvergenzanalyse von Wu von 1983 definieren die moderne Formulierung. Lehrbücher von Autoren wie Christopher Bishop (Pattern Recognition and Machine Learning) und Chris Bishop bieten detaillierte Behandlungen, die EM mit breiteren Themen der probabilistischen Modellierung und anderen Lernalgorithmen verbinden.