Last week's k-means clusters unlabeled data by alternating two steps: assign each point to its nearest center, then move each center to the mean of its points. Every assignment is all-or-nothing. A Gaussian mixture model (GMM) says instead that the data came from Gaussian "bumps", each with its own center , shape and share of the data . A point near a boundary is then, say, 60% cluster 1 and 40% cluster 2. Those percentages are the responsibilities. The model is fit by maximizing the likelihood of the data with the expectation-maximization (EM) algorithm, which is k-means with soft assignments: compute responsibilities (E-step), then recompute weighted means, covariances and weights (M-step), and repeat. Like k-means, it can stop at a local optimum and you have to choose . Unlike k-means, it gives you a full probability density, so you can also score how unusual a point is or generate new data.
After this you canRecap: k-means as an optimization problem
Clustering is unsupervised: we have points and no labels, and we want to discover groups. k-means, from last week, does it like this (slide 2):
- Choose , the number of clusters, and initialize centers , e.g. at random data points.
- Assignment step: assign every point to its nearest center (Euclidean distance).
- Update step: move each center to the mean of the points assigned to it.
- Repeat 2–3 until nothing changes (or a maximum number of iterations).
Slides 3–4 show this is minimizing a cost, the distortion. Introduce assignment variables , which are 1 if point belongs to cluster and 0 otherwise. The professor calls these "hard" assignments because each is 0 or 1 (05:24).
- 1 if point is assigned to cluster , else 0. Each row of the matrix has exactly one 1.
- center of cluster
- distortion: total squared distance from points to their own centers
The two steps each minimize over one set of variables while the other is held fixed:
- Over (centers fixed): each point's term is separate, so pick the closest center.
- Over (assignments fixed): set the gradient to zero.
This is the mean of the points in cluster . Keep this formula in mind: the GMM mean update has exactly the same shape, with replaced by a fraction.
Neither step can increase , so k-means always converges (slide 4 plots dropping and flattening within a few iterations). But the objective is non-convex (06:02). That means it can converge to a local minimum, and different random starts give different answers (slide 5, two runs with on the same data that end at different costs). The fix the professor gives (06:40) is to run k-means several times and keep the run with the lowest .
Slide 3 first writes the distortion as , where loosely means "point , which sits in cluster ". Then it defines the indicator as with and mixed up. The clean version is the double sum above: if is assigned to cluster , otherwise 0.
"Once you have an application that relates to clustering, the first algorithm I suggest you try is k-means," because it is so cheap to compute. If it solves your problem, you are done. If not, try something richer, such as today's GMM.
Applications covered on slides 6–8:
- Vector quantization: replace every vector by its cluster center (its "code word"). This is used for compression and noise reduction, and the lecture mentions the bag-of-words model as an example (06:40).
- Image segmentation / color compression: cluster all pixels by their 3-D RGB color and repaint each pixel with its center's color. gives a two-tone image, and already looks close to the original. The professor notes the weakness (08:34): this ignores where pixels are, even though neighboring pixels usually belong to the same region.
- Face clustering ("Groundhog Day"): flatten each detected face patch into a long intensity vector (a 16×16 patch gives 256 numbers), then run k-means. With , the clusters roughly separate the main actors, plus a cluster of non-faces.
Points 1, 2 and 9 are currently assigned to a center at 4. What does the update step move that center to, and what is the distortion contributed by those points before and after?
New center = mean = . It doesn't move, so the distortion is the same before and after: .
Assignments to other centers could still change in the next assignment step, for example if another center sits near 9.
Hard vs soft assignment
The professor names this as the key difference between the two methods (13:30). In k-means a point on the boundary between two clusters is assigned 100% to one of them, even if it is almost equally far from both. Slide 9 calls this "a poor representation" for points near the boundary.
A GMM replaces with a soft assignment , the probability that point came from cluster :
Each row of is a probability distribution over the clusters. If you need a single label, take the most probable cluster (scikit-learn's predict). If you want the soft version, read the row itself (predict_proba).
Keep this picture in mind for the rest of the lecture. Every GMM formula is a k-means formula with replaced by : "count the points in cluster " becomes "add up the fractions", and "average the points in cluster " becomes "take a weighted average of all points".
The mixture model: a weighted sum of bumps
One Gaussian can only describe a single bump. Real data distributions often have several bumps, like the red curve on slide 9. The idea: combine simple models into a complex one. Add up Gaussians, each scaled by a weight:
- the -th component: a Gaussian density with mean and covariance matrix
- mixing coefficient (weight): the share of the data that component accounts for
- number of components, chosen by you
- all parameters together:
The constraints on are what keep a valid density: each component integrates to 1, so the mixture integrates to . The professor stresses (16:04) that "mixture" just means this weighted sum. A Gaussian mixture is one whose components are Gaussians. Use another distribution for the components and you get another mixture model (Bishop §9.3.3 does Bernoulli mixtures, for example).
The generative story
Géron describes the same model as a recipe for generating data. This is why the professor calls a GMM a generative model (38:40):
- Pick a component at random, with .
- Draw .
We see but never , so is a latent (hidden) variable. Summing over the possible values of gives back the mixture formula above. The responsibility is simply the probability that after seeing . This recipe is also how you sample new data from a fitted GMM (the professor leaves the details to you; it is exactly these two steps, and scikit-learn does it with gm.sample(n)).
The slides and Bishop write , points, components. Géron writes the weights as , uses for the number of instances and for the number of clusters. In 1-D, the slides sometimes write ; the second argument is meant as the spread, and the density uses the variance .
The covariance sets each cluster's shape
covariance_type)In dimensions each component is
Its contours (curves of equal density) are ellipses (ellipsoids in higher dimensions). The professor's summary (17:12): the mean sets the center of the cluster; the covariance matrix sets its shape. The ellipse axes point along the eigenvectors of , and their half-lengths are proportional to the square roots of the eigenvalues. A nonzero off-diagonal entry tilts the ellipse.
Slide 10's example (Old Faithful eruption data) makes the point. One Gaussian fit to two clumps gives one long tilted ellipse that covers the empty gap between them. A mixture of two Gaussians puts one ellipse on each clump. That is already a clustering.
A full covariance has free numbers per component, which is a lot when is large or data is scarce. Géron lists scikit-learn's options for restricting it:
covariance_type | Constraint | Shape |
|---|---|---|
"full" (default) | each component has its own unconstrained | any ellipse, any tilt |
"tied" | all components share one | same ellipse everywhere |
"diag" | diagonal | ellipses aligned with the axes |
"spherical" | circles of different sizes |
Training cost is for spherical/diag and for tied/full (Géron), so full covariances do not scale to many features.
The cost function: negative log-likelihood
k-means minimized a distortion. A GMM is a probability model, so we fit it by maximum likelihood: choose the parameters that make the observed data most probable.
- One point: .
- All points. Assume the points are i.i.d. (independent and identically distributed): no point's probability depends on the others (19:08). Then the probability of the whole dataset is a product:
- Take the log. The product of many numbers below 1 is astronomically small. The professor's example (20:45): 1000 points each with probability 0.1 give , which a computer can't store. In double precision it rounds to exactly 0, since the smallest positive double is about . The log turns the product into a sum, , which is perfectly representable. Because log is strictly increasing, maximizing the log-likelihood gives the same parameters as maximizing the likelihood.
- Negate it to get something to minimize, matching the "cost function" language of k-means:
Minimizing and maximizing the log-likelihood are the same thing. This guide uses whichever reads more naturally. EM is usually described as maximizing , and that is how the professor describes the M-step at 34:18.
Slide 10 says is " and in this case". The mixing weights are parameters too, and the very next slide estimates them. In the lecture (23:12) the professor lists all three: , , .
The professor first says "the negative log-likelihood is a convex function", then corrects himself at 23:56: "I'm sorry, I'm wrong." The correct statement: is not convex, just as the k-means distortion is not. The sum inside the log is the culprit (Bishop §9.2.1). What he meant is that once the assignments are held fixed, the remaining problem is easy and has a closed-form optimum. That is exactly what EM exploits.
Why not just compute the product of the and maximize that directly?
With many points the product underflows to 0 in floating point, so every parameter setting looks equally bad and there is no gradient to follow. The log turns it into a sum of moderate negative numbers with the same maximizer.
Deriving the updates: responsibilities appear
The professor's general rule for any cost function (31:02): first try computing the gradient and setting it to zero. Do that for each parameter.
Means
Use the gradient of a log-Gaussian and the chain rule through the log:
A fraction appears:
The fraction is the responsibility of component for point :
It's Bayes' rule: prior times likelihood , divided by the total. So . Set the gradient to zero, multiply by , and rearrange (the professor writes out this step at 26:14):
- responsibility: how much of point "belongs" to component ; rows sum to 1
- effective number of points in component (a sum of fractions, so not necessarily a whole number)
Compare with k-means' . It is the same formula, a weighted mean, but every point now contributes to every component in proportion to its responsibility (28:46–30:04).
Slide 11 writes . Since is the negative log-likelihood, the derivative needs a minus sign, as written above. It doesn't change the result, because we set it to zero. (Bishop's printed Eq. 9.16, which differentiates the positive log-likelihood, has its own slip: it shows where belongs. The final Eq. 9.17 is correct.)
Covariances
This is the ordinary sample covariance, with each point weighted by : a weighted covariance (32:40). In 1-D it reduces to the weighted variance shown below. Use the new here (Bishop Eq. 9.25).
Mixing weights
Here there is a constraint, , so we add a Lagrange multiplier and minimize :
Multiply by to get . Summing over gives , so and
This is the average responsibility of component : the fraction of the data it accounts for (33:12).
The lecture calls these "closed-form solutions" (31:02, 34:04). Bishop (§9.2.2, p. 436) stresses the opposite: the right-hand sides contain , and depends on the very parameters we are solving for. They are coupled equations, not a formula you evaluate once. What they do give is a natural iteration: freeze , solve for the parameters, recompute , and repeat. That iteration is EM.
Three points have responsibilities for component 1. What are and ?
, and
Divide by , not by . Dividing by is the most common slip.
The EM algorithm
Expectation-maximization just alternates the two halves of the previous section (slide 12):
- Initialize (randomly, or from k-means).
- E-step (expectation): with the parameters fixed, compute every responsibility . This is the soft "assignment" step.
- M-step (maximization): with the responsibilities fixed, re-estimate the parameters: This is the "update the centers" step, now with weights.
- Repeat until the log-likelihood (or the parameters) stops changing.
| k-means | EM for a GMM | |
|---|---|---|
| Assign | for the nearest center | E-step: by Bayes' rule |
| Update | = mean of its points | M-step: weighted , , and |
| Objective | distortion never increases | log-likelihood never decreases |
| Stops at | a local minimum | a local maximum (or saddle) |
The slides only say "repeat until convergence". The stronger fact, proved in Bishop §9.4, is that each EM iteration never decreases the log-likelihood. That makes the log-likelihood a good bug check: if it ever goes down, your code is wrong.
Worked example: one EM iteration by hand
Six 1-D points: . Fit . Start from , , , .
- E-step shortcut. With equal weights and variances the normalizing constants cancel, so only the exponents matter: That's the logistic curve in the Section 2 figure. For example, at : , so .
- The full E-step table (densities are ):Check a row: ✓ (the cancel).
−1.8 0.2897 0.0079 0.973 0.027 −1.5 0.3521 0.0175 0.953 0.047 −0.2 0.2897 0.1942 0.599 0.401 1.3 0.0283 0.3814 0.069 0.931 1.7 0.0104 0.3123 0.032 0.968 2.4 0.0012 0.1497 0.008 0.992 - M-step: effective counts and weights. so . Then and . Component 2 now claims more than half the data. It picks up 40% of the middle point plus a little of each left-hand point (0.475 in total), while component 1 gets only 0.109 from the right-hand points.
- M-step: means. and (they add to ✓). So
- M-step: variances (around the new means): and . So
- Did it help? The log-likelihood went from to . It increased, as EM guarantees.
Repeating the loop gives the table and figures below. After about five iterations nothing changes. The final clusters are and , with means very close to those groups' plain averages ( and ).
| Iteration | ||||
|---|---|---|---|---|
| 0 (start) | 0.500, 0.500 | −1.000, 1.000 | 1.000, 1.000 | −11.006 |
| 1 | 0.439, 0.561 | −1.191, 1.496 | 0.700, 0.819 | −10.101 |
| 2 | 0.452, 0.548 | −1.257, 1.617 | 0.454, 0.534 | −9.708 |
| 3 | 0.475, 0.525 | −1.216, 1.706 | 0.458, 0.377 | −9.459 |
| 4 | 0.495, 0.505 | −1.175, 1.781 | 0.480, 0.243 | −9.232 |
| 5 | 0.500, 0.500 | −1.165, 1.800 | 0.486, 0.208 | −9.211 |
| converged | 0.500, 0.500 | −1.165, 1.800 | 0.487, 0.207 | −9.211 |
The lecture describes the M-step as trying to "push away" the two Gaussians. Nothing in the M-step pushes the means apart. Each mean simply moves to the responsibility-weighted average of the data. In slide 13's example (and ours), the points split into a left group and a right group, so the means separate. With other data they could just as well move toward each other.
Slide 12 fixes and and estimates only the two means, and slide 13 then runs EM on that model. Our worked example updates everything, which is what GaussianMixture does. If you only update the means, the E-step is unchanged and you just skip the and updates.
In the E-step shortcut above, what would be for a point at ? Why?
. With equal weights and equal variances, is exactly as far from as from , so neither component is favored.
GMM vs k-means in 2-D
Slide 14 (Bishop's Figure 9.8) runs EM on the same Old Faithful data as the k-means example. Both components start as unit circles (identity covariance) at the k-means starting centers. After the first E-step, points in between are colored purple: partly blue, partly red. Each M-step then moves each ellipse to the "center of mass of its ink" and reshapes it to that ink's covariance. After 20 iterations () it has converged. The professor's takeaway (38:00): the difference from k-means is the assignment, which "gradually changes" rather than jumping at a line.
When the soft, shaped clusters matter
k-means is a special case of EM
The slide margin notes (slide 14) that "k-means is a special case of GMM". Bishop §9.3.2 makes this precise. Give every component the same spherical covariance and keep fixed. Then
As shrinks, the term for the nearest mean dominates the denominator exponentially, so the responsibilities harden into k-means' 0/1 assignments (as long as no is 0). The mean update becomes k-means' centroid update. This is the steepening curve in the Section 2 figure.
| k-means | GMM (EM) | |
|---|---|---|
| Assignment | hard, | soft, |
| Learns | centers only | centers, covariances (shape, size, tilt), weights |
| Cluster shape | implicitly round, similar sizes | any ellipse (with "full") |
| Output | a partition | a density : can score points and sample new ones |
| Cost per iteration | low | higher (densities, covariances); also needs more iterations |
| Shared problems | choose ; sensitive to initialization; converges to local optima | |
Why there are always several optima
The 3-D surface on slide 13 is titled "2D data example", but its axes are the two means and , and the height is the likelihood . It is a picture of the 1-D example's parameter space, like the contour plot above, not of 2-D data. The two peaks (labeled 1 and 2 in the margin) are the same fit with the component labels swapped. In general a -component fit has such equivalent copies (Bishop §9.2.1, "identifiability"). They are harmless, but they are one concrete reason the objective is non-convex.
Practicalities
Slide 14 lists three issues: initialization, the choice of , and local optima. The lecture adds the generative-model benefit. The textbooks fill in how to handle each one.
Initialization and local optima
- Initialize with k-means (slide 14). Run k-means first, then start EM with = the k-means centers, = each cluster's sample covariance, and = the fraction of points in each cluster (Bishop p. 438). This is scikit-learn's default. EM takes many more iterations than k-means, and each one costs more, so a good start saves time.
- Restart several times. EM finds a local maximum of , not necessarily the global one. Run it from several starts and keep the run with the highest log-likelihood. Géron notes that scikit-learn's
n_initdefaults to 1, so set it explicitly (e.g.n_init=10).
Move the two bars in the 2-D figure closer together (1.0 apart instead of 1.4). With scikit-learn's default k-means initialization, even with n_init=20, EM stays near k-means' wrong split and stops at (59% of points labeled correctly). Starting from random data points instead (init_params="random_from_data") finds the right answer, and 100% correct. Initializing from k-means is a good default, but not a guarantee.
Collapsing components (singularities)
Neither the slides nor the lecture mention this, but it is the standard failure of maximum-likelihood GMMs (Bishop §9.2.1). Put one component's mean exactly on a data point and shrink its variance. That point's density blows up, while the other component keeps the remaining points' likelihood finite. So .
Component 1: , a broad Gaussian over all the data. Component 2: , centered on the single point 2.4. As shrinks through 1, 0.1, 0.01, 0.001, the log-likelihood goes −12.10, −11.83, −9.55, −7.25, and it keeps rising without limit. At this nonsense "fit" already beats the honest EM solution (−9.21).
In practice, implementations guard against this. scikit-learn adds a small constant to every covariance's diagonal (reg_covar), and Bishop suggests resetting a collapsing component to a random mean and a large covariance. It's also one more reason a Bayesian treatment (Géron's BayesianGaussianMixture) is attractive.
Choosing K
The lecture says only "choice of ". The slide's handwritten notes suggest two practical routes: look for an "elbow" in the cost curve, or split the data into training and test sets, fit on the training data, and compare on the test data. Géron's recommended tool is an information criterion, which rewards fit and penalizes parameters:
- the maximized likelihood of the fitted model, so at convergence
- number of free parameters. A full-covariance GMM in dimensions has . The is there because the weights must sum to 1.
- number of data points (Géron: )
You can't just pick the with the best likelihood. More components never fit worse, so keeps rising with all the way to one component per point. Géron also warns that k-means' tools (inertia, silhouette score) are unreliable here, because GMM clusters aren't spherical or equal-sized.
A density, not just clusters
- Sampling (generative model, 38:40). Draw a component with probabilities , then draw from that Gaussian. The professor leaves this for you to look up; it is exactly the two-step recipe in Section 3.
- Anomaly detection (Géron, p. 266). Points in low-density regions are anomalies. Pick a threshold on that flags the expected fraction of outliers. For example, if about 4% of products are defective, flag the 4% of points with the lowest density. If you get too many false alarms, lower the threshold. Because the GMM also fits the outliers, you may need to fit, remove the worst outliers, and refit.
gm = GaussianMixture(n_components=3, covariance_type="full", n_init=10).fit(X)
gm.weights_, gm.means_, gm.covariances_ are ; gm.predict_proba(X) gives the responsibilities and gm.predict(X) the hard labels; gm.score_samples(X) gives (for anomaly thresholds); gm.bic(X), gm.aic(X); gm.sample(n).
How many free parameters does a full-covariance GMM with components have in dimensions?
Per component: 2 for the mean, plus 3 for a symmetric 2×2 covariance (two variances and one covariance), so 5. Three components give 15, plus free weights. Total .
Cheat sheet
| k-means distortion | , ; |
| Mixture density | , , |
| Cost | ; minimize (= maximize log-likelihood); non-convex |
| Why log | product of small numbers underflows; log turns it into a sum, same maximizer |
| E-step | (Bayes' rule; rows sum to 1) |
| M-step | ; ; with the new ; |
| 1-D, 2 comps, equal , | , |
| EM guarantee | log-likelihood never decreases; converges to a local optimum; restart (n_init), init from k-means |
| k-means as a limit | , ⇒ |
| Covariance types | full (any ellipse) · tied (shared) · diag (axis-aligned) · spherical (circles) |
| Choosing K | BIC , AIC , lower is better; full GMM: |
| Pitfalls | local optima; component collapsing onto a point (); label-swapped copies of every solution |
| Uses | soft clustering, density estimation, sampling new data, anomaly detection (low ) |
Practice
Q1What is the key difference between k-means' and a GMM's ?
Q2Two 1-D components with , , , . What is the responsibility of component 2 for ?
Q3After an E-step on points, the responsibilities for component 1 add up to . The M-step sets to:
Q4Points have . The M-step mean is:
Q5Why does GMM fitting work with the (negative) log-likelihood instead of the likelihood itself?
Q6Which statement about EM for GMMs is true?
Q7Under what limit does EM for a GMM turn into k-means?
Q8Your clusters look like ellipses stretched along the x-axis or y-axis, never tilted, and of different sizes. The cheapest adequate covariance_type is:
Q9For BIC, how many free parameters does a full-covariance GMM with in dimensions have?
Q10During EM one component shrinks onto a single data point and the log-likelihood shoots toward . What is happening?
Problem 1: Data . Start with , , , , . Do one full EM iteration: responsibilities, , , , .
E-step. Equal weights and variances, so
| 0 | −4 | 0.982 | 0.018 |
| 1 | −2 | 0.881 | 0.119 |
| 3 | 2 | 0.119 | 0.881 |
| 4 | 4 | 0.018 | 0.982 |
M-step. , and by symmetry. So .
By symmetry, .
and by symmetry.
The means moved outward toward the two pairs, and the variances shrank. The log-likelihood rose from −7.158 to −6.462.
Verified in Python (numpy/scipy), including the log-likelihoods before and after.
Problem 2: Derive by minimizing subject to . Then explain in one sentence why .
Form , writing .
Multiply by : , i.e. .
Sum over : . The left side is , and the right side is (next line). So and . ∎
, because each point's responsibilities sum to 1: every point is shared out completely among the components.
Bishop does the same with the positive log-likelihood and gets ; the sign of just flips with the sign of the objective.