EM-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Der Expectation-Maximization-Algorithmus (selten auch Estimation-Maximization-Algorithmus, kurz EM-Algorithmus) ist ein Algorithmus der mathematischen Statistik.

Der EM-Algorithmus wird vorrangig zur Ballungsanalyse verwendet. Siehe hierzu den Abschnitt „EM-Algorithmus“ im Artikel Clusteranalyse.

Inhaltsverzeichnis

1 Funktionsweise
2 Formulierung als Zufallsexperiment
3 Lösungsverfahren
4 Vorteile
5 Instanzen des EM-Algorithmus
6 Beweis für den Maximization-Schritt bei Normalverteilungsannahme
7 Literatur

[Bearbeiten] Funktionsweise

Es liegen Objekte mit einer gewissen Anzahl von Eigenschaften vor. Die Eigenschaften nehmen zufällige Werte an. Einige Eigenschaften können gemessen werden, andere jedoch nicht. Formal gesehen sind die Objekte Instanzen einer mehrdimensionalen Zufallsvariablen X, die einer unbekannten Wahrscheinlichkeitsverteilung p(x) unterliegt; einige Dimensionen sind „beobachtbar“, andere sind „versteckt“. Ziel ist es, die unbekannte Wahrscheinlichkeitsverteilung zu bestimmen.

Zunächst nimmt man an, p(x) sei bis auf einige Parameter bekannt. Meist wählt man p als Mischverteilung, also als gewichtete Summe von so vielen Standardverteilungen, wie beobachtbare Eigenschaften vorliegen. Wählt man beispielsweise als Standardverteilung die Normalverteilung, so sind die unbekannten Parameter jeweils der Mittelwert μ und die Varianz σ. Ziel ist es nun, die Parameter Θ der vermuteten Wahrscheinlichkeitsverteilung zu bestimmen. Wählt man eine Mischverteilung, so beinhaltet Θ auch die Gewichtungsfaktoren der Summe.

Für gewöhnlich geht man ein solches Problem mit der Maximum-Likelihood-Methode an. Dies ist hier jedoch nicht möglich, da die gesuchten Parameter von den versteckten Eigenschaften abhängen – und diese sind unbekannt. Um trotzdem zum Ziel zu kommen, wird also eine Methode benötigt, die gleichzeitig mit den gesuchten Endparametern die versteckten Parameter schätzt. Diese Aufgabe erfüllt der EM-Algorithmus.

Der EM-Algorithmus arbeitet iterativ und führt in jedem Durchgang zwei Schritte aus:

Versteckte Parameter Y schätzen. Zunächst werden die versteckten Parameter aus den im vorherigen Durchgang bestimmten Endparametern Θ und den beobachteten Daten X geschätzt. Dazu wird die sogenannte Q-Funktion verwendet, die einen vorläufigen Erwartungswert der gesuchten Verteilung berechnet.
Endparameter Θ bestimmen. Jetzt, wo die versteckten Parameter abgeschätzt sind, wird die Maximum-Likelihood-Methode angewandt, um die eigentlich gesuchten Parameter zu bestimmen.

Der Algorithmus endet, wenn sich die bestimmten Parameter nicht mehr wesentlich ändern.

Bewiesenermaßen konvergiert die Folge der bestimmten Θs, d. h. der Algorithmus terminiert auf jeden Fall. Zudem bilden die bestimmten Parameter Θ ein lokales Optimum; das bedeutet, sie sind im Allgemeinen gut, es könnte jedoch unter Umständen (viel) bessere geben.

[Bearbeiten] Formulierung als Zufallsexperiment

Rein formal wird beim EM-Algorithmus angenommen, dass die Werte der beobachteten stochastischen Größe auf folgende Art und Weise zustandekommen: Wähle zuerst eine der eingehenden Zufallsvariablen aus und übernimm deren Wert als Endergebnis. Das bedeutet, dass genau ein Gewicht den Wert eins annimmt und alle anderen null sind. Bei der Approximation der Gewichte durch den EM-Algorithmus ist dies normalerweise aber nicht mehr der Fall. Die Wahrscheinlichkeitsdichte eines Zielwertes lässt sich bei Normalverteilungsannahme und konstanter Varianz der einzelnen Zufallsvariablen darstellen als: $p(y_i|h)= \frac{1}{\sqrt{2\pi^2}\sigma} e^{- \frac{1}{2\sigma^2} \sum_{j=1}^{n} w_{ij}(y_i-\mu_j)^2}$

Dabei besitzen die verwendeten Bezeichnungen folgende Bedeutungen:

$w i j$ : Gewicht der $j$ -ten Zufallsvariable für den $i$ -ten Wert der Zielgröße
$n$ : Anzahl der Gewichte
$y i$ : Wert der $i$ -ten Zielgröße
$h$ : Stichprobe
$μ j$ : Erwartungswert der $j$ -ten Zufallsvariable
$σ 2$ : Varianz

[Bearbeiten] Lösungsverfahren

Der EM-Algorithmus besteht aus mehreren Iterationen der Schritte Expectation und Maximization.

Im Expectation-Schritt werden die Erwartungswerte der Gewichte berechnet unter der Annahme, dass die Erwartungswerte der eingehenden Zufallsvariablen den in Schritt zwei berechneten entsprechen. Dies ist allerdings nur möglich, falls es sich nicht um die erste Iteration handelt.

Die Erwartungswerte lassen sich darstellen als $E[w_{ij}]=p(X_j=y_i |\mu _j = \mu _{j,\mathrm{appr}})/ \sum _{k=1}^n p(X_k=y_i|\mu_k = \mu_{k,\mathrm{appr}})$

Im Maximization-Schritt werden die Erwartungwerte der Wahrscheinlichkeitsverteilungen der einzelnen Zufallsvariablen bestimmt, bei denen die Wahrscheinlichkeit für das Eintreffen des Stichprobenergebnisses, unter der Annahme, dass die exakten Werte der Gewichte jeweils ihren Erwartungswerten entsprechen, maximiert wird (Maximum-Likelihood-Algorithmus). Die auf diese Weise geschätzten Erwartungswerte ergeben sich bei Normalverteilungsannahme durch $\mu_{j,\mathrm{appr}}=\frac{1}{n} \sum_{i=1}^n E[w_{ij}] y_i$

[Bearbeiten] Vorteile

Kann mit unvollständigen Beobachtungen umgehen

[Bearbeiten] Instanzen des EM-Algorithmus

Schätzen der Parameter einer Mischverteilung
Baum-Welch-Algorithmus zum Schätzen der Parameter eines Hidden-Markov-Modells
…

[Bearbeiten] Beweis für den Maximization-Schritt bei Normalverteilungsannahme

Bewiesen werden soll: $\mathrm{maxarg}_{\mu_k}\prod_{i=1}^m P\left( y|h \right) =^? \frac{1}{m} \sum_{i=1}^{m} \frac{1}{2\sigma ^2} E[w_{ik}] y_i$

Anstatt $P (y | h)$ zu maximieren, kann auch $ln P (y | h)$ maximiert werden, da der Logarithmus eine streng monoton steigende Funktion ist.

$\mathrm{maxarg}_{\mu} \ln \prod_{i=1}^m P(y\|h)$	$= \mathrm{maxarg}_{\mu} \left( \sum_{i=1}^m \left( \ln \frac{1}{\sqrt{2\pi^2}} - \sum_{j=1}^n \frac{1}{2\sigma ^2} E[w_{ij}] (y_i-\mu_j)^2 \right) \right)$
	$= \mathrm{maxarg}_{\mu} \left( m \ln \frac{1}{\sqrt{2\pi^2}} - \frac{1}{2\sigma^2} \sum_{i=1}^m \sum_{j=1}^n E[w_{ij}] (y_i-\mu_j)^2 \right)$

Der Minuend ist eine Konstante, deswegen ist es ausreichend, den Subtrahend zu minimieren:

$\mathrm{minarg}_{\mu} \left( \frac{1}{2\sigma^2} \sum_{i=1}^m \sum_{j=1}^n E \left[w_{ij} \right] \left(y_i-\mu_j \right)^2 \right)=$ $\mathrm{minarg}_{\mu} \left(\sum_{i=1}^m \sum_{j=1}^n E[w_{ij}] (y_i-\mu_j)^2 \right)$

Eine quadratische Summe ergibt stets einen nichtnegativen Wert. Daher ist das absolute Minimum durch 0 beschränkt und somit auch ein lokales Minimum. Man setze die 1. Ableitung für diesen Term $t$ nach jedem $μ k$ auf 0:

$\frac{\mathrm{d}t}{\mathrm{d}\mu_k} = -2\sum_{i=1}^m E \left[w_{ik} \right] \left(y_i-\mu_k \right) = 0$ ,

denn die Ableitung aller Summanden der Summe über j sind 0, außer für j=k. Folglich:

$\sum_{i=1}^m E[w_{ik}] y_i= m\mu_k \quad \Rightarrow \quad \mu_k=\frac{1}{m} \sum_{i=1}^m E\left[w_{ik} \right] y_i$

q.e.d.

[Bearbeiten] Literatur

Dempster, A.P., Laird. N.M., Rubin, D.B.: Maximum-Likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 1977
Mitchell, Tom M., Machine Learning. The Mc-Graw-Hill Companies, Inc., 1997

Von „http://de.wikipedia.org../../../e/m/-/EM-Algorithmus_c0d2.html“

Kategorie: Algorithmus