\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML03.4 · Gaussian mixtures and the EM algorithm

A free, illustrated module of 4 lessons and one interactive in ML03 Unsupervised Learning: A mixture of Gaussians; The EM algorithm, step by step; Why EM climbs; Gaussian mixtures in the plane.

ML03.4 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of ML03 Unsupervised Learning in the Machine Learning track.

k-means gives every point one cluster and every cluster the same round shape. A Gaussian mixture gives every cluster its own centre, width and weight, and gives every point a probability of belonging to each. These four lessons build the mixture as a story of how data are made, fit it with the EM algorithm one E-step and one M-step at a time, prove that EM never lowers the likelihood (and see k-means fall out as its hard limit), and take mixtures into the plane, where covariance ellipses fit the tilted clusters that k-means cut the wrong way and BIC chooses how many components to keep.

What you need first. k-means and its objective (ML03.1), Bayes’ rule (M06.4), densities (M06.6) and maximum likelihood (S02.3). The last lesson uses eigenvectors of a symmetric matrix and the ellipses they draw (M03.3, M03.4).

Lessons

1. A mixture of Gaussians ML03.4.1 25 min

   Model data as made by a two-stage story: pick a component, then draw from its bell curve. Write the mixture density, share each point between the components by Bayes’ rule, and see why the log-likelihood has no closed-form maximum.

2. The EM algorithm, step by step ML03.4.2 25 min

   Fit a Gaussian mixture by alternating two easy steps: share each point between the components, then refit each component to its share. Derive both steps, run one full iteration by hand on the six values, and code it safely with log-sum-exp.

3. Why EM climbs ML03.4.3 25 min

   Prove that EM never lowers the likelihood: Jensen’s inequality gives a lower bound that the E-step makes touch and the M-step raises. Then find k-means as EM’s hard limit, and meet the collapse and the local optima that the proof does not rule out.

4. Gaussian mixtures in the plane ML03.4.4 25 min

   Give each component a mean vector and a covariance matrix, so that clusters can be tilted ellipses. Derive the M-step in several dimensions, count the parameters of the four covariance types, and choose K and the type by BIC and AIC.

The interactive

ML03.4-X1 · EM stepper. Points on a line or in the plane with K Gaussians drawn as curves or ellipses. Press E to shade every point by its responsibilities and M to move the means, widths and weights, or play, and watch the log-likelihood climb; a random start shows that EM can stop at a worse answer. It lives in The EM algorithm, step by step.