1.4 Das Große Ganze

Hätten wir neben den Datenpunkten \(\mathbf{x}=(x_1,\dots,x_n)\) auch die Gruppenzuordnungen \(\mathbf{z}=(z_{11},\dots,z_{nG})\) beobachtet, dann könnten wir folgende Likelihood (\(\tilde{\mathcal{L}}\)) bzw. Log-Likelihood (\(\tilde{\ell}\)) Funktion aufstellen: \[\begin{align*} \tilde{\mathcal{L}}(\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\sigma}|\mathbf{x},\mathbf{z}) &=\prod_{i=1}^n\prod_{g=1}^G\left(\pi_gf(x_i|\mu_g,\sigma_g)\right)^{z_{ig}}\\[2ex] \tilde{\ell}(\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\sigma}|\mathbf{x},\mathbf{z}) &=\sum_{i=1}^n\sum_{g=1}^Gz_{ig}\left\{\ln\left(\pi_g\right)+\ln\left(f(x_i|\mu_g,\sigma_g)\right)\right\} \end{align*}\]

  • Im Gegensatz zur ursprünglichen Log-Likelihood Funktion (\(\ell\)), wäre die neue Log-Likelihood Funktion \(\tilde\ell\) einfach zu maximieren, da hier keine Summe innerhalb der Logarithmusfunktion steckt, sodass wir direkt den Logarithmus der Normalverteilung berechnen können. Dies vereinfacht das Maximierungsproblem deutlich, da die Normalverteilung zur Exponentialfamilie gehört.

  • Aber: Wir beobachten die Realisationen \(\mathbf{z}=(z_{11},\dots,z_{nG})\) nicht, sondern kennen lediglich die Verteilung der Zufallsvariablen \(\mathbf{Z}=(Z_{11},\dots,Z_{nG})\). Dies führt zu einer stochastischen Version der Log-Likelihood Funktion: \[ \tilde{\ell}(\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\sigma}|\mathbf{x},\mathbf{Z})=\sum_{i=1}^n\sum_{g=1}^GZ_{ig}\left\{\ln\left(\pi_g\right)+\ln\left(f(x_i|\mu_g,\sigma_g)\right)\right\} \]

  • Von dieser können jedoch den bedingten Erwartungswert berechnen: \[ E(\tilde{\ell}(\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\sigma}|\mathbf{x},\mathbf{z})|X_i=x_i)=\sum_{i=1}^n\sum_{g=1}^Gp_{ig}\left\{\ln\left(\pi_g\right)+\ln\left(f(x_i|\mu_g,\sigma_g)\right)\right\} \]

1.4.1 Der EM Algorithmus: Die abstrakte Version

Der folgende EM Algorithmus unterscheidet sich wieder lediglich in der Notation von den oben bereits besprochenen Versionen (siehe Kapitel 1.2.3). Die hier gewählte Notation verdeutlicht, dass der Expectation-Schritt die zu maximierende Log-Likelihood Funktion aktualisiert und diese dann im (Maximization)-Schritt maximiert wird. Darüber hinaus ist die gewählte Notation abstrakt genug, um die Grundidee des EM Algorithmuses auf andere Maximum Likelihood Probleme zu übertragen. Im Folgenden wird der Parametervektor \((\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\sigma})\) der Einfachheit halber auch mit \(\boldsymbol{\theta}\) bezeichnet.

  1. Setze Startwerte \(\boldsymbol{\theta}^{(0)}=(\pi^{(0)}, \mu^{(0)}, \sigma^{(0)})\)

  2. Für \(r=1,2,\dots\)

    • (Expectation) Berechne: \[\begin{align*} \mathcal{Q}(\boldsymbol{\theta},\boldsymbol{\theta}^{(r-1)}) &=E_{\boldsymbol{\theta}^{(r-1)}}(\tilde{\ell}(\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\sigma}|\mathbf{x},\mathbf{z})|X_i=x_i)\\ &=\sum_{i=1}^n\sum_{k=1}^Kp_{ig}^{(r-1)}\left\{\ln\left(\pi_g\right)+\ln\left(f(x_i|\mu_g,\sigma_g)\right)\right\} \end{align*}\]

    • (Maximization) Berechne: \[\begin{align*} \boldsymbol{\theta}^{(r)}=\arg\max_{\boldsymbol{\theta}}\mathcal{Q}(\boldsymbol{\theta},\boldsymbol{\theta}^{(r-1)}) \end{align*}\]

  3. Prüfe Konvergenz:

    • Stoppe, falls sich der Wert der maximierten Log-Likelihood Funktion, \(\mathcal{Q}(\boldsymbol{\theta}^{(r)},\boldsymbol{\theta}^{(r-1)})\), nicht mehr ändert.

Ende

Dem gemeinen Pinguin ist der EM Algorithmus egal (Abbildung 1.5).

Pinguinforschung am Limit.

Abbildung 1.5: Pinguinforschung am Limit.