K-means como um caso limite do algoritmo EM para misturas de Gauss com covariâncias indo para

Meu objetivo é ver que o algoritmo K-means é de fato o algoritmo de Expectativa-Maximização para misturas Gaussianas, em que todos os componentes têm covariância no limite como .$\sigma^2 I$$\lim_{\sigma \to 0}$

Suponha que temos um conjunto de dados $\{x_1, \dots ,x_N\}$ de observações de variável aleatória $X$ .
A função objetivo para médias M é dada por:

$$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$ em que $r_{nk}$ é uma variável de indicador binário de uma designação definitiva de x_n$x_n$ para o cluster $k$ .
(ponto de dados se $x_n$ é atribuído a agrupar $k$ , então $r_{nk} = 1$ e $r_{nj} = 0$ para $j \ne$ k).
O algoritmo K-means minimiza $J$ através da iteração até a convergência, o que envolve duas etapas sucessivas:
(E) minimiza$J$ com relação a $\{r_{nk}\}_{n,k}$ mantendo todos $\mu_k$ fixos
(M) minimize $J$ com relação a $\{\mu_k\}_k$ mantendo todos os $r_{nk}$ fixos

Em geral, denotando todos os dados observados por $X$ , todas as variáveis ​​latentes por $Z$ e o conjunto de todos os parâmetros do modelo por $\theta$ , o algoritmo EM maximiza a distribuição posterior $p(\theta | X)$ através da iteração até a convergência, de duas etapas alternadas:
(E ) calcule a expectativa $Q(\theta, \theta^{\text{old}}) := \sum_{Z}p(Z | X, \theta^{\text{old}})\log p(Z,X|\theta)$
(M) encontre $\theta^{\text{new}} = \arg \max_{\theta} Q(\theta, \theta^{\text{old}})$

Agora, considere a distribuição gaussiana mistura: Introduzindo um latente -dimensional binário variável aleatória por , vemos que: AssimK z p ( z k = 1 ) = π k p ( X , Z ) = N ∏ n = 1 K ∏ μ k , Σ k ) z n k γ ( z

$$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}}$$ logp(X,Z|μ,Σ,π)=N ∑ n=1K ∑ k=1znk)E(znk)=γ(znk)Q( $$\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))$$

Se agora todos os gaussianos no modelo de mistura têm covariância , considerando o limite , posso mostrar facilmente que onde é definido acima. Portanto, a etapa (E) atualiza como no algoritmo K-means.σ → 0 γ ( z n k ) $\sigma^2 I$$\sigma \to 0$ r n k r n $\gamma(z_{nk}) \to r_{nk}$$r_{nk}$$r_{nk}$

No entanto, tenho problemas com a maximização de nesse contexto, como para . É verdade que até alguma multiplicação constante e escalar: ?$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$

Talvez esteja faltando alguma coisa. Algum conselho?

É verdade que até alguma multiplicação constante e escalar: ?$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$

Não é esse o caso, pois - como você se observou - o limite diverge.

No entanto, se primeiro transformarmos e depois tomarmos o limite, convergiremos para o objetivo de k-mean. Para e , temos$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}$$

Multiplicando por (que não afeta o algoritmo EM, pois não é otimizado, mas constante) e coletando todos os termos constantes em , vemos que Observe que maximizar essa função com relação a para qualquer e dá o mesmo resultar como a função objetivo acima, ou seja, é uma formulação equivalente da etapa M. Mas tomar o limite agora produz .$\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$

---

Como um aparte, na minha opinião, uma formulação um pouco mais elegante do EM é usar a função objetivo Usando essa função de objetivo, o algoritmo EM equivale a alternância entre otimizar com relação a (etapa M) e (etapa E). Tomando o limite, vemos que o passo M e o passo E convergem para o algoritmo k-means.Fμ

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

Veja também uma visão alternativa do EM .