EM-Algorithmus

Die Diskussion über diesen Antrag findet auf der Löschkandidatenseite statt.
Hier der konkrete Grund, warum dieser Artikel nicht den Qualitätsanforderungen entsprechen soll:

Begründung:Ich möchte mir angesichts der Qualität des Gebotenen jeden weiteren Kommentar hier Verkneifen. Wikiquette und Wikiliebe verbieten mir meiner Meinung zu diesem "Artikel" Ausdruck zu verleihen... --((ó)) Käffchen?!? 14:01, 13. Sep 2005 (CEST)

---

Der Expectation-Maximization-Algorithmus ist ein Algorithmus aus der mathematischen Statistik. Die Vorrausetzung für seine Anwendung besteht darin, dass sich eine beobachtete stochastische Größe als gewichtete Summe mehrerer Zufallsvariablen beschreiben läßt. 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 Verfahren 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, daß die Werte der beobachteten stochastischen Größe auf folgende Art und Weise zustandekommen: Wähle zuerst eine der eingehenden Zufallsvariablen aus und übernehme 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: Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle p(y_i|h)= \frac{1}{\sqrt{2\pi ^2 }} 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_{ij}$ Gewicht der j. Zufallsvariable für den i.Wert der Zielgröße
• n: Anzahl der Gewichte
• $y_{i}$: Wert der i. Zielgröße
• h: Stichprobe
• $\mu _{j}$: Erwartungswert der j.Zufallsvariable
• $\sigma ^{2}$: Varianz

Lösungsverfahren

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

• Im Expecation-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,appr})/\sum _{k=1}^{n}p(X_{k}=y_{i}|\mu _{k}=\mu _{k,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,appr}={\frac {1}{n}}\sum _{i=1}^{n}E[w_{ij}]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 Maximation-Schritt bei Normalverteilungsannahme

Bewiesen werden soll: $maxarg_{\mu }\Pi _{i=1}^{m}P(y_{i}/h)=^{!}{\frac {1}{n}}\sum _{i=1}^{n}E[w_{ij}]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.

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle maxarg_{\mu } ln \Pi_{i=1}^m P(y|h)=\sum_{i=1}^n \frac{1}{\sqrt {2\pi^2} } - (\sum_{j=1}^m E[w_{ij}] (y_j-\mu_ij))^2}
der erste Summand ist eine Konstante, daher ist es ausreichend den zweiten zu minimieren.

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle minarg_{mu} (\sum_{j=1}^m E(w_{ij}] (y_j-\mu_ij)^2}

Da dieser Term immer positiv ist, ist das absolute Minimum durch null beschränkt und daher auch ein lokales Minimum. Man setze die 1. Ableitung auf null:

$\sum _{j=1}^{m}2E[w_{ij}](y_{j}-\mu _{ij})=0$
$\sum _{j=1}^{m}2E[w_{ij}]y_{j}=n\mu _{ij}$
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \mu_{ij}=\frac{1}{n} \sum_{j=1}^m E[w_{ij}] y_j}

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