K bedeutet als Grenzfall des EM-Algorithmus für Gaußsche Gemische mit Kovarianzen bis

Mein Ziel ist es zu sehen, dass der K-Mittelwert-Algorithmus tatsächlich ein Erwartungsmaximierungsalgorithmus für Gaußsche Gemische ist, bei dem alle Komponenten eine Kovarianz im Grenzwert als .$\sigma^2 I$$\lim_{\sigma \to 0}$

Angenommen , wir haben einen Datensatz $\{x_1, \dots ,x_N\}$ von Beobachtungen von Zufallsvariablen $X$ .
Die Zielfunktion für M-Mittel ist gegeben durch:

$$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$ wobei $r_{nk}$ ist eine binäre Indikatorvariable einer harten Zuordnung von $x_n$ zu Cluster $k$ .
(Wenn der Datenpunkt $x_n$ dem Cluster k zugewiesen ist $k$, ist $r_{nk} = 1$ und $r_{nj} = 0$ für $j \ne$ k).
Der K-Mittelwert-Algorithmus minimiert $J$ durch Iteration bis zur Konvergenz, was zwei aufeinanderfolgende Schritte umfasst:
(E) Minimieren$J$ in Bezug auf $\{r_{nk}\}_{n,k}$ hält alle $\mu_k$ fest
(M) minimiert $J$ in Bezug auf $\{\mu_k\}_k$ hält alle $r_{nk}$ fest

Im Allgemeinen maximiert der EM-Algorithmus, indem er alle beobachteten Daten mit $X$ , alle latenten Variablen mit $Z$ und alle Modellparameter mit $\theta$ , die posteriore Verteilung $p(\theta | X)$ durch Iteration bis zur Konvergenz von zwei abwechselnden Schritten:
(E. ) Berechnen Sie die Erwartung $Q(\theta, \theta^{\text{old}}) := \sum_{Z}p(Z | X, \theta^{\text{old}})\log p(Z,X|\theta)$
(M) find $\theta^{\text{new}} = \arg \max_{\theta} Q(\theta, \theta^{\text{old}})$

Betrachten Sie nun die Gaußsche Mischungsverteilung: Einführung einer latenten dimensionalen binären Zufallsvariablen durch , wir sehen, dass: Also

$$p(x) = \sum_{k=1}^K \pi_k N(x | \mu_k, \Sigma_k)$$ $K$$z$$p(z_k = 1) = \pi_k$
$$p(X, Z) = \prod_{n=1}^N\prod_{k=1}^K \pi_k^{z_{nk}} N(x_n | \mu_k, \Sigma_k)^{z_{nk}}$$ $$\gamma(z_k) := p(z_k = 1 | x) = \frac{\pi_k N(x| \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j N(x | \mu_j, \Sigma_j)}$$ $$\log p(X,Z | \mu, \Sigma, \pi) = \sum_{n=1}^N \sum_{k=1}^K z_{nk}(\log \pi_k + \log N(x_n| \mu_k, \Sigma_k))$$ $$\mathbb{E}(z_{nk}) = \gamma(z_{nk})$$ $$Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk})(\log \pi_k + \log N(x_n| \mu_k, \Sigma_k))$$

Wenn jetzt alle Gaußschen im Mischungsmodell die Kovarianz , kann unter Berücksichtigung der Grenze leicht zeigen, dass wobei as ist oben definiert. In der Tat aktualisiert der (E) -Schritt wie im K-Mittelwert-Algorithmus.$\sigma^2 I$$\sigma \to 0$$\gamma(z_{nk}) \to r_{nk}$$r_{nk}$$r_{nk}$

Ich habe jedoch Probleme mit der Maximierung von in diesem Zusammenhang, wie für . Stimmt es, dass bis zu einer konstanten und skalaren Multiplikation: ?$Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}})$$x \ne \mu$ $\lim_{\sigma \to 0} log(N(x|\mu,\sigma^2)) = - \infty$
$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$

Vielleicht fehlt mir etwas. Irgendein Rat?

Stimmt es, dass bis zu einer konstanten und skalaren Multiplikation: ?$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$

Dies ist nicht der Fall, da - wie Sie selbst beobachtet haben - die Grenze abweicht.

Wenn wir jedoch zuerst transformieren und dann die Grenze nehmen, konvergieren wir zum k-Mittelwert-Ziel. Für und wir$Q$$\Sigma_k = \sigma^2 I$$\pi_k = 1/K$

$$\begin{align} Q &= \sum_{n,k} \gamma_{nk} \left( \log \pi_k + \log N(x_n \mid \mu_k, \Sigma_k) \right) \\ &= N \log\frac{1}{K} - \frac{1}{\sigma^2} \sum_{n,k} \gamma_{nk} ||x_n - \mu_k||^2 - N \frac{D}{2} \log 2\pi\sigma^2. \end{align}$$

Durch Multiplizieren mit (was den EM-Algorithmus nicht beeinflusst, da nicht optimiert, sondern konstant ist) und Sammeln aller konstanten Terme in wir, dass Beachten Sie, dass die Maximierung dieser Funktion in Bezug auf für jedes und dasselbe ergibt Ergebnis als obige Zielfunktion, dh es ist eine äquivalente Formulierung des M-Schritts. Aber das Limit zu nehmen ergibt jetzt .$\sigma^2$$\sigma$$C$

$$\begin{align} Q &\propto - \sum_{n,k} \gamma_{nk} ||x_n - \mu_k||^2 + \sigma^2 C. \end{align}$$ $\mu$$\gamma$$\sigma$$-J$

---

Abgesehen davon besteht eine meiner Ansicht nach etwas elegantere Formulierung von EM darin, die Zielfunktion Mit dieser Zielfunktion läuft der EM-Algorithmus auf Alternieren hinaus zwischen der Optimierung von in Bezug auf (M-Schritt) und (E-Schritt). Wenn wir die Grenze nehmen, sehen wir, dass sowohl der M-Schritt als auch der E-Schritt zum k-Mittelwert-Algorithmus konvergieren.

$$\begin{align} F(\mu, \gamma) &= \sum_{n,k} \gamma_{nk} \log \pi_k N(x_n \mid \mu_k, \Sigma_k)/\gamma_{nk} \\ &\propto -\sum_{n,k} \sum_{n, k} \gamma_{nk} ||x_n - \mu_k||^2 - \sigma^2 \sum_{n,k} \gamma_{nk} \log \gamma_{nk} + \sigma^2 C. \end{align}$$ $F$$\mu$$\gamma$

Siehe auch eine alternative Ansicht von EM .