Der Expectation-Maximization-Algorithmus (EM-Algorithmus) ist eine iterative statistische Methode zur Bestimmung von Maximum-Likelihood-Schätzungen der Parameter in Modellen mit latenten (unbeobachteten) Variablen. Ein Gaußsches Mischmodell (GMM) ist ein probabilistisches Modell, das annimmt, dass alle Datenpunkte aus einer Mischung einer endlichen Anzahl von Gaußschen Verteilungen mit unbekannten Parametern erzeugt werden. Der EM-Algorithmus ist der Standardansatz zur Anpassung eines GMM, wobei zwischen einem Erwartungsschritt (E-Schritt) und einem Maximierungsschritt (M-Schritt) abgewechselt wird, bis Konvergenz erreicht ist. Diese Technik liegt vielen Anwendungen im Machine learning zugrunde, einschließlich Clustering, Dichteschätzung und Anomalieerkennung.
Der EM-Algorithmus wurde formal in einem Artikel von 1977 von Arthur Dempster, Nan Laird und Donald Rubin eingeführt, obwohl frühere Versionen in der Statistikliteratur existierten. Das GMM selbst geht auf die frühen Arbeiten zu Mischmodellen von Karl Pearson im Jahr 1894 zurück, der die Momentenmethode verwendete, um ein zweikomponentiges Gaußsches Mischmodell an Krebsdaten anzupassen. Die Kombination von EM und GMM wurde zu einem Eckpfeiler des unüberwachten Lernens, lange vor modernen Deep learning-Ansätzen, und bleibt in zeitgenössischen Artificial intelligence-Systemen relevant.
Mathematische Formulierung
Ein GMM mit K Komponenten modelliert die Wahrscheinlichkeitsdichte eines Datenpunkts x als gewichtete Summe von K Gaußschen Dichten: p(x) = sum_{k=1}^K pi_k * N(x | mu_k, Sigma_k), wobei pi_k die Mischungskoeffizienten sind (die sich zu 1 summieren), mu_k die Mittelwertvektoren und Sigma_k die Kovarianzmatrizen. Die latente Variable z gibt an, welche Komponente jede Beobachtung erzeugt hat. Der EM-Algorithmus iteriert zwei Schritte. Im E-Schritt berechnet er die Posteriori-Wahrscheinlichkeit (Verantwortlichkeit), dass jede Komponente jeden Datenpunkt erzeugt hat, gegeben die aktuellen Parameterschätzungen. Im M-Schritt aktualisiert er die Parameter (pi_k, mu_k, Sigma_k), indem er die erwartete Log-Likelihood der vollständigen Daten maximiert, wobei die Verantwortlichkeiten als Gewichte verwendet werden. Der Algorithmus garantiert eine nicht abnehmende Likelihood bei jeder Iteration und konvergiert zu einem lokalen Optimum.
Anwendungen im maschinellen Lernen
Im Machine learning dienen GMMs als flexibles Werkzeug für weiches Clustering, bei dem jeder Punkt mit unterschiedlichen Wahrscheinlichkeiten zu allen Clustern gehört, im Gegensatz zu harten Clustering-Methoden wie k-means. Sie werden in der Bildsegmentierung, Spracherkennung und Anomalieerkennung eingesetzt. Beispielsweise modellieren GMMs in der Computer Vision Hintergrundpixel in der Videoüberwachung. In der Sprachverarbeitung modellierten GMMs historisch akustische Merkmale, bevor sie durch Neural network-basierte Systeme ersetzt wurden. Der EM-Algorithmus erscheint auch in versteckten Markov-Modellen (über den Baum-Welch-Algorithmus, einen Spezialfall) und bei der Behandlung fehlender Daten in allgemeinen statistischen Modellen.
Beziehung zur modernen KI
Während Deep learning GMMs für viele hochdimensionale Aufgaben abgelöst hat, bleibt der EM-Algorithmus konzeptionell einflussreich. Varianten von EM werden beim Training von großen Sprachmodellen für Aufgaben wie die Erwartungsmaximierung zur Wortausrichtung in der maschinellen Übersetzung verwendet. Das Prinzip des Algorithmus, zwischen Inferenz und Optimierung zu wechseln, erscheint in variationalen Autoencodern und anderen latenten Variablenmodellen. Forscher an Institutionen wie MIT CSAIL und Stanford AI Lab untersuchen EM weiterhin wegen seiner theoretischen Garantien und Effizienz. In der Praxis werden GMMs weiterhin in Produktionssystemen für Aufgaben wie Sprecherverifikation und finanzielle Risikomodellierung eingesetzt, oft neben Generative AI-Techniken.
Erweiterungen und Varianten
Mehrere Erweiterungen adressieren die Einschränkungen von EM, wie langsame Konvergenz und Empfindlichkeit gegenüber der Initialisierung. Stochastisches EM und inkrementelles EM aktualisieren Parameter mithilfe von Mini-Batches und verbessern so die Skalierbarkeit. Variationales Bayes'sches EM behandelt Parameter als Zufallsvariablen und liefert eine vollständige Posteriori-Verteilung. Der K-Means Clustering-Algorithmus kann als Grenzfall mit harter Zuordnung von EM für GMMs mit gleichen isotropen Kovarianzen angesehen werden. Für hochdimensionale Daten reduzieren diagonale oder geteilte Kovarianzmatrizen die Anzahl der Parameter. Die Expectation propagation- und Monte-Carlo-EM-Varianten behandeln unlösbare Integrale. Diese Entwicklungen halten EM im Zeitalter der Artificial intelligence relevant, wo es oft als Basislinie oder Baustein in komplexeren Modellen dient.
Praktische Überlegungen
Die Implementierung von EM für GMMs erfordert die Wahl der Anzahl der Komponenten K, oft über Informationskriterien wie das Bayes'sche Informationskriterium (BIC) oder Kreuzvalidierung. Die Initialisierung kann k-means-Ergebnisse oder zufällige Startwerte verwenden. Der Algorithmus kann zu lokalen Optima konvergieren, daher sind mehrere Neustarts üblich. Die numerische Stabilität wird durch die Verwendung von Log-Likelihoods und die Behandlung singulärer Kovarianzmatrizen mit Regularisierung verbessert. In modernen Softwarebibliotheken wie scikit-learn ist EM für GMMs mit effizienten linearen Algebra-Routinen implementiert. Die Zeitkomplexität des Algorithmus pro Iteration beträgt O(NKD^2) für vollständige Kovarianzen, wobei N die Anzahl der Punkte und D die Dimensionalität ist, was ihn für Datensätze mittlerer Größe praktikabel macht. Für großskalige Probleme können AWS Trainium und andere spezialisierte Hardware die Matrixoperationen beschleunigen, obwohl EM typischerweise nicht der Engpass in End-to-End-Machine learning-Pipelines ist.
Historischer Kontext
Die Entwicklung des EM-Algorithmus wurde durch Probleme in der Genetik und der Umfragestichprobenverfahren motiviert, wo fehlende Daten häufig waren. Seine Formalisierung vereinheitlichte mehrere frühere iterative Methoden, einschließlich jener für Faktorenanalyse und gemischte Modelle. Der Artikel von 1977 wurde einer der am häufigsten zitierten in der Statistik. Über die Jahrzehnte wurde EM in so unterschiedlichen Bereichen angewendet wie Astronomie (Schätzung von Galaxienverteilungen), Wirtschaftswissenschaften (Modellierung von Einkommensverteilungen) und Biologie (Genexpressions-Clustering). Seine Einfachheit und theoretische Eleganz haben es zu einem Standardthema in Lehrbüchern über Machine learning und Statistik gemacht, einschließlich jener von Christopher Bishop und anderen. Trotz des Aufstiegs von Deep learning bleiben EM und GMMs wesentliche Werkzeuge im Werkzeugkasten des Datenwissenschaftlers, insbesondere für Probleme mit klarer latenter Struktur und moderater Dimensionalität.
Siehe auch
- K-Means Clustering
- hidden-markov-model
- Variational Autoencoder
- Expectation propagation
- density-estimation