# K-means as limit of Soft K-means algorithm

I encountered the following exercise

Show that as the stiffness $\beta$ goes to $\infty$, the soft $K$-means algorithm becomes identical to the original hard $K$-means algorithm, except for the way in which means with no assigned points behave. Describe what those means do instead of sitting still.

The notation is as follows:

The point $\mathbb{x}^{(n)}$ gives a weight to the $k$-th cluster update through the responsibility $$r_k^{(n)}=\frac{\exp{(-\beta d(m^{(k)},\mathbb{x}^{(n)}))}}{\sum_i \exp{(-\beta d(m^{(i)},\mathbb{x}^{(n)}))}}$$

where $m^{(k)}$ is the $k$-th cluster point and $d(x,y) =\frac{1}{2}\sum_i (x_i-y_i)^2$. Then the update of $m^{(k)}$ is done with

$$m^{(k)}=\frac{\sum_i r_k^{(i)}\mathbb{x}^{(i)}}{\sum_i r_k^{(i)}}$$

As stiffness $\beta$ goes to $\infty$ I see how soft $K$-means becomes hard $K$-means.

The second part of the problem is asking about means which would have no assigned points in the context of hard $K$-means and thus not move. With soft $K$-means however they would move but does anyone know geometrically what they do?

Try to find a probabilistic interpretation for each $r$. Then try to express the new position as an expectation over the r's.
• I am baffled at what to do. For a mean with no assigned points each $r^{(i)}$ goes to $0$ as $\beta$ goes to $\infty$. But how the new mean $m$ behaves in the limit depends on the comparative rates the $r^{(i)}$'s go to zero which depends on the other means. How to interpret all of this into some simple geometric interpretation eludes me. Jun 25, 2013 at 1:16