K-means sebagai batas kasus algoritma EM untuk campuran Gaussian dengan kovarian akan

Tujuan saya adalah untuk melihat bahwa algoritma K-means sebenarnya adalah algoritma Ekspektasi-Maksimalisasi untuk campuran Gaussian di mana semua komponen memiliki kovarian dalam batas sebagai .$\sigma^2 I$$\lim_{\sigma \to 0}$

Misalkan kita memiliki kumpulan data $\{x_1, \dots ,x_N\}$ pengamatan dari variabel acak $X$ .
Fungsi objektif untuk M-means diberikan oleh:

$$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$ mana $r_{nk}$ adalah variabel indikator biner dari penugasan sulit $x_n$ ke cluster $k$ .
(jika titik data $x_n$ ditugaskan ke cluster $k$ , maka $r_{nk} = 1$ dan $r_{nj} = 0$ untuk $j \ne$ k).
Algoritma K-means meminimalkan $J$ melalui iterasi hingga konvergensi, yang melibatkan dua langkah berturut-turut:
(E) minimal$J$ sehubungan dengan $\{r_{nk}\}_{n,k}$ menjaga semua $\mu_k$ tetap
(M) meminimalkan $J$ sehubungan dengan $\{\mu_k\}_k$ menjaga semua $r_{nk}$ tetap

Secara umum, menunjukkan semua data yang diamati oleh $X$ , semua variabel laten oleh $Z$ dan set semua parameter model oleh $\theta$ , algoritma EM memaksimalkan p distribusi posterior (\ theta | X)$p(\theta | X)$ melalui iterasi hingga konvergensi, dari dua langkah bergantian:
(E ) menghitung ekspektasi $Q(\theta, \theta^{\text{old}}) := \sum_{Z}p(Z | X, \theta^{\text{old}})\log p(Z,X|\theta)$
(M) temukan $\theta^{\text{new}} = \arg \max_{\theta} Q(\theta, \theta^{\text{old}})$

Sekarang perhatikan distribusi campuran Gaussian: Memperkenalkan variabel acak biner laten -dimensi oleh , kita melihat bahwa: Jadi

$$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))$$

Jika sekarang semua Gaussians dalam model campuran memiliki kovarian , dengan mempertimbangkan batas Saya dapat dengan mudah menunjukkan bahwa mana adalah sebagai didefinisikan di atas. Jadi memang langkah (E) memperbarui seperti pada algoritma K-means.$\sigma^2 I$$\sigma \to 0$$\gamma(z_{nk}) \to r_{nk}$$r_{nk}$$r_{nk}$

Namun, saya memiliki masalah dengan memaksimalkan dalam konteks ini, seperti untuk . Apakah benar, bahwa hingga beberapa perkalian konstan dan skalar: ?$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$

Mungkin saya melewatkan sesuatu. Ada saran?

Apakah benar bahwa hingga beberapa penggandaan konstan dan skalar: ?$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$

Ini tidak terjadi karena - seperti yang Anda amati sendiri - batasnya berbeda.

Namun, jika kita pertama-tama mengubah dan kemudian mengambil batas, kita bertemu dengan tujuan k-means. Untuk dan kita miliki$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}$$

Mengalikan dengan (yang tidak mempengaruhi algoritma EM, karena tidak dioptimalkan tetapi konstan) dan mengumpulkan semua istilah konstan dalam , kita melihat bahwa Perhatikan bahwa memaksimalkan fungsi ini sehubungan dengan untuk setiap dan memberikan hal yang sama hasil sebagai fungsi objektif di atas, yaitu, itu adalah formulasi setara dari langkah-M. Tetapi mengambil batas sekarang menghasilkan .$\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$

---

Selain itu, menurut saya, formulasi EM yang sedikit lebih elegan adalah menggunakan fungsi objektif Menggunakan fungsi objektif ini, algoritme EM sama dengan bergantian antara mengoptimalkan sehubungan dengan (M-step) dan (E-step). Mengambil batas kita melihat bahwa baik M-step dan E-step bertemu dengan algoritma k-means.

$$\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$

Lihat juga pandangan alternatif EM .