Was ist der Unterschied zwischen EM und Gradient Ascent?

Was ist der Unterschied zwischen den Algorithmen EM (Expectation Maximization) und Gradient Ascent (oder Descent)? Gibt es eine Bedingung, unter der sie gleichwertig sind?

gradient-descent expectation-maximization Aslan986
quelle

Antworten:

Von:

Xu L und Jordan MI (1996). Über Konvergenzeigenschaften des EM-Algorithmus für Gaußsche Gemische . Neural Computation 2: 129 & ndash; 151.

Abstrakt:

Wir zeigen, dass der EM-Schritt im Parameterraum über eine Projektionsmatrix P aus dem Gradienten erhalten wird, und wir geben einen expliziten Ausdruck für die Matrix.

Seite 2

Insbesondere zeigen wir, dass der EM-Schritt durch Vormultiplizieren des Gradienten mit einer positiven Denitmatrix erhalten werden kann. Wir geben einen expliziten Ausdruck für die Matrix ...

Seite 3

Das heißt, der EM-Algorithmus kann als Aufstiegsalgorithmus mit variablem Metrikgradienten betrachtet werden ...

In diesem Artikel werden explizite Transformationen des EM-Algorithmus in Gradientenanstieg, Newton, Quasi-Newton, beschrieben.

Aus Wikipedia

Es gibt andere Methoden, um Schätzungen der maximalen Wahrscheinlichkeit zu finden, z. B. Gradientenabnahme, konjugierter Gradient oder Variationen der Gauß-Newton-Methode. Im Gegensatz zu EM erfordern solche Verfahren typischerweise die Auswertung erster und / oder zweiter Ableitungen der Wahrscheinlichkeitsfunktion.

Ron Coleman
quelle

Diese Antwort scheint darauf hinzudeuten, dass EM und Gradientenabstieg im Grunde derselbe Algorithmus sind, mit Transformationen, die zum Umschalten von einem Algorithmus zum anderen zur Verfügung stehen. Dies ist im Allgemeinen definitiv nicht der Fall und hängt stark vom berücksichtigten generativen Modell ab. Der zitierte Aufsatz zieht nur Schlussfolgerungen für Gaußsche Mischungsmodelle (die relativ einfache generative Modelle sind), und das zu Recht. Nach meiner (zugegebenermaßen begrenzten) Erfahrung ist EM die einzige Möglichkeit, sinnvolle Aktualisierungsregeln abzuleiten, wenn das Modell stark nichtlinear ist und die Rolle der latenten Variablen wichtig ist.

Blau

Nein, sie sind nicht gleichwertig. Insbesondere ist die EM-Konvergenz viel langsamer.

Wenn Sie an einer Optimierungssicht auf EM interessiert sind, werden Sie in diesem Artikel sehen, dass der EM-Algorithmus ein Sonderfall einer breiteren Klasse von Algorithmen ist (Proximalpunkt-Algorithmen).

Elvis
quelle

Oder für eine ähnliche Idee Hinton und Neal (1998)

conjugateprior

"EM-Konvergenz ist viel langsamer"; Dies ist nicht genau definiert und sicherlich nicht allgemein zutreffend. EM-Algorithmen sind eine ganze Klasse von Algorithmen. Für viele Probleme, ist ein gewisser EM - Algorithmus der Stand der Technik.

Cliff AB

@CliffAB, bitte zögern Sie nicht, darauf einzugehen. Ich würde gerne Ihre Argumente lesen. Als ich diese Antwort aus 4 Jahren las, wurde mir klar, dass ich sie heute nicht beantworten würde. Seitdem habe ich entdeckt , dass in vielen Fällen die EM ist ein Gradient Aufstieg mit einem ‚Lernrate‘ Parameter auf dem aktuellen Punkt je ... (ich in eine Weile Punkt Ergebnisse der Sortierung diese Antwort bearbeiten kann)

Elvis

"Langsamere Konvergenz" könnte als Konvergenzrate definiert werden. Die Konvergenzrate eines Gradientenanstiegs hängt von der 'Lernrate' ab, die nicht einfach zu wählen ist, was den Gradientenanstieg in vielen Fällen schwierig macht. Ich habe jedoch immer noch das Gefühl, dass EM in einigen Fällen der einzig mögliche Algorithmus sein kann (die Ableitungen der Wahrscheinlichkeit oder der Wahrscheinlichkeit selbst sind schwer zu berechnen), seine Konvergenzrate jedoch im Vergleich zu einer Newton-ähnlichen Methode schlecht ist.

Elvis

"Der" EM-Algorithmus ist wirklich eine ganze Klasse von Algorithmen; Eine, bei der die ursprüngliche Zielfunktion nur schwer zu optimieren ist. Wenn jedoch eine andere Variable bekannt wäre, wäre die Lösung viel einfacher (normalerweise in geschlossener Form). Die grundlegende Gliederung besteht darin, die erwartete Variable abhängig von den aktuellen Werten der anderen Parameter auszufüllen und dann die Parameter basierend auf dem erwarteten Wert der Variablen zu aktualisieren. Es wurde gezeigt, dass die Konvergenz des Algorithmus davon abhängt, wie aussagekräftig die unterstellten Daten sind. Je "informativer" die fehlenden Daten sind, desto langsamer ist die Konvergenz.

Cliff AB