Model-Based Clustering and the EM Algorithm

Clustering as fitting a mixture model by maximum likelihood. The mixture likelihood, the EM algorithm derived from a lower bound with the proof that the likelihood never decreases, Gaussian and Bernoulli mixtures, k-means as the limit of a spherical Gaussian mixture whose variance goes to zero, and what EM does not guarantee, computed on six points, eleven documents and Reuters.

K-means gave each of its six points $A$ to $F$ wholly to one of two clusters. From the seeds $A$ and $B$ it sent $C = (3, 4)$ to the second cluster, although $C$ lies between the two groups. How can a clustering say that a point belongs mostly to one cluster and partly to another, and what would such a clustering be optimizing? It can treat each cluster as a probability distribution and the data as draws from a mixture of them. Then the parameters are chosen to make the observed data as probable as possible, and each point's memberships are the probabilities that each cluster produced it.

Model-based clustering assumes the data were generated by a probabilistic model with one component per cluster and recovers the model from the data. The fitted model defines the clusters. The standard fitting method is the expectation-maximization (EM) algorithm of Dempster, Laird, and Rubin (1977). Its result is a soft clustering: every document has a degree of membership in every cluster. This article is the home of the EM algorithm on this site. The fit of the 2-Poisson model used it earlier, and probabilistic latent semantic analysis applies the same bound to a different model.

Here is the route. First we write down the mixture model and its likelihood. Then we derive EM in full: a lower bound from Jensen's inequality, the E step that makes the bound tight, the M step that raises it, and the proof that the likelihood never decreases. Next we show exactly in what sense k-means is a limit of EM. Then we fit the document model of Manning, Raghavan, and Schütze (2008, §16.5) to eleven small documents and to Reuters. Finally we list what EM does not guarantee. The article assumes the k-means algorithm and the Bernoulli document model of the Bernoulli model.

The mixture model

A mixture model with $K$ components generates each data item in two steps:

  1. choose a component $k$ with probability $\alpha_k$, where the mixing weights $\alpha_1, \dots, \alpha_K$ are positive and sum to 1;
  2. draw the item $x$ from that component's distribution $p(x \mid \theta_k)$, where $\theta_k$ holds the component's parameters.

We observe the items but not the components that produced them. Write $\Theta$ for all the parameters together. The probability (or density) of one item is a weighted sum over the components that could have produced it:

$$p(x \mid \Theta) = \sum_{k=1}^{K} \alpha_k\, p(x \mid \theta_k).$$

For $N$ items $x_1, \dots, x_N$ drawn independently, the log-likelihood is

$$L(\Theta) = \sum_{n=1}^{N} \log \sum_{k=1}^{K} \alpha_k\, p(x_n \mid \theta_k).$$

Maximum likelihood chooses the $\Theta$ that maximizes $L$, the same criterion that trained Naive Bayes. There the class of every training document was known, so the likelihood was a product of single terms and the best parameters were relative frequencies. Here the logarithm sits outside a sum. Setting the derivatives of $L$ to zero gives equations in which every parameter appears inside every term, with no closed-form solution. EM gets around this.

Two component families are used in this article.

  • Spherical Gaussian. The item is a vector $\vec{x}$ in $M$ dimensions, and component $k$ has a mean $\vec{\mu}_k$ and a variance $\sigma_k^2$ shared by all coordinates:

$$p(\vec{x} \mid \theta_k) = (2\pi\sigma_k^2)^{-M/2} \exp\!\Big(-\frac{\lvert \vec{x} - \vec{\mu}_k \rvert^2}{2\sigma_k^2}\Big).$$

  • Multivariate Bernoulli. The item is a document, recorded as $x_m = 1$ if term $m$ occurs in it and $x_m = 0$ if not. Component $k$ has one parameter per term, $q_{mk}$, the probability that a document of cluster $k$ contains term $m$:

$$p(x \mid \theta_k) = \prod_{m=1}^{M} q_{mk}^{\,x_m} (1 - q_{mk})^{1 - x_m}.$$

Given the parameters, Bayes' rule gives the probability that component $k$ produced item $x_n$. It is called the responsibility of component $k$ for item $n$:

$$r_{nk} = \frac{\alpha_k\, p(x_n \mid \theta_k)}{\sum_{j=1}^{K} \alpha_j\, p(x_n \mid \theta_j)}.$$

The responsibilities of one item are positive and sum to 1. They are the soft assignment.

Example (the responsibility of C). With two spherical Gaussians of variance 1 centered on the seeds $A = (1, 1)$ and $B = (1.5, 2)$ and equal weights, the first component's responsibility for $C$ is 0.033. The squared distances from $C$ are 13 and 6.25. The factors $\alpha_k$ and $(2\pi)^{-1}$ are the same for both components and cancel, leaving

$$r_{C1} = \frac{e^{-13/2}}{e^{-13/2} + e^{-6.25/2}} = \frac{1}{1 + e^{3.375}} = 0.033.$$

K-means would report only that $C$ is nearer $B$. The mixture reports how much nearer, on a scale set by the variance.

The EM algorithm

EM alternates two steps. The E step computes the responsibilities from the current parameters. The M step re-estimates the parameters as if each item belonged to each cluster with a fractional weight equal to its responsibility. The next four subsections derive both steps and prove that each pass cannot lower $L$.

A lower bound from Jensen's inequality

Here is the idea in one sentence. We cannot maximize $L$ directly, so we build a function that lies below $L$ everywhere, touches it at the current parameters, and is easy to maximize.

Jensen's inequality for the logarithm. Let $w_1, \dots, w_K$ be nonnegative weights that sum to 1 and $a_1, \dots, a_K$ positive numbers. Then

$$\log \sum_{k} w_k a_k \;\ge\; \sum_{k} w_k \log a_k,$$

with equality exactly when all $a_k$ with $w_k > 0$ are equal.

Proof. For $t > 0$, $\log t \le t - 1$, with equality only at $t = 1$. To see this, let $f(t) = t - 1 - \log t$. Then $f'(t) = 1 - 1/t$ is negative for $t < 1$ and positive for $t > 1$, so $f$ has its only minimum at $t = 1$, where $f(1) = 0$. Now write $\bar{a} = \sum_k w_k a_k$ and apply the inequality to $t = a_k / \bar{a}$:

$$\sum_k w_k \log a_k - \log \bar{a} = \sum_k w_k \log \frac{a_k}{\bar{a}} \le \sum_k w_k \Big( \frac{a_k}{\bar{a}} - 1 \Big) = \frac{\bar{a}}{\bar{a}} - 1 = 0.$$

Equality requires $a_k / \bar{a} = 1$ for every $k$ with $w_k > 0$. $\blacksquare$

The bound. For each item $n$, let $w_{n1}, \dots, w_{nK}$ be any positive weights that sum to 1. Multiply and divide each term of the inner sum of $L$ by $w_{nk}$ and apply Jensen's inequality with $a_k = \alpha_k\, p(x_n \mid \theta_k) / w_{nk}$:

$$L(\Theta) = \sum_n \log \sum_k w_{nk}\, \frac{\alpha_k\, p(x_n \mid \theta_k)}{w_{nk}} \;\ge\; \sum_n \sum_k w_{nk} \log \frac{\alpha_k\, p(x_n \mid \theta_k)}{w_{nk}} \;=\; F(w, \Theta).$$

So $F(w, \Theta) \le L(\Theta)$ for every choice of the weights $w$ and every $\Theta$. If some $w_{nk}$ is zero, drop that term from both sums. The first sum then covers only part of $p(x_n \mid \Theta)$, so the inequality still holds.

The E step makes the bound tight

Fix the parameters at their current values $\Theta^{\text{old}}$. By the equality case of Jensen's inequality, $F(w, \Theta^{\text{old}}) = L(\Theta^{\text{old}})$ exactly when, for each $n$, the ratio $\alpha_k\, p(x_n \mid \theta_k) / w_{nk}$ is the same for every $k$. That makes $w_{nk}$ proportional to $\alpha_k\, p(x_n \mid \theta_k)$. Since the weights sum to 1, they are the responsibilities:

$$w_{nk} = r_{nk} = \frac{\alpha_k\, p(x_n \mid \theta_k)}{\sum_j \alpha_j\, p(x_n \mid \theta_j)} \quad \text{computed at } \Theta^{\text{old}}.$$

If a responsibility is zero, the term dropped from the first sum, $\alpha_k\, p(x_n \mid \theta_k)$, is itself zero. Nothing is lost, and the bound is still tight.

The same fact can be read from an identity. Since $\alpha_k\, p(x_n \mid \theta_k) = r_{nk}(\Theta)\, p(x_n \mid \Theta)$, where $r_{nk}(\Theta)$ is the responsibility computed at $\Theta$,

$$F(w, \Theta) = \sum_n \sum_k w_{nk} \Big[ \log p(x_n \mid \Theta) + \log \frac{r_{nk}(\Theta)}{w_{nk}} \Big] = L(\Theta) - \sum_n \sum_k w_{nk} \log \frac{w_{nk}}{r_{nk}(\Theta)}.$$

The subtracted double sum is nonnegative by Jensen's inequality and zero exactly when $w = r(\Theta)$. For each item it is the Kullback-Leibler divergence from the weights to the responsibilities.

The M step raises the bound

Now hold the weights fixed at $r$, the responsibilities computed at $\Theta^{\text{old}}$, and maximize $F(r, \Theta)$ over $\Theta$. Split the logarithm:

$$F(r, \Theta) = \underbrace{\sum_n \sum_k r_{nk} \big[ \log \alpha_k + \log p(x_n \mid \theta_k) \big]}_{Q(\Theta)} \;-\; \sum_n \sum_k r_{nk} \log r_{nk}.$$

The last sum does not involve $\Theta$. So the M step maximizes $Q(\Theta)$, which is called the expected complete-data log-likelihood. The name comes from this reading. If the component $z_n$ that produced each item were observed, the log-likelihood of the complete data would be $\sum_n [\log \alpha_{z_n} + \log p(x_n \mid \theta_{z_n})]$. $Q$ is its expectation when each $z_n$ equals $k$ with probability $r_{nk}$.

In $Q$ the logarithm acts on single factors, so the parameters separate. Write $N_k = \sum_n r_{nk}$ for the effective size of cluster $k$. The sizes sum to $N$. One lemma handles every parameter that is a probability.

Lemma (weighted counts). Let $c_1, \dots, c_J \ge 0$ with total $c > 0$. Over all probability distributions $(p_1, \dots, p_J)$, the sum $\sum_j c_j \log p_j$ is largest at $p_j = c_j / c$ and nowhere else.

Proof. Let $p$ be any distribution, and sum over the $j$ with $c_j > 0$. Using $\log t \le t - 1$,

$$\sum_j c_j \log p_j - \sum_j c_j \log \frac{c_j}{c} = \sum_j c_j \log \frac{c\, p_j}{c_j} \le \sum_j c_j \Big( \frac{c\, p_j}{c_j} - 1 \Big) = c \sum_j p_j - c \le 0.$$

Equality needs $c\, p_j / c_j = 1$ for every $j$ with $c_j > 0$. $\blacksquare$

Mixing weights. The weights enter $Q$ through $\sum_k N_k \log \alpha_k$. By the lemma, the maximum is at

$$\alpha_k = \frac{N_k}{N}.$$

Bernoulli parameters. Parameter $q_{mk}$ enters $Q$ through $a \log q_{mk} + b \log(1 - q_{mk})$, with $a = \sum_n r_{nk} x_{nm}$ and $b = N_k - a$. That is the lemma with two outcomes, so

$$q_{mk} = \frac{\sum_n r_{nk}\, x_{nm}}{N_k}.$$

This is the fraction of cluster $k$'s documents that contain term $m$, with each document counted by its responsibility. It is the estimate of Bernoulli Naive Bayes with fractional counts, as Manning, Raghavan, and Schütze (2008, §16.5) observe.

Gaussian means. The means enter $Q$ through $-\sum_k \frac{1}{2\sigma_k^2} \sum_n r_{nk} \lvert \vec{x}_n - \vec{\mu}_k \rvert^2$, so each mean must minimize a weighted sum of squared distances. Let $\vec{m}_k = \frac{1}{N_k} \sum_n r_{nk}\, \vec{x}_n$ be the weighted mean. For any point $\vec{v}$, expand around $\vec{m}_k$ as in the k-means update step:

$$\sum_n r_{nk} \lvert \vec{x}_n - \vec{v} \rvert^2 = \sum_n r_{nk} \lvert \vec{x}_n - \vec{m}_k \rvert^2 + 2 (\vec{m}_k - \vec{v}) \cdot \sum_n r_{nk} (\vec{x}_n - \vec{m}_k) + N_k \lvert \vec{m}_k - \vec{v} \rvert^2.$$

The middle term is zero because $\sum_n r_{nk} \vec{x}_n = N_k \vec{m}_k$. The last term is zero only at $\vec{v} = \vec{m}_k$. So

$$\vec{\mu}_k = \frac{1}{N_k} \sum_n r_{nk}\, \vec{x}_n.$$

Gaussian variances. With the means at their new values, let $S_k = \sum_n r_{nk} \lvert \vec{x}_n - \vec{\mu}_k \rvert^2$. The variance of component $k$ enters $Q$ through $g(s) = -\frac{M N_k}{2} \log s - \frac{S_k}{2s}$ with $s = \sigma_k^2$. Its derivative $g'(s) = -\frac{M N_k}{2s} + \frac{S_k}{2s^2}$ is positive for $s < S_k / (M N_k)$ and negative beyond, so

$$\sigma_k^2 = \frac{S_k}{M N_k}.$$

The weighted sum of squares is smallest at the same $\vec{\mu}_k$ whatever $\sigma_k^2$ is, so fixing the means first and then the variance gives the joint maximum of $Q$. The formula needs $S_k > 0$. If the whole weight of component $k$ lies on one point, $S_k = 0$, $g$ grows without bound as $s \to 0$, and the M step has no maximizer. That is the collapse described under "An unbounded likelihood" below.

If all components must share one variance, the same argument applied to the sum over $k$ gives $\sigma^2 = \sum_k S_k / (MN)$. If the variance is held fixed, this update is skipped.

The likelihood never decreases

Theorem. Let $\Theta^{\text{new}}$ be the result of one E step and one M step from $\Theta^{\text{old}}$. Then $L(\Theta^{\text{new}}) \ge L(\Theta^{\text{old}})$.

Proof. Let $r$ be the responsibilities at $\Theta^{\text{old}}$. Then

$$L(\Theta^{\text{new}}) \;\ge\; F(r, \Theta^{\text{new}}) \;\ge\; F(r, \Theta^{\text{old}}) \;=\; L(\Theta^{\text{old}}).$$

The first inequality is the lower bound, which holds for any weights. The second holds because the M step chose $\Theta^{\text{new}}$ to maximize $F(r, \cdot)$. The equality is the E step. $\blacksquare$

Two remarks follow from the proof. First, the M step does not have to maximize $F$. Any step that does not lower it keeps the chain of inequalities, which is what allows partial M steps. Second, if $L(\Theta^{\text{new}}) = L(\Theta^{\text{old}})$, then $\Theta^{\text{old}}$ already maximized $F(r, \cdot)$. With the M steps above the maximizer is unique, so the parameters did not move. Dempster, Laird, and Rubin (1977) proved the monotone increase for the general case of data with missing parts, of which a mixture is one instance.

One iteration on the six points

Back to the six points of the k-means algorithm, with $K = 2$, both variances held at 1, equal starting weights, and starting means at the seeds $A$ and $B$. The E step gives each point's responsibility for the first component from its squared distances $d_1$ and $d_2$, as $1 / (1 + e^{(d_1 - d_2)/2})$:

Point $d_1$ $d_2$ $r_{n1}$ $r_{n2}$
A 0 1.25 0.6514 0.3486
B 1.25 0 0.3486 0.6514
C 13 6.25 0.0331 0.9669
D 52 37.25 0.0006 0.9994
E 22.25 13 0.0097 0.9903
F 28.25 18 0.0059 0.9941

The effective sizes are the column sums, $N_1 = 1.0493$ and $N_2 = 4.9507$. The M step gives weights $\alpha_1 = 1.0493 / 6 = 0.1749$ and $\alpha_2 = 0.8251$, and the weighted means $\vec{\mu}_1 = (1.274, 1.490)$ and $\vec{\mu}_2 = (3.467, 4.532)$. Compare k-means from the same seeds. Its first update left the first centroid at $A$ and moved the second to $(3.5, 4.6)$. Here the first mean has already moved toward $B$, because $B$ gives it a third of its weight.

The log-likelihood rose from $-51.53$ to $-20.79$ in this iteration. Continuing, it rises at every iteration and stops changing after ten, at $-18.77$. The fitted means are $(1.266, 1.523)$ and $(4.004, 5.255)$, close to the centroids $(1.25, 1.5)$ and $(4, 5.25)$ of the best k-means clustering. The weights are 0.336 and 0.664. Point $C$ ends with responsibility 0.019 for the first component, and every other point is closer to 0 or 1 than that.

K-means as a limit of EM

A common summary is "k-means is a special case of EM". The precise statement is narrower, and it is a statement about a limit.

The model. A mixture of $K$ spherical Gaussians that all share one variance $\sigma^2$, where $\sigma^2$ is held fixed and not fitted. The means are fitted. The weights may be fitted or fixed, as long as they are positive. Write $d_{nk} = \lvert \vec{x}_n - \vec{\mu}_k \rvert^2$.

Here is the plan. We show three things as $\sigma^2 \to 0$ with the means and weights held at any fixed values. The E step turns into the k-means assignment step. The M step for the means is then the k-means update step. And the log-likelihood, suitably scaled, turns into the residual sum of squares.

The E step. Dividing the numerator and denominator of $r_{nk}$ by $\alpha_k e^{-d_{nk}/2\sigma^2}$,

$$r_{nk} = \frac{\alpha_k e^{-d_{nk}/2\sigma^2}}{\sum_j \alpha_j e^{-d_{nj}/2\sigma^2}} = \frac{1}{1 + \sum_{j \ne k} \frac{\alpha_j}{\alpha_k} \exp\!\big( -\frac{d_{nj} - d_{nk}}{2\sigma^2} \big)}.$$

Suppose mean $k$ is the unique nearest mean to $\vec{x}_n$. Then every $d_{nj} - d_{nk}$ is positive, every exponential tends to 0 as $\sigma^2 \to 0$, and $r_{nk} \to 1$. The other responsibilities of that point sum to $1 - r_{nk}$ and tend to 0. So the soft assignment tends to the hard assignment to the nearest mean. If several means tie for nearest, the exponentials for the tied means equal 1 for every $\sigma^2$. The point's responsibility is then split among the tied means in proportion to their weights, and the limit is not a hard assignment.

The M step. With responsibilities of 0 and 1, $N_k$ is the number of points assigned to cluster $k$ and $\vec{\mu}_k = \frac{1}{N_k} \sum_n r_{nk} \vec{x}_n$ is their mean. That is the centroid update. So when no point is tied and no cluster is empty, one EM iteration from given means tends to one iteration of Lloyd's algorithm from the same means.

The objective. Define $G(\Theta) = -2\sigma^2 \sum_n \log \sum_k \alpha_k e^{-d_{nk}/2\sigma^2}$. Then

$$L(\Theta) = -\frac{NM}{2} \log(2\pi\sigma^2) - \frac{G(\Theta)}{2\sigma^2},$$

so at fixed $\sigma^2$, maximizing $L$ is minimizing $G$. Let $d_n^{*} = \min_k d_{nk}$ and let $\alpha_{\min}$ be the smallest weight. Every term of the inner sum is at most $\alpha_k e^{-d_n^{*}/2\sigma^2}$, and the weights sum to 1. The term of the nearest mean alone is at least $\alpha_{\min} e^{-d_n^{*}/2\sigma^2}$. Therefore

$$\alpha_{\min}\, e^{-d_n^{*}/2\sigma^2} \;\le\; \sum_k \alpha_k e^{-d_{nk}/2\sigma^2} \;\le\; e^{-d_n^{*}/2\sigma^2}.$$

Taking $-2\sigma^2 \log$ of all three and summing over $n$,

$$\sum_n d_n^{*} \;\le\; G(\Theta) \;\le\; \sum_n d_n^{*} + 2 N \sigma^2 \log \frac{1}{\alpha_{\min}}.$$

The left side is the sum of squared distances from each point to its nearest mean. That is the RSS of the means with the best assignment, the quantity k-means minimizes. So $G$ tends to it as $\sigma^2 \to 0$, uniformly in the means when the weights are fixed. Manning, Raghavan, and Schütze (2008, §16.4.1, §16.5) state the equivalence of minimal RSS and maximum likelihood for the hard-assignment version of this model, in which each point is charged to one component only. Its log-likelihood is exactly $-\mathrm{RSS}/2\sigma^2$ plus a constant, at any variance. The bound above says in what sense the equivalence also holds for the soft mixture: in the limit (Bishop, 2006, chapter 9).

The limit checked on the six points. Take the centroids of Lloyd's second iteration, $(1, 1)$ and $(3.5, 4.6)$. Point $B$ is at squared distances 1.25 and 10.76 from them. Its responsibility for the first component is 0.629 at $\sigma^2 = 9$, 0.767 at $\sigma^2 = 4$, 0.991 at $\sigma^2 = 1$ and 1.000 at $\sigma^2 = 0.25$. With $\sigma^2 = 0.01$, the EM means from the seeds $A$ and $B$ agree with Lloyd's centroids at every iteration to within $10^{-6}$. At the final centroids with equal weights, the bound above reads $7.875 \le G \le 7.875 + 8.32\,\sigma^2$, and the script finds

$\sigma^2$ 1 0.1 0.01 0.001 0.0001
$G$ 16.12 8.71 7.958 7.883 7.876

approaching the RSS of 7.875.

Example (a common misstatement). The statement "k-means is EM with hard assignments" is true only in the limit just described. Three things separate the two at any positive variance. EM for this model never assigns a point wholly to one cluster. A tied point stays shared, as $C$ does between means at $A$ and $D$, where its responsibility equals the mixing weight for every $\sigma^2$. And if the variance is fitted instead of fixed, the algorithm is not k-means in any limit: on the six points it settles at $\sigma^2 = 0.658$ from all 15 seed pairs.

The other direction is also instructive. With a large fixed variance the assignments become so soft that the clusters merge. At $\sigma^2 = 9$, EM from the seeds $A$ and $B$ moves both means to $(3.083, 4)$, the mean of all six points. At $\sigma^2 = 4$ the means stay apart, at $(1.732, 2.157)$ and $(3.868, 5.070)$, and $C$ has responsibility 0.282 for the first. These are results of this run on these six points.

Documents: the Bernoulli mixture

For documents, Manning, Raghavan, and Schütze (2008, §16.5) use the multivariate Bernoulli components defined above. The E step is then Bernoulli Naive Bayes classification with the clusters as classes, normalized to give probabilities. The M step is Bernoulli Naive Bayes training with fractional counts. Their example has eleven documents over 18 distinct terms:

Doc Text Doc Text
1 hot chocolate cocoa beans 7 sweet sugar
2 cocoa ghana africa 8 sugar cane brazil
3 beans harvest ghana 9 sweet sugar beet
4 cocoa butter 10 sweet cake icing
5 butter truffles 11 cake black forest
6 sweet chocolate

The text seeds cluster 1 with document 6 and cluster 2 with document 7. The first computed column of its Table 16.3 has documents 1 and 6 in cluster 1, documents 7, 8 and 9 in cluster 2, and the other six split evenly. We start from that column. Like the text, we add $\epsilon = 0.0001$ to every responsibility in the M step. The table follows five documents; $\alpha_1$ is the weight used in that iteration's E step.

Iteration $\alpha_1$ $r_{2,1}$ $r_{5,1}$ $r_{6,1}$ $r_{10,1}$ $r_{11,1}$ $L$
2 0.45 0.79 0.52 1.00 0.40 0.57 $-74.54$
3 0.53 0.99 0.66 1.00 0.14 0.58 $-71.58$
4 0.57 1.00 0.91 1.00 0.01 0.41 $-68.98$
5 0.58 1.00 1.00 1.00 0.00 0.07 $-67.34$
7 0.55 1.00 1.00 0.99 0.00 0.00 $-65.64$
14 0.53 1.00 1.00 0.78 0.00 0.00 $-65.54$
17 0.48 1.00 1.00 0.08 0.00 0.00 $-64.68$
20 0.45 1.00 1.00 0.00 0.00 0.00 $-64.27$

The run has three phases. In five iterations the cocoa documents gather in cluster 1 and the sugar documents in cluster 2. Then comes a long flat stretch in which only document 6, sweet chocolate, is in doubt. Finally document 6 crosses to cluster 2, and the run settles on documents 1 to 5 against documents 6 to 11. Our values agree with every printed digit of the text's table at iterations 2 to 5 and 25, except one parameter in the third decimal (0.639 against 0.640). The text's column for iteration 15 falls between our iterations 13 and 14. On the flat stretch the timing depends on small details of the arithmetic.

Smoothing is doing real work here. Run the same start without $\epsilon$, which is the exact EM of the derivation. It stops after eight iterations with documents 1 to 6 against 7 to 11, at $L = -65.64$, lower than the $-64.27$ of the smoothed run. The reason is a zero. The starting column gives both documents that contain chocolate, 1 and 6, wholly to cluster 1, so the first M step already sets $q_{\text{chocolate},2} = 0$. Then document 6 has probability zero under cluster 2, its responsibility $r_{6,2}$ is exactly zero, and the next M step leaves the parameter at zero. Exact EM can never leave such a point.

The proof above is not contradicted: the likelihood did not decrease. But the stopping point is not a maximum, nor even a stationary point. It lies on the boundary of the parameter space, and the likelihood rises as soon as the parameter leaves zero. To see it, hold every other parameter at its value there and raise $q_{\text{chocolate},2}$ from 0 to a small $\eta$. Document 6 gains the probability $\alpha_2\, \eta\, \tilde{P}_2$, where $\tilde{P}_2$ is the product of its other cluster-2 factors, on top of its cluster-1 probability $\alpha_1 P_1$. Each of the five documents of cluster 2, none of which contains chocolate, has its probability multiplied by $1 - \eta$. Documents 1 to 5 have probability zero under cluster 2 for other reasons and are unaffected. So

$$\frac{dL}{d\eta}\Big|_{\eta = 0} = \frac{\alpha_2 \tilde{P}_2}{\alpha_1 P_1} - 5 = 7.93 - 5 = 2.93 > 0.$$

Exact EM cannot take that step, because every update of the parameter multiplies by the zero responsibility.

The smoothed M step is not the maximizer of $F$, so the theorem does not cover it. In this run the log-likelihood still rose at every iteration, which is an observation, not a guarantee.

Add-one smoothing keeps the guarantee. A standard alternative is the estimate of Bernoulli Naive Bayes with add-one smoothing,

$$q_{mk} = \frac{\sum_n r_{nk}\, x_{nm} + 1}{N_k + 2}.$$

This is an exact M step for a different objective. Add to $L$ the penalty $\sum_{m,k} [\log q_{mk} + \log(1 - q_{mk})]$, which is the logarithm of a prior density proportional to $q(1-q)$ on each parameter. The penalty does not involve the weights $w$, so $F$ plus the penalty is a lower bound on $L$ plus the penalty, tight at the same E step. In the M step, $q_{mk}$ now enters through $(a + 1) \log q_{mk} + (b + 1) \log(1 - q_{mk})$, and the lemma gives the formula above. The chain of inequalities then shows that the penalized log-likelihood never decreases. No parameter can reach 0 or 1, so no document is ever locked out of a cluster.

Reuters: the mixture against k-means

The unit's running collection is the 7,487 Reuters stories in six categories from K-means in practice, with the same 3,000 terms. For the mixture, each story is reduced to which terms it contains, 41.8 distinct terms on average. We fitted a Bernoulli mixture with $K = 6$ by EM with add-one smoothing, from 30 seeded random soft assignments. Each run stopped when the penalized log-likelihood rose by less than one part in $10^9$. The script asserts that it never fell. Every story was then given to its cluster of highest responsibility and the result graded against the categories with the measures that evaluating clusterings and clustering measures corrected for chance define. The k-means column repeats the 30 random-seed runs on TF-IDF vectors from that article. Values are medians with interquartile ranges.

Measure K-means on TF-IDF vectors Bernoulli mixture by EM
Purity 0.784 (0.740 to 0.803) 0.773 (0.762 to 0.784)
NMI 0.459 (0.401 to 0.509) 0.418 (0.393 to 0.440)
Rand index 0.703 (0.662 to 0.737) 0.772 (0.756 to 0.779)
Adjusted Rand index 0.305 (0.215 to 0.395) 0.495 (0.435 to 0.504)
Iterations 28.5 (21 to 39) 114.5 (78 to 153)

Four things stand out, all of them observations on this collection.

  • The measures disagree about the winner. The mixture has the lower purity and NMI and the higher Rand index and adjusted Rand index. The two methods also use different document representations, so the table compares two pipelines, not only two algorithms.
  • The soft clustering is nearly hard. Over the 30 runs, the median share of stories with a responsibility above 0.99 for one cluster is 96.7 percent (interquartile range 96.5 to 96.9). A document's likelihood is a product of 3,000 factors, so the ratio between two clusters is usually enormous, and Bayes' rule turns it into a probability near 0 or 1. The text's remark that its eleven-document example ends hard "somewhat atypically" does not carry over to this model at this size.
  • Every run stopped somewhere different. The 30 runs ended at 30 distinct log-likelihoods, from $-1{,}063{,}317$ to $-1{,}051{,}200$. EM took about four times as many iterations as k-means.
  • A higher likelihood did not mean better agreement with the categories. Over the 30 runs the rank correlation between log-likelihood and NMI is $-0.12$ (two-sided $p = 0.52$). That is no detectable relation, and not the positive one that "a higher likelihood is better" would predict. K-means in practice found a clearer version of the same warning for RSS over 300 runs.

What EM does not guarantee

The theorem promises that the likelihood does not fall. It promises nothing more, and three limits matter in practice.

Local maxima. Different starts end at different likelihoods. On the eleven documents, exact EM from 30 random soft starts ended at 20 distinct log-likelihoods between $-72.38$ and $-64.27$. Seven runs reached $-64.27$, the clustering of documents 1 to 5 against 6 to 11. The median run ended at $-67.04$. The usual remedies are those of k-means: several starts, keeping the highest likelihood, or a start from another algorithm's clustering. The text recommends a k-means clustering as the start, which EM then softens.

Stopping points that are not maxima. The exact run on the eleven documents stopped at $-65.64$ at a point on the boundary of the parameter space, where a zero parameter blocks the direction in which the likelihood increases. That point is neither a local maximum nor a stationary point, as the derivative computed above shows. Away from the boundary the guarantee is also limited. Under regularity conditions, which include that the iterates stay in the interior of the parameter space, every limit point of EM is a stationary point of the likelihood, and a stationary point need not be a local maximum (Wu, 1983). The boundary point of the eleven documents falls outside those conditions.

An unbounded likelihood. For Gaussian mixtures in which each component has its own variance, the maximum of the likelihood does not exist. Put the first mean exactly on a data point $\vec{x}_1$ and let its variance $s$ shrink, keeping the second component fixed with positive density everywhere. The density of $\vec{x}_1$ is at least $\alpha_1 (2\pi s)^{-M/2}$, which grows without bound. Every other point keeps a density of at least $\alpha_2$ times that of the second component. So $L \to \infty$ as $s \to 0$ (Bishop, 2006, chapter 9). On the six points, with the first component on $A$ and the second fitted to all six points:

$s$ 1 $10^{-2}$ $10^{-4}$ $10^{-8}$ $10^{-16}$ $10^{-32}$
$L$ $-22.81$ $-19.99$ $-15.39$ $-6.18$ 12.25 49.09

EM can find these degenerate solutions. Fitting a variance per component from each of the 15 seed pairs, with starting variance 1, two runs (seeds $D$, $E$ and seeds $D$, $F$) put one component on $D$ alone and drove its variance toward zero. The other 13 ended at the same finite fit, with $L = -16.74$.

A single shared variance removes the problem whenever the data have more than $K$ distinct points. Then two distinct points share a nearest mean, so one of them is at distance at least $\delta$ from every mean, where $\delta$ is half the smallest distance between distinct points. Its density is at most $(2\pi\sigma^2)^{-M/2} e^{-\delta^2/2\sigma^2}$, and every other density is at most $(2\pi\sigma^2)^{-M/2}$. Hence $L \le -\frac{NM}{2} \log(2\pi\sigma^2) - \frac{\delta^2}{2\sigma^2}$, which is bounded above over all $\sigma^2 > 0$. On the six points all 15 seed pairs reached the same fit, $L = -18.32$ with $\sigma^2 = 0.658$.

Choosing the number of components. The likelihood cannot choose $K$. A mixture with $K + 1$ components can copy any mixture with $K$ by giving the extra component a weight near zero, so the largest attainable likelihood never falls as $K$ grows. The standard criteria subtract a penalty for the number of free parameters, $q(K)$. The Akaike criterion minimizes $-2L + 2q(K)$ (Manning, Raghavan, and Schütze, 2008, §16.4.1), and the Bayesian information criterion minimizes $-2L + q(K) \log N$ (Schwarz, 1978). Both rest on large-sample arguments. Schwarz derived his for independent observations from an exponential family, which a mixture is not. For mixtures the regularity those arguments need also fails where a component's weight reaches 0 or two components coincide, because the parameters are then not identifiable. Both criteria are used for mixtures as heuristics, and the text warns that AIC can rarely be applied to text clustering without modification. This article did not test either criterion on Reuters. One current use of this machinery is in retrieval for language models: RAPTOR clusters passage embeddings with Gaussian mixtures fitted by EM, with the number of components chosen by the Bayesian information criterion (Sarthi et al., 2024).

Worked problems

Problems 1 to 5 are Exercises 16.15, 16.16, 16.17, 16.6 and 16.21 of the course text (Manning, Raghavan, and Schütze, 2008), restated in our own words. Exercises 16.18 and 16.19 of the text, the EM steps for a Gaussian mixture and k-means as a limit, are answered in the body above.

Problem 1 (document 6 changes sides). Document 6 seeded cluster 1 but ends in cluster 2. Explain why it changes membership.

It moves because sweet comes to belong to cluster 2, and because smoothing leaves it a way across. At iteration 7 of the run above, cluster 1 holds documents 1 to 6 and cluster 2 holds documents 7 to 11. The parameters are then $q_{\text{sweet},1} = 0.166$ and $q_{\text{sweet},2} = 0.600$, since three of the five documents of cluster 2 contain sweet and only document 6 does in cluster 1. So sweet argues for cluster 2. Against that, $q_{\text{chocolate},1} = 0.333$ while $q_{\text{chocolate},2}$ is about $8 \times 10^{-4}$, nonzero only because of $\epsilon$. The result is a small responsibility, $r_{6,2} = 0.006$. From there the process feeds itself. A little of document 6 in cluster 2 raises $q_{\text{chocolate},2}$ and $q_{\text{sweet},2}$, which raises $r_{6,2}$ in the next E step. The responsibility $r_{6,1}$ falls from 0.99 at iteration 7 to 0.78 at iteration 14 and 0.08 at iteration 17. Without $\epsilon$ the parameter $q_{\text{chocolate},2}$ is exactly zero and document 6 stays in cluster 1, as the body showed.

Problem 2 (the exact limit). The parameters in the last column of the text's table are rounded. Find the exact values EM converges to.

In the limit the assignment is hard, documents 1 to 5 in cluster 1 and 6 to 11 in cluster 2, and each parameter is a plain fraction of documents, up to corrections of order $\epsilon$. Africa occurs in one of the five documents of cluster 1 and cocoa in three. Brazil occurs in one of the six documents of cluster 2, sugar in three and sweet in four. So

$$q_{\text{africa},1} = \tfrac{1}{5},\quad q_{\text{cocoa},1} = \tfrac{3}{5},\quad q_{\text{brazil},2} = \tfrac{1}{6},\quad q_{\text{sugar},2} = \tfrac{1}{2},\quad q_{\text{sweet},2} = \tfrac{2}{3},\quad \alpha_1 = \tfrac{5}{11},$$

and $q_{\text{africa},2} = q_{\text{cocoa},2} = q_{\text{brazil},1} = q_{\text{sugar},1} = q_{\text{sweet},1} = 0$. The text prints 0.200, 0.600, 0.167, 0.500, 0.667 and 0.45. This hard clustering is a stopping point of exact EM as well: every document contains a term that the other cluster lacks, so its probability under the other cluster is zero. Its log-likelihood is $-64.27$.

Problem 3 (k-means on the same documents). Cluster the eleven documents with k-means. After how many iterations does it converge, and how does the result compare with EM's?

With the documents as 0/1 term vectors and the same seeds, documents 6 and 7, k-means stops at the second assignment step with $\{1, \dots, 6, 10, 11\}$ and $\{7, 8, 9\}$. The squared distance between two such vectors is the number of terms in exactly one of them. In the first assignment step, documents 2, 3, 4, 5, 10 and 11 are equally far from both seeds. For example, document 10 is at squared distance 3 from each, and document 2 at 5 from each. A tie goes to the lower-numbered cluster, so all six join cluster 1. Documents 8 and 9 contain sugar and are nearer document 7. After the update no document changes cluster. The RSS is 19.67.

EM's clustering, documents 1 to 5 against 6 to 11, has RSS 18.80, which is the lowest of all 1,023 ways to split the eleven documents in two. So here the mixture's best fit and the k-means optimum coincide, and k-means from these seeds misses it. The difference is in how the two treat an undecided document. K-means must commit every document in the first step, and six of the eleven are committed by a tie-breaking rule. EM leaves them split evenly and lets later iterations decide. Seeded with documents 1 and 7, k-means stops at $\{1, 2, 3, 4\}$ and the rest, with RSS 19.07.

Problem 4 (the cost of EM). For $I$ iterations, k-means costs $\Theta(IKNM)$. What does EM cost?

The same order, $\Theta(IKNM)$, for the Bernoulli mixture with dense vectors. The E step computes $K$ likelihoods for each of $N$ documents, each a product over $M$ terms: $\Theta(KNM)$. The M step adds each document's vector into each of $K$ parameter vectors with its responsibility: again $\Theta(KNM)$, against $\Theta(NM)$ for the k-means update, where a document touches one centroid. With sparse documents both steps can be made proportional to the number of distinct terms present. The number of iterations is larger in practice: on Reuters the median was 114.5 against 28.5.

Problem 5 (AIC for the Bernoulli mixture). Derive an AIC criterion for the multivariate Bernoulli mixture, and apply it to the eleven documents for one and two clusters.

The criterion is $\min_K [-2L(K) + 2q(K)]$ with $q(K) = KM + K - 1$. Each of the $K$ clusters has $M$ term parameters that vary freely, and the $K$ weights sum to 1, which leaves $K - 1$ free. So

$$\mathrm{AIC}(K) = -2 L(K) + 2 (KM + K - 1),$$

where $L(K)$ is the largest log-likelihood with $K$ clusters. For the eleven documents $M = 18$. With one cluster, each $q_m$ is the fraction of documents containing term $m$, and $L(1) = -79.69$ with $q(1) = 18$: $\mathrm{AIC}(1) = 159.38 + 36 = 195.38$. With two clusters, the best fit found is $L(2) = -64.27$ with $q(2) = 37$: $\mathrm{AIC}(2) = 128.54 + 74 = 202.54$. The criterion prefers one cluster. Eleven documents do not support 37 parameters, however sensible the two clusters look.

What we have learned

Model-based clustering replaces the centroids of k-means with probability distributions and its objective with a likelihood. The EM algorithm maximizes a lower bound that the E step makes tight and the M step raises, so the likelihood never decreases. Its E step is classification by Bayes' rule, and its M step is training with fractional counts. K-means is the limit of EM for spherical Gaussians with one fixed variance as that variance goes to zero: the responsibilities harden, the means become centroids, and the scaled log-likelihood becomes RSS. The guarantee stops at monotonicity. EM ends at local maxima, and on the boundary of the parameter space it can stop at a point that is not even stationary. A Gaussian mixture with free variances has no maximum at all.

On Reuters the mixture and k-means were graded with purity, NMI and the Rand index, and the measures disagreed about which was better. Evaluating clusterings defines each measure and shows what each one rewards. The mixture of this article gives every document one hidden cluster. Probabilistic latent semantic analysis gives every word occurrence its own, and is fitted by the same algorithm.

Every number in this article is computed by tools/experiments/clustering/mixture_em.py in the site repository.

References

  • Bishop, C. M. (2006). Pattern Recognition and Machine Learning, chapter 9. Springer. record · 3 pages
  • Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1), 1–38. record · 3 pages
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 16.4.1 and 16.5. Cambridge University Press. record · 93 pages
  • Sarthi, P., Abdullah, S., Tuli, A., Khanna, S., Goldie, A., and Manning, C. D. (2024). RAPTOR: Recursive abstractive processing for tree-organized retrieval. In Proceedings of the International Conference on Learning Representations (ICLR). record
  • Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statistics, 6(2), 461–464. record · 2 pages
  • Wu, C. F. J. (1983). On the convergence properties of the EM algorithm. The Annals of Statistics, 11(1), 95–103. record