Algorithmus zur Maximierung der Motivationserwartung

Im EM-Algorithmus-Ansatz verwenden wir Jensens Ungleichung, um zu

$$\log p(x|\theta) \geq \int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz - \int \log p(z|x,\theta) p(z|x,\theta^{(k)})dz$$

und definiere durch$\theta^{(k+1)}$

$$\theta^{(k+1)}=\arg \max_{\theta}\int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz$$

Alles, was ich in EM lese, macht es einfach zu Ende, aber ich habe mich immer unwohl gefühlt, weil ich keine Erklärung dafür habe, warum der EM-Algorithmus auf natürliche Weise entsteht. Ich verstehe, dass $\log$ Likelihood in der Regel behandelt wird, um Addition statt Multiplikation zu behandeln, aber das Auftreten von $\log$ in der Definition von $\theta^{(k+1)}$ fühlt sich für mich unmotiviert an. Warum sollte man $\log$ und nicht andere monotone Funktionen berücksichtigen ? Aus verschiedenen Gründen vermute ich, dass die "Bedeutung" oder "Motivation" der Erwartungsmaximierung eine Erklärung in Form von Informationstheorie und ausreichender Statistik hat. Wenn es eine solche Erklärung gäbe, wäre das viel befriedigender als nur ein abstrakter Algorithmus.

Der EM-Algorithmus hat unterschiedliche Interpretationen und kann in unterschiedlichen Anwendungen in unterschiedlichen Formen auftreten.

Alles beginnt mit der Wahrscheinlichkeitsfunktion oder äquivalent mit der log-Wahrscheinlichkeitsfunktion wir maximieren möchten. (Wir verwenden im Allgemeinen den Logarithmus, um die Berechnung zu vereinfachen: Er ist streng monoton, konkav und .) In einer idealen Welt hängt der Wert von nur vom Modellparameter ab. , damit wir den Raum von durchsuchen und einen finden können, der maximiert .log p ( x | θ ) log ( a b ) = log a + log b p θ θ $p(x \vert \theta)$$\log p(x \vert \theta)$$\log(ab) = \log a + \log b$$p$ $\theta$$\theta$$p$

In vielen interessanten realen Anwendungen sind die Dinge jedoch komplizierter, da nicht alle Variablen beobachtet werden. Ja, wir können direkt beobachten , aber einige andere Variablen werden nicht beobachtet. Aufgrund der fehlenden Variablen wir uns in einer Art Henne-Ei-Situation: Ohne wir den Parameter nicht schätzen, und ohne wir nicht schließen, wie der Wert von kann.z z z θ θ $x$$z$ $z$$z$$\theta$$\theta$$z$

Hier kommt der EM-Algorithmus ins Spiel. Wir beginnen mit einer anfänglichen Schätzung der Modellparameter und leiten daraus die erwarteten Werte der fehlenden Variablen (dh der E - Schritt). Wenn wir die Werte von , können wir die Wahrscheinlichkeit für die Parameter thgr; maximieren (dh den M-Schritt, der der Gleichung in der Problemstellung entspricht). Mit diesem können wir die neuen erwarteten Werte von (ein weiterer E-Schritt) usw. ableiten . In einem anderen Wort nehmen wir in jedem Schritt eines der beiden, undz z θ arg max θ z z $\theta$$z$$z$$\theta$$\arg \max$$\theta$$z$$z$$\theta$, ist bekannt. Wir wiederholen diesen iterativen Prozess, bis die Wahrscheinlichkeit nicht mehr erhöht werden kann.

Dies ist der EM-Algorithmus in Kürze. Es ist bekannt, dass die Wahrscheinlichkeit während dieses iterativen EM-Prozesses niemals abnimmt. Beachten Sie jedoch, dass der EM-Algorithmus kein globales Optimum garantiert. Das heißt, es könnte zu einem lokalen Optimum der Wahrscheinlichkeitsfunktion kommen.

Das Auftreten von in der Gleichung von ist unvermeidlich, da hier die Funktion, die Sie maximieren möchten, als Log-Wahrscheinlichkeit geschrieben wird.θ ( k + 1 $\log$$\theta^{(k+1)}$

Wahrscheinlichkeit vs. Log-Wahrscheinlichkeit

Wie bereits gesagt, wird mit größter Wahrscheinlichkeit eingeführt, weil es im Allgemeinen einfacher ist, Summen als Produkte zu optimieren. Der Grund, warum wir andere monotone Funktionen nicht berücksichtigen, ist, dass der Logarithmus die einzigartige Funktion mit der Eigenschaft ist, Produkte in Summen umzuwandeln.$\log$

Ein anderer Weg, den Logarithmus zu motivieren, ist der folgende: Anstatt die Wahrscheinlichkeit der Daten unter unserem Modell zu maximieren, könnten wir gleichwertig versuchen, die Kullback-Leibler-Divergenz zwischen der Datenverteilung und der zu minimieren Modellverteilung, ,p ( x ∣ θ $p_\text{data}(x)$$p(x \mid \theta)$

$$D_\text{KL}[p_\text{data}(x) \mid\mid p(x \mid \theta)] = \int p_\text{data}(x) \log \frac{p_\text{data}(x)}{p(x \mid \theta)} \, dx = const - \int p_\text{data}(x)\log p(x \mid \theta) \, dx.$$

Der erste Term auf der rechten Seite ist in den Parametern konstant. Wenn wir Stichproben aus der Datenverteilung (unseren Datenpunkten) haben, können wir den zweiten Term mit der durchschnittlichen Log-Wahrscheinlichkeit der Daten approximieren.$N$

$$\int p_\text{data}(x)\log p(x \mid \theta) \, dx \approx \frac{1}{N} \sum_n \log p(x_n \mid \theta).$$

Eine alternative Ansicht von EM

Ich bin nicht sicher, ob dies die Art von Erklärung sein wird, nach der Sie suchen, aber ich fand die folgende Ansicht der Erwartungsmaximierung viel aufschlussreicher als ihre Motivation durch Jensens Ungleichung (eine detaillierte Beschreibung finden Sie in Neal & Hinton (1998)). oder im PRML-Buch von Chris Bishop, Kapitel 9.3).

Es ist nicht schwer, das zu zeigen

$$\log p(x \mid \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz + D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)]$$

für jedes . Nennen wir den ersten Term auf der rechten Seite , so impliziert dies diesF ( q , θ $q(z \mid x)$$F(q, \theta)$

$$F(q, \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz = \log p(x \mid \theta) - D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)].$$

Da die KL-Divergenz immer positiv ist , ist eine Untergrenze der log-Wahrscheinlichkeit für jedes feste . Nun kann EM als abwechselnd maximierendes in Bezug auf und . Insbesondere durch Einstellen in der E-Schritt, wir die Divergenz KL auf der rechten Seite minimieren und damit maximieren .q F q & thgr ; q ( z ≤ x ) = p ( z ≤ x , & thgr; ) $F(q, \theta)$$q$$F$$q$$\theta$$q(z \mid x) = p(z \mid x, \theta)$$F$

Die Arbeit, die ich in Bezug auf Erwartungsmaximierung als klarstellend empfand, ist das Bayes'sche K-Mittel als "Maximierungs-Erwartungs" -Algorithmus (pdf) von Welling und Kurihara.

Angenommen, wir haben ein probabilistisches Modell mit Beobachtungen, versteckten Zufallsvariablen und insgesamt Parametern. Wir erhalten einen Datensatz und sind (durch höhere Potenzen) gezwungen, .x z & thgr ; D p ( z , & thgr ; | D $p(x,z,\theta)$$x$$z$$\theta$$D$$p(z,\theta|D)$

1. Gibbs-Probenahme

Wir können durch Abtasten approximieren . Gibbs-Abtastung ergibt durch Alternieren von:p ( z , θ | D $p(z,\theta|D)$$p(z,\theta|D)$

$$\theta \sim p(\theta|z,D) \\ z \sim p(z|\theta,D)$$

2. Variationsbayes

Stattdessen können wir versuchen, eine Verteilung und erstellen und den Unterschied zu der Verteilung, die wir nach minimieren . Der Unterschied zwischen Distributionen hat einen passenden ausgefallenen Namen, die KL-Divergenz. Um zu minimieren, aktualisieren wir:q ( z ) p ( θ , z | D ) K L [ q ( θ ) q ( z ) | | p ( θ , z | D ) $q(\theta)$$q(z)$$p(\theta,z|D)$$KL[q(\theta)q(z)||p(\theta,z|D)]$

$$q(\theta) \propto \exp (E [\log p(\theta,z,D) ]_{q(z)} ) \\ q(z) \propto \exp (E [\log p(\theta,z,D) ]_{q(\theta)} )$$

3. Erwartung-Maximierung

Es kann als extrem angesehen werden, vollständige Wahrscheinlichkeitsverteilungen sowohl für als auch für zu finden. Warum überlegen wir uns nicht stattdessen eine Punktschätzung für eine davon und halten die andere nett und nuanciert? In EM wird der Parameter ; als derjenige festgelegt, der einer vollständigen Verteilung unwürdig ist, und auf seinen MAP-Wert (Maximum A Posteriori) .θ θ θ $z$$\theta$$\theta$$\theta^*$

$$\theta^* = \underset{\theta}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(z)} \\ q(z) = p(z|\theta^*,D)$$

Hier wäre eine bessere Schreibweise: Der argmax-Operator kann mehrere Werte zurückgeben. Aber lasst uns nicht picken. Im Vergleich zu Bayes-Variationen ändert sich das Ergebnis nicht, wenn by korrigiert wird , sodass dies nicht mehr erforderlich ist.log $\theta^* \in \operatorname{argmax}$$\log$$\exp$

4. Maximierung-Erwartung

Es gibt keinen Grund, als verwöhntes Kind zu behandeln . Wir können auch nur verwenden Punkt schätzt für unsere verborgenen Variablen und geben den Parameter den Luxus einer vollständigen Verteilung.z *$z$$z^*$$\theta$

$$z^* = \underset{z}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(\theta)} \\ q(\theta) = p(\theta|z^*,D)$$

Wenn unsere versteckten Variablen Indikatorvariablen sind, haben wir plötzlich eine rechnerisch günstige Methode, um Rückschlüsse auf die Anzahl der Cluster zu ziehen. Dies ist mit anderen Worten: Modellauswahl (oder automatische Relevanzerkennung oder stellen Sie sich einen anderen Phantasienamen vor).$z$

5. Iterierte bedingte Modi

Natürlich ist es das Vorzeigekind der ungefähren Folgerung, Punktschätzungen sowohl für die Parameter als auch für die Beobachtungen .$\theta$$z$

$$\theta^* = \underset{\theta}{\operatorname{argmax}} p(\theta,z^*,D) \\ z^* = \underset{z}{\operatorname{argmax}} p(\theta^*,z,D) \\ $$

Um zu sehen, wie sich Maximization-Expectation auswirkt, kann ich den Artikel nur empfehlen. Meiner Meinung nach liegt die Stärke dieses Artikels jedoch nicht in der Anwendung auf eine Mittel-Alternative, sondern in dieser klaren und prägnanten Darstellung der Approximation.$k$

Dem EM-Algorithmus liegt eine nützliche Optimierungstechnik zugrunde. Es wird jedoch normalerweise in der Sprache der Wahrscheinlichkeitstheorie ausgedrückt, sodass es schwer zu erkennen ist, dass es sich im Kern um eine Methode handelt, die nichts mit Wahrscheinlichkeit und Erwartung zu tun hat.

Betrachten Sie das Problem der Maximierung von (oder äquivalent ) in Bezug auf . Wenn Sie einen Ausdruck für aufschreiben und ihn auf Null setzen, erhalten Sie häufig eine zu lösende transzendentale Gleichung. Diese können böse sein.log g ( x ) x g ' ( x

$$g(x)=\sum_i\exp(f_i(x))$$ $\log g(x)$$x$$g'(x)$

Nehmen wir nun an, dass in dem Sinne gut zusammenspielt, dass Sie mit linearen Kombinationen leicht etwas optimieren können. Wenn beispielsweise alle in quadratisch sind, ist auch eine Linearkombination von quadratisch und daher leicht zu optimieren.f i ( x ) x f i ( x $f_i$$f_i(x)$$x$$f_i(x)$

Unter dieser Annahme wäre es cool, wenn wir zur Optimierung von das irgendwie über die mischen könnten, damit es das erfüllt s und eliminiere sie. Dann könnte das zusammen spielen. Das können wir aber nicht.log Σ exp f $\log g(x)=\log \sum_i\exp(f_i(x))$$\log$$\sum$$\exp$$f_i$

Lassen Sie uns das nächstbeste tun. Wir werden eine andere Funktion , die ähnlich ist . Und wir werden es aus linearen Kombinationen des .g f $h$$g$$f_i$

Nehmen wir an, ist eine Vermutung für einen optimalen Wert. Wir möchten das verbessern. Finden wir eine andere Funktion , die zu und seiner Ableitung bei passt , dh und . Wenn Sie ein Diagramm von in einer kleinen Nachbarschaft von zeichnen, wird es ähnlich wie aussehen . h g x 0 g ( x 0 ) = h ( x 0 ) g ' ( x 0 ) = h ' ( x 0 ) h x 0$x_0$$h$$g$$x_0$$g(x_0)=h(x_0)$$g'(x_0)=h'(x_0)$$h$$x_0$$g$

Sie können zeigen, dassWir wollen etwas, das zu passt . Es gibt eine natürliche Wahl:Sie können sehen, dass sie bei übereinstimmen . Wir erhaltenDa eine Konstante ist, haben wir eine einfache lineare Kombination von deren Ableitung mit übereinstimmt . Wir müssen nur die Konstante in wählen , um .x 0 h ( x ) = Konstante + ∑ i f i ( x ) exp ( f i ( x 0 ) ) . x = x 0 h ' ( x ) =

$$g'(x)=\sum_i f_i'(x)\exp(f_i(x)).$$ $x_0$ $$h(x)=\mbox{constant}+\sum_i f_i(x)\exp(f_i(x_0)).$$ $x=x_0$x 0 f i ghg( x 0 )=h( x 0 $$h'(x)=\sum_i f_i'(x)\exp(f_i(x_0)).$$ $x_0$$f_i$$g$$h$$g(x_0)=h(x_0)$

Also bilden wir ausgehend von und optimieren dieses. Da es in der Nähe von ähnlich ist, hoffen wir, dass das Optimum von dem Optimum von g ähnlich ist. Sobald Sie eine neue Schätzung haben, konstruieren Sie das nächste und wiederholen Sie es. h ( x ) g ( x ) x 0 h $x_0$$h(x)$$g(x)$$x_0$$h$$h$

Ich hoffe das hat die Wahl von motiviert . Dies ist genau der Vorgang, der in EM stattfindet.$h$

Aber es gibt noch einen wichtigen Punkt. Mit Jensens Ungleichung können Sie zeigen, dass . Dies bedeutet, dass Sie bei der Optimierung von immer ein , das Vergleich zu größer macht . Obwohl durch seine lokale Ähnlichkeit mit motiviert war , ist es sicher, bei jeder Iteration global zu maximieren . Die Hoffnung, die ich oben erwähnte, ist nicht erforderlich.h ( x ) x g g ( x 0 ) h g $h(x)\le g(x)$$h(x)$$x$$g$$g(x_0)$$h$$g$$h$

Dies gibt auch einen Hinweis darauf, wann EM zu verwenden ist: Wenn Linearkombinationen der Argumente für die Funktion einfacher zu optimieren sind. Zum Beispiel, wenn sie quadratisch sind - wie es passiert, wenn mit Gaußschen Mischungen gearbeitet wird. Dies ist besonders relevant für Statistiken, bei denen viele der Standardverteilungen aus exponentiellen Familien stammen .$\exp$

Wie Sie sagten, werde ich nicht auf technische Details eingehen. Es gibt einige sehr schöne Tutorials. Einer meiner Favoriten ist Andrew Ngs Vorlesungsskript . Schauen Sie sich auch die Referenzen hier an .

1. EM ist natürlich motiviert für Mischmodelle und Modelle mit versteckten Faktoren im Allgemeinen. Nehmen wir zum Beispiel den Fall der Gaußschen Mischungsmodelle (GMM). Hier modellieren wir die Dichte der Beobachtungen als gewichtete Summe von Gaußschen: wobei die Wahrscheinlichkeit ist, dass die Stichprobe durch die i-te Komponente verursacht / erzeugt wurde, der Mittelwert der Verteilung ist und die Kovarianz ist Matrix. Der Weg, diesen Ausdruck zu verstehen, ist der folgende: Jedes Datenmuster wurde von einer Komponente erzeugt / verursacht, aber wir wissen nicht, welche. Der Ansatz besteht dann darin, die Unsicherheit in Bezug auf die Wahrscheinlichkeit auszudrücken (p ( x ) = K ∑ i = 1 π i N ( x | μ i , Σ i ) π i x μ i Σ i π $K$

   $$p(x) = \sum_{i=1}^{K}\pi_{i} \mathcal{N}(x|\mu_{i}, \Sigma_{i})$$ $\pi_{i}$$x$$\mu_{i}$$\Sigma_{i}$$\pi_{i}$ stellt die Wahrscheinlichkeit dar, dass die i-te Komponente diese Stichprobe berücksichtigen kann, und nimmt die gewichtete Summe. Stellen Sie sich als konkretes Beispiel vor, Sie möchten Textdokumente gruppieren. Die Idee ist anzunehmen, dass jedes Dokument zu einem Thema (Wissenschaft, Sport, ...) gehört, das Sie vorher nicht kennen !. Mögliche Themen sind versteckte Variablen. Anschließend erhalten Sie eine Reihe von Dokumenten. Wenn Sie n-Gramm oder die von Ihnen extrahierten Funktionen zählen, möchten Sie diese Cluster finden und feststellen, zu welchem ​​Cluster jedes Dokument gehört. EM ist ein Verfahren, das dieses Problem schrittweise angreift: Der Erwartungsschritt versucht, die Zuordnung der bisher erreichten Stichproben zu verbessern. Mit dem Maximierungsschritt verbessern Sie die Parameter der Mischung, dh die Form der Cluster.

2. Der Punkt verwendet keine monotonen Funktionen, sondern konvexe Funktionen. Und der Grund ist die Ungleichung von Jensen, die sicherstellt, dass sich die Schätzungen des EM-Algorithmus bei jedem Schritt verbessern.