Dériver l'algorithme K-means comme limite de maximisation des attentes pour les mélanges gaussiens

Christopher Bishop définit la valeur attendue de la fonction de vraisemblance du journal des données complètes (c'est-à-dire en supposant que l'on nous donne à la fois les données observables X et les données latentes Z) comme suit:

$$\mathbb{E}_\textbf{Z}[\ln p(\textbf{X},\textbf{Z} \mid \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})] = \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk})\{\ln \pi_k + \ln \mathcal{N}(\textbf{x}_n \mid \ \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)\} \tag 1$$

où est défini comme:$\gamma(z_{nk})$

$$\frac{\pi_k \mathcal{N}(\textbf{x}_n \mid \ \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)}{\sum_{j=1}^K \pi_j \mathcal{N}(\textbf{x}_n \mid \ \boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)} \tag 2$$

L'idée, telle que décrite, est de considérer un modèle de mélange gaussien dans lequel les matrices de covariance des composants du mélange sont données par , où est un paramètre de variance qui est partagé par tous les composants, tels que cette:$\epsilon \textbf{I}$$\epsilon$

$$p(\textbf x \mid \boldsymbol \mu_k, \boldsymbol \Sigma_k) = \frac{1}{(2 \pi \epsilon)^\frac{M}{2}} \exp\big\{{-\frac{1}{2 \epsilon} \|\textbf x - \boldsymbol \mu_k\|^2}\big\} \tag 3$$

et ainsi, $\gamma(z_{nk})$ est maintenant défini comme:

$$\frac{\pi_k \exp\{ - \| \textbf x_n - \boldsymbol \mu_k\|^2 / 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{ - \| \textbf x_n - \boldsymbol \mu_j\|^2 / 2 \epsilon\}} \tag 4$$

L' argument est maintenant le suivant:

si l'on considère la limite , on voit que dans le dénominateur le terme pour lequel est le plus petit, ira à zéro le plus lentement, et donc les responsabilités pour le point de données vont toutes à zéro sauf pour le terme j, dont la responsabilité ira à l'unité. Ainsi, dans cette limite, nous obtenons une affectation difficile des points de données aux clusters, tout comme dans l' algorithme moyens, de sorte que$\epsilon \to 0$$\| \textbf x_n - \boldsymbol \mu_j\|^2$$\gamma(z_{nk})$$\textbf x_n$$\gamma(z_{nk})$$K$$\gamma(z_{nk}) \to r_{nk}$

où est défini comme:$r_{nk}$

$$\begin{equation*} f(n) = \begin{cases} 1 & \text{if } k = \text{arg } \text{min}_j \|\textbf x_n - \boldsymbol \mu_j\|^2\\ 0 & \text{otherwise}\\ \tag 5 \end{cases} \end{equation*}$$

Ma question est de savoir comment l'argument ci-dessus tient? A savoir, qu'est-ce que cela signifie pour un terme d'aller à zéro ? Et comment le fait de prendre la limite dans l'équation entraîne-t-il une responsabilité binaire?$\textbf{most slowly}$$\epsilon \to 0$$4$

Ecrivons Alors Si nous prenons nous avons où sauf pour où

$$\|\textbf x_n - \boldsymbol \mu_k\|^2=\delta_k\,.$$ $$\frac{\pi_k \exp\{ - \| \textbf x_n - \boldsymbol \mu_k\|^2 / 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{ - \| \textbf x_n - \boldsymbol \mu_j\|^2 / 2 \epsilon\}}=\frac{\pi_k \exp\{ - \delta_k/ 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{ - \delta_j/ 2 \epsilon\}}$$ $$\delta^*=\min_n\delta_n\,,$$ $$\begin{align*} \frac{\pi_k \exp\{ - \delta_k/ 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{ - \delta_j/ 2 \epsilon\}}&=\frac{\pi_k \exp\{(\delta^*- \delta_k)/ 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{(\delta^* - \delta_j)/ 2 \epsilon\}} \end{align*}$$ $\delta^*-\delta_k<0$$k=k^*$$\delta^*-\delta_{k^*}=0$ . Donc, pour tout , puisque, pour , tandis que $k\ne k^*$ $$\lim_{\epsilon\to 0} \frac{\pi_k \exp\{(\delta^*- \delta_k)/ 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{(\delta^* - \delta_j)/ 2 \epsilon\}}=\lim_{\epsilon\to 0} \frac{\pi_k \exp\{(\delta^*- \delta_k)/ 2 \epsilon\}}{\pi_{k^*}+\sum_{j\ne k^*} \pi_j \exp\{(\delta^* - \delta_j)/ 2 \epsilon\}}=0$$ $a>0$ $$\lim_{\epsilon\to 0}\exp\{-a/\epsilon \}=0$$ $$\lim_{\epsilon\to 0} \frac{\pi_{k^*} \exp\{(\delta^*- \delta_{k^*})/ 2 \epsilon\}}{\sum_{j=1}^K \pi_j \exp\{(\delta^* - \delta_j)/ 2 \epsilon\}}=\lim_{\epsilon\to 0} \frac{\pi_{k^*} \times 1}{\pi_{k^*}+\sum_{j\ne k^*} \pi_j \exp\{(\delta^* - \delta_j)/ 2 \epsilon\}}=1$$