Gaussian Mixture Models

Soft clustering with multivariate normal components fitted by EM. The likelihood proved unbounded and exact EM steps proved never to reach the collapse; the covariance update; affine equivariance, which k-means lacks; k-means and Mahalanobis k-means as small-variance limits; label switching; the number of components by BIC. On 5,176 NHANES adults the best two-component fit splits by build, not by sex, from all 30 starts. Worked problems carry out one EM iteration, show k-means changing with the units, and compare two values of K by BIC.

Of the 5,176 adults examined in the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 who have a blood pressure reading and whose height and weight were both measured (National Center for Health Statistics, 2020), 2,512 are men and 2,664 are women. The men average 173.5 cm and 88.4 kg, the women 159.8 cm and 77.0 kg. Suppose the sex column were lost. A mixture of two bivariate normal distributions, one for each unseen group, is the natural model for such data: could fitting it recover the sexes? On these data it does not. The best two-component fit that EM found, the same from all 30 random starts, divides the adults into a heavier group of about a quarter and a lighter group of three quarters, and agrees with sex for only 54.5% of them, barely better than the 51.5% of calling everyone a woman. The two sexes' own normal distributions fit the data worse, by 402.8 in log-likelihood. This article examines why, and what the mixture does guarantee.

A Gaussian mixture model describes a $p$-dimensional observation as drawn from one of $K$ multivariate normal distributions, the components, chosen at random with probabilities $\alpha_1, \ldots, \alpha_K$. The component that produced each observation is not recorded. Fitting the model by maximum likelihood with the EM algorithm (Dempster, Laird and Rubin, 1977) gives a soft clustering: every observation receives a probability of belonging to each component.

Here is the route. Model-Based Clustering and the EM Algorithm already derives EM for mixtures with spherical components, proves that k-means is its limit for one shared, fixed variance, and shows that free variances make the likelihood unbounded; The EM Algorithm proves monotonicity for any model with missing data. This article takes the general case, in which every component has its own full covariance matrix. First we prove that the likelihood has no maximum, and that EM's exact steps never reach the collapse. Then we derive the covariance update and prove that the fit does not depend on the units of measurement. Next we test the model on the known-truth NHANES data, against k-means, and measure how much the answer depends on the starting point. Then we prove the small-variance limits for general covariance matrices, prove that label switching makes the components indistinguishable in a Bayesian posterior, and choose $K$ by BIC. The article assumes The Multivariate Normal Distribution and the EM algorithm of Model-Based Clustering and the EM Algorithm.

The model and its notation

The unit's notation is kept (Multivariate Statistics). The data are $n$ vectors $\mathbf x_1, \ldots, \mathbf x_n$ in $\mathbb R^p$; $N_p(\boldsymbol\mu, \Sigma)$ is the normal distribution with mean vector $\boldsymbol\mu$ and covariance matrix $\Sigma$ (for $p = 1$ the second argument is the variance), with density $$\varphi(\mathbf x; \boldsymbol\mu, \Sigma) = (2\pi)^{-p/2}(\det\Sigma)^{-1/2}\exp\!\Big(-\tfrac12(\mathbf x - \boldsymbol\mu)^{\mathsf T}\Sigma^{-1}(\mathbf x - \boldsymbol\mu)\Big)$$ for positive definite $\Sigma$ (The Multivariate Normal Distribution, Theorem 4). The mixture has weights $\alpha_k > 0$ summing to 1, means $\boldsymbol\mu_k$ and positive definite covariance matrices $\Sigma_k$, collected in $\theta$. Its density and log-likelihood are $$f(\mathbf x \mid \theta) = \sum_{k=1}^K \alpha_k\,\varphi(\mathbf x; \boldsymbol\mu_k, \Sigma_k), \qquad \ell(\theta) = \sum_{i=1}^n \ln f(\mathbf x_i \mid \theta).$$ The weights are written $\alpha_k$, as in Model-Based Clustering and the EM Algorithm, to keep $\pi$ for the prior of the Bayesian sections. The responsibility of component $k$ for observation $i$ is the posterior probability, by Bayes' rule, that $k$ produced it: $$r_{ik} = \frac{\alpha_k\,\varphi(\mathbf x_i; \boldsymbol\mu_k, \Sigma_k)}{f(\mathbf x_i \mid \theta)}.$$ A mixture with full covariance matrices has $q(K) = (K - 1) + Kp + Kp(p+1)/2$ free parameters: $K - 1$ weights, $K$ means of $p$ entries, and $K$ symmetric matrices of $p(p+1)/2$ distinct entries. For height and weight, $p = 2$ and $q(K) = 6K - 1$.

The likelihood has no maximum

Here is the idea in one sentence. Center a component on one observation and shrink its covariance: the density at that observation grows without bound, while the other components keep every other observation's density away from zero.

Theorem 1 (an unbounded likelihood). Let $K \ge 2$ and $n \ge 1$. Fix components $2, \ldots, K$ with positive weights and positive definite covariance matrices, and fix $\alpha_1 > 0$. Then $\ell(\theta) \to \infty$ as $s \to 0$ in each of two cases:

  1. (collapse onto a point) $\boldsymbol\mu_1 = \mathbf x_1$ and $\Sigma_1 = sI_p$;
  2. (collapse onto a hyperplane) some observations lie in an affine hyperplane $H = \{\mathbf x : \mathbf b^{\mathsf T}\mathbf x = c\}$ with $\lVert \mathbf b \rVert = 1$, $\boldsymbol\mu_1$ lies in $H$, and $\Sigma_1 = \Sigma_1(s) = (I_p - \mathbf b\mathbf b^{\mathsf T}) + s\,\mathbf b\mathbf b^{\mathsf T}$.

In particular the likelihood has no global maximum.

Proof. Part 1. Every term of $f$ is positive, so $f(\mathbf x_1 \mid \theta) \ge \alpha_1\varphi(\mathbf x_1; \mathbf x_1, sI_p) = \alpha_1(2\pi s)^{-p/2}$, and for $i \ge 2$, $f(\mathbf x_i \mid \theta) \ge \alpha_2\varphi(\mathbf x_i; \boldsymbol\mu_2, \Sigma_2)$, which does not depend on $s$. Hence $$\ell(\theta) \ge \ln\alpha_1 - \frac p2\ln(2\pi) - \frac p2\ln s + \sum_{i=2}^n\ln\big(\alpha_2\varphi(\mathbf x_i; \boldsymbol\mu_2, \Sigma_2)\big),$$ and the right side tends to $+\infty$ as $s \to 0$.

Part 2. The matrix $\Sigma_1(s)$ has eigenvalue $s$ along $\mathbf b$ and 1 in every direction orthogonal to it, so $\det\Sigma_1(s) = s$ and $$\Sigma_1(s)^{-1} = (I_p - \mathbf b\mathbf b^{\mathsf T}) + s^{-1}\mathbf b\mathbf b^{\mathsf T}.$$ For an observation $\mathbf x_i$ on $H$, $\mathbf b^{\mathsf T}(\mathbf x_i - \boldsymbol\mu_1) = c - c = 0$, so $(\mathbf x_i - \boldsymbol\mu_1)^{\mathsf T}\Sigma_1(s)^{-1}(\mathbf x_i - \boldsymbol\mu_1) = \lVert \mathbf x_i - \boldsymbol\mu_1 \rVert^2$ for every $s$, and $\varphi(\mathbf x_i; \boldsymbol\mu_1, \Sigma_1(s)) = (2\pi)^{-p/2}s^{-1/2}e^{-\lVert \mathbf x_i - \boldsymbol\mu_1 \rVert^2/2}$, which tends to $\infty$. Bound $f(\mathbf x_i \mid \theta)$ below by $\alpha_1$ times that density for one such observation and by $\alpha_2\varphi(\mathbf x_i; \boldsymbol\mu_2, \Sigma_2)$ for every other observation, as in part 1; the lower bound tends to $+\infty$.

A global maximum would be a finite value that no $\theta$ exceeds. $\square$

The proof needs only one observation, which is why a free variance per component is enough for the trouble; Model-Based Clustering and the EM Algorithm shows it for spherical components. Full covariance matrices allow the second kind of collapse, part 2. One observation always lies on a hyperplane, and any $p$ observations lie on a common one, which is the most that a hyperplane can be made to hold in general. With $p = 2$, a component can collapse onto the line through any two adults.

The collapse on the NHANES data. Put one component, with weight $\tfrac12$, on the first adult in the file (158.3 cm, 79.5 kg) with covariance $sI_2$, and the other, with weight $\tfrac12$, at the single bivariate normal fitted to all 5,176 adults. The log-likelihood is $-45{,}848.2$ at $s = 10^{-2}$, $-45{,}836.4$ at $10^{-8}$, $-45{,}781.2$ at $10^{-32}$, $-45{,}560.1$ at $10^{-128}$ and $-45{,}265.4$ at $10^{-256}$. From $s = 10^{-8}$ on it equals the lower bound of the proof to two decimals, so it rises by $\frac p2 \cdot 8\ln 10 = 18.42$ for every factor of $10^{-8}$. At that rate it passes the best two-component fit found below, $-41{,}810.0$, only near $s = 10^{-1{,}757}$, far below the smallest positive double-precision number. The rise is slow, and no amount of it says anything about the data.

What EM does near the collapse. The singularity is a limit that the exact algorithm cannot reach in a finite number of steps.

Theorem 2 (the exact EM step stays inside). Suppose the observations do not all lie in one affine hyperplane. If every weight is positive and every covariance matrix positive definite, then after one E step and one M step (given in the next section) the same is true.

Proof. The E step gives positive responsibilities: each $r_{ik}$ is a ratio of positive numbers, because a normal density with a positive definite covariance is positive everywhere. So $N_k = \sum_i r_{ik} > 0$, and the new weight $N_k/n$ is positive. The new covariance is $A_k/N_k$ with $A_k = \sum_i r_{ik}(\mathbf x_i - \mathbf m_k)(\mathbf x_i - \mathbf m_k)^{\mathsf T}$, where $\mathbf m_k$ is the weighted mean. For any vector $\mathbf v \ne \mathbf 0$, $\mathbf v^{\mathsf T}A_k\mathbf v = \sum_i r_{ik}\big(\mathbf v^{\mathsf T}(\mathbf x_i - \mathbf m_k)\big)^2 \ge 0$, and since every $r_{ik} > 0$ it is 0 only if $\mathbf v^{\mathsf T}\mathbf x_i = \mathbf v^{\mathsf T}\mathbf m_k$ for every $i$, that is, if all observations lie in the hyperplane $\{\mathbf x : \mathbf v^{\mathsf T}\mathbf x = \mathbf v^{\mathsf T}\mathbf m_k\}$. By assumption they do not, so $A_k$ is positive definite. $\square$

So every iterate has a finite likelihood, and the collapse can only be approached, with a covariance whose smallest eigenvalue shrinks toward zero over many iterations. Software therefore watches for small eigenvalues or small weights. The script of this article stops a run as degenerate when a covariance matrix has an eigenvalue below $10^{-8}$ or a weight below 2.5 observations' worth; no run on the NHANES data, for any $K$ from 1 to 6, triggered either test (the script asserts it). The theory of maximum likelihood for mixtures turns to local maxima or to constrained ones instead. Hathaway (1985) reformulated estimation for univariate normal mixtures "using simple constraints" (his abstract) so that the problem has a strongly consistent global solution; Redner and Walker (1984) survey maximum likelihood and EM for mixture densities.

The EM updates

EM alternates a step that computes the responsibilities from the current parameters with a step that refits each component to the data weighted by its responsibilities. Model-Based Clustering and the EM Algorithm derives both steps for spherical components and proves that each iteration cannot lower the likelihood; The EM Algorithm proves the same for any model with missing data (its Theorem 1), whenever the M step does not lower the expected complete-data log-likelihood $$Q(\theta) = \sum_{i=1}^n\sum_{k=1}^K r_{ik}\Big[\ln\alpha_k - \frac p2\ln(2\pi) - \frac12\ln\det\Sigma_k - \frac12(\mathbf x_i - \boldsymbol\mu_k)^{\mathsf T}\Sigma_k^{-1}(\mathbf x_i - \boldsymbol\mu_k)\Big],$$ with the responsibilities held at their values from the E step. Only the covariance step is new here.

Theorem 3 (the M step). Let all $r_{ik} > 0$, put $N_k = \sum_i r_{ik}$ and $\mathbf m_k = N_k^{-1}\sum_i r_{ik}\mathbf x_i$, and suppose the observations do not lie in one affine hyperplane. Then $Q$ has the unique maximizer $$\alpha_k = \frac{N_k}{n}, \qquad \boldsymbol\mu_k = \mathbf m_k, \qquad \Sigma_k = \frac{1}{N_k}\sum_{i=1}^n r_{ik}(\mathbf x_i - \mathbf m_k)(\mathbf x_i - \mathbf m_k)^{\mathsf T}.$$

Proof. The weights enter $Q$ only through $\sum_k N_k\ln\alpha_k$, maximized uniquely at $\alpha_k = N_k/n$ by the weighted-counts lemma of Model-Based Clustering and the EM Algorithm. Component $k$'s mean and covariance enter only through its own term. For any positive definite $\Sigma_k$ and any $\boldsymbol\mu$, expanding around $\mathbf m_k$, $$\sum_i r_{ik}(\mathbf x_i - \boldsymbol\mu)^{\mathsf T}\Sigma_k^{-1}(\mathbf x_i - \boldsymbol\mu) = \sum_i r_{ik}(\mathbf x_i - \mathbf m_k)^{\mathsf T}\Sigma_k^{-1}(\mathbf x_i - \mathbf m_k) + N_k(\mathbf m_k - \boldsymbol\mu)^{\mathsf T}\Sigma_k^{-1}(\mathbf m_k - \boldsymbol\mu),$$ because the cross term is $2(\mathbf m_k - \boldsymbol\mu)^{\mathsf T}\Sigma_k^{-1}\sum_i r_{ik}(\mathbf x_i - \mathbf m_k)$ and $\sum_i r_{ik}(\mathbf x_i - \mathbf m_k) = \mathbf 0$. The last term is positive unless $\boldsymbol\mu = \mathbf m_k$, so the best mean is $\mathbf m_k$ whatever $\Sigma_k$ is. With $\boldsymbol\mu_k = \mathbf m_k$, the term of component $k$ is, up to a constant, $-\frac{N_k}{2}\ln\det\Sigma_k - \frac12\operatorname{tr}(\Sigma_k^{-1}A_k)$, using $\mathbf a^{\mathsf T}M\mathbf a = \operatorname{tr}(M\mathbf a\mathbf a^{\mathsf T})$; here $A_k$ is the weighted scatter matrix of Theorem 2, positive definite by that proof. Lemma 4 of Hotelling's T-Squared Test proves that $-\frac{n}{2}\ln\det\Sigma - \frac12\operatorname{tr}(\Sigma^{-1}M)$ has the unique maximum $\Sigma = M/n$ over positive definite $\Sigma$, for positive definite $M$ and any $n > 0$; with $M = A_k$ and $n = N_k$ it gives $\Sigma_k = A_k/N_k$. $\square$

With $K = 1$ and all responsibilities 1, the M step is the maximum likelihood fit of one normal: the sample mean and $\hat\Sigma = A/n$, the divisor-$n$ covariance matrix. The mixture's M step is that fit with each observation counted with weight $r_{ik}$.

One iteration as an algorithm. From the current $\theta$: compute $r_{ik}$ for every $i$ and $k$ (working with logarithms and subtracting the largest term before exponentiating, so that densities of $10^{-300}$ do not underflow); then set $\alpha_k$, $\boldsymbol\mu_k$ and $\Sigma_k$ by Theorem 3. Each iteration costs a constant times $nKp^2$ operations plus $Kp^3$ for the matrix factorizations, and by The EM Algorithm (Theorem 1) it cannot lower $\ell$; in the script's runs no iteration lowered $\ell$ by more than $10^{-8}$, the asserted tolerance for rounding.

The fit does not depend on the units

Measure height in inches instead of centimeters, or standardize both variables, and k-means can return a different clustering (K-means in Practice shows how scaling changes its clusters). A Gaussian mixture with full covariance matrices cannot.

Theorem 4 (affine equivariance). Let $B$ be an invertible $p \times p$ matrix and $\mathbf c$ a vector, and put $\mathbf y_i = B\mathbf x_i + \mathbf c$. Start EM on the $\mathbf y_i$ from the weights $\alpha_k$, means $B\boldsymbol\mu_k + \mathbf c$ and covariances $B\Sigma_kB^{\mathsf T}$, and EM on the $\mathbf x_i$ from $\alpha_k$, $\boldsymbol\mu_k$, $\Sigma_k$. Then at every iteration the two runs have the same responsibilities, the parameters of the first are the transforms of those of the second, and the log-likelihoods differ by the constant $n\ln\lvert\det B\rvert$.

Proof. By The Multivariate Normal Distribution (Theorem 4) and $\det(B\Sigma B^{\mathsf T}) = (\det B)^2\det\Sigma$, together with $(B\mathbf x - B\boldsymbol\mu)^{\mathsf T}(B\Sigma B^{\mathsf T})^{-1}(B\mathbf x - B\boldsymbol\mu) = (\mathbf x - \boldsymbol\mu)^{\mathsf T}\Sigma^{-1}(\mathbf x - \boldsymbol\mu)$, $$\varphi(B\mathbf x + \mathbf c; B\boldsymbol\mu + \mathbf c, B\Sigma B^{\mathsf T}) = \frac{\varphi(\mathbf x; \boldsymbol\mu, \Sigma)}{\lvert\det B\rvert}.$$ Every component's density at $\mathbf y_i$ is divided by the same factor, which cancels from the ratio $r_{ik}$, so the responsibilities agree; every $f(\mathbf y_i)$ is $f(\mathbf x_i)/\lvert\det B\rvert$, which gives the constant difference in $\ell$. With equal responsibilities, the M step on the $\mathbf y_i$ gives the same weights, the weighted mean $B\mathbf m_k + \mathbf c$ and the weighted scatter $\sum_i r_{ik}B(\mathbf x_i - \mathbf m_k)(\mathbf x_i - \mathbf m_k)^{\mathsf T}B^{\mathsf T} = BA_kB^{\mathsf T}$, which are the transforms of the M step on the $\mathbf x_i$. Induction on the iterations finishes the proof. $\square$

K-means has no such property. Its partitions are preserved by rotations, reflections, translations and a common rescaling of all coordinates, but not by a change of units in one coordinate: Problem 2 below gives four points on which such a change moves k-means from one partition to the other. The theorem also says that standardizing the variables before fitting a full-covariance mixture changes nothing, which the script checks: from the same 30 starts, on the standardized data, 50 iterations give the same responsibilities to $10^{-8}$.

Known truth: does the mixture find the sexes?

Back to the 5,176 adults. Their two groups are known, so the fit can be graded.

The sexes' own normals. Fitting one bivariate normal to each sex by maximum likelihood gives means (173.5 cm, 88.4 kg) for men and (159.8 cm, 77.0 kg) for women, standard deviations of 7.7 and 7.0 cm in height and 22.0 and 22.3 kg in weight, and height–weight correlations of 0.44 and 0.32. Call the mixture with these components and the weights 2,512/5,176 and 2,664/5,176 the labeled fit. Its log-likelihood is $-42{,}212.8$. Its Bayes rule, which assigns each adult to the component with the larger responsibility, gets sex right for 83.2% of the adults, with an adjusted Rand index of 0.440 against sex. (The adjusted Rand index is 1 for identical partitions and has expected value 0 for unrelated ones; Clustering Measures Corrected for Chance defines it.) It is a reference for how much height and weight can say about sex when the two normals are given, and it is well below 100% because the two distributions overlap heavily.

The best mixture. EM with $K = 2$ was started 30 times (seeds 1 to 30), each time from two adults drawn at random as the means, the overall covariance matrix for both components and equal weights, and stopped when the log-likelihood rose by less than $10^{-9}$. All 30 runs ended at the same point, with log-likelihood $-41{,}810.0$, after a median of 247.5 iterations (interquartile range 238 to 257.8). Its components are

Component Weight Mean height (cm) Mean weight (kg) SD height SD weight Correlation
Heavier 0.271 170.8 105.3 10.1 25.3 0.25
Lighter 0.729 164.9 74.1 9.5 14.7 0.46

The two means differ by 6 cm in height and 31 kg in weight. Each component mixes men and women: the heavier component's hard cluster holds 564 men and 408 women, the lighter one 1,948 men and 2,256 women. Agreement with sex is 54.5% and the adjusted Rand index is 0.008, which is essentially no relation. Started from the labeled fit itself, EM moves away from it and reaches the same point after 267 iterations, with agreement 54.5%. The labeled fit is not even a stationary point of the likelihood: there, the derivative of $\ell$ with respect to the men's mean height is 5.06 per centimeter.

Example (a common misreading). "The mixture failed to converge" or "EM found a bad local maximum" are the natural readings, and both are wrong here. Every start reached the same point, and that point has a log-likelihood higher than the labeled fit by 402.8. The mixture is doing what it was asked: finding the two normal distributions whose mixture best describes the joint distribution of height and weight. The sexes are not that pair. Within each sex, weight is skewed to the right (skewness 1.04 for men and 1.34 for women). A likely reading is that a mixture of two normals spends one of its components on the long tail of heavy adults of both sexes; the check below supports it. A mixture component is a piece of a density, not necessarily a population.

Check: remove the skewness. Refit on height and the natural logarithm of weight, whose skewness within sex is 0.27 for men and 0.41 for women. Over the same 30 starts, EM on height and ln weight reached 2 distinct end points, 16 runs reaching the better one, and agreement with sex has median 74.9% (interquartile range 67.9 to 74.9), with adjusted Rand index 0.248 (0.128 to 0.248). The better end point, higher by 24.2 in log-likelihood, agrees with sex for 74.9% of the adults and the other for 67.9%. Taking the logarithm of weight removed most of the skewness and moved the best fit from a split by build to a split much closer to sex (74.9% agreement, against 54.5%, though still short of the labeled fit's 83.2%), which is consistent with the explanation, though one experiment on one transformation does not prove it.

Against k-means. From the same pairs of starting adults, Lloyd's algorithm (The k-means Algorithm) gives these agreements with sex (median and interquartile range over the 30 seeds):

Method Agreement with sex (%) Adjusted Rand index
Labeled fit (uses sex; reference) 83.2 0.440
Gaussian mixture, EM 54.5 (54.5 to 54.5) 0.008 (0.008 to 0.008)
k-means on centimeters and kilograms 61.2 (61.2 to 61.2) 0.050 (0.050 to 0.050)
k-means on standardized variables 76.0 (76.0 to 76.1) 0.271 (0.271 to 0.272)

Unsupervised, k-means on standardized variables came closest to sex in this experiment, and the full-covariance mixture came last. That is not a general ranking. One reading is that k-means looks for compact groups of similar size, and that here this bias happens to point toward the sexes; the mixture looks for the best density and finds a different structure. K-means also changed its answer with the units, from 61.2% to 76.0% agreement, and by Theorem 4 the mixture cannot. When the groups are known, as here, a supervised method uses them: Linear Discriminant Analysis classifies sex from the same height and weight.

How much the start matters

For $K = 2$ the answer did not depend on the start at all: one end point from 30 starts. Larger $K$ is different. For each $K$ from 2 to 6, the 30 runs (seeds 1 to 30, same starting rule) ended as follows; the shortfall is the run's log-likelihood below the best of the 30.

$K$ Distinct end points Runs at the best Median shortfall Largest shortfall Median iterations
2 1 30 0.0 0.0 247.5
3 3 14 14.3 20.0 1,587.5
4 5 4 5.5 14.3 1,520
5 6 20 0.0 16.0 2,108
6 8 5 3.0 9.8 2,873.5

In this experiment the number of distinct end points grew with $K$. A run whose iterates converge to a point short of the best has reached, in the limit, a fixed point of EM other than the best one (the EM map is continuous there, because the formulas of Theorem 3 are continuous in the responsibilities, which are continuous in $\theta$, while every $N_k > 0$ and every scatter matrix is positive definite), which is a stationary point of the likelihood (The EM Algorithm, Corollary to Theorem 2) and may be a local maximum or a saddle (that article shows a stationary point that is not a maximum). Stopping when the rise falls below $10^{-9}$ is evidence of being near such a point, not a proof of having reached it. The standard remedy is the one used here: many starts, keeping the highest likelihood. With six components, 9 of the 30 runs were still rising, by more than $10^{-9}$ per iteration, when they reached the cap of 5,000 iterations. Those 9 had not converged: their values in the $K = 6$ row are where they stopped, not fixed points, and they are counted among its distinct end points. None of the 180 runs became degenerate.

K-means as a small-variance limit

Model-Based Clustering and the EM Algorithm proves that for spherical components sharing one fixed variance $\sigma^2$, the responsibilities tend to the hard nearest-mean assignment as $\sigma^2 \to 0$, the mean update becomes the centroid update, and the scaled log-likelihood tends to the k-means objective. The same argument works for any fixed shapes, with an explicit rate.

Theorem 5 (small-variance limit). Fix positive weights $\alpha_k$, means $\boldsymbol\mu_k$ and positive definite matrices $\Sigma_k$, and give component $k$ the covariance $\varepsilon\Sigma_k$. Write $\delta_{ik} = (\mathbf x_i - \boldsymbol\mu_k)^{\mathsf T}\Sigma_k^{-1}(\mathbf x_i - \boldsymbol\mu_k)$. If component $k$ is the unique minimizer of $\delta_{ij}$ over $j$, with margin $\Delta_i = \min_{j \ne k}(\delta_{ij} - \delta_{ik}) > 0$, then $$1 - r_{ik} \le \sum_{j \ne k}\frac{\alpha_j}{\alpha_k}\sqrt{\frac{\det\Sigma_k}{\det\Sigma_j}}\;e^{-\Delta_i/(2\varepsilon)},$$ so $r_{ik} \to 1$ as $\varepsilon \to 0$. With a shared matrix, $\Sigma_k = \Sigma_0$ for every $k$, the bound is $\frac{1 - \alpha_k}{\alpha_k}e^{-\Delta_i/(2\varepsilon)}$.

Proof. Write $a_j = \alpha_j\varphi(\mathbf x_i; \boldsymbol\mu_j, \varepsilon\Sigma_j) = \alpha_j(2\pi\varepsilon)^{-p/2}(\det\Sigma_j)^{-1/2}e^{-\delta_{ij}/(2\varepsilon)}$, using $\det(\varepsilon\Sigma_j) = \varepsilon^p\det\Sigma_j$. Then $1 - r_{ik} = \sum_{j \ne k}a_j/\sum_l a_l \le \sum_{j \ne k}a_j/a_k$, and $$\frac{a_j}{a_k} = \frac{\alpha_j}{\alpha_k}\sqrt{\frac{\det\Sigma_k}{\det\Sigma_j}}\;e^{-(\delta_{ij} - \delta_{ik})/(2\varepsilon)} \le \frac{\alpha_j}{\alpha_k}\sqrt{\frac{\det\Sigma_k}{\det\Sigma_j}}\;e^{-\Delta_i/(2\varepsilon)}.$$ With a shared matrix the determinants cancel and $\sum_{j \ne k}\alpha_j = 1 - \alpha_k$. $\square$

Three consequences follow. With $\Sigma_0 = I_p$, $\delta_{ik}$ is the squared Euclidean distance, and the limiting E step is the k-means assignment. With a shared $\Sigma_0 \ne I_p$, it is the assignment to the nearest mean in the Mahalanobis distance of $\Sigma_0$, which is k-means run after transforming the data by $\Sigma_0^{-1/2}$. With different $\Sigma_k$, each point goes to the component whose own Mahalanobis distance is smallest; the factors $\det\Sigma_k$ only enter the rate. In every case, once the responsibilities are 0 or 1, the mean step of Theorem 3, whose proof needs only $N_k > 0$, gives the centroid of each hard cluster. The bound holds at every iteration for which the weights stay away from 0, so the limit is unaffected by fitting the weights. The limit is not reached at any positive $\varepsilon$: every density is positive, so every responsibility lies strictly between 0 and 1. With a shared matrix, a point equidistant from two means keeps responsibilities in the ratio of their weights for every $\varepsilon$.

On the NHANES adults. Take the centroids of the k-means run from seed 1 on the raw scale, (163.6 cm, 70.1 kg) and (172.5 cm, 108.8 kg), equal weights and the covariance $\varepsilon I_2$ for both (in squared centimeters and kilograms). The number of adults with responsibility below 0.99 for their nearest centroid is 1,729 at $\varepsilon = 100$, 152 at $\varepsilon = 10$, 17 at $\varepsilon = 1$ and 3 at $\varepsilon = 0.1$, and every responsibility satisfies the bound of Theorem 5, which the script asserts. In the Mahalanobis variant, take $\Sigma_0$ the pooled within-cluster covariance matrix of the best mixture's two hard clusters and the centroids of k-means in that metric. With equal weights, the larger responsibility goes to the nearer mean in this metric at every $\varepsilon$, so the hard assignments agree with that k-means for any $\varepsilon$; what the limit adds is that at $\varepsilon = 0.01$ every responsibility is within the bound of Theorem 5 of 0 or 1 (the script asserts it), and only 35 adults have responsibility below 0.99 for their nearer mean. These clusters agree with sex for 56.9% of the adults.

Label switching

The likelihood does not know the components' names. For any permutation $\tau$ of $\{1, \ldots, K\}$, write $\tau\theta$ for the parameter in which component $k$ takes the weight, mean and covariance of component $\tau(k)$. Since $f$ is a sum over components, $f(\mathbf x \mid \tau\theta) = f(\mathbf x \mid \theta)$ and $\ell(\tau\theta) = \ell(\theta)$. A local maximum with distinct components therefore comes with $K! - 1$ copies, all with the same likelihood. Across the 30 runs with $K = 2$, the heavier (and taller) component was labeled 1 in 15 runs and 2 in the other 15: the same fit, with the labels decided by the start. For maximum likelihood this is harmless once the components are sorted by a feature. In a Bayesian analysis it is not.

Theorem 6 (symmetric posteriors). Let the prior density $\pi(\theta)$ be invariant under every permutation of the components, $\pi(\tau\theta) = \pi(\theta)$. Then the posterior is invariant too, and the posterior distributions of the $K$ components' parameters $(\alpha_k, \boldsymbol\mu_k, \Sigma_k)$ are all the same. In particular, whenever they exist, $E[\boldsymbol\mu_1 \mid \mathbf x] = \cdots = E[\boldsymbol\mu_K \mid \mathbf x] = E\big[\tfrac1K\sum_k\boldsymbol\mu_k \,\big|\, \mathbf x\big]$.

Proof. The posterior density is proportional to $\pi(\theta)\prod_i f(\mathbf x_i \mid \theta)$, and both factors are unchanged when $\theta$ is replaced by $\tau\theta$. For a function $h$ of one component's parameters, write $\theta_k$ for component $k$'s triple. The map $\theta \mapsto \tau\theta$ permutes coordinates, so it preserves volume (for the weights, with densities taken with respect to the uniform measure on the simplex, which every permutation preserves), and changing variables gives $$E[h(\theta_1) \mid \mathbf x] = \int h(\theta_1)\,\pi(\theta \mid \mathbf x)\,d\theta = \int h\big((\tau\theta)_1\big)\,\pi(\tau\theta \mid \mathbf x)\,d\theta = \int h(\theta_{\tau(1)})\,\pi(\theta \mid \mathbf x)\,d\theta = E[h(\theta_{\tau(1)}) \mid \mathbf x].$$ Choosing $\tau$ with $\tau(1) = j$ shows that every component has the same posterior expectation of every function $h$, hence the same posterior distribution. Averaging the equal means over $k$ gives the last expression. $\square$

So with an exchangeable prior, the posterior mean of "the first component's mean" is the average of all the means, which describes no component. Stephens (2000) states the consequence in his summary: estimating parameters by their posterior means and summarizing the joint posterior by its marginals "often leads to nonsensical answers", and that imposing artificial identifiability constraints, such as an ordering of the means, "fails in general to solve the problem"; he proposes relabeling the sampler's output to minimize a posterior expected loss. Celeux, Hurn and Robert (2000) note in their abstract that the posterior has $k!$ modes and that standard Markov chain Monte Carlo samplers tend to stay near one of them.

Example (a sampler that switches, and one that does not). Draw 40 adults at random (seeds 1 to 30) and model their heights as an equal mixture of two normals with a known common standard deviation of 7.3 cm, the pooled within-sex value, and independent normal priors on the two means with mean 166.5 cm (the overall mean height) and standard deviation 20 cm. That prior is exchangeable. A Gibbs sampler (Markov Chain Monte Carlo) alternates drawing each adult's component given the means and each mean given its adults, for 5,000 sweeps. Over the 30 samples, the two means traded order a median of 3 times (interquartile range 0 to 28.3), and 14 chains never switched. The share of sweeps with $\mu_1 < \mu_2$ had median 0.553 (interquartile range 0.406 to 1.000), where Theorem 6 says the exact posterior probability is $\tfrac12$. For the first sample, whose mean height is 166.4 cm, a direct computation of the posterior on a grid illustrates the theorem: both posterior means equal 167.0 cm, while the posterior means of the smaller and the larger of the two are 159.7 and 174.3 cm. Ordering is a sensible summary for this one-dimensional example, but the theorem is the reason the raw output cannot be averaged.

Choosing the number of components

Any $K$-component fit is also a $(K + 1)$-component fit with the same likelihood: split one component into two identical copies with half its weight each. So a fit with more components can always do at least as well, and the likelihood alone cannot choose $K$. The Bayesian information criterion (Schwarz, 1978), $\mathrm{BIC} = -2\hat\ell + q(K)\ln n$, penalizes each free parameter by $\ln n$; Bayes Factors and Posterior Model Probabilities derives it from Laplace's approximation to the marginal likelihood (its Corollary 2) and shows that its error does not vanish, and Model Selection compares it with other criteria. Fraley and Raftery (2002) review model-based clustering as a principled approach to questions such as how many clusters there are. For the adults, with $\ln 5{,}176 = 8.552$ and $\hat\ell$ the best of 30 runs:

$K$ $\hat\ell$ $q(K)$ BIC
1 $-42{,}272.8$ 5 84,588.4
2 $-41{,}810.0$ 11 83,714.0
3 $-41{,}739.3$ 17 83,624.0
4 $-41{,}695.5$ 23 83,587.7
5 $-41{,}669.2$ 29 83,586.5
6 $-41{,}655.4$ 35 83,610.1

BIC chooses $K = 5$, with $K = 4$ almost tied. Two adult sexes, the known truth, are not what the criterion finds, for the reason of the previous sections: two normals do not describe the joint distribution, and BIC asks how many normals do. Three cautions apply to the criterion itself. Its derivation in Bayes Factors and Posterior Model Probabilities assumes a regular model with a consistent estimate, and a mixture with too many components is not regular: its extra component can have weight 0 or coincide with another, where the parameters are not identifiable. The $\hat\ell$ in it is the best end point EM found, at best a local maximum, since Theorem 1 rules out a global one. And the error of order 1 that the criterion carries means that differences of a few units, like the 1.2 between $K = 4$ and $K = 5$, are not decisive.

What is proved, what is cited, what the experiment shows

Proved on this page: the unboundedness of the mixture likelihood by collapse onto a point and onto a hyperplane (Theorem 1, parts 1 and 2); the positivity of every exact EM iterate when the data do not lie in a hyperplane (Theorem 2); the full-covariance M step (Theorem 3); affine equivariance of EM (Theorem 4); the small-variance limit with general covariance shapes and an explicit bound on $1 - r_{ik}$ (Theorem 5); the permutation invariance of the likelihood and the equality of the components' posteriors under an exchangeable prior (Theorem 6).

Used from other pages: the EM algorithm, the weighted-counts lemma, the spherical small-variance limit and the k-means objective limit (Model-Based Clustering and the EM Algorithm); monotonicity of EM and the stationarity of its fixed points (The EM Algorithm); the normal density and its behavior under affine maps (The Multivariate Normal Distribution); the maximum of $-\frac n2\ln\det\Sigma - \frac12\operatorname{tr}(\Sigma^{-1}M)$ (Lemma 4 of Hotelling's T-Squared Test); BIC from Laplace's approximation (Bayes Factors and Posterior Model Probabilities); the Gibbs sampler (Markov Chain Monte Carlo).

Cited: Dempster, Laird and Rubin (1977) for the EM algorithm; Hathaway (1985) and Redner and Walker (1984), from their abstracts, on constrained estimation and on the literature; Stephens (2000) and Celeux, Hurn and Robert (2000), from their abstracts, on label switching; Fraley and Raftery (2002), from their abstract, on model-based clustering; Schwarz (1978) for the criterion.

Observed in the experiments: on the 5,176 adults, the best two-component mixture splits by build rather than sex and is reached from every start; the labeled fit is not a stationary point; agreement with sex is higher for k-means on standardized variables; on the logarithm of weight the picture changes as reported above; the number of distinct end points grows with $K$; BIC chooses five components; the Gibbs sampler's switching. Every number on this page is computed by tools/experiments/statistics/gaussian-mixture-models.py.

Worked problems

These problems are posed for this article on small exact cases and on the unit's data; the unit has no course assignments. The script recomputes every number.

Problem 1 (one EM iteration by hand). Four observations on a line, $x = 1, 2, 4, 5$, are fitted by a two-component mixture starting from means 1 and 5, variances 1 and equal weights. Carry out one E step and one M step, and check that the log-likelihood rose.

Solution. With equal weights and variances, the factors $\alpha_k(2\pi)^{-1/2}$ cancel and $r_{i1} = 1/\big(1 + e^{((x_i - 1)^2 - (x_i - 5)^2)/2}\big)$. For $x = 1$ the exponent is $(0 - 16)/2 = -8$, so $r_{11} = 1/(1 + e^{-8}) = 0.99966$; for $x = 2$ it is $(1 - 9)/2 = -4$, giving 0.98201; for $x = 4$ and $x = 5$ the exponents are $+4$ and $+8$, giving 0.01799 and 0.00034. The data and the start are symmetric about 3, so the responsibility of component 2 for $x$ equals that of component 1 for $6 - x$, and $N_1 = N_2 = 0.99966 + 0.98201 + 0.01799 + 0.00034 = 2$ exactly: the weights stay $\tfrac12$. The new first mean is $\sum_i r_{i1}x_i/2 = 1.5187$ and the second, by symmetry, $6 - 1.5187 = 4.4813$. The new variance of each is $\sum_i r_{i1}(x_i - \mu_1)^2/2 = 0.3056$. The means moved inward, toward the centers of $\{1, 2\}$ and $\{4, 5\}$, which are 1.5 and 4.5, and the variances fell from 1 toward the within-pair value of $\tfrac14$. The log-likelihood rose from $-7.411$ to $-5.716$, as The EM Algorithm guarantees.

Problem 2 (k-means changes with the units; the mixture does not). Four points are $(0, 0)$, $(0, 1)$, $(10, 0)$ and $(10, 1)$, the second coordinate a length in meters. Find the best k-means partition into two clusters, then measure the second coordinate in centimeters, so that it reads 0 and 100. Explain why a full-covariance mixture cannot behave the same way.

Solution. Four points have seven partitions into two nonempty clusters: three into pairs and four that set one point apart. Splitting by the first coordinate gives clusters $\{(0,0), (0,1)\}$ and $\{(10,0), (10,1)\}$, each with its centroid halfway up and residual sum of squares $4 \times \tfrac14 = 1$. Splitting by the second gives centroids $(5, 0)$ and $(5, 1)$ and residual sum of squares $4 \times 25 = 100$. The two diagonals have both centroids at $(5, \tfrac12)$ and residual sum of squares $4(25 + \tfrac14) = 101$. Setting one point apart leaves three points whose centroid is $\tfrac23$ of the way across in each coordinate from the lone point's side, with residual sum of squares $\tfrac{200}{3} + \tfrac23 = 67\tfrac13$, the same for each of the four by symmetry. So the best partition is by the first coordinate. In centimeters, the pair splits cost $4 \times 2{,}500 = 10{,}000$ (by the first coordinate), $4 \times 25 = 100$ (by the second) and $4(25 + 2{,}500) = 10{,}100$ (diagonals), and setting one point apart costs $\tfrac{200}{3} + \tfrac{20{,}000}{3} = 6{,}733\tfrac13$: now the best partition is by the second coordinate. The data did not change, only the units. For a full-covariance mixture, the change of units is the linear map $B = \operatorname{diag}(1, 100)$, and Theorem 4 says that every EM run on the new data is the old run transformed, with the same responsibilities and therefore the same clusters, and log-likelihood lower by exactly $n\ln 100$ for every parameter, so the ranking of fits is unchanged too.

Problem 3 (counting parameters and comparing $K = 4$ with $K = 5$). Count the free parameters of a bivariate mixture with $K$ components when the covariance matrices are full, diagonal or spherical, and use the table of BIC values to say how strongly the criterion prefers five components to four.

Solution. Each case has $K - 1$ free weights and $2K$ mean coordinates. A full $2 \times 2$ covariance matrix has 3 free entries, a diagonal one 2 and a spherical one 1. So $q = (K - 1) + 2K + 3K = 6K - 1$, $(K - 1) + 4K = 5K - 1$, or $(K - 1) + 3K = 4K - 1$. For $K = 4$ these are 23, 19 and 15; for $K = 5$, 29, 24 and 19. With full matrices, going from four to five components gains 26.3 in log-likelihood and adds 6 parameters, which cost $6 \times 8.552/2 = 25.7$ on the same scale. So BIC(4) $-$ BIC(5) $= 2(26.3 - 25.7) = 1.2$ to the rounding shown, or 1.23 before rounding. Read through Corollary 2 of Bayes Factors and Posterior Model Probabilities, $e^{\Delta\mathrm{BIC}/2} = e^{0.615} = 1.85$ is an approximate Bayes factor for five components against four, which that article's error analysis says is uncertain by a factor of order 1. The data hardly distinguish the two.

Summary

  • A Gaussian mixture with free covariance matrices has an unbounded likelihood: a component centered on one observation with a shrinking covariance drives it to infinity, and with full matrices a component can also collapse onto a hyperplane (Theorem 1). Exact EM steps never reach the collapse when the data do not lie in a hyperplane (Theorem 2), but can approach it.
  • The M step sets each weight to $N_k/n$, each mean to the weighted mean and each covariance to the weighted scatter divided by $N_k$ (Theorem 3).
  • EM for full-covariance mixtures is equivariant under invertible affine maps, so units and standardization do not matter; k-means is not (Theorem 4, Problem 2).
  • As the covariances shrink to $\varepsilon\Sigma_k$, the responsibilities harden at the rate $e^{-\Delta/(2\varepsilon)}$: shared $\Sigma_0 = I$ gives k-means, shared $\Sigma_0$ gives Mahalanobis k-means (Theorem 5).
  • Permuting the labels leaves the likelihood unchanged, and with an exchangeable prior every component has the same posterior (Theorem 6).
  • On 5,176 NHANES adults the best two-component fit, reached from all 30 starts, splits by build and agrees with sex for 54.5%; the sexes' own normals fit worse by 402.8 in log-likelihood; BIC chooses five components.

What we have learned

A Gaussian mixture fitted by EM is a precise statement about a density, and the NHANES adults showed how far that can be from a statement about groups. Two sexes with overlapping, right-skewed weight distributions are not two normal distributions, and on these data the likelihood, from every start, preferred a split into heavier and lighter adults; the logarithm of weight moved the fit much closer to sex, which points to the skewness as the likely reason. The theory around the fit is sharper than the fit's interpretation: the likelihood has no maximum, yet EM's exact steps stay inside the parameter space; the fit ignores units, which k-means does not; k-means is the limit of vanishing variances, with any fixed shape; and the components have no names, so a Bayesian posterior that treats them alike cannot tell them apart.

The next article, The Singular Value Decomposition in Statistics, turns from fitting several covariance matrices to decomposing one data matrix, and proves the low-rank approximation theorem beneath principal components, latent semantic indexing and ridge regression.

References