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 
, die einer unbekannten Wahrscheinlichkeitsverteilung 
unterliegt; einige Dimensionen sind „beobachtbar“, andere sind „versteckt“. Ziel ist es, die unbekannte Wahrscheinlichkeitsverteilung zu bestimmen.
Zunächst nimmt man an, sei bis auf einige Parameter bekannt. Meist wählt man 
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 Erwartungswert 
und die Varianz 
. Ziel ist es nun, die Parameter 
der vermuteten Wahrscheinlichkeitsverteilung zu bestimmen. Wählt man eine Mischverteilung, so enthält 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 mit den gesuchten Endparametern die versteckten Eigenschaften schätzt. Diese Aufgabe erfüllt der EM-Algorithmus.
Der EM-Algorithmus arbeitet iterativ und führt in jedem Durchgang zwei Schritte aus:
- E-Schritt: Versteckte Eigenschaften
schätzen. Zunächst werden die versteckten Eigenschaften aus den im vorherigen Durchgang bestimmten Endparametern und den beobachteten Daten geschätzt. Dazu wird die sogenannte Q-Funktion verwendet, die einen vorläufigen Erwartungswert der gesuchten Verteilung berechnet.
- M-Schritt: Endparameter bestimmen. Jetzt, wo die versteckten Eigenschaften 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 , das heißt, der Algorithmus terminiert auf jeden Fall. Allerdings bildet das Ergebnis meist nur ein lokales Optimum, welches zwar gut, aber nicht unbedingt optimal ist. Es ist daher nötig den Algorithmus mit vielen unterschiedlichen Startwerten auszuführen, um ein Endergebnis möglichst nah am Optimum zu finden.
Um den EM-Algorithmus anzuwenden, benötigt man einige beobachtete Daten , eine parametrische Dichte 
, eine Beschreibung der vollständigen Daten 
, die gefunden werden sollen, sowie die parametrische Dichte 
. Man kann davon ausgehen, dass bereits festgelegt worden ist, wie die vollständigen Daten aussehen, und dass sie als kontinuierliche Zufallsvariable mit der Dichte modelliert werden können, wobei 
. Man beobachtet nicht direkt. Stattdessen beobachtet man einen Wert 
der Zufallsvariablen 
für eine bestimmte Funktion 
. Beispielsweise könnte die Funktion eine Menge auf deren Mittelwert abbilden, oder wenn eine komplexe Zahl ist, sieht man nur deren Absolutwert, oder könnte nur die L-Norm eines Vektors zurückgeben usw. Da man nur zur Verfügung hat, kann man den Maximum-Likelihood-Schätzer (MLE) für 
bilden:
![{\displaystyle \operatorname {E} [w_{ij}]=p(X_{j}=y_{i}|\mu _{j}=\mu _{j,\mathrm {appr} })/\sum _{k=1}^{n}p(X_{k}=y_{i}\mid \mu _{k}=\mu _{k,\mathrm {appr} })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fac546501e0e22454e17128fe02806e7cbb637e)
![{\displaystyle \mu _{j,\mathrm {appr} }={\frac {\sum _{i=1}^{N}\operatorname {E} [w_{ij}]y_{i}}{\sum _{i=1}^{N}\operatorname {E} [w_{ij}]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6dc3d49a26acfa065331620547844c3e5a19aea)
![{\displaystyle \operatorname {E} [w_{ij}]={\begin{cases}1,&{\text{falls}}\quad ||\mu _{i}-X_{j}||=\min _{i}{||\mu _{i}-X_{j}||}\\0,&{\text{sonst.}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79c9d29f36ed14b252d1995d0f3129e91a57b8d0)
![{\displaystyle \mu _{j}={\frac {1}{\sum _{i}^{n}\operatorname {E} [w_{ij}]}}\sum _{i=1}^{n}\operatorname {E} [w_{ij}]y_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2234cdd53ea6337434431c6e82207f81cc60a853)
![{\displaystyle {\underset {\mu _{k}}{\mathrm {arg\,max} }}\prod _{i=1}^{m}P\left(y\mid h\right)={\frac {1}{m}}\sum _{i=1}^{m}{\frac {1}{2\sigma ^{2}}}\operatorname {E} [w_{ik}]y_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6903788c68a5c332c8b7eb9c44afc49e99f8e2ac)
^{2}\right)\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/594ef731bcc4c78bd88cc004f452ae0fa6a37333)
^{2}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6966de75a24c09cfd5d833c48141dec3d099ea3)
![{\displaystyle {\underset {\mu }{\mathrm {arg\,min} }}\left({\frac {1}{2\sigma ^{2}}}\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} \left[w_{ij}\right]\left(y_{i}-\mu _{j}\right)^{2}\right)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aec20840126575abd76ee950f07df49e1d5b614f)
^{2}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0c8b865537a29e9f11003215149b54906ea90ac)
![{\displaystyle {\frac {\mathrm {d} t}{\mathrm {d} \mu _{k}}}=-2\sum _{i=1}^{m}\operatorname {E} \left[w_{ik}\right]\left(y_{i}-\mu _{k}\right)=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67cd4be98621735cb4477d4c7a2662b6f8c5514c)
![{\displaystyle \sum _{i=1}^{m}\operatorname {E} [w_{ik}]y_{i}=\mu _{k}\sum _{i=1}^{m}\operatorname {E} [w_{ik}]\quad \Rightarrow \quad \mu _{k}={\frac {\sum _{i=1}^{m}\operatorname {E} \left[w_{ik}\right]y_{i}}{\sum _{i=1}^{m}\operatorname {E} [w_{ik}]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5c64e08ed3c70e61f45fb0865a85a7ad13b1301)