8
$\begingroup$

My goal is to see that K-means algorithm is in fact Expectation-Maximization algorithm for Gaussian mixtures in which all components have covariance $\sigma^2 I$ in the limit as $\lim_{\sigma \to 0}$.

Suppose we have a data set $\{x_1, \dots ,x_N\}$ of observations of random variable $X$.
The objective function for M-means is given by: $$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$ where $r_{nk}$ is binary indicator variable of a hard assignment of $x_n$ to cluster $k$.
(if data point $x_n$ is assigned to cluster $k$, then $r_{nk} = 1$ and $r_{nj} = 0$ for $j \ne$ k).
K-means algorithm minimize $J$ through iteration until convergence, that involves two successive steps:
(E) minimize $J$ with respect to $\{r_{nk}\}_{n,k}$ keeping all $\mu_k$ fixed
(M) minimize $J$ with respect to $\{\mu_k\}_k$ keeping all $r_{nk}$ fixed

In general, denoting all observed data by $X$, all latent variables by $Z$ and set of all model parameters by $\theta$, the EM algorithm maximize posterior distribution $p(\theta | X)$ through iteration until convergence, of two alternating steps:
(E) calculate the expectation $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}})$

Now consider the Gaussian mixture distribution: $$p(x) = \sum_{k=1}^K \pi_k N(x | \mu_k, \Sigma_k)$$ Introducing a latent $K$-dimensional binary random variable $z$ by $p(z_k = 1) = \pi_k$, we see that:
$$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})$$ So $$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))$$

If now all Gaussians in the mixture model have covariance $\sigma^2 I$, considering the limit $\sigma \to 0$ I can easily show that $\gamma(z_{nk}) \to r_{nk}$ where $r_{nk}$ is as defined above. So indeed the (E) step updates $r_{nk}$ as in the K-means algorithm.

However, I have problem with maximizing $Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}})$ in this context, as for $x \ne \mu$ $\lim_{\sigma \to 0} log(N(x|\mu,\sigma^2)) = - \infty$.
Is it true, that up to some constant and scalar multiplication: $\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$ ?

Maybe I'm missing something. Any advice?

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site, @Andrzej. Please post the full question -- do not expext that people will go search for your book. $\endgroup$ – StasK Oct 4 '14 at 20:29
  • 1
    $\begingroup$ Dear StasK, I've just posted the full question and hope it is clear now. $\endgroup$ – Andrzej Neugebauer Oct 5 '14 at 22:49
3
$\begingroup$

Is it true that up to some constant and scalar multiplication: $\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$?

This is not the case since – as you observed yourself – the limit diverges.

However, if we first transform $Q$ and then take the limit, we converge to the k-means objective. For $\Sigma_k = \sigma^2 I$ and $\pi_k = 1/K$ we have

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

Multiplying by $\sigma^2$ (which does not affect the EM algorithm, since $\sigma$ is not optimized but constant) and collecting all the constant terms in $C$, we see that \begin{align} Q &\propto - \sum_{n,k} \gamma_{nk} ||x_n - \mu_k||^2 + \sigma^2 C. \end{align} Note that maximizing this function with respect to $\mu$ for any $\gamma$ and $\sigma$ gives the same result as the objective function above, i.e., it is an equivalent formulation of the M-step. But taking the limit now yields $-J$.


As an aside, an in my view slightly more elegant formulation of EM is to use the objective function \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} Using this objective function, the EM algorithm amounts to alternating between optimizing $F$ with respect to $\mu$ (M-step) and $\gamma$ (E-step). Taking the limit we see that both the M-step and the E-step converge to the k-means algorithm.

See also an alternative view of EM.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.