K-means comme cas limite de l'algorithme EM pour les mélanges gaussiens avec covariances

Mon objectif est de voir que l'algorithme K-means est en fait un algorithme d'expectation-maximisation pour les mélanges gaussiens dans lequel toutes les composantes ont une covariance dans la limite comme .$\sigma^2 I$$\lim_{\sigma \to 0}$

Supposons que nous ayons un ensemble de données $\{x_1, \dots ,x_N\}$ des observations de variable aléatoire $X$ .
La fonction objective pour les moyennes M est donnée par:

$$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$ où $r_{nk}$ est une variable indicatrice binaire d'une affectation dure de $x_n$ au cluster $k$ .
(si le point de données $x_n$ est affecté au cluster $k$ , alors $r_{nk} = 1$ et $r_{nj} = 0$ pour $j \ne$ k).
L'algorithme K-means minimise $J$ par itération jusqu'à la convergence, ce qui implique deux étapes successives:
(E) minimiser$J$ par rapport à $\{r_{nk}\}_{n,k}$ gardant tous les $\mu_k$ fixes
(M) minimiser $J$ par rapport à $\{\mu_k\}_k$ gardant tous les $r_{nk}$ fixes

En général, désignant toutes les données observées par $X$ , toutes les variables latentes par $Z$ et l'ensemble de tous les paramètres du modèle par $\theta$ , l'algorithme EM maximise la distribution postérieure $p(\theta | X)$ par itération jusqu'à convergence, de deux étapes alternées:
(E ) calculer l'espérance $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}})$

Considérons maintenant la distribution du mélange gaussien: Présentation d'une variable aléatoire binaire latente de dimension par , on voit que: Donc

$$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 maintenant tous les Gaussiens dans le modèle de mélange ont une covariance , considérant la limite je peux facilement montrer que où est aussi défini ci-dessus. Ainsi, l'étape (E) met à jour comme dans l'algorithme K-means.$\sigma^2 I$$\sigma \to 0$$\gamma(z_{nk}) \to r_{nk}$$r_{nk}$$r_{nk}$

Cependant, j'ai du mal à maximiser dans ce contexte, comme pour . Est-il vrai que jusqu'à une multiplication constante et scalaire: ?$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$

Peut-être que je manque quelque chose. Aucun conseil?

Est-il vrai que jusqu'à une multiplication constante et scalaire: ?$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$

Ce n'est pas le cas puisque - comme vous l'avez constaté vous-même - la limite diverge.

Cependant, si l' on d' abord transformons et puis prendre la limite, on converge à l'objectif k-means. Pour et nous avons$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}$$

En multipliant par (ce qui n'affecte pas l'algorithme EM, car n'est pas optimisé mais constant) et en collectant tous les termes constants en , nous voyons que Notez que maximiser cette fonction par rapport à pour tout et donne la même chose comme fonction objectif ci-dessus, c'est-à-dire qu'il s'agit d'une formulation équivalente de l'étape M. Mais prendre la limite donne maintenant .$\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$

---

Soit dit en passant, à mon avis, une formulation légèrement plus élégante d'EM consiste à utiliser la fonction objectif En utilisant cette fonction objective, l'algorithme EM revient à alterner entre l'optimisation de par rapport à (étape M) et (étape E). En prenant la limite, nous voyons que le pas M et le pas E convergent vers l'algorithme des k-moyennes.

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

Voir également une vue alternative de EM .