Stanford CS229 Machine Learning | Spring 2026 | Lecture 9: K-Means and GMM (non-EM)

Unsupervised learning algorithms, such as K-Means and Gaussian Mixture Models (GMM), identify underlying patterns in unlabeled data by iteratively refining estimates of hidden structures.

• Hard clustering — K-Means assigns each data point strictly to the closest centroid, which is then recalculated as the arithmetic average of all points assigned to that center [09:07].
• Computational constraints — Because finding the global optimum is NP-hard, K-Means is sensitive to initialization and frequently settles into local minima rather than an optimal configuration [16:47].
• Initialization influence — Utilizing methods like K-Means++ to seed the starting centroids improves the likelihood of arriving at a robust approximation of the data's structure [19:34].
• Probabilistic assignment — GMM replaces hard labels with soft assignment, providing a probability vector for every data point that indicates its likelihood of belonging to each of the $K$ sources [32:11].
• EM algorithm iteration — The Expectation-Maximization process repeatedly updates parameters through two phases:
  • Expectation step — Calculates the likelihood of data points belonging to clusters given the current model [50:40].
  • Maximization step — Updates the model parameters (means, variances, and mixing weights) to better fit those calculated assignments [50:40].
• Lower bound optimization — The algorithm ensures convergence by maximizing a surrogate function that acts as a lower bound for the likelihood, a mathematical technique derived from convex analysis and Jensen's inequality [1:12:46].

How does the EM algorithm determine convergence criteria when dealing with latent variables?

What are the primary differences in assumptions when modeling data with K-Means versus GMM?