Derivando o algoritmo K-means como um limite de Maximização de Expectativas para Misturas Gaussianas

Christopher Bishop define o valor esperado da função de probabilidade do log de dados completos (ou seja, assumindo que recebemos os dados observáveis ​​X e os dados latentes Z) da seguinte maneira:

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

onde $\gamma(z_{nk})$ é definido como:

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

A idéia, como descrita, é considerar um Modelo de Mistura Gaussiano no qual as matrizes de covariância dos componentes da mistura são dadas por $\epsilon \textbf{I}$ , em que $\epsilon$ é um parâmetro de variação compartilhado por todos os componentes, como aquele:

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

e assim, $\gamma(z_{nk})$ agora é definido como:

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

O argumento agora é o seguinte:

se considerarmos o limite , vemos que no denominador o termo para o qual é menor, passará a zero mais lentamente e, portanto, as responsabilidades para o ponto de dados vão para zero, exceto pelo termo j, pela qual a responsabilidade irá para a unidade. Assim, nesse limite, obtemos uma atribuição rígida de pontos de dados para clusters, assim como no algoritmo -eans, de modo 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}$

onde é definido como:$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*}$$

Minha pergunta é como o argumento acima se aplica? Ou seja, o que significa um termo ir para zero ? E como levar o limite na eqn resulta em uma responsabilidade binária?$\textbf{most slowly}$$\epsilon \to 0$$4$

Vamos escrever Então Se usarmos teremos where exceto em queπ k exp { - ‖ x n - μ k ‖ 2 / 2 ε

$$\|\textbf x_n - \boldsymbol \mu_k\|^2=\delta_k\,.$$ δ∗=minnδ $$\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\}}$$ π k exp { - δ k / 2 ϵ $$\delta^*=\min_n\delta_n\,,$$ δ*-δk<0K=k*δ*-δk*=0k≠k*limε→0πkexp{(δ∗-δk)/2 $$\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$ . Portanto, para todos os , , pois, para , enquanto $k\ne k^*$um>0limε→0exp{-um/ε}=0limε→0π k * exp{(δ∗-δ 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$$