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

## Executive summary

This lecture provides a deep dive into unsupervised machine learning algorithms, focusing on K-Means clustering and its probabilistic extension, Gaussian Mixture Models (GMM). The core mathematical framework for solving GMM is the Expectation-Maximization (EM) algorithm. Key concepts include understanding how to model structure without explicit labels, utilizing latent variables, and employing convex analysis via Jensen's inequality to derive the iterative estimation procedure.

## Key takeaways

- Unsupervised vs. Supervised Learning: Unlike supervised learning (where labels define separation), unsupervised learning aims to model inherent structure or clusters within unlabeled data, making it a fundamentally more challenging problem that requires stronger assumptions and accepting weaker guarantees.
- K-Means Clustering: K-Means is an iterative algorithm where points are assigned to the nearest cluster center ($oldsymbol{ ext{mu}}_i$). The process involves two steps: (1) assigning each point to its closest $oldsymbol{ ext{mu}}$, and (2) recalculating the new cluster centers based on the arithmetic mean of all assigned points. Finding the optimal clustering is NP-hard, meaning initialization matters.
- Gaussian Mixture Models (GMM): GMMs are a probabilistic relaxation of K-Means, modeling data as mixtures of Gaussian distributions. Instead of hard assignments, points are assigned probabilities to belong to each source/cluster. The model is defined by means ($oldsymbol{ ext{mu}}$), covariances ($oldsymbol{ ext{Sigma}}$), and mixing proportions ($oldsymbol{f}$).
- Expectation-Maximization (EM) Algorithm: The EM algorithm is used to estimate the parameters of latent variable models like GMM. It alternates between two steps: the E-step (calculating the probability $W_{ij}$ that each point belongs to each source given current parameter estimates) and the M-step (re-estimating all model parameters, including means and covariances, based on these probabilities).
- Convexity and Jensen's Inequality: The EM algorithm relies on convex analysis. Convex functions are those where the line segment connecting any two points lies above the function graph (e.g., $x^2$). Jensen's inequality is used to derive a lower bound for the log-likelihood function, allowing the complex optimization problem to be solved iteratively.

## Technical details

- K-Means Algorithm: Given $N$ points and an integer $K$, the algorithm initializes $K$ centers ($oldsymbol{ ext{mu}}_i$). It iteratively assigns point $oldsymbol{x}_i$ to cluster $J$ if it minimizes the distance (Euclidean distance) to $oldsymbol{ ext{mu}}_J$. The new center is then calculated as the arithmetic mean of all points assigned to that cluster. Convergence occurs when assignments and centers stabilize.
- GMM Model Formulation: The probability density function (PDF) for a point $oldsymbol{x}$ is modeled as a weighted sum of Gaussian components: $p(oldsymbol{x}) = rac{1}{Z} ext{Mixture}(oldsymbol{ ext{mu}}_j, oldsymbol{ ext{Sigma}}_j)$. The model assumes that the data are generated by multiple sources (Gaussian distributions) with different means and covariances.
- EM Algorithm Steps: The EM algorithm iteratively estimates parameters ($oldsymbol{ ext{mu}}, oldsymbol{ ext{Sigma}}, oldsymbol{f}$): The E-step calculates the responsibility $W_{ij} = p(Z_i=j | oldsymbol{x}_i, heta^{ ext{old}})$, which is the probability that point $oldsymbol{x}_i$ belongs to source $j$. The M-step updates parameters by maximizing the expected complete log-likelihood using these responsibilities.
- Optimization via Convex Relaxation: The optimization of the likelihood function is achieved by constructing a lower bound, $L_T( heta)$, which is guaranteed to be concave (convex relaxation). Maximizing this simpler surrogate function allows for an iterative estimation procedure that converges toward the maximum likelihood estimate.

## Practical implications

- Clustering data sets (e.g., identifying distinct groups of genes or astronomical objects) when labels are unavailable.
- Source separation in signal processing, such as distinguishing different types of light sources (quasars vs. stars) based on observed photon distributions.
- Understanding the underlying structure of complex datasets by modeling them as mixtures of simpler probability distributions.

## Topics

Unsupervised Learning, Clustering Algorithms, Gaussian Mixture Models (GMM), Expectation-Maximization (EM) Algorithm, Convex Optimization, Latent Variables, Maximum Likelihood Estimation, Stanford CS229 Machine Learning Course Website, Stanford AI Programs Information

Source: https://www.youtube.com/watch?v=bSmIGBCoffA