Der Erwartungs-Maximierungs-Algorithmus (EM-Algorithmus) ist eine iterative Methode in der Statistik und im maschinellen Lernen zur Bestimmung lokaler Maximum-Likelihood- oder Maximum-a-posteriori-Schätzungen von Parametern in statistischen Modellen, die von unbeobachteten latenten Variablen abhängen. EM wechselt zwischen einem Erwartungsschritt (E-Schritt), der eine Funktion für die erwartete Log-Likelihood unter Verwendung aktueller Parameterschätzungen berechnet, und einem Maximierungsschritt (M-Schritt), der die Parameter aktualisiert, um diese erwartete Log-Likelihood zu maximieren. Diese aktualisierten Schätzungen fließen dann in den nächsten E-Schritt ein, und der Prozess wiederholt sich bis zur Konvergenz.
Im maschinellen Lernen ist EM ein zentrales Werkzeug für Modelle mit unvollständigen Daten, wie Mischmodelle (z. B. Gaußsche Mischmodelle) und verborgene Markov-Modelle. Es findet Anwendung beim Clustering, bei der Bildsegmentierung und bei der Parameterschätzung für probabilistische grafische Modelle und dient als Grundlage für fortgeschrittenere variationale Inferenz, die in tiefen generativen Modellen verwendet wird.
Geschichte
Der EM-Algorithmus wurde in einem Artikel von Arthur Dempster, Nan Laird und Donald Rubin aus dem Jahr 1977 formal benannt und erklärt, aber die Methode war zuvor für spezifische Fälle vorgeschlagen worden. Cedric Smith verwendete Genzählung zur Schätzung von Allelfrequenzen, und H.O. Hartley führte 1958 einen verwandten Ansatz ein, den Hartley mit Hocking 1977 erweiterte und der zentrale Konzepte lieferte. Rolf Sundberg entwickelte eine detaillierte Behandlung für exponentielle Familien, beeinflusst von Per Martin-Löf und Anders Martin-Löf. Der Artikel von Dempster-Laird-Rubin verallgemeinerte die Methode und erweiterte sie für eine breitere Klasse, obwohl sein Konvergenzbeweis fehlerhaft war. C. F. Jeff Wu lieferte 1983 eine korrigierte Konvergenzanalyse und etablierte die Gültigkeit von EM über exponentielle Familien hinaus. Der Algorithmus wurde zu einem Standard in der statistischen Analyse, und spätere Arbeiten, wie die von Meng und van Dyk (1997), verfeinerten ihn weiter.
Algorithmusschritte
Der EM-Algorithmus befasst sich mit Optimierungsproblemen, bei denen die Likelihood-Funktion latente Variablen enthält, was eine direkte derivativebasierte Maximierung in vielen Fällen unmöglich macht. Stattdessen löst der Algorithmus iterativ ineinandergreifende Gleichungen: Die Parameter hängen von latenten Variablen ab, und latente Variablen hängen von Parametern ab, was bei direkter Substitution in der Regel unlösbare Gleichungen ergibt.
EM durchbricht diesen Zyklus, indem es zwischen zwei Schritten wechselt:
- E-Schritt: Bei gegebenen aktuellen Parameterschätzungen aus der vorherigen Iteration wird der erwartete Wert der Log-Likelihood in Bezug auf die Verteilung der latenten Variablen berechnet, konditioniert auf die beobachteten Daten.
- M-Schritt: Maximierung der erwarteten Log-Likelihood in Bezug auf die Parameter, was neue Schätzungen ergibt, die garantiert die Likelihood der beobachteten Daten erhöhen oder konstant halten (nicht abnehmend). Dies wird bis zur Konvergenz wiederholt.
Wenn das Modell unabhängige latente Variablen hat, vereinfacht sich der E-Schritt zur Bestimmung der Maximum-a-posteriori-Schätzung der latenten Variablen, oft unter Verwendung von Methoden wie dem Viterbi-Algorithmus für verborgene Markov-Modelle. Der gesamte Prozess erreicht schließlich ein lokales Maximum der marginalen Likelihood, garantiert jedoch lokale Maxima und nicht das globale Optimum. Bei Mischmodellen kann das Verfahren zu einer Lösung mit Singularitäten konvergieren, z. B. wenn eine Komponente eine Varianz von null hat und ihr Mittelwert mit einem Datenpunkt übereinstimmt.
Anwendungen
EM wird für Mischungen geschätzter Gauß-Verteilungen und zur Lösung mehrerer linearer Regressionsprobleme mit fehlenden Daten verwendet. Im maschinellen Lernen ist es eine Kernkomponente bei der Übererwartung für latente Variablenmodelle, einschließlich Gaußscher Mischmodelle für das Clustering, wie sie in scikit-learn und anderen Bibliotheken implementiert sind. Es liegt auch Algorithmen für Markov-Ketten für Textsequenzen und für die Bildsegmentierung in der Computer Vision zugrunde.
Die Methode wurde in Bereichen wie Bayesschen Netzen und probabilistischen grafischen Modellen übernommen, wobei einflussreiche Persönlichkeiten wie Michael Jordan und Daphne Koller sie auf strukturierte Modelle anwendeten. In modernen Kontexten dient EM als theoretisches Rückgrat für iterative Optimierung in Graphcore-Modellen, obwohl tiefe neuronale Netze oft gradientenbasierte Methoden verwenden.
Varianten und Erweiterungen
Mehrere Varianten verbessern das Basis-EM. Das generalisierte EM (GEM) lockert den M-Schritt, indem es Parameter findet, die die erwartete Log-Likelihood erhöhen statt maximieren. Die Erwartungs-konditionale-Maximierung (ECM) teilt den M-Schritt in einfachere Unterschritte auf, was sie für eingeschränkte Parameter nützlich macht. Das Monte-Carlo-EM verwendet stochastisches Sampling (z. B. Markov-Ketten-Monte-Carlo) im E-Schritt, wenn die erwartete Log-Likelihood nicht analytisch berechnet werden kann. Diese Methoden behalten die Kernrobustheit von EM bei, bewältigen jedoch spezifische Herausforderungen bei den Rechenkosten.
In der generativen KI tauchen EM-Ideen beim Lernen auf, wenn Modelle latente Repräsentationen haben, aber generative Modelle wie generative KI stützen sich heute auf frequentistische oder probabilistische Ansätze, die auf neuronale Netze zugeschnitten sind.
Grenzen und Überlegungen
EM garantiert nicht das Auffinden eines globalen Maximums; es kann bei einem lokalen Maximum oder Sattelpunkt stoppen. Es kann empfindlich auf Initialisierungen reagieren, und in einigen Fällen haben Lösungen eine künstliche Singularität. Darüber hinaus setzt der E-Schritt voraus, dass die erwartete Log-Likelihood berechnet werden kann, was bei komplexen Modellen möglicherweise nicht durchführbar ist. Varianten wie variationale Inferenz (eine Alternative für approximative Inferenz) oder gemeinsame Methoden könnten geeignet sein. In modernen ML-Kontexten verlassen sich Fachleute oft auf EM wegen seiner Einfachheit, aber für tiefe GP-Modelle oder neuronale Netze wird gradientenbasierte Optimierung bevorzugt.
Siehe auch
Referenzen
- 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.
- Wu, C. F. J. (1983). On the convergence properties of the EM algorithm. Annals of Statistics.
- Hartley, H. O. (1958). Maximum likelihood estimation from incomplete data. Biometrics.
{, "infobox": {"type": "algorithm", "introduced": "1977", "introduced_by": "Arthur Dempster, Nan Laird, and Donald Rubin", "related": ["machine-learning", "artificial-intelligence", "deep-learning"]}, ", "categories": ["statistical-algorithms", "machine-learning", "latent-variable-models","optimization-methods"]}