K-significa como caso límite del algoritmo EM para mezclas gaussianas con covarianzas Voy a

Mi objetivo es ver que el algoritmo K-means es, de hecho, un algoritmo de maximización de expectativas para mezclas gaussianas en las que todos los componentes tienen covarianza en el límite como .$\sigma^2 I$$\lim_{\sigma \to 0}$

Supongamos que tenemos un conjunto de datos $\{x_1, \dots ,x_N\}$ de las observaciones de la variable aleatoria $X$ .
La función objetivo para las medias M viene dada por:

$$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$ donde $r_{nk}$ es una variable indicadora binaria de una asignación difícil de $x_n$ al clúster $k$ .
(si el punto de datos $x_n$ se asigna al clúster $k$ , entonces $r_{nk} = 1$ y $r_{nj} = 0$ para $j \ne$ k).
El algoritmo K-means minimiza $J$ través de la iteración hasta la convergencia, que implica dos pasos sucesivos:
(E) minimizar$J$ con respecto a $\{r_{nk}\}_{n,k}$ manteniendo todo $\mu_k$ fijo
(M) minimice $J$ con respecto a $\{\mu_k\}_k$ manteniendo todo $r_{nk}$ fijo

En general, denotando todos los datos observados por $X$ , todas las variables latentes por $Z$ y el conjunto de todos los parámetros del modelo por $\theta$ , el algoritmo EM maximiza la distribución posterior $p(\theta | X)$ través de la iteración hasta la convergencia, de dos pasos alternos:
(E ) calcule la expectativa $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}})$

Ahora considere la distribución de la mezcla gaussiana: Presentando una variable aleatoria binaria dimensional latente por , vemos que: Entonces

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

Si ahora todos los gaussianos en el modelo de mezcla tienen covarianza , considerando el límite , puedo mostrar fácilmente que donde es como definido anteriormente. De hecho, el paso (E) actualiza como en el algoritmo K-means.$\sigma^2 I$$\sigma \to 0$$\gamma(z_{nk}) \to r_{nk}$$r_{nk}$$r_{nk}$

Sin embargo, tengo problemas para maximizar en este contexto, como para . ¿Es cierto que hasta una multiplicación constante y 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$

Tal vez me estoy perdiendo algo. ¿Algún consejo?

¿Es cierto que hasta una multiplicación constante y escalar: ?$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$

Este no es el caso ya que, como usted mismo observó, el límite diverge.

Sin embargo, si primero transformamos y luego tomamos el límite, convergemos al objetivo k-means. Para y tenemos$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 no afecta el algoritmo EM, ya que no está optimizado sino constante) y recolectando todos los términos constantes en , vemos que Tenga en cuenta que maximizar esta función con respecto a para cualquier y da lo mismo resultado como la función objetivo anterior, es decir, es una formulación equivalente del paso M. Pero tomar el límite ahora produce .$\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$

---

Por otro lado, en mi opinión, una formulación ligeramente más elegante de EM es usar la función objetivo Usando esta función objetivo, el algoritmo EM equivale a alternar entre optimizar con respecto a (paso M) y (paso E). Tomando el límite, vemos que tanto el paso M como el paso E convergen con el algoritmo 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$

Vea también una vista alternativa de EM .