Der Expectation-Maximization-Algorithmus (auch EM-Algorithmus) ist ein Algorithmus aus der mathematischen Statistik.

Die Voraussetzung für seine Anwendung besteht darin, dass sich eine beobachtete stochastische Größe als gewichtete Summe mehrerer Zufallsvariablen beschreiben lässt. In diesem Fall können mit Hilfe des EM-Algorithmus bei einer gegebenen Stichprobe sowohl Varianz und Erwartungswert der eingehenden Zufallsvariablen als auch die Gewichte geschätzt werden. Für die Verwendung dieses Verfahrens müssen in der Stichprobe Werte für die beobachtete Zielgröße enthalten sein. Die Eingangsvariablen bilden häufig mehrere Modelle ab, deren Güte anhand des EM-Algorithmus bestimmt werden soll. Das bedeutet, je höher das Gewicht für eine bestimmte Zufallsvariable ist, desto höher wird die Qualität des entsprechenden Modells bewertet. Für den Fall, dass die einzelnen Modelle unabhängig voneinander sind, ermittelt der EM-Algorithmus das optimale Mischungsverhältnis, sodass das aus der gewichteten Summe gebildete kombinierte Modell eine höhere Genauigkeit besitzt als jedes der eingehenden Modelle.

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)=\; \backslash frac\{1\}\{\backslash sqrt\{2\backslash pi^2\}\}\; e^\{-\; \backslash frac\{1\}\{2\backslash sigma^2\}\; \backslash sum\_\{j=1\}^\{n\}\; w\_\{ij\}(y\_i-\backslash mu\_j)^2\}$

Dabei besitzen die verwendeten Bezeichnungen folgende Bedeutungen:

• $w\_\{ij\}$: 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
• $\backslash mu\_j$: Erwartungswert der $j$-ten Zufallsvariable
• $\backslash sigma^2$: Varianz

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*=p(X\_j=y\_i\; |\backslash mu\; \_j\; =\; \backslash mu\; \_\{j,\backslash mathrm\{appr\}\})/\; \backslash sum\; \_\{k=1\}^n\; p(X\_k=y\_i|\backslash mu\_k\; =\; \backslash mu\_\{k,\backslash 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 $\backslash mu\_\{j,\backslash mathrm\{appr\}\}=\backslash frac\{1\}\{n\}\; \backslash sum\_\{i=1\}^n\; E*y\_i$

Vorteile

• Kann mit unvollständigen Beobachtungen umgehen

Instanzen des EM-Algorithmus

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

Beweis für den Maximization-Schritt bei Normalverteilungsannahme

Bewiesen werden soll: $\backslash mathrm\{maxarg\}\_\{\backslash mu\_k\}\backslash prod\_\{i=1\}^m\; P\backslash left(\; y|h\; \backslash right)\; =^?\; \backslash frac\{1\}\{m\}\; \backslash sum\_\{i=1\}^\{m\}\; \backslash frac\{1\}\{2\backslash sigma\; ^2\}\; E*y\_i$

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

= \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^* (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^* (y_i-\mu_j)^2 \right)

\mathrm{maxarg}_{\mu} \ln \prod_{i=1}^m P(y >h)	$$
	$$

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

$\backslash mathrm\{minarg\}\_\{\backslash mu\}\; \backslash left(\; \backslash frac\{1\}\{2\backslash sigma^2\}\; \backslash sum\_\{i=1\}^m\; \backslash sum\_\{j=1\}^n\; E\; \backslash left\backslash right\backslash left(y\_i-\backslash mu\_j\; \backslash right)^2\; \backslash right)=$ $\backslash mathrm\{minarg\}\_\{\backslash mu\}\; \backslash left(\backslash sum\_\{i=1\}^m\; \backslash sum\_\{j=1\}^n\; E*(y\_i-\backslash mu\_j)^2\; \backslash 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 $\backslash mu\_k$ auf 0:

$\backslash frac\{\backslash mathrm\{d\}t\}\{\backslash mathrm\{d\}\backslash mu\_k\}\; =\; -2\backslash sum\_\{i=1\}^m\; E\; \backslash left\backslash right\backslash left(y\_i-\backslash mu\_k\; \backslash right)\; =\; 0$,

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

$\backslash sum\_\{i=1\}^m\; E*y\_i=\; m\backslash mu\_k\; \backslash quad\; \backslash Rightarrow\; \backslash quad\; \backslash mu\_k=\backslash frac\{1\}\{m\}\; \backslash sum\_\{i=1\}^m\; E\backslash left\backslash righty\_i$

q.e.d.

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

Algorithmus

Expectation-maximization algorithm | Algorithme espérance-maximisation