Advanced Machine Learning

17: Expectation Maximization

Schedule (you are here )

# date topic description
124-Aug-2026Introduction
226-Aug-2026Foundations of learningDrop/Add
331-Aug-2026PAC learnabilityHW1
402-Sep-2026Linear learning models
507-Sep-2026Labor Day HolidayHoliday
609-Sep-2026Principal Component AnalysisProject ideas
714-Sep-2026Curse of DimensionalityHW2, HW1 due
816-Sep-2026Bayesian Decision Theory
921-Sep-2026Parameter estimation: MLE
1023-Sep-2026Parameter estimation: MAP & NBfinalize teams
1128-Sep-2026Logistic RegressionHW3, HW2 due
1230-Sep-2026Kernel Density Estimation
1305-Oct-2026Support Vector Machines
1407-Oct-2026Matrix Factorization
1512-Oct-2026* MidtermExam, HW3 due
1614-Oct-2026k-means clustering
1719-Oct-2026Invited: Intro to Causal Learning I
# date topic description
1821-Oct-2026Invited: Intro to Causal Learning II
1926-Oct-2026* Mid-point projects checkpointHW4, P
2028-Oct-2026Expectation Maximization
2102-Nov-2026Stochastic Gradient Descent
2204-Nov-2026Automatic Differentiation
2309-Nov-2026Nonlinear embedding approachesHW5, HW4 due
2411-Nov-2026Model comparison
2516-Nov-2026Model Calibration
2618-Nov-2026Convolutional Neural Networks
2723-Nov-2026Thanksgiving BreakHoliday
2825-Nov-2026Thanksgiving BreakHoliday
2930-Nov-2026Word Embedding
3002-Dec-2026Project Final PresentationsHW5 due, P
3107-Dec-2026Presentation spillover / Exam prepClasses End
3209-Dec-2026* Final ExamExam
3316-Dec-2026Project Reportsdue
3417-Dec-2026Grades due 5 p.m.PAWS

Outline for the lecture

  • Do we even need EM for GMM? (Log-Sum & Singularity Collapse)
  • GMM Estimation: A Hack (Pseudo-Newton & Soft K-Means)
  • Convexity, Jensen's Inequality & Derivation of EM
  • KL Divergence, ELBO & Variational View of EM
  • General Multivariate GMMs via EM & Practical Guide
  • Take Home Points

Connecting the Dots: The Road to Expectation Maximization

1. Foundations & Linear Representations
ERM, PAC generalization, linear models, PCA subspace projections, and the curse of dimensionality.
2. Bayesian Decision & Parametric MLE / MAP
When labels $y$ are observed, exponential-family log-likelihoods decouple nicely into closed-form MLE/MAP updates.
3. Non-parametric & Kernel Methods
Parzen windows / KDE place a kernel at every $N$ points; SVMs sparsify boundaries via KKT conditions.
4. Unsupervised Structure: Factorization & K-Means
Alternating minimization (hard & soft K-means) partitions unlabeled data into $K$ clusters heuristically.
5. Today: Latent Variables & Expectation Maximization
How do we perform rigorous Maximum Likelihood Estimation when cluster memberships $\vec{z}$ are hidden/missing?
# date topic
2–4Aug–SepERM, PAC & Linear Models
6–709–14 SepPCA & Curse of Dimensionality
816-Sep-2026Bayesian Decision Theory
9–1021–23 SepParameter Estimation: MLE, MAP & NB
1128-Sep-2026Logistic Regression
1230-Sep-2026Kernel Density Estimation
1305-Oct-2026Support Vector Machines
1407-Oct-2026Matrix Factorization
1614-Oct-2026k-means clustering
17–1819–21 OctIntro to Causal Learning I & II
1926-Oct-2026Mid-point projects checkpoint
2028-Oct-2026Expectation Maximization

Do we even need EM for GMM?

Gaussian Mixture Model

Likelihood: $\prob{p}{\vec{x}} = \sum_{k=1}^K \pi_k\prob{N}{\vec{x}|\vec{\mu}_k, \bm{\Sigma}_k}$
$$\begin{aligned} \mbox{for simplicity }\bm{\Sigma}_k & = \sigma^2 \bm{I}\\ \prob{p}{\vec{x}|y=k} & = \prob{N}{\vec{\mu}_k, \sigma^2 \bm{I}}\\ \prob{p}{y=k} & = \pi_k\\ \mbox{parameters: } & \vec{\mu}_1, \dots, \vec{\mu}_K, \; \sigma^2, \; \pi_1, \dots, \pi_K \end{aligned}$$
But do we even need the hidden variables?

Maximum (Log) Likelihood Estimation

$$\ln \prob{p}{\bm{X}|\{\vec{\mu}_k\}, \{\bm{\Sigma}_k\}, \{\pi_k\}} = \sum_{n=1}^N \ln\left\{\sum_{k=1}^K \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \sigma_k^2\bm{I}} \right\}$$

Difficult to optimize

  • Remember the exponential family? $$\prob{p}{\vec{x}|\vec{\eta}} = \prob{h}{\vec{x}}\prob{g}{\vec{\eta}}e^{\vec{\eta}^T\prob{u}{\vec{x}}}$$
  • How easy the $\log$-likelihood was back then: $$\begin{aligned} \log{\cal L} & = \sum \log \prob{p}{\vec{x}|\vec{\eta}} = \sum \log \prob{h}{\vec{x}} + \sum \log \prob{g}{\vec{\eta}} + \sum \vec{\eta}^T\prob{u}{\vec{x}} \end{aligned}$$
  • But a mixture $\sum_{k=1}^K \pi_k \prob{p}{\vec{x}|\vec{\eta}_k}$ is not in the exponential family!
  • The sum inside the logarithm prevents $\ln$ from canceling $\exp$:
    $$\ln \prob{p}{\bm{X}| \{\vec{\mu}_k\}, \{\bm{\Sigma}_k\}, \{\pi_k\}} = \sum_{n=1}^N\ln\left\{\sum_{k=1}^K \pi_k\prob{N}{\vec{x}_n|\vec{\mu}_k, \sigma_k^2\bm{I}} \right\}$$

Another problem (common to MLE)

  • Suppose $K = 2$
  • Suppose one component centers right on a single data point: $\vec{\mu}_k = \vec{x}_i$
  • What is going to happen with our MLE? $${\cal N}(x_i | \mu_k, \sigma_k^2) = \frac{1}{\sqrt{2\pi\sigma_k^2}} e^{-\frac{(x_i-\mu_k)^2}{2\sigma_k^2}}$$
MLE collapse
$${\cal N}(x_i \mid \mu_k = x_i, \sigma_k^2) = \frac{1}{\sqrt{2\pi}\,\sigma_k} \to \infty \quad \text{as} \quad \sigma_k \to 0$$

GMM MLE Singularity & Variance Collapse

Drag μ₂ onto xᵢ = 8.20 and shrink σ₂ → 0 to see unconstrained MLE blow up.
Spike Height: -- Log-Likelihood ln P(X|θ): --

GMM estimation: a hack

Mixture of 2 Gaussians

  • $$\prob{p}{x_n|\mu_1, \mu_2, \sigma} = \sum_{k=1}^2 \pi_k\prob{N}{x_n|\mu_k, \sigma^2}$$
  • $$\prob{p}{x_n|\mu_1, \mu_2, \sigma} = \sum_{k=1}^2 \pi_k\frac{1}{\sqrt{2\pi\sigma^2}}\exp{\left(-\frac{(x_n-\mu_k)^2}{2\sigma^2}\right)}$$
  • Let's assume $\pi_1 = \pi_2 = 1/2$ and pack parameters into $\vec{\theta} = \{\mu_1, \mu_2, \sigma\}$

Mixture of 2 Gaussians

assuming known $\mu_k$ and $\sigma$

$$\begin{aligned} \prob{P}{k=1|x_n,\vec{\theta}} & = \frac{1}{1 + \exp{\left[-(w_1x_n+w_0)\right]}}\\ \prob{P}{k=2|x_n,\vec{\theta}} & = \frac{1}{1 + \exp{\left[+(w_1x_n+w_0)\right]}} \end{aligned}$$
recall logistic regression and softmax!

Mixture of 2 Gaussians

assuming known $\sigma$ but not $\mu_k$

  • $$\prob{p}{x_n|\mu_1, \mu_2, \sigma} = \sum_{k=1}^2 \pi_k\frac{1}{\sqrt{2\pi\sigma^2}}\exp{\left(-\frac{(x_n-\mu_k)^2}{2\sigma^2}\right)}$$
  • $$\prob{p}{\bm{X}|\mu_1, \mu_2, \sigma} = \underset{n}{\prod} \prob{p}{x_n|\mu_1, \mu_2, \sigma}$$
  • Taking the derivative of the log-likelihood ${\cal L} = \ln \prob{p}{\bm{X}|\vec{\theta}}$: $$\frac{\partial {\cal L}}{\partial \mu_k} = \sum_n \prob{P}{k|x_n,\vec{\theta}} \frac{x_n-\mu_k}{\sigma^2}$$

Mixture of 2 Gaussians

assuming known $\sigma$ but not $\mu_k$

  • First derivative of the log-likelihood: $$\frac{\partial {\cal L}}{\partial \mu_k} = \sum_n \prob{P}{k|x_n,\vec{\theta}} \frac{x_n-\mu_k}{\sigma^2}$$
  • Approximate second derivative$^{*}$: $$\frac{\partial^2 {\cal L}}{\partial \mu_k^2} \approx -\sum_n \prob{P}{k|x_n,\vec{\theta}} \frac{1}{\sigma^2}$$

Mixture of 2 Gaussians

assuming known $\sigma$ but not $\mu_k$

Using the good old Newton-Raphson update: $\mu_k \leftarrow \mu_k - \frac{\partial {\cal L}}{\partial \mu_k}\Big/\frac{\partial^2 {\cal L}}{\partial \mu_k^2}$
Yields the weighted average update: $$\mu_k = \frac{\sum_n \prob{P}{k|x_n,\vec{\theta}} x_n}{\sum_n \prob{P}{k|x_n,\vec{\theta}} }$$

Compare to soft k-means: Iterations

Update
  • Re-estimate the $K$ cluster centers (aka the centroid or mean), by assuming the memberships found above are correct: $$\begin{aligned} \hat{\vec{\mu}}_k &= \frac{\underset{n}{\sum}r_k^n \vec{x}_n}{R_k}, \qquad R_k = \underset{n}{\sum} r_k^n \end{aligned}$$

GMMs and k-means

  • Responsibilities $r_k^n = \prob{P}{k|\vec{x}_n,\vec{\theta}}$ are posteriors over latent cluster assignments
  • Update is maximization of the likelihood holding responsibilities fixed
Both "hacky" approaches to solve a latent variable problem are instances of a rigorous general principle:
Expectation Maximization (EM): a meta-algorithm

too important to simply skim!

EM paper

Convexity

Convexity

Shades of Convex

Convex
x f(x) Flat plateau: f′′(x) = 0 f(x) = max(0, |x| − 1)²
$f''(x) \ge 0$ (chord $\ge$ curve).
Flat/linear segments allowed $\implies$ minimum need not be unique.
Strictly convex
x f(x) −ln(x) Unique min (even with f′′(0) = 0) f(x) = x⁴ or −ln(x)
Chord strictly above curve ($x_1 \ne x_2$).
No flat segments $\implies$ unique minimum (even if $f''(x)=0$ at a point).
Strongly convex
x f(x) f′′(x) ≥ m > 0 everywhere f(x) = x² (bounded below by m/2 x²)
$f''(x) \ge m > 0$ everywhere.
Grows at least as fast as a quadratic bowl $\frac{m}{2}(x-x_0)^2$ $\implies$ fast convergence!

Convexity

Theorem:
If $f(x)$ is twice differentiable on $[a,b]$ and $f^{\prime \prime}(x) \ge 0$ on $[a,b]$ then $f(x)$ is convex on $[a,b]$.

Convexity of logarithm

Theorem:
$-\ln(x)$ is strictly convex on $(0, \infty)$   $\left(\text{since } \frac{d^2}{dx^2}[-\ln x] = \frac{1}{x^2} > 0\right)$

Jensen's inequality

Theorem:
Let $f$ be a convex function on an interval $I$. If $x_1, x_2, \dots, x_n \in I$ with $\lambda_1, \lambda_2, \dots, \lambda_n \ge 0$ and $\sum_{i=1}^n\lambda_i=1$: $$f\left(\sum_{i=1}^n\lambda_ix_i\right) \le \sum_{i=1}^n \lambda_i f(x_i)$$

Thanks to Jensen's inequality

Since $-\ln(x)$ is strictly convex, $\ln(x)$ is strictly concave, which reverses the inequality: $$\ln\left(\sum_{i=1}^n\lambda_ix_i\right) \ge \sum_{i=1}^n \lambda_i \ln{(x_i)}$$
In expectation notation (for $\lambda_i = q(z_i)$):   $\ln \EE_{q}[X] \ge \EE_{q}[\ln X]$, with equality iff $x_1 = x_2 = \dots = x_n$.
Now we are ready!

Jensen's Inequality: Log of Sum vs. Sum of Logs

Curve (Log of Sum) f(E[X]): 0.869 Secant Chord (Sum of Logs) E[f(X)]: 0.540 Jensen Gap: 0.329

Derivation of EM algorithm

  • Our goal is to maximize the log-likelihood function: $$\prob{L}{\vec{\theta}} = \ln \prob{P}{\bm{X}|\vec{\theta}}$$
  • Equivalently, if at step $n$ we have $\vec{\theta}_n$, we want $\vec{\theta}$ such that: $$\prob{L}{\vec{\theta}} \gt \prob{L}{\vec{\theta}_n}$$
  • Yet equivalently, we want to maximize the improvement: $$\prob{L}{\vth} - \prob{L}{\vec{\theta}_n} = \ln\prob{P}{\bm{X}|\vec{\theta}} - \ln\prob{P}{\bm{X}|\vec{\theta}_n}$$
  • Looks difficult!

Introducing latent random variables $\vec{z}$

  • By marginalization over the hidden variables $\vec{z}$: $$\prob{P}{\bm{X}|\vec{\theta}} = \sum_{\vec{z}} \prob{P}{\bm{X}|\vec{z}, \vth}\prob{P}{\vec{z}|\vth}$$
  • Our objective improvement: $$\prob{L}{\vth} - \prob{L}{\vec{\theta}_n} = \ln\prob{P}{\bm{X}|\vec{\theta}} - \ln\prob{P}{\bm{X}|\vec{\theta}_n}$$
  • Becomes: $$\prob{L}{\vth} - \prob{L}{\vec{\theta}_n} = \underbrace{\ln \sum_{\vec{z}} \prob{P}{\bm{X}|\vec{z}, \vth}\prob{P}{\vec{z}|\vth}}_{\text{log of a sum!}} - \ln\prob{P}{\bm{X}|\vec{\theta}_n}$$

How can we push $\ln$ inside the sum?

Jensen's inequality $\ln\left(\sum_{\vec{z}} \lambda_{\vec{z}} x_{\vec{z}}\right) \ge \sum_{\vec{z}} \lambda_{\vec{z}} \ln(x_{\vec{z}})$ needs weights $\lambda_{\vec{z}} \ge 0$ with $\sum_{\vec{z}} \lambda_{\vec{z}} = 1$.
  • Any probability distribution over the hidden variables $\vec{z}$ sums to $1$!
  • At step $n$, what is our best guess for $\vec{z}$ given $\bm{X}$ and current $\vth_n$?
  • $$\lambda_{\vec{z}} = \prob{P}{\vec{z}|\bm{X}, \vth_n} \qquad \left(\text{since } \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} = 1\right)$$
  • Trick: multiply and divide inside the sum by $\prob{P}{\vec{z}|\bm{X}, \vth_n}$!

Modifying the objective

$$\prob{L}{\vth} - \prob{L}{\vth_n} = \ln \sum_{\vec{z}} \prob{P}{\bm{X}|\vec{z}, \vth}\prob{P}{\vec{z}|\vth} \cdot \color{#268bd2}{\frac{\prob{P}{\vec{z}|\bm{X}, \vth_n}}{\prob{P}{\vec{z}|\bm{X}, \vth_n}}} - \ln \prob{P}{\bm{X}|\vth_n}$$
$$\color{#cb4b16}{\ge} \sum_{\vec{z}} \color{#268bd2}{\prob{P}{\vec{z}|\bm{X}, \vth_n}} \ln \left( \frac{\prob{P}{\bm{X}|\vec{z}, \vth}\prob{P}{\vec{z}|\vth}}{\color{#268bd2}{\prob{P}{\vec{z}|\bm{X}, \vth_n}}} \right) - \ln \prob{P}{\bm{X}|\vth_n}$$
$$= \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \left( \frac{\prob{P}{\bm{X}|\vec{z}, \vth}\prob{P}{\vec{z}|\vth}}{\prob{P}{\vec{z}|\bm{X}, \vth_n}\prob{P}{\bm{X}|\vth_n}} \right) \;\def\; \mathbf{\Delta(\vth|\vth_n)}$$

Why is $\Delta(\vth|\vth_n)$ tractable to optimize?

Use $\ln(A/B) = \ln A - \ln B$ and $\prob{P}{\bm{X}|\vec{z},\vth}\prob{P}{\vec{z}|\vth} = \prob{P}{\bm{X},\vec{z}|\vth}$ to split the $\ln$:

$\displaystyle \Delta(\vth|\vth_n) = \sum_{\vec{z}} \underbrace{\color{#268bd2}{\prob{P}{\vec{z}|\bm{X}, \vth_n}}}_{\substack{\text{fixed weights}\\ \text{(only old }\vth_n\text{!)}}} \ln \underbrace{\color{#859900}{\prob{P}{\bm{X}, \vec{z}|\vth}}}_{\substack{\text{complete-data likelihood}\\ \text{(no sum inside }\ln\text{!)}}} \;-\; \underbrace{\sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \big(\prob{P}{\vec{z}|\bm{X}, \vth_n}\prob{P}{\bm{X}|\vth_n}\big)}_{\text{constant w.r.t. }\vth\text{!}}$
  • 1. No sum inside $\ln$: $\sum_{\vec{z}}$ sits outside the logarithm (a weighted sum of logs!).
  • 2. Old $\vth_n$ terms are frozen: $\prob{P}{\vec{z}|\bm{X}, \vth_n}$ and the second sum do not depend on $\vth$ at all!
  • 3. Complete-data $\ln \prob{P}{\bm{X}, \vec{z}|\vth}$ is easy: Pretends hidden $\vec{z}$ is observed, so $\ln$ acts directly on a single component distribution (where $\ln$ cancels $\exp$!).

Why $\Delta(\vth|\vth_n)$ and what is ${\cal L}(\vth|\vth_n)$?

$\displaystyle \underbrace{\prob{L}{\vth} - \prob{L}{\vth_n}}_{\text{True improvement}} \;\ge\; \underbrace{\Delta(\vth|\vth_n)}_{\text{Guaranteed improvement}}$
  • What is $\Delta(\vth|\vth_n)$? A tractable floor on how much $\vth$ improves over $\vth_n$. If $\Delta(\vth|\vth_n) > 0$, then $\prob{L}{\vth} > \prob{L}{\vth_n}$ is guaranteed!
  • Move $\prob{L}{\vth_n}$ to the right-hand side to define the lower bound ${\cal L}(\vth|\vth_n)$:
    $\displaystyle \prob{L}{\vth} \;\ge\; \underbrace{\prob{L}{\vth_n} + \Delta(\vth|\vth_n)}_{\def\; {\cal L}(\vth|\vth_n)}$
  • What is ${\cal L}(\vth|\vth_n)$? A simple curve (sum of logs!) that lies completely underneath the difficult log-likelihood $\prob{L}{\vth}$.

When does $\prob{L}{\vth} = {\cal L}(\vth|\vth_n)$?

$${\cal L}(\vth_n|\vth_n) = \prob{L}{\vth_n} + \Delta(\vth_n|\vth_n)$$
$$= \prob{L}{\vth_n} + \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \frac{\overbrace{\prob{P}{\bm{X}|\vec{z}, \vth_n}\prob{P}{\vec{z}|\vth_n}}^{\prob{P}{\bm{X}, \vec{z}|\vth_n}}}{\underbrace{\prob{P}{\vec{z}|\bm{X}, \vth_n}\prob{P}{\bm{X}|\vth_n}}_{\prob{P}{\bm{X}, \vec{z}|\vth_n}}}$$
$$= \prob{L}{\vth_n} + \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \underbrace{\ln 1}_{0} = \prob{L}{\vth_n}$$
At $\vth = \vth_n$, the lower bound ${\cal L}(\vth|\vth_n)$ touches $\prob{L}{\vth}$!

What happens when we optimize ${\cal L}(\vth|\vth_n)$?

EM figure iterative
$\displaystyle \prob{L}{\vth_{n+1}} \;\ge\; {\cal L}(\vth_{n+1}|\vth_n) \;\ge\; {\cal L}(\vth_n|\vth_n) \;=\; \prob{L}{\vth_n}$

Minorize-Maximize & Surrogate Lower Bounds

E-Step Active: Surrogate touches L(θ) at θₜ.
EM Cycle:
Iter: 0 θₜ: 4.35 L(θₜ): --
Seed Initialization:

What happens when we optimize ${\cal L}(\vth|\vth_n)$?

$$\vth_{n+1} = \underset{\vth}{\argmax}\; {\cal L}(\vth|\vth_n) = \underset{\vth}{\argmax} \left\{ \cancel{\prob{L}{\vth_n}} + \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \frac{\prob{P}{\bm{X}|\vec{z}, \vth}\prob{P}{\vec{z}|\vth}}{\cancel{\prob{P}{\bm{X}|\vth_n}\prob{P}{\vec{z}|\bm{X}, \vth_n}}} \right\}$$
Drop terms that do not depend on $\vth$: $$\vth_{n+1} = \underset{\vth}{\argmax} \left\{ \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \prob{P}{\bm{X}, \vec{z}|\vth} \right\}$$
$\displaystyle \vth_{n+1} = \underset{\vth}{\argmax} \; \underbrace{\EE_{\vec{z}|\bm{X}, \vth_n}\!\left[ \ln \prob{P}{\bm{X}, \vec{z}|\vth} \right]}_{\def\; Q(\vth|\vth_n)}$

The EM Algorithm

1. Expectation Step (E-Step): Build the analytical objective $Q(\vth|\vth_n)$
Requires a known analytical form for the complete-data log-likelihood $\ln \prob{P}{\bm{X}, \vec{z}|\vth}$!
Evaluate posterior $\prob{P}{\vec{z}|\bm{X}, \vth_n}$ at fixed $\vth_n$, keeping $\vth$ as a free symbolic variable:
$\displaystyle Q(\vth|\vth_n) = \EE_{\vec{z}|\bm{X},\vth_n}\!\left[\ln \prob{P}{\bm{X}, \vec{z}|\vth}\right] = \sum_{\vec{z}} \underbrace{\prob{P}{\vec{z}|\bm{X}, \vth_n}}_{\text{numbers (at }\vth_n\text{)}} \;\cdot\; \underbrace{\ln \prob{P}{\bm{X}, \vec{z}|\vth}}_{\text{analytical formula in }\vth}$
2. Maximization Step (M-Step): Maximize $Q(\vth|\vth_n)$ over $\vth$
$\displaystyle \vth_{n+1} = \underset{\vth}{\argmax} \; Q(\vth|\vth_n) \qquad \Big(\text{solve } \nabla_{\vth} Q(\vth|\vth_n) = \vec{0}\Big)$

How big is the gap $\prob{L}{\vth} - {\cal L}(\vth|\vth_n)$?

  • Away from $\vth_n$, the true log-likelihood $\prob{L}{\vth}$ sits strictly above the lower bound ${\cal L}(\vth|\vth_n)$.
  • Using $\prob{P}{\bm{X}, \vec{z}|\vth} = \prob{P}{\vec{z}|\bm{X}, \vth}\prob{P}{\bm{X}|\vth}$, the vertical gap is: $$\prob{L}{\vth} - {\cal L}(\vth|\vth_n) = \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \frac{\prob{P}{\vec{z}|\bm{X}, \vth_n}}{\prob{P}{\vec{z}|\bm{X}, \vth}} \;\ge\; 0$$
  • This gap between two distributions $q(\vec{z})$ and $p(\vec{z})$ is the Kullback-Leibler (KL) Divergence!

Kullback-Leibler (KL) Divergence

How different is distribution $q$ from target distribution $p$?
$$D_{\text{KL}}(q \parallel p) \;\def\; \sum_{\vec{z}} q(\vec{z}) \ln \frac{q(\vec{z})}{p(\vec{z})} \;=\; \EE_{q}\!\left[\ln \frac{q(\vec{z})}{p(\vec{z})}\right]$$
  • Always non-negative (by Jensen's inequality):   $D_{\text{KL}}(q \parallel p) \ge 0$
  • Zero iff distributions match:   $D_{\text{KL}}(q \parallel p) = 0 \iff q(\vec{z}) = p(\vec{z})$
  • Asymmetric (order matters!):   $D_{\text{KL}}(q \parallel p) \ne D_{\text{KL}}(p \parallel q)$

Kullback-Leibler divergence: Asymmetry

KLD
Left: $\argmin_q D_{\text{KL}}(p \parallel q)$ spreads over all modes  |  Right: $\argmin_q D_{\text{KL}}(q \parallel p)$ locks onto one mode (used in EM!)

Forward vs. Reverse KL Divergence

Optimize q(x):
D_KL(p∥q): -- D_KL(q∥p): --

Yet another view of EM: ELBO

For any probability distribution $q(\vec{z})$ over the hidden variables:

$\displaystyle \underbrace{\ln \prob{P}{\bm{X}|\vth}}_{\text{True Log-Likelihood } L(\vth)} \;=\; \underbrace{\sum_{\vec{z}} q(\vec{z}) \ln \frac{\prob{P}{\bm{X}, \vec{z}|\vth}}{q(\vec{z})}}_{\text{Evidence Lower Bound } \text{ELBO}(q, \vth)} \;+\; \underbrace{D_{\text{KL}}\!\left(q(\vec{z}) \;\middle\|\; \prob{P}{\vec{z}|\bm{X}, \vth}\right)}_{\text{Gap } \ge\, 0}$
  • E-Step (fix $\vth_n$, optimize $q$): Set $q(\vec{z}) = \prob{P}{\vec{z}|\bm{X}, \vth_n}$ so the gap $D_{\text{KL}} = 0$ (lower bound touches $L(\vth_n)$!).
  • M-Step (fix $q$, optimize $\vth$): Maximize $\text{ELBO}(q, \vth)$ over $\vth$ (climb to the peak of the lower bound!).
  • If true $\prob{P}{\vec{z}|\bm{X}, \vth}$ is intractable, pick the closest tractable $q(\vec{z})$ $\implies$ Variational Inference & VAEs!

EM for Gaussian Mixture Models

GMM: From Mixture Sum to Latent Product

  • Observed (incomplete) log-likelihood has a sum trapped inside the $\ln$:
    $\displaystyle \ln \prob{P}{\bm{X}|\vth} = \sum_{n=1}^N \ln \left\{ \sum_{k=1}^K \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k} \right\}$
  • Introduce a 1-of-$K$ binary indicator $\vec{z}_n = (z_{n1}, \dots, z_{nK}) \in \{0, 1\}^K$ with $\sum_{k=1}^K z_{nk} = 1$ ($z_{nk}=1$ if point $\vec{x}_n$ came from cluster $k$, and $0$ otherwise).
  • Since $a^1 = a$ and $a^0 = 1$, picking cluster $k$ becomes a product of powers:
    $\displaystyle \prob{P}{\vec{z}_n|\vth} = \prod_{k=1}^K \pi_k^{z_{nk}}, \qquad \prob{P}{\vec{x}_n|\vec{z}_n, \vth} = \prod_{k=1}^K \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k}^{z_{nk}}$
    $\displaystyle \implies \prob{P}{\bm{X}, \bm{Z}|\vth} = \prod_{n=1}^N \prod_{k=1}^K \Big[ \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k} \Big]^{z_{nk}}$

Why latent variables make GMM easy

Now take $\ln$ of the product $\prob{P}{\bm{X}, \bm{Z}|\vth}$ — the exponent $z_{nk}$ comes down in front!

$\displaystyle \ln \prob{P}{\bm{X}, \bm{Z} | \vth} = \ln \prod_{n=1}^N \prod_{k=1}^K \Big[ \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k} \Big]^{z_{nk}} = \sum_{n=1}^N \sum_{k=1}^K z_{nk} \Big[ \ln \pi_k + \ln \prob{N}{\vec{x}_n | \vec{\mu}_k, \bm{\Sigma}_k} \Big]$
  • Because $\ln \prob{P}{\bm{X}, \bm{Z}|\vth}$ is linear in $z_{nk}$, taking $\EE_{\bm{Z}|\bm{X}, \vth_n}[\cdot]$ in the E-step simply replaces $z_{nk}$ with its expected value $\gamma_{nk}$:
    $\displaystyle Q(\vth|\vth_n) = \sum_{n=1}^N \sum_{k=1}^K \gamma_{nk} \Big[ \ln \pi_k + \ln \prob{N}{\vec{x}_n | \vec{\mu}_k, \bm{\Sigma}_k} \Big]$
    $\displaystyle \text{where } \gamma_{nk} \;\def\; \EE[z_{nk} | \vec{x}_n, \vth_n] = \prob{P}{z_{nk} = 1 | \vec{x}_n, \vth_n}$

GMM: E-Step and M-Step

1. E-Step: Soft responsibilities $\gamma_{nk}$ and effective cluster size $N_k$
$$\gamma_{nk} = \frac{\pi_k \prob{N}{\vec{x}_n \mid \vec{\mu}_k, \bm{\Sigma}_k}}{\sum_{j=1}^K \pi_j \prob{N}{\vec{x}_n \mid \vec{\mu}_j, \bm{\Sigma}_j}}, \qquad N_k = \sum_{n=1}^N \gamma_{nk}$$
2. M-Step: Update means, covariances, and mixing weights
$$\begin{aligned} \vec{\mu}_k^{\text{new}} &= \frac{1}{N_k} \sum_{n=1}^N \gamma_{nk} \vec{x}_n, \qquad \pi_k^{\text{new}} = \frac{N_k}{N} \\ \bm{\Sigma}_k^{\text{new}} &= \frac{1}{N_k} \sum_{n=1}^N \gamma_{nk} (\vec{x}_n - \vec{\mu}_k^{\text{new}})(\vec{x}_n - \vec{\mu}_k^{\text{new}})^T \end{aligned}$$

2D Multivariate GMM EM Playground

Stage: Initialized Iter: 0 ln P(X|θ): --
Each point's pie chart shows γₙₖ = P(zₙ = k | xₙ).

K-Means is a Limit of GMM EM

Fix spherical covariance $\bm{\Sigma}_k = \sigma^2 \bm{I}$ and equal weights $\pi_k = 1/K$:
$\displaystyle \gamma_{nk} = \frac{\exp\!\left(-\frac{\|\vec{x}_n - \vec{\mu}_k\|^2}{2\sigma^2}\right)}{\sum_{j=1}^K \exp\!\left(-\frac{\|\vec{x}_n - \vec{\mu}_j\|^2}{2\sigma^2}\right)} \;\xrightarrow{\;\sigma^2 \to 0\;}\; \begin{cases} 1 & \text{if } k = \argmin_j \|\vec{x}_n - \vec{\mu}_j\|^2 \\ 0 & \text{otherwise} \end{cases}$
  • Hard K-Means: $\sigma^2 \to 0$ limit with hard $\{0, 1\}$ assignments and spherical clusters.
  • Full GMM via EM: Soft responsibilities $\gamma_{nk} \in [0, 1]$ and elliptical clusters $\bm{\Sigma}_k$.

Take Home Points

  • Why Direct MLE Fails on Mixtures: $\ln \sum_k \pi_k {\cal N}_k$ traps a sum inside the $\log$ and suffers from $\sigma_k \to 0$ singularities.
  • Jensen's Inequality Builds a Lower Bound: Concavity of $\ln$ turns the log-of-sums into a tractable sum-of-logs curve ${\cal L}(\vth|\vth_n) = \prob{L}{\vth_n} + \Delta(\vth|\vth_n) \le \prob{L}{\vth}$.
  • Why EM Never Goes Downhill: ${\cal L}(\vth|\vth_n)$ touches $\prob{L}{\vth}$ at $\vth_n$ ($\Delta(\vth_n|\vth_n)=0$), so maximizing ${\cal L}$ guarantees $\prob{L}{\vth_{n+1}} \ge \prob{L}{\vth_n}$.
  • The Gap is KL Divergence: $\prob{L}{\vth} = \text{ELBO}(q, \vth) + D_{\text{KL}}\!\left(q(\vec{z}) \parallel \prob{P}{\vec{z}|\bm{X},\vth}\right)$.
  • E-Step vs. M-Step: E-step sets $q(\vec{z}) = \prob{P}{\vec{z}|\bm{X},\vth_n}$ (closing the KL gap to $0$); M-step maximizes expected complete log-likelihood $Q(\vth|\vth_n)$.