Erwartungsmaximierungsalgorithmus - Expectation–maximization algorithm

In Statistik , eine Erwartungsmaximierung ( EM ) Algorithmus ist eine iterative Methode (lokal) zu finden Maximum - Likelihood oder Maximum a posteriori (MAP) Schätzungen der Parameter in statistischen Modellen , wobei das Modell auf unbeobachtet hängt latente Variablen . Die EM-Iteration wechselt zwischen der Durchführung eines Erwartungsschritts (E), der eine Funktion für die Erwartung der logarithmischen Wahrscheinlichkeit erzeugt, die unter Verwendung der aktuellen Schätzung für die Parameter bewertet wird, und einem Maximierungsschritt (M), der Parameter berechnet, die den erwarteten logarithmischen Wert maximieren. Wahrscheinlichkeit auf der gefundenE- Schritt. Diese Parameterschätzungen werden dann verwendet, um die Verteilung der latenten Variablen im nächsten E-Schritt zu bestimmen.

EM-Clustering von Old Faithful- Eruptionsdaten. Das zufällige Ausgangsmodell (das aufgrund der unterschiedlichen Skalen der Achsen wie zwei sehr flache und breite Kugeln erscheint) wird an die beobachteten Daten angepasst. In den ersten Iterationen ändert sich das Modell erheblich, konvergiert dann aber zu den beiden Modi des Geysirs . Visualisiert mit ELKI .

Geschichte

Der EM-Algorithmus wurde in einem klassischen Papier von 1977 von Arthur Dempster , Nan Laird und Donald Rubin erklärt und benannt . Sie wiesen darauf hin, dass die Methode von früheren Autoren "vielfach unter besonderen Umständen vorgeschlagen" worden sei. Eine der frühesten ist die Gen-Zählmethode zur Schätzung der Allelfrequenzen von Cedric Smith . Eine sehr detaillierte Behandlung der EM-Methode für exponentielle Familien wurde von Rolf Sundberg in seiner Dissertation und mehreren Artikeln nach seiner Zusammenarbeit mit Per Martin-Löf und Anders Martin-Löf veröffentlicht . Das Dempster-Laird-Rubin-Papier von 1977 verallgemeinerte die Methode und skizzierte eine Konvergenzanalyse für eine breitere Klasse von Problemen. Das Dempster-Laird-Rubin-Papier etablierte die EM-Methode als wichtiges Werkzeug der statistischen Analyse.

Die Konvergenzanalyse des Dempster-Laird-Rubin-Algorithmus war fehlerhaft und eine korrekte Konvergenzanalyse wurde 1983 von CF Jeff Wu veröffentlicht. Wus Beweis stellte die Konvergenz der EM-Methode außerhalb der exponentiellen Familie fest , wie von Dempster-Laird-Rubin behauptet.

Einführung

Der EM-Algorithmus wird verwendet, um (lokale) Maximum-Likelihood- Parameter eines statistischen Modells in Fällen zu finden, in denen die Gleichungen nicht direkt gelöst werden können. Typischerweise beinhalten diese Modelle neben unbekannten Parametern und bekannten Datenbeobachtungen latente Variablen . Das heißt, es gibt entweder fehlende Werte unter den Daten oder das Modell kann einfacher formuliert werden, indem die Existenz weiterer unbeobachteter Datenpunkte angenommen wird. Beispielsweise kann ein Mischungsmodell einfacher beschrieben werden, indem angenommen wird, dass jeder beobachtete Datenpunkt einen entsprechenden unbeobachteten Datenpunkt oder eine latente Variable hat, die die Mischungskomponente spezifiziert, zu der jeder Datenpunkt gehört.

Das Finden einer Maximum-Likelihood-Lösung erfordert typischerweise, die Ableitungen der Likelihood-Funktion in Bezug auf alle unbekannten Werte, die Parameter und die latenten Variablen zu nehmen und gleichzeitig die resultierenden Gleichungen zu lösen. In statistischen Modellen mit latenten Variablen ist dies in der Regel nicht möglich. Stattdessen ist das Ergebnis typischerweise ein Satz ineinandergreifender Gleichungen, in denen die Lösung der Parameter die Werte der latenten Variablen erfordert und umgekehrt, aber das Einsetzen eines Satzes von Gleichungen in den anderen erzeugt eine unlösbare Gleichung.

Der EM-Algorithmus geht von der Beobachtung aus, dass es eine Möglichkeit gibt, diese beiden Gleichungssätze numerisch zu lösen. Man kann einfach beliebige Werte für eine der beiden Mengen von Unbekannten auswählen, sie verwenden, um die zweite Menge zu schätzen, dann diese neuen Werte verwenden, um eine bessere Schätzung der ersten Menge zu finden, und dann zwischen den beiden wechseln, bis die resultierenden Werte beide konvergieren zu Fixpunkten. Es ist nicht offensichtlich, dass dies funktioniert, aber es kann in diesem Zusammenhang bewiesen werden. Zusätzlich kann bewiesen werden, dass die Ableitung der Likelihood an diesem Punkt (willkürlich nahe) Null ist, was wiederum bedeutet, dass der Punkt entweder ein lokales Maximum oder ein Sattelpunkt ist . Im Allgemeinen können mehrere Maxima auftreten, ohne dass garantiert wird, dass das globale Maximum gefunden wird. Einige Likelihoods enthalten auch Singularitäten , dh unsinnige Maxima. Beispielsweise beinhaltet eine der Lösungen , die durch EM in einem Mischungsmodell gefunden werden können, das Einstellen einer der Komponenten auf eine Varianz von null und des mittleren Parameters für dieselbe Komponente auf einen der Datenpunkte.

Beschreibung

Bei einem statistischen Modell, das einen Satz beobachteter Daten, einen Satz unbeobachteter latenter Daten oder fehlender Werte und einen Vektor unbekannter Parameter zusammen mit einer Likelihood-Funktion erzeugt , wird die Maximum-Likelihood-Schätzung (MLE) der unbekannten Parameter durch Maximieren von . bestimmt die marginale Wahrscheinlichkeit der beobachteten Daten ${\displaystyle\mathbf{X}}$ ${\displaystyle\mathbf{Z}}$${\displaystyle {\boldsymbol {\theta}}}$ ${\displaystyle L({\boldsymbol {\theta}};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta}} )}$

${\displaystyle L({\boldsymbol {\theta}};\mathbf{X})=p(\mathbf{X}\mid {\boldsymbol{\theta}})=\int p(\mathbf{X} , \mathbf {Z} \mid {\boldsymbol {\theta}})\,d\mathbf {Z} =\int p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta}} )p(\mathbf{X}\mid {\boldsymbol{\theta}})\,d\mathbf{Z}}$

Diese Menge ist jedoch oft hartnäckig, da sie unbeobachtet ist und die Verteilung von unbekannt ist, bevor sie erreicht wird . ${\displaystyle\mathbf{Z}}$${\displaystyle\mathbf{Z}}$${\displaystyle {\boldsymbol {\theta}}}$

Der EM-Algorithmus versucht, den MLE der marginalen Likelihood zu finden, indem er diese beiden Schritte iterativ anwendet:

Erwartungsschritt (E-Schritt) : Definiere als erwarteten Wert der Log- Likelihood-Funktion von , in Bezug auf die aktuelle bedingte Verteilung von gegebenen und den aktuellen Schätzungen der Parameter : ${\displaystyle Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})}$${\displaystyle {\boldsymbol {\theta}}}$${\displaystyle\mathbf{Z}}$${\displaystyle\mathbf{X}}$${\displaystyle {\boldsymbol {\theta}}^{(t)}}$

${\displaystyle Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta}}^{(t)}}\left[\log L({\boldsymbol {\theta}};\mathbf{X},\mathbf{Z})\right]\,}$

Maximierungsschritt (M-Schritt) : Finden Sie die Parameter, die diese Menge maximieren:

${\displaystyle {\boldsymbol {\theta}}^{(t+1)}={\underset {\boldsymbol {\theta}}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\ Theta}}\mid {\boldsymbol {\theta}}^{(t)})\,}$

Die typischen Modelle, auf die EM angewendet wird, verwenden als latente Variable, die die Zugehörigkeit zu einer Gruppe von Gruppen anzeigt: ${\displaystyle\mathbf{Z}}$

1. Die beobachteten Datenpunkte können diskret sein (Werte in einer endlichen oder abzählbar unendlichen Menge annehmen) oder kontinuierlich (annehmend Werte in einer überzählbar unendlichen Menge). Jedem Datenpunkt kann ein Beobachtungsvektor zugeordnet sein.${\displaystyle\mathbf{X}}$
2. Die fehlenden Werte (auch bekannt als latente Variablen ) sind diskret , werden aus einer festen Anzahl von Werten gezogen und haben eine latente Variable pro beobachteter Einheit.${\displaystyle\mathbf{Z}}$
3. Die Parameter sind kontinuierlich und haben zwei Arten: Parameter, die allen Datenpunkten zugeordnet sind, und diejenigen, die einem spezifischen Wert einer latenten Variablen zugeordnet sind (dh allen Datenpunkten zugeordnet, deren entsprechende latente Variable diesen Wert hat).

Es ist jedoch möglich, EM auf andere Arten von Modellen anzuwenden.

Die Motivation ist wie folgt. Wenn der Wert der Parameter bekannt ist, kann der Wert der latenten Variablen normalerweise durch Maximieren der Log-Likelihood über alle möglichen Werte von gefunden werden , entweder einfach durch Iteration oder durch einen Algorithmus wie den Baum-Welch-Algorithmus für Hidden Markov Modelle . Umgekehrt, wenn wir den Wert der latenten Variablen kennen , können wir relativ leicht eine Schätzung der Parameter finden , typischerweise indem wir einfach die beobachteten Datenpunkte nach dem Wert der zugeordneten latenten Variablen gruppieren und die Werte mitteln oder eine Funktion der Werte der Punkte in jeder Gruppe. Dies legt einen iterativen Algorithmus nahe, falls beide und unbekannt sind: ${\displaystyle {\boldsymbol {\theta}}}$${\displaystyle\mathbf{Z}}$${\displaystyle\mathbf{Z}}$${\displaystyle\mathbf{Z}}$${\displaystyle\mathbf{Z}}$${\displaystyle {\boldsymbol {\theta}}}$${\displaystyle {\boldsymbol {\theta}}}$${\displaystyle\mathbf{Z}}$

1. Initialisieren Sie zunächst die Parameter mit einigen zufälligen Werten.${\displaystyle {\boldsymbol {\theta}}}$
2. Berechnen Sie die Wahrscheinlichkeit jedes möglichen Wertes von gegeben .${\displaystyle\mathbf{Z}}$${\displaystyle {\boldsymbol {\theta}}}$
3. Verwenden Sie dann die soeben berechneten Werte von , um eine bessere Schätzung für die Parameter zu berechnen .${\displaystyle\mathbf{Z}}$${\displaystyle {\boldsymbol {\theta}}}$
4. Iterieren Sie die Schritte 2 und 3, bis die Konvergenz erreicht ist.

Der soeben beschriebene Algorithmus nähert sich monoton einem lokalen Minimum der Kostenfunktion.

Eigenschaften

Von einem Erwartungsschritt (E) zu sprechen, ist ein bisschen falsch . Was im ersten Schritt berechnet wird, sind die festen, datenabhängigen Parameter der Funktion Q . Sobald die Parameter von Q bekannt sind, ist sie vollständig bestimmt und wird im zweiten (M) Schritt eines EM-Algorithmus maximiert.

Obwohl eine EM-Iteration die Wahrscheinlichkeitsfunktion der beobachteten Daten (dh die marginale) erhöht, gibt es keine Garantie dafür, dass die Folge zu einem Maximum-Likelihood-Schätzer konvergiert . Für multimodale Verteilungen bedeutet dies, dass ein EM-Algorithmus abhängig von den Startwerten gegen ein lokales Maximum der beobachteten Daten-Likelihood-Funktion konvergieren kann . Es gibt eine Vielzahl von heuristischen oder metaheuristischen Ansätzen, um einem lokalen Maximum zu entkommen, wie z. B. Hill Climbing mit zufälligem Neustart (beginnend mit mehreren verschiedenen zufälligen anfänglichen Schätzungen θ ^{( t )} ) oder die Anwendung simulierter Ausheilverfahren .

EM ist besonders nützlich, wenn die Wahrscheinlichkeit eine exponentielle Familie ist : Der E-Schritt wird zur Summe der Erwartungen einer ausreichenden Statistik , und der M-Schritt beinhaltet die Maximierung einer linearen Funktion. In einem solchen Fall ist es normalerweise möglich , mithilfe der Sundberg-Formel (veröffentlicht von Rolf Sundberg unter Verwendung unveröffentlichter Ergebnisse von Per Martin-Löf und Anders Martin-Löf ) für jeden Schritt Aktualisierungen von Ausdrücken in geschlossener Form abzuleiten .

Die EM-Methode wurde modifiziert, um maximale a posteriori (MAP)-Schätzungen für die Bayessche Inferenz in der Originalarbeit von Dempster, Laird und Rubin zu berechnen .

Es gibt andere Methoden, um Schätzungen der maximalen Wahrscheinlichkeit zu finden, wie z. B. Gradientenabstieg , konjugierter Gradient oder Varianten des Gauß-Newton-Algorithmus . Im Gegensatz zu EM erfordern solche Verfahren typischerweise die Auswertung erster und/oder zweiter Ableitungen der Likelihood-Funktion.

Korrektheitsnachweis

Erwartungsmaximierung dient eher der Verbesserung als der direkten Verbesserung . Hier wird gezeigt, dass Verbesserungen der ersteren Verbesserungen der letzteren implizieren. ${\displaystyle Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})}$${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta}})}$

Für alle mit einer Wahrscheinlichkeit ungleich Null können wir schreiben ${\displaystyle\mathbf{Z}}$${\displaystyle p(\mathbf{Z}\mid\mathbf{X},{\boldsymbol{\theta}})}$

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta}})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta}}) -\log p(\mathbf{Z}\mid\mathbf{X} ,{\boldsymbol{\theta}}).}$

Wir nehmen den Erwartungswert über mögliche Werte der unbekannten Daten unter die aktuelle Parameterschätzung, indem wir beide Seiten mit multiplizieren und über summieren (oder integrieren) . Die linke Seite ist der Erwartungswert einer Konstanten, also erhalten wir: ${\displaystyle\mathbf{Z}}$${\displaystyle \theta^{(t)}}$${\displaystyle p(\mathbf{Z}\mid\mathbf{X} ,{\boldsymbol {\theta}}^{(t)})}$${\displaystyle\mathbf{Z}}$

${\displaystyle {\begin{ausgerichtet}\log p(\mathbf {X} \mid {\boldsymbol {\theta}})&=\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf{X},{\boldsymbol{\theta}}^{(t)})\log p(\mathbf{X},\mathbf{Z} \mid {\boldsymbol {\theta}})-\sum _{\mathbf{Z}}p(\mathbf{Z}\mid\mathbf{X},{\boldsymbol {\theta}}^{(t)})\log p(\mathbf{Z}\mid\ mathbf {X} ,{\boldsymbol {\theta}})\\&=Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})+H({\ Fettsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)}),\end{ausgerichtet}}}$

wobei wird durch die negierte Summe definiert, die es ersetzt. Diese letzte Gleichung gilt für jeden Wert von einschließlich , ${\displaystyle H({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})}$${\displaystyle {\boldsymbol {\theta}}}$${\displaystyle {\boldsymbol {\theta}}={\boldsymbol {\theta}}^{(t)}}$

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta}}^{(t)})=Q({\boldsymbol {\theta}}^{(t)}\mid {\ Fettsymbol {\theta}}^{(t)})+H({\boldsymbol {\theta}}^{(t)}\mid {\boldsymbol {\theta}}^{(t)}),}$

und Subtrahieren dieser letzten Gleichung von der vorherigen Gleichung ergibt

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta}})-\log p(\mathbf {X} \mid {\boldsymbol {\theta}}^{(t)}) =Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})-Q({\boldsymbol {\theta}}^{(t)}\mid {\boldsymbol {\theta}}^{(t)})+H({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})-H({\boldsymbol {\theta} }^{(t)}\mid {\boldsymbol {\theta}}^{(t)}),}$

Die Ungleichung von Gibbs sagt uns jedoch, dass , also können wir daraus schließen, dass ${\displaystyle H({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})\geq H({\boldsymbol {\theta}}^{(t)}\mid {\boldsymbol {\theta}}^{(t)})}$

${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta}})-\log p(\mathbf {X} \mid {\boldsymbol {\theta}}^{(t)}) \geq Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})-Q({\boldsymbol {\theta}}^{(t)}\mid {\ Fettsymbol {\theta}}^{(t)}).}$

Mit Worten, die Entscheidung, sich zu verbessern, führt dazu, dass man sich mindestens genauso stark verbessert. ${\displaystyle {\boldsymbol {\theta}}}$${\displaystyle Q({\boldsymbol {\theta}}\mid {\boldsymbol {\theta}}^{(t)})}$${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta}})}$

Als Maximierungs-Maximierungs-Verfahren

Der EM-Algorithmus kann als zwei alternierende Maximierungsschritte betrachtet werden, also als Beispiel für einen Koordinatenabstieg . Betrachten Sie die Funktion:

${\displaystyle F(q,\theta ):=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q),}$

wobei q eine willkürliche Wahrscheinlichkeitsverteilung über die unbeobachteten Daten z ist und H(q) die Entropie der Verteilung q ist . Diese Funktion kann geschrieben werden als

${\displaystyle F(q,\theta)=-D_{\textrm{KL}}{\big(}q\parallel p_{Z\mid X}(\cdot\mid x;\theta){\big)} +\log L(\theta;x),}$

wobei die bedingte Verteilung der unbeobachteten Daten bei den beobachteten Daten und die Kullback-Leibler-Divergenz ist . ${\displaystyle p_{Z\mid X}(\cdot\mid x;\theta)}$${\displaystyle x}$${\displaystyle D_{KL}}$

Dann können die Schritte im EM-Algorithmus wie folgt betrachtet werden:

Erwartungsschritt : Wählen Sie , um zu maximieren : ${\displaystyle q}$${\displaystyle F}$

${\displaystyle q^{(t)}=\operatorname {arg\,max} _{q}\ F(q,\theta^{(t)})}$

Maximierungsschritt : Wählen Sie zum Maximieren : ${\displaystyle\theta}$${\displaystyle F}$

${\displaystyle \theta^{(t+1)}=\operatorname {arg\,max} _{\theta}\ F(q^{(t)},\theta)}$

Anwendungen

EM wird häufig zur Parameterschätzung von gemischten Modellen verwendet , insbesondere in der quantitativen Genetik .

In der Psychometrie ist EM ein wichtiges Werkzeug zur Schätzung von Itemparametern und latenten Fähigkeiten von Item-Response-Theorie- Modellen.

Mit der Fähigkeit, mit fehlenden Daten umzugehen und nicht identifizierte Variablen zu beobachten, werden EM zu einem nützlichen Instrument, um das Risiko eines Portfolios zu bewerten und zu steuern.

Der EM-Algorithmus (und seine schnellere Variante der geordneten Subset-Erwartungsmaximierung ) wird auch häufig in der medizinischen Bildrekonstruktion verwendet , insbesondere in der Positronen-Emissions-Tomographie , der Einzelphotonen-Emissions-Computertomographie und der Röntgen -Computertomographie . Siehe unten für andere schnellere Varianten von EM.

In der Bautechnik ist der Algorithmus Structural Identification using Expectation Maximization (STRIDE) eine reine Ausgabemethode zum Identifizieren von Eigenschwingungseigenschaften eines Struktursystems mithilfe von Sensordaten (siehe Operational Modal Analysis ).

EM wird auch für das Clustering von Daten verwendet . In der Verarbeitung natürlicher Sprache sind zwei prominente Instanzen des Algorithmus der Baum-Welch-Algorithmus für Hidden-Markov-Modelle und der Inside-Outside-Algorithmus für die unbeaufsichtigte Induktion probabilistischer kontextfreier Grammatiken .

Filtern und Glätten von EM-Algorithmen

Ein Kalman-Filter wird typischerweise für die Online-Zustandsschätzung verwendet, und ein Minimum-Varianz-Glätter kann für die Offline- oder Batch-Zustandsschätzung verwendet werden. Diese Lösungen mit minimaler Varianz erfordern jedoch Schätzungen der Parameter des Zustandsraummodells. EM-Algorithmen können verwendet werden, um Probleme der gemeinsamen Zustands- und Parameterschätzung zu lösen.

Filter- und Glättungs-EM-Algorithmen entstehen durch Wiederholung dieses zweistufigen Verfahrens:

E-Schritt

Betreiben Sie einen Kalman-Filter oder einen Glättungsmechanismus mit minimaler Varianz, der mit aktuellen Parameterschätzungen entworfen wurde, um aktualisierte Zustandsschätzungen zu erhalten.

M-Schritt

Verwenden Sie die gefilterten oder geglätteten Zustandsschätzungen in Maximum-Likelihood-Berechnungen, um aktualisierte Parameterschätzungen zu erhalten.

Angenommen, ein Kalman-Filter oder ein Minimum-Varianz-Glättungsgerät arbeitet mit Messungen eines Systems mit einem einzigen Eingang und einem einzigen Ausgang, die zusätzliches weißes Rauschen besitzen. Eine aktualisierte Schätzung der Messrauschenvarianz kann aus der Maximum-Likelihood- Berechnung erhalten werden

${\displaystyle {\widehat{\sigma}}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{ \widehat{x}}_{k})}^{2},}$

wo sind skalare Ausgabeschätzungen, die von einem Filter oder einem Glätter aus N skalaren Messungen berechnet werden . Die obige Aktualisierung kann auch zum Aktualisieren einer Poisson-Messungsrauschintensität angewendet werden. In ähnlicher Weise kann für einen autoregressiven Prozess erster Ordnung eine aktualisierte Schätzung der Prozessrauschvarianz berechnet werden durch ${\displaystyle {\widehat {x}}_{k}}$${\displaystyle z_{k}}$

${\displaystyle {\widehat {\sigma}}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat{x} }_{k+1}-{\widehat{F}}{\widehat{x}}_{k})}^{2},}$

wobei und skalare Zustandsschätzungen sind, die von einem Filter oder einem Glätter berechnet werden. Die aktualisierte Schätzung des Modellkoeffizienten erhält man über ${\displaystyle {\widehat {x}}_{k}}$${\displaystyle {\widehat {x}}_{k+1}}$

${\displaystyle {\widehat{F}}={\frac {\sum_{k=1}^{N}({\widehat{x}}_{k+1}-{\widehat{F}}{ \widehat{x}}_{k})}{\sum_{k=1}^{N}{\widehat{x}}_{k}^{2}}}.}$

Die Konvergenz von Parameterschätzungen wie den obigen ist gut untersucht.

Varianten

Eine Reihe von Methoden wurde vorgeschlagen, um die manchmal langsame Konvergenz des EM-Algorithmus zu beschleunigen, beispielsweise solche, die konjugierte Gradienten und modifizierte Newton-Methoden (Newton-Raphson) verwenden. Außerdem kann EM mit eingeschränkten Schätzverfahren verwendet werden.

Der Algorithmus zur Parameter-erweiterten Erwartungsmaximierung (PX-EM) bietet oft eine Beschleunigung durch "Verwendung einer 'Kovarianzanpassung', um die Analyse des M-Schritts zu korrigieren, wobei zusätzliche Informationen genutzt werden, die in den imputierten vollständigen Daten erfasst werden".

Bedingte Erwartungsmaximierung (ECM) ersetzt jeden M Schritt durch eine Folge von bedingten Maximierungsschritten (CM), in denen jeder Parameter θ _i einzeln maximiert wird, bedingt davon, dass die anderen Parameter fest bleiben. Selbst kann in den Algorithmus zur bedingten Maximierung der Erwartung (ECME) erweitert werden.

Diese Idee wird im verallgemeinerten Erwartungsmaximierungsalgorithmus (GEM) weiter erweitert , bei dem nur eine Erhöhung der Zielfunktion F sowohl für den E-Schritt als auch für den M-Schritt angestrebt wird, wie im Abschnitt Als Maximierungs-Maximierungs-Verfahren beschrieben . GEM wird in einer verteilten Umgebung weiterentwickelt und zeigt vielversprechende Ergebnisse.

Es ist auch möglich, den EM-Algorithmus als Unterklasse des MM- Algorithmus (Majorize/Minimize oder Minorize/Maximize, je nach Kontext) zu betrachten und daher jede Maschinerie zu verwenden, die im allgemeineren Fall entwickelt wurde.

α-EM-Algorithmus

Die im EM-Algorithmus verwendete Q-Funktion basiert auf der logarithmischen Wahrscheinlichkeit. Daher wird er als der log-EM-Algorithmus angesehen. Die Verwendung der logarithmischen Wahrscheinlichkeit kann auf die des α-log-Likelihood-Verhältnisses verallgemeinert werden. Dann kann das α-log-Likelihood-Verhältnis der beobachteten Daten unter Verwendung der Q-Funktion des α-log-Likelihood-Verhältnisses und der α-Divergenz exakt als Gleichheit ausgedrückt werden. Das Erhalten dieser Q-Funktion ist ein verallgemeinerter E-Schritt. Seine Maximierung ist ein verallgemeinerter M-Schritt. Dieses Paar wird als α-EM-Algorithmus bezeichnet, der als Unterklasse den log-EM-Algorithmus enthält. Somit ist der α-EM-Algorithmus von Yasuo Matsuyama eine exakte Verallgemeinerung des log-EM-Algorithmus. Es ist keine Berechnung des Gradienten oder der Hesse-Matrix erforderlich. Das α-EM zeigt eine schnellere Konvergenz als der log-EM-Algorithmus, wenn ein geeignetes α gewählt wird. Der α-EM-Algorithmus führt zu einer schnelleren Version des Hidden-Markov-Modell-Schätzalgorithmus α-HMM.

Beziehung zu Variations-Bayes-Methoden

EM ist eine teilweise nicht-bayesianische Methode mit maximaler Wahrscheinlichkeit. Das Endergebnis ergibt eine Wahrscheinlichkeitsverteilung über die latenten Variablen (im Bayesschen Stil) zusammen mit einer Punktschätzung für θ (entweder eine Schätzung der maximalen Wahrscheinlichkeit oder ein Posterior-Modus). Eine voll Bayes - Version kann dies gewünscht, ist eine Wahrscheinlichkeitsverteilung über geben θ und die latenten Variablen. Der Bayessche Ansatz zur Inferenz besteht darin, θ einfach als eine weitere latente Variable zu behandeln . In diesem Paradigma verschwindet die Unterscheidung zwischen den E- und M-Schritten. Wenn die faktorisierte Q-Approximation wie oben beschrieben verwendet wird ( variational Bayes ), kann die Lösung über jede latente Variable (jetzt einschließlich θ ) iterieren und sie einzeln optimieren. Nun werden k Schritte pro Iteration benötigt, wobei k die Anzahl der latenten Variablen ist. Bei grafischen Modellen ist dies einfach zu bewerkstelligen, da das neue Q jeder Variablen nur von ihrer Markov-Deckschicht abhängt , sodass die lokale Nachrichtenweitergabe für eine effiziente Inferenz verwendet werden kann.

Geometrische Interpretation

In der Informationsgeometrie werden der E-Schritt und der M-Schritt als Projektionen unter dual- affinen Verbindungen interpretiert , die als e-Verbindung und m-Verbindung bezeichnet werden; auch die Kullback-Leibler-Divergenz kann so verstanden werden.

Beispiele

Gaußsche Mischung

Vergleich von k-Means und EM an künstlichen Daten, die mit ELKI visualisiert wurden . Mit den Varianzen kann der EM-Algorithmus die Normalverteilungen exakt beschreiben, während k-means die Daten in Voronoi- Zellen aufteilt. Die Clustermitte wird durch das hellere, größere Symbol angezeigt.

Eine Animation, die den EM-Algorithmus demonstriert, der ein zweikomponentiges Gaussian- Mischungsmodell an den Old Faithful- Datensatz anpasst. Der Algorithmus geht von einer zufälligen Initialisierung zur Konvergenz durch.

Sei eine Stichprobe unabhängiger Beobachtungen aus einer Mischung von zwei multivariaten Normalverteilungen der Dimension , und seien die latenten Variablen, die die Komponente bestimmen, aus der die Beobachtung stammt. ${\displaystyle \mathbf{x} =(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n})}$${\displaystyle n}$${\displaystyle d}$${\displaystyle \mathbf{z} =(z_{1},z_{2},\ldots,z_{n})}$

${\displaystyle X_{i}\mid (Z_{i}=1)\sim {\mathcal{N}}_{d}({\boldsymbol {\mu}}_{1},\Sigma_{1} )}$ und ${\displaystyle X_{i}\mid (Z_{i}=2)\sim {\mathcal{N}}_{d}({\boldsymbol {\mu}}_{2},\Sigma_{2} ),}$

wo

${\displaystyle \operatorname {P} (Z_{i}=1)=\tau_{1}\,}$ und ${\displaystyle \operatorname {P} (Z_{i}=2)=\tau_{2}=1-\tau_{1}.}$

Das Ziel besteht darin, die unbekannten Parameter zu schätzen, die den Mischungswert zwischen den Gauß-Funktionen und den Mittelwerten und Kovarianzen von jedem darstellen:

${\displaystyle \theta ={\big (}{\boldsymbol {\tau}},{\boldsymbol {\mu}}_{1},{\boldsymbol {\mu}}_{2},\Sigma_{ 1},\Sigma_{2}{\big)},}$

wobei die Wahrscheinlichkeitsfunktion für unvollständige Daten

${\displaystyle L(\theta;\mathbf{x})=\prod_{i=1}^{n}\sum_{j=1}^{2}\tau_{j}\f(\mathbf {x}_{i};{\boldsymbol {\mu}}_{j},\Sigma_{j}),}$

und die Likelihoodfunktion für vollständige Daten ist

${\displaystyle L(\theta;\mathbf{x},\mathbf{z})=p(\mathbf{x},\mathbf{z}\mid\theta)=\prod_{i=1}^{ n}\prod_{j=1}^{2}\ [f(\mathbf{x}_{i};{\boldsymbol {\mu}}_{j},\Sigma_{j})\tau _{j}]^{\mathbb{I} (z_{i}=j)},}$

oder

${\displaystyle L(\theta;\mathbf{x},\mathbf{z})=\exp \left\{\sum_{i=1}^{n}\sum_{j=1}^{2 }\mathbb{I}(z_{i}=j){\big[}\log\tau_{j}-{\tfrac {1}{2}}\log |\Sigma_{j}|-{ \tfrac {1}{2}}(\mathbf{x}_{i}-{\boldsymbol {\mu}}_{j})^{\top}\Sigma_{j}^{-1}( \mathbf{x}_{i}-{\boldsymbol {\mu}}_{j})-{\tfrac{d}{2}}\log(2\pi){\big]}\right\} ,}$

wobei eine Indikatorfunktion und die Wahrscheinlichkeitsdichtefunktion einer multivariaten Normalen ist. ${\displaystyle\mathbb{I}}$${\displaystyle f}$

Bei der letzten Gleichheit ist für jedes i ein Indikator gleich null und ein Indikator ist gleich eins. Die innere Summe reduziert sich somit auf einen Term. ${\displaystyle \mathbb{I} (z_{i}=j)}$

E-Schritt

Angesichts unserer aktuelle Schätzung der Parameter θ ^{( t )} , die bedingte Verteilung des Z _i bestimmt wird durch Bayes Theorem die proportionale Höhe des normal sein Dichte durch gewichtete τ :

${\displaystyle T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{ (t)})={\frac{\tau_{j}^{(t)}\f(\mathbf{x}_{i};{\boldsymbol {\mu}}_{j}^{( t)},\Sigma_{j}^{(t)})}{\tau_{1}^{(t)}\f(\mathbf{x}_{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma_{1}^{(t)})+\tau_{2}^{(t)}\f(\mathbf{x}_{i };{\boldsymbol {\mu}}_{2}^{(t)},\Sigma_{2}^{(t)})}}.}$

Diese werden als "Zugehörigkeitswahrscheinlichkeiten" bezeichnet, die normalerweise als Ausgabe des E-Schritts betrachtet werden (obwohl dies nicht die Q-Funktion von unten ist).

Dieser E-Schritt entspricht der Einrichtung dieser Funktion für Q:

${\displaystyle {\begin{ausgerichtet}Q(\theta\mid \theta^{(t)})&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,\mathbf {\ theta } ^{(t)}}[\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X},\mathbf{\theta}^{(t)}}[\log\prod_{i=1}^{n}L(\theta;\mathbf{x}_{i},Z_{i })]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,\mathbf {\theta } ^{(t)}}[\sum _{i=1}^ {n}\log L(\theta;\mathbf{x}_{i},Z_{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{Z_ {i}\mid \mathbf {X} ;\mathbf {\theta} ^{(t)}}[\log L(\theta;\mathbf{x}_{i},Z_{i})]\\ &=\sum_{i=1}^{n}\sum_{j=1}^{2}P(Z_{i}=j\mid X_{i}=\mathbf{x}_{i} ;\theta^{(t)})\log L(\theta_{j};\mathbf{x}_{i},j)\\&=\sum_{i=1}^{n}\ Summe _{j=1}^{2}T_{j,i}^{(t)}{\big [}\log \tau_{j}-{\tfrac {1}{2}}\log | \Sigma_{j}|-{\tfrac {1}{2}}(\mathbf{x}_{i}-{\boldsymbol {\mu}}_{j})^{\top }\Sigma_ {j}^{-1}(\mathbf{x}_{i}-{\boldsymbol {\mu}}_{j})-{\tfrac {d}{2}}\log(2\pi) {\big]}.\end{ausgerichtet}}}$

Der Erwartungswert innerhalb der Summe wird in Bezug auf die Wahrscheinlichkeitsdichtefunktion genommen , die für jeden Trainingssatz unterschiedlich sein kann. Alles im E-Schritt ist bekannt, bevor der Schritt ausgeführt wird, außer , das gemäß der Gleichung am Anfang des E-Schritt-Abschnitts berechnet wird. ${\displaystyle \log L(\theta;\mathbf{x}_{i},Z_{i})}$${\displaystyle P(Z_{i}\mid X_{i}=\mathbf{x}_{i};\theta^{(t)})}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle T_{j,i}}$

Diese volle bedingte Erwartung muss nicht in einem Schritt berechnet werden, da τ und μ / Σ in getrennten linearen Terme erscheinen und kann somit unabhängig maximiert werden.

M-Schritt

Da Q ( θ  |  θ ^{( t )} ) quadratisch ist, bedeutet dies, dass die Bestimmung der Maximierungswerte von θ relativ einfach ist. Auch können τ , ( μ ₁ , Σ ₁ ) und ( μ ₂ , Σ ₂ ) alle unabhängig maximiert werden, da sie alle in separaten linearen Ausdrücken erscheinen.

Betrachten Sie zunächst τ , das die Nebenbedingung τ ₁ + τ ₂ =1 hat:

${\displaystyle {\begin{aligned}{\boldsymbol {\tau}}^{(t+1)}&={\underset {\boldsymbol {\tau}}{\operatorname {arg\,max} }}\ Q(\theta \mid \theta ^{(t)})\\&={\underset {\boldsymbol {\tau}}{\operatorname {arg\,max} }}\ \left\{\left[\ Summe _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau_{1}+\left[\sum_{i=1}^{n} T_{2,i}^{(t)}\right]\log\tau_{2}\right\}.\end{aligned}}}$

Dieser hat die gleiche Form wie der MLE für die Binomialverteilung , also

${\displaystyle \tau_{j}^{(t+1)}={\frac {\sum_{i=1}^{n}T_{j,i}^{(t)}}{\sum _{i=1}^{n}(T_{1,i}^{(t)}+T_{2,i}^{(t)})}}={\frac {1}{n}} \sum_{i=1}^{n}T_{j,i}^{(t)}.}$

Für die nächsten Schätzungen von ( μ ₁ ,Σ ₁ ):

${\displaystyle {\begin{ausgerichtet}({\boldsymbol {\mu}}_{1}^{(t+1)},\Sigma_{1}^{(t+1)})&={\ underset {{\boldsymbol {\mu}}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}Q(\theta \mid \theta ^{(t)})\\ &={\underset {{\boldsymbol {\mu}}_{1},\Sigma_{1}}{\operatorname {arg\,max} }}\sum _{i=1}^{n}T_ {1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log |\Sigma_{1}|-{\tfrac {1}{2}}(\mathbf {x}_{i}-{\boldsymbol {\mu}}_{1})^{\top}\Sigma_{1}^{-1}(\mathbf {x}_{i}-{\ Fettsymbol {\mu}}_{1})\right\}\end{ausgerichtet}}.}$

Dies hat die gleiche Form wie ein gewichteter MLE für eine Normalverteilung, also

${\displaystyle {\boldsymbol {\mu}}_{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t )}\mathbf{x}_{i}}{\sum_{i=1}^{n}T_{1,i}^{(t)}}}}$ und ${\displaystyle \Sigma_{1}^{(t+1)}={\frac {\sum_{i=1}^{n}T_{1,i}^{(t)}(\mathbf { x} _{i}-{\boldsymbol {\mu}}_{1}^{(t+1)})(\mathbf {x}_{i}-{\boldsymbol {\mu}}_{1 }^{(t+1)})^{\top}}{\sum_{i=1}^{n}T_{1,i}^{(t)}}}}$

und durch Symmetrie

${\displaystyle {\boldsymbol {\mu}}_{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t )}\mathbf{x}_{i}}{\sum_{i=1}^{n}T_{2,i}^{(t)}}}}$ und ${\displaystyle \Sigma_{2}^{(t+1)}={\frac {\sum_{i=1}^{n}T_{2,i}^{(t)}(\mathbf { x} _{i}-{\boldsymbol {\mu}}_{2}^{(t+1)})(\mathbf {x}_{i}-{\boldsymbol {\mu}}_{2 }^{(t+1)})^{\top}}{\sum_{i=1}^{n}T_{2,i}^{(t)}}}.}$

Beendigung

Beenden Sie den iterativen Prozess, wenn er unter einem voreingestellten Schwellenwert liegt. ${\displaystyle E_{Z\mid\theta^{(t)},\mathbf{x}}[\log L(\theta^{(t)};\mathbf{x},\mathbf{Z})] \leq E_{Z\mid\theta^{(t-1)},\mathbf{x}}[\log L(\theta^{(t-1)};\mathbf{x},\mathbf{Z } )]+\varepsilon }$${\displaystyle\varepsilon}$

Verallgemeinerung

Der oben dargestellte Algorithmus kann für Mischungen von mehr als zwei multivariaten Normalverteilungen verallgemeinert werden .

Abgeschnittene und zensierte Regression

Der EM-Algorithmus wurde für den Fall implementiert, dass ein zugrunde liegendes lineares Regressionsmodell existiert, das die Variation einer bestimmten Größe erklärt, die tatsächlich beobachteten Werte jedoch zensierte oder abgeschnittene Versionen der im Modell dargestellten Werte sind. Sonderfälle dieses Modells umfassen zensierte oder abgeschnittene Beobachtungen aus einer Normalverteilung .

Alternativen

EM konvergiert typischerweise zu einem lokalen Optimum, nicht notwendigerweise zum globalen Optimum, ohne dass die Konvergenzrate im Allgemeinen begrenzt ist. Es ist möglich, dass es in hohen Dimensionen beliebig schlecht sein kann und es eine exponentielle Anzahl lokaler Optima gibt. Daher besteht ein Bedarf an alternativen Methoden für garantiertes Lernen, insbesondere im hochdimensionalen Setting. Es gibt Alternativen zu EM mit besseren Konsistenzgarantien, die als momentbasierte Ansätze oder sogenannte Spektraltechniken bezeichnet werden . Momentbasierte Ansätze zum Erlernen der Parameter eines probabilistischen Modells sind in letzter Zeit von zunehmendem Interesse, da sie Garantien wie die globale Konvergenz unter bestimmten Bedingungen genießen, im Gegensatz zu EM, das oft von dem Problem des Hängenbleibens in lokalen Optima geplagt wird. Für eine Reihe wichtiger Modelle wie Mischungsmodelle, HMMs usw. können Algorithmen mit Lerngarantien abgeleitet werden. Bei diesen Spektralverfahren treten keine störenden lokalen Optima auf, und die wahren Parameter können unter gewissen Regularitätsbedingungen konsistent geschätzt werden.

Siehe auch

• Gemischverteilung
• zusammengesetzte Verteilung
• Dichteschätzung
• Totalabsorptionsspektroskopie
• Der EM-Algorithmus kann als Spezialfall des Majorize-Minimization (MM)-Algorithmus angesehen werden .

Verweise

Weiterlesen

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Einführung in die mathematische Statistik . Upper Saddle River, NJ: Pearson Prentice Hall. S. 359–364.
• Dellaert, Frank (2002). „Der Erwartungsmaximierungsalgorithmus“. CiteSeerX  10.1.1.9.9735 . Cite Journal erfordert |journal=( Hilfe ) gibt eine einfachere Erklärung des EM-Algorithmus in Bezug auf die Maximierung der unteren Grenze.
• Bischof, Christopher M. (2006). Mustererkennung und maschinelles Lernen . Springer. ISBN 978-0-387-31073-2.
• Gupta, MR; Chen, Y. (2010). „Theorie und Verwendung des EM-Algorithmus“. Grundlagen und Trends in der Signalverarbeitung . 4 (3): 223–296. CiteSeerX  10.1.1.219.6830 . doi : 10.1561/2000000034 . Ein gut geschriebenes Kurzbuch über EM, einschließlich detaillierter Ableitung von EM für GMMs, HMMs und Dirichlet.
• Bilmes, Jeff (1998). "Ein sanftes Tutorial des EM-Algorithmus und seiner Anwendung auf die Parameterschätzung für Gaußsche Mischung und Hidden-Markov-Modelle". CiteSeerX  10.1.1.28.613 . Cite Journal erfordert |journal=( Hilfe ) enthält eine vereinfachte Ableitung der EM-Gleichungen für Gauß'sche Mischungen und Gauß'sche Mischungen Hidden-Markov-Modelle.
• McLachlan, Geoffrey J.; Krishnan, Thriyambakam (2008). Der EM-Algorithmus und Erweiterungen (2. Aufl.). Hoboken: Wiley. ISBN 978-0-471-20170-0.

Externe Links

• Im Rahmen der gepaarten SOCR- Aktivitäten und Applets werden verschiedene 1D-, 2D- und 3D- Demonstrationen von EM zusammen mit Mixture Modeling bereitgestellt . Diese Applets und Aktivitäten zeigen empirisch die Eigenschaften des EM-Algorithmus zur Parameterschätzung in verschiedenen Einstellungen.
• k-MLE: Ein schneller Algorithmus zum Erlernen statistischer Mischungsmodelle
• Klassenhierarchie in C++ (GPL) einschließlich Gaussian Mixtures
• Das Online-Lehrbuch: Information Theory, Inference, and Learning Algorithms von David JC MacKay enthält einfache Beispiele des EM-Algorithmus wie Clustering mit dem weichen k- Means-Algorithmus und betont die Variationssicht des EM-Algorithmus, wie in beschrieben Kapitel 33.7 von Version 7.2 (vierte Auflage).
• Variational Algorithms for Approximate Bayesian Inference von MJ Beal enthält Vergleiche von EM mit Variational Bayesian EM und Ableitungen mehrerer Modelle, einschließlich Variational Bayesian HMMs ( Kapitel ).
• Der Erwartungsmaximierungsalgorithmus: Ein kurzes Tutorial , Eine eigenständige Ableitung des EM-Algorithmus von Sean Borman.
• Der EM-Algorithmus von Xiaojin Zhu.
• EM-Algorithmus und Varianten: ein informelles Tutorial von Alexis Roche. Eine knappe und sehr klare Beschreibung von EM und vielen interessanten Varianten.