24

Ich habe einige Erklärungen zum EM-Algorithmus gelesen (z. B. aus Bishops Mustererkennung und maschinellem Lernen sowie aus dem ersten Kurs von Roger und Gerolami über maschinelles Lernen). Die Ableitung von EM ist in Ordnung, ich verstehe es. Ich verstehe auch, warum der Algorithmus etwas überdeckt: Bei jedem Schritt verbessern wir das Ergebnis und die Wahrscheinlichkeit wird durch 1,0 begrenzt. Wenn wir also eine einfache Tatsache verwenden (wenn eine Funktion zunimmt und begrenzt wird, konvergiert sie), wissen wir, dass der Algorithmus gegen konvergiert eine Lösung.

Woher wissen wir jedoch, dass es sich um ein lokales Minimum handelt? Bei jedem Schritt berücksichtigen wir nur eine Koordinate (entweder latente Variable oder Parameter), sodass wir möglicherweise etwas übersehen, so dass das lokale Minimum das gleichzeitige Bewegen um beide Koordinaten erfordert.

Dies ist meines Erachtens ein ähnliches Problem wie das der allgemeinen Klasse von Hill Climbing-Algorithmen, für die EM ein Beispiel ist. Für einen allgemeinen Hill Climbing-Algorithmus haben wir dieses Problem für die Funktion f (x, y) = x * y. Wenn wir von (0, 0) beginnen, können wir uns nur unter gleichzeitiger Berücksichtigung beider Richtungen von 0 nach oben bewegen.

missing-data convergence expectation-maximization michal
quelle

3

Die Wahrscheinlichkeit ist nur für feste Abweichungen begrenzt. Das heißt, in der Binomialsituation ist die Varianz ; oder in der Gaußschen Situation, wenn angenommen wird, dass die Varianz bekannt ist. Wenn die Varianz unbekannt ist und geschätzt werden muss, ist die Wahrscheinlichkeit nicht begrenzt. Auch im EM-Algorithmus gibt es eine generische Trennung von fehlenden und Parametern, zumindest für die häufigeren Statistiker, aber die Oberflächen können tatsächlich Sättel haben.

p (1 - p)

$p(1-p)$

StasK

@Stask Ich bin mir nicht sicher, ob die Wahrscheinlichkeit auch bei festen Abweichungen generell begrenzt ist. Beschränken Sie sich auf eine bestimmte Familie?

Glen_b

27

Es ist nicht garantiert, dass EM zu einem lokalen Minimum konvergiert. Es ist nur garantiert, dass die Konvergenz in Bezug auf die Parameter zu einem Punkt mit einem Gefälle von Null erfolgt. So kann es in der Tat an Sattelpunkten hängen bleiben.

Tom Minka
quelle

1

Beispiele finden Sie auf den Seiten 20 und 38 hier , S. 22. 85 hier - versuchen Sie "Sattelpunkt" in Amazon Reader.

StasK

13

Zuallererst ist es möglich, dass EM gegen ein lokales Minimum , ein lokales Maximum oder einen Sattelpunkt der Wahrscheinlichkeitsfunktion konvergiert . Genauer gesagt, wie Tom Minka betonte, wird EM garantiert zu einem Punkt mit einem Gefälle von Null konvergieren .

Ich kann mir zwei Möglichkeiten vorstellen, dies zu sehen. Die erste Ansicht ist reine Intuition, und die zweite Ansicht ist die Skizze eines formalen Beweises. Zunächst werde ich kurz erläutern, wie EM funktioniert:

Die Expectation Maximization (EM) ist eine sequentiell gebundene Optimierungstechnik, bei der in Iteration zuerst eine (untere) Grenze für die Wahrscheinlichkeitsfunktion und dann die Grenze maximiert wird, um die neue Lösung , und mache das so lange, bis sich die neue Lösung nicht mehr ändert. $t$ $b_t(\theta)$ $L(\theta)$ $\theta_t = \arg\max_\theta b_t(\theta)$

Erwartungsmaximierung als Gradientenanstieg

In jeder Iteration erfordert EM, dass die Schranke die Wahrscheinlichkeitsfunktion bei der Lösung der vorherigen Iteration berührt, dh, dass was impliziert, dass ihre Gradienten auch gleich sind; das heißt . EM ist also mindestens so gut wie Gradientenanstieg, weil mindestens so gut wie ist . Mit anderen Worten: $t$ $b_t$ $L$ $\theta_{t-1}$ $g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$ $\theta_t$ $\theta_{t-1} + \eta g$

Konvergiert EM gegen dann ist ein Konvergenzpunkt für den Gradientenanstieg, und EM erfüllt alle Eigenschaften, die für Gradientenanstiegslösungen gelten (einschließlich des Gradientenwerts Null). $\theta^*$ $\theta^*$

Skizze eines formalen Beweises

Man kann zeigen, dass die Lücke zwischen den Grenzen und der Wahrscheinlichkeitsfunktion gegen Null konvergiert; das ist Man kann beweisen, dass der Gradient der Schranke auch gegen den Gradienten der Wahrscheinlichkeitsfunktion konvergiert; das heißt: Aufgrund von und und dass die in EM verwendeten Grenzen differenzierbar sind und dass , haben wir das und daher .

\begin{matrix} (1) & lim_{t \to \infty} L (θ_{t}) - b_{t} (θ_{t}) = 0. \end{matrix}

$\lim_{t \rightarrow \infty} L(\theta_t) - b_t(\theta_t) = 0. \tag{1}$

\begin{matrix} (2) & lim_{t \to \infty} \nabla L (θ_{t}) = \nabla b_{t} (θ_{t}) . \end{matrix}

$\lim_{t \rightarrow \infty} \nabla L(\theta_t) = \nabla b_t(\theta_t). \tag{2}$

(1)

$(1)$

(2)

$(2)$

θ_{t} = \arg max_{θ} b_{t} (θ)

$\theta_t = \arg\max_\theta b_t(\theta)$

\nabla b_{t} (θ_{t}) = 0

$\nabla b_t(\theta_t)=0$

lim_{t \to \infty} \nabla L (θ_{t}) = 0

$\lim_{t \rightarrow \infty} \nabla L(\theta_t) = 0$

Sobi
quelle

Warum konvergiert der Expectation Maximization-Algorithmus garantiert gegen ein lokales Optimum?

Antworten:

Erwartungsmaximierung als Gradientenanstieg

Skizze eines formalen Beweises