Expectation Maximization (EM) ist eine Art probabilistische Methode zur Klassifizierung von Daten. Bitte korrigieren Sie mich, wenn ich falsch liege, wenn es sich nicht um einen Klassifikator handelt.
Was ist eine intuitive Erklärung dieser EM-Technik? Was ist expectation
hier und was ist maximized
?
machine-learning
cluster-analysis
data-mining
mathematical-optimization
expectation-maximization
Londoner Typ
quelle
quelle
Antworten:
Hinweis: Den Code hinter dieser Antwort finden Sie hier .
Angenommen, wir haben einige Daten aus zwei verschiedenen Gruppen, rot und blau:
Hier können wir sehen, welcher Datenpunkt zur roten oder blauen Gruppe gehört. Dies macht es einfach, die Parameter zu finden, die jede Gruppe charakterisieren. Zum Beispiel liegt der Mittelwert der roten Gruppe bei 3, der Mittelwert der blauen Gruppe bei 7 (und wir könnten die genauen Mittelwerte finden, wenn wir wollten).
Dies wird allgemein als Maximum-Likelihood-Schätzung bezeichnet . Bei einigen Daten berechnen wir den Wert eines Parameters (oder von Parametern), der diese Daten am besten erklärt.
Stellen Sie sich nun vor, wir können nicht sehen, welcher Wert aus welcher Gruppe entnommen wurde. Für uns sieht alles lila aus:
Hier haben wir das Wissen, dass es zwei Gruppen von Werten gibt, aber wir wissen nicht, zu welcher Gruppe ein bestimmter Wert gehört.
Können wir noch die Mittelwerte für die rote und die blaue Gruppe abschätzen, die am besten zu diesen Daten passen?
Ja, oft können wir! Die Erwartungsmaximierung gibt uns eine Möglichkeit, dies zu tun. Die sehr allgemeine Idee hinter dem Algorithmus ist folgende:
Diese Schritte bedürfen einer weiteren Erläuterung, daher gehe ich auf das oben beschriebene Problem ein.
Beispiel: Schätzung von Mittelwert und Standardabweichung
In diesem Beispiel werde ich Python verwenden, aber der Code sollte ziemlich leicht zu verstehen sein, wenn Sie mit dieser Sprache nicht vertraut sind.
Angenommen, wir haben zwei Gruppen, rot und blau, wobei die Werte wie im obigen Bild verteilt sind. Insbesondere enthält jede Gruppe einen Wert aus einer Normalverteilung mit den folgenden Parametern:
Hier ist noch einmal ein Bild dieser roten und blauen Gruppen (damit Sie nicht nach oben scrollen müssen):
Wenn wir die Farbe jedes Punktes sehen können (dh zu welcher Gruppe er gehört), ist es sehr einfach, den Mittelwert und die Standardabweichung für jede Gruppe zu schätzen. Wir übergeben nur die roten und blauen Werte an die in NumPy integrierten Funktionen. Beispielsweise:
Aber was ist, wenn wir die Farben der Punkte nicht sehen können ? Das heißt, anstelle von Rot oder Blau wurde jeder Punkt lila gefärbt.
Um zu versuchen, die Mittelwert- und Standardabweichungsparameter für die roten und blauen Gruppen wiederherzustellen, können wir die Erwartungsmaximierung verwenden.
Unser erster Schritt ( Schritt 1 oben) besteht darin, die Parameterwerte für den Mittelwert und die Standardabweichung jeder Gruppe zu erraten. Wir müssen nicht intelligent raten; Wir können beliebige Zahlen auswählen:
Diese Parameterschätzungen erzeugen Glockenkurven, die folgendermaßen aussehen:
Das sind schlechte Schätzungen. Beide Mittel (die vertikalen gepunkteten Linien) sehen zum Beispiel für sinnvolle Punktgruppen weit entfernt von jeder Art von "Mitte" aus. Wir wollen diese Schätzungen verbessern.
Der nächste Schritt ( Schritt 2 ) besteht darin, die Wahrscheinlichkeit zu berechnen, mit der jeder Datenpunkt unter den aktuellen Parameterschätzungen erscheint:
Hier haben wir einfach jeden Datenpunkt in die Wahrscheinlichkeitsdichtefunktion für eine Normalverteilung eingefügt, wobei wir unsere aktuellen Schätzungen zum Mittelwert und zur Standardabweichung für Rot und Blau verwenden. Dies sagt uns zum Beispiel, dass nach unseren derzeitigen Schätzungen der Datenpunkt bei 1,761 viel wahrscheinlicher rot (0,189) als blau (0,00003) ist.
Für jeden Datenpunkt können wir diese beiden Wahrscheinlichkeitswerte in Gewichte umwandeln ( Schritt 3 ), sodass sie wie folgt zu 1 summieren:
Mit unseren aktuellen Schätzungen und unseren neu berechneten Gewichten können wir jetzt neue Schätzungen für den Mittelwert und die Standardabweichung der roten und blauen Gruppe berechnen ( Schritt 4 ).
Wir berechnen zweimal den Mittelwert und die Standardabweichung unter Verwendung aller Datenpunkte, jedoch mit unterschiedlichen Gewichtungen: einmal für die roten Gewichte und einmal für die blauen Gewichte.
Das Schlüsselelement der Intuition ist, dass je größer das Gewicht einer Farbe auf einem Datenpunkt ist, desto stärker beeinflusst der Datenpunkt die nächsten Schätzungen für die Parameter dieser Farbe. Dies hat den Effekt, dass die Parameter in die richtige Richtung "gezogen" werden.
Wir haben neue Schätzungen für die Parameter. Um sie wieder zu verbessern, können wir zu Schritt 2 zurückkehren und den Vorgang wiederholen. Wir tun dies, bis die Schätzungen konvergieren oder nachdem eine bestimmte Anzahl von Iterationen durchgeführt wurde ( Schritt 5 ).
Für unsere Daten sehen die ersten fünf Iterationen dieses Prozesses folgendermaßen aus (neuere Iterationen sehen stärker aus):
Wir sehen, dass die Mittelwerte bereits bei einigen Werten konvergieren und auch die Formen der Kurven (bestimmt durch die Standardabweichung) stabiler werden.
Wenn wir 20 Iterationen fortsetzen, erhalten wir Folgendes:
Der EM-Prozess hat sich den folgenden Werten angenähert, die den tatsächlichen Werten sehr nahe kommen (wo wir die Farben sehen können - keine versteckten Variablen):
Im obigen Code haben Sie möglicherweise bemerkt, dass die neue Schätzung für die Standardabweichung unter Verwendung der Schätzung der vorherigen Iteration für den Mittelwert berechnet wurde. Letztendlich spielt es keine Rolle, ob wir zuerst einen neuen Wert für den Mittelwert berechnen, da wir nur die (gewichtete) Varianz der Werte um einen zentralen Punkt herum finden. Die Schätzungen für die Parameter werden weiterhin konvergieren.
quelle
EM ist ein Algorithmus zum Maximieren einer Wahrscheinlichkeitsfunktion, wenn einige der Variablen in Ihrem Modell nicht beobachtet werden (dh wenn Sie latente Variablen haben).
Sie könnten sich fragen, wenn wir nur versuchen, eine Funktion zu maximieren, warum wir nicht einfach die vorhandene Maschinerie zum Maximieren einer Funktion verwenden. Wenn Sie versuchen, dies zu maximieren, indem Sie Derivate nehmen und auf Null setzen, stellen Sie fest, dass die Bedingungen erster Ordnung in vielen Fällen keine Lösung haben. Es gibt ein Henne-Ei-Problem, das Sie zur Lösung Ihrer Modellparameter benötigen, um die Verteilung Ihrer nicht beobachteten Daten zu kennen. Die Verteilung Ihrer nicht beobachteten Daten hängt jedoch von Ihren Modellparametern ab.
EM versucht, dies zu umgehen, indem es iterativ eine Verteilung für die nicht beobachteten Daten errät, dann die Modellparameter schätzt, indem es etwas maximiert, das eine Untergrenze für die tatsächliche Wahrscheinlichkeitsfunktion darstellt, und dies bis zur Konvergenz wiederholt:
Der EM-Algorithmus
Beginnen Sie mit der Schätzung der Werte Ihrer Modellparameter
E-Schritt: Verwenden Sie für jeden Datenpunkt mit fehlenden Werten Ihre Modellgleichung, um die Verteilung der fehlenden Daten anhand Ihrer aktuellen Schätzung der Modellparameter und der beobachteten Daten zu ermitteln (beachten Sie, dass Sie für jeden fehlenden Wert eine Verteilung suchen Wert, nicht für den erwarteten Wert). Nachdem wir nun eine Verteilung für jeden fehlenden Wert haben, können wir die Erwartung der Wahrscheinlichkeitsfunktion in Bezug auf die nicht beobachteten Variablen berechnen. Wenn unsere Vermutung für den Modellparameter korrekt war, ist diese erwartete Wahrscheinlichkeit die tatsächliche Wahrscheinlichkeit unserer beobachteten Daten. Wenn die Parameter nicht korrekt waren, handelt es sich nur um eine Untergrenze.
M-Schritt: Nachdem wir nun eine erwartete Wahrscheinlichkeitsfunktion ohne nicht beobachtete Variablen haben, maximieren Sie die Funktion wie im vollständig beobachteten Fall, um eine neue Schätzung Ihrer Modellparameter zu erhalten.
Wiederholen bis zur Konvergenz.
quelle
Hier ist ein einfaches Rezept, um den Algorithmus zur Erwartungsmaximierung zu verstehen:
1- Lesen Sie dieses EM-Tutorial von Do und Batzoglou.
2- Möglicherweise haben Sie Fragezeichen im Kopf. Schauen Sie sich die Erklärungen auf dieser Seite zum Austausch von Mathe-Stapeln an .
3- Sehen Sie sich diesen Code an, den ich in Python geschrieben habe und der das Beispiel im EM-Tutorial von Punkt 1 erklärt:
Warnung: Der Code ist möglicherweise chaotisch / suboptimal, da ich kein Python-Entwickler bin. Aber es macht den Job.
quelle
Technisch gesehen ist der Begriff "EM" etwas unterbestimmt, aber ich gehe davon aus, dass Sie sich auf die Clusteranalysetechnik der Gaußschen Mischungsmodellierung beziehen, die ein Beispiel für das allgemeine EM-Prinzip ist.
Tatsächlich ist die EM-Clusteranalyse kein Klassifikator . Ich weiß, dass einige Leute Clustering als "unbeaufsichtigte Klassifizierung" betrachten, aber tatsächlich ist die Clusteranalyse etwas ganz anderes.
Der Hauptunterschied und das große Missverständnis, das Menschen bei der Clusteranalyse immer haben, besteht darin, dass es in der Clusteranalyse keine "richtige Lösung" gibt . Es ist eine Methode zur Entdeckung von Wissen , es soll tatsächlich etwas Neues finden ! Dies macht die Bewertung sehr schwierig. Es wird häufig anhand einer bekannten Klassifizierung als Referenz bewertet, aber das ist nicht immer angemessen: Die Klassifizierung, die Sie haben, spiegelt möglicherweise die Daten wider oder nicht.
Lassen Sie mich ein Beispiel geben: Sie haben einen großen Kundendatensatz, einschließlich Geschlechtsdaten. Eine Methode, die diesen Datensatz in "männlich" und "weiblich" aufteilt, ist optimal, wenn Sie ihn mit den vorhandenen Klassen vergleichen. In einer "Vorhersage" -Methode ist dies gut, da Sie für neue Benutzer jetzt deren Geschlecht vorhersagen können. In einer "Wissensentdeckungs" -Methode ist dies tatsächlich schlecht, weil Sie eine neue Struktur in den Daten entdecken wollten . Eine Methode, die z. B. die Daten in ältere Menschen und Kinder aufteilt, würde jedoch in Bezug auf die männliche / weibliche Klasse so schlecht abschneiden, wie es nur geht . Dies wäre jedoch ein hervorragendes Clustering-Ergebnis (wenn das Alter nicht angegeben würde).
Nun zurück zu EM. Im Wesentlichen wird davon ausgegangen, dass Ihre Daten aus mehreren multivariaten Normalverteilungen bestehen (beachten Sie, dass dies eine ist ausgegangen, sehr starke Annahme ist, insbesondere wenn Sie die Anzahl der Cluster festlegen!). Anschließend wird versucht, ein lokales optimales Modell dafür zu finden, indem abwechselnd das Modell und die Objektzuordnung zum Modell verbessert werden .
Um die besten Ergebnisse in einem Klassifizierungskontext zu erzielen, wählen Sie die Anzahl der größeren Cluster als die Anzahl der Klassen ist, oder wenden Sie die Clusterbildung sogar nur auf einzelne Klassen an (um herauszufinden, ob innerhalb der Klasse eine Struktur vorhanden ist!).
Angenommen, Sie möchten einen Klassifikator trainieren, um "Autos", "Fahrräder" und "Lastwagen" zu unterscheiden. Es hat wenig Sinn anzunehmen, dass die Daten aus genau 3 Normalverteilungen bestehen. Sie können jedoch davon ausgehen, dass es mehr als eine Art von Autos (sowie Lastwagen und Fahrräder) gibt. Anstatt einen Klassifikator für diese drei Klassen zu trainieren, gruppieren Sie Autos, Lastwagen und Fahrräder in jeweils 10 Gruppen (oder vielleicht 10 Autos, 3 Lastwagen und 3 Fahrräder, was auch immer) und trainieren dann einen Klassifikator, um diese 30 Klassen zu unterscheiden, und dann Führen Sie das Klassenergebnis wieder mit den ursprünglichen Klassen zusammen. Möglicherweise stellen Sie auch fest, dass es einen Cluster gibt, der besonders schwer zu klassifizieren ist, z. B. Trikes. Es sind etwas Autos und etwas Fahrräder. Oder Lieferwagen, die eher übergroßen Autos als Lastwagen ähneln.
quelle
Da andere Antworten gut sind, werde ich versuchen, eine andere Perspektive zu bieten und den intuitiven Teil der Frage anzugehen.
Der EM-Algorithmus (Expectation-Maximization) ist eine Variante einer Klasse iterativer Algorithmen, die Dualität verwenden
Auszug (Schwerpunkt Mine):
Normalerweise ein duales B von einem Objekts A in irgendeiner Weise mit A verbunden, wodurch eine gewisse Symmetrie oder Kompatibilität erhalten bleibt . Zum Beispiel AB = const
Beispiele für iterative Algorithmen, die Dualität (im vorherigen Sinne) verwenden, sind:
In ähnlicher Weise kann der EM-Algorithmus auch als zwei doppelte Maximierungsschritte angesehen werden :
In einem iterativen Algorithmus unter Verwendung von Dualität gibt es die explizite (oder implizite) Annahme eines Gleichgewichts- (oder festen) Konvergenzpunkts (für EM wird dies unter Verwendung von Jensens Ungleichung bewiesen).
Der Umriss solcher Algorithmen lautet also:
Beachten Sie, dass ein solcher Algorithmus, wenn er zu einem (globalen) Optimum konvergiert, eine Konfiguration gefunden hat, die in beiden Sinnen am besten ist (dh sowohl in der x- Domäne / den Parametern als auch in der y- Domäne / den Parametern). Der Algorithmus kann jedoch nur ein lokales Optimum und nicht das globale Optimum finden.
Ich würde sagen, dies ist die intuitive Beschreibung des Umrisses des Algorithmus
Für die statistischen Argumente und Anwendungen haben andere Antworten gute Erklärungen gegeben (siehe auch Referenzen in dieser Antwort)
quelle
Die akzeptierte Antwort bezieht sich auf das Chuong EM Paper , das EM in angemessener Weise erklärt. Es gibt auch ein Youtube-Video , in dem das Papier ausführlicher erklärt wird.
Um es noch einmal zusammenzufassen, hier ist das Szenario:
Im Fall der Frage des ersten Versuchs würden wir intuitiv denken, dass B sie generiert hat, da der Anteil der Köpfe sehr gut mit der Tendenz von B übereinstimmt ... aber dieser Wert war nur eine Vermutung, daher können wir nicht sicher sein.
In diesem Sinne denke ich gerne an die EM-Lösung wie folgt:
Dies mag eine Vereinfachung sein (oder auf einigen Ebenen sogar grundlegend falsch), aber ich hoffe, dass dies auf einer intuitiven Ebene hilft!
quelle
EM wird verwendet, um die Wahrscheinlichkeit eines Modells Q mit latenten Variablen Z zu maximieren.
Es ist eine iterative Optimierung.
e-step: Berechnen Sie bei gegebener aktueller Schätzung von Z die erwartete Loglikelihood-Funktion
m-Schritt: Finde Theta, das dieses Q maximiert
GMM Beispiel:
e-step: Schätzen Sie die Etikettenzuweisungen für jeden Datenpunkt unter Berücksichtigung der aktuellen Schätzung der gmm-Parameter
m-Schritt: Maximieren Sie ein neues Theta angesichts der neuen Etikettenzuordnungen
K-means ist auch ein EM-Algorithmus und es gibt viele erklärende Animationen zu K-means.
quelle
Unter Verwendung des gleichen Artikels von Do und Batzoglou, der in Zhubarbs Antwort zitiert wurde, implementierte ich EM für dieses Problem in Java . Die Kommentare zu seiner Antwort zeigen, dass der Algorithmus an einem lokalen Optimum hängen bleibt, was auch bei meiner Implementierung auftritt, wenn die Parameter thetaA und thetaB gleich sind.
Unten ist die Standardausgabe meines Codes, die die Konvergenz der Parameter zeigt.
Unten ist meine Java-Implementierung von EM zur Lösung des Problems in (Do und Batzoglou, 2008). Der Kern der Implementierung ist die Schleife, in der EM ausgeführt wird, bis die Parameter konvergieren.
Unten ist der gesamte Code.
quelle