K-means as limit of Soft K-means algorithm

Question

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?

Answer 1

When I look at the case where we have a single point and two clusters, it seems to me that both clusters in soft k-means will eventually be centered around the single point.

In the soft k-means, there is no such thing as an "un-assigned" cluster, so each cluster that would've been unassigned in the hard k-means will center on the nearest point.

Answer 2

Try to find a probabilistic interpretation for each $r$. Then try to express the new position as an expectation over the r's.