K-means algorithm's EM "Maximization" step

Question

I'm a software engineer and am trying to understand how Lloyd's K-Means algorithm fits into the general framework of the Expectation-Maximization (EM) algorithm. I previously read the question "Clustering with K-Means and EM: how are they related?", but it still doesn't make sense.

I fully understand the K-Means algorithm as such:

Steps:

1. Make an initial guess for the centroid positions of K clusters

2. Repeat until convergence {
    Expectation: Assign each data point to the nearest cluster centroid
    Maximization: Recompute the position of each cluster's centroid
   }

I also understand the EM algorithm from this question and this paper to be:

Variables:
i. Latent variables
ii. Parameters theta of an assumed model

Steps:

1. Guess theta

2. Repeat until convergence {
    Expectation: Compute distribution over latent variables
                  using current theta
    Maximization: Use MLE formulas to compute new theta from
                  latent variable distribution
   }

So my specific questions relate to how Lloyd's K-Means algorithm fits in the EM framework:

A. What is the "latent variable" in K-means? Is it the assignment of the data points to the clusters?

B. What are the parameters "theta" that we are trying to compute in K-Means?

C. In the maximization step for K-Means, which MLE formula and what model are we using to recompute theta? I understand that we recompute the centroids as if they are the "center of mass" of all the data points in a given cluster, but what kind of "model" is that?

Answer 1

The mean is the MLE of the center. The parametes theta are the position of the cluster center.

This part of k-means is why it does not work with other distance functions.

Answer 2

A. What is the "latent variable" in K-means? Is it the assignment of the data points to the clusters?

The latent variables in K-means are discrete, and you can just paraphrase "Assign each data point to the nearest cluster centroid" as "Compute one hot over latent variables (for each sample) using current cluster centroid."

B. What are the parameters "theta" that we are trying to compute in K-Means?

"theta" represents the centroid(only mean, no variance), and you can also rephrase "Recompute the position of each cluster's centroid" as "Use the averaging to compute new centroid from categorical one hots (in each of the k categories)".

C. In the maximization step for K-Means, which MLE formula and what model are we using to recompute theta? I understand that we recompute the centroids as if they are the "center of mass" of all the data points in a given cluster, but what kind of "model" is that?

The formula of the expectation(assign each data point to the closest cluster center using a hard assignment) is

$$z_n^{(t)}=\text{arg max}_k(x_n-\mu_k^{(t)})^T\Sigma_k^{-1(t)}(x_n-\mu^{(t)})$$

And for the maximization(set $\mu_k$ equal to the mean of all data points assigned to cluster $k$) step it is:

$$\hat \mu_k=\text{arg max}\langle l_c(\theta)\rangle \Rightarrow \mu_k^{(t+1)}=\frac{\sum_n \delta(z_n^{(t)}, k)x_n}{\sum_n \delta(z_n^{(t)}, k)}$$