Density Estimation Overview

Chapter 10 had no labels and asked for a compact representation. Chapter 11 has no labels either and asks for the density itself: the third of the book’s four pillars, “density estimation, where we are interested in modeling the distribution of the data.”

The chapter opens by admitting the obvious model is inadequate — a single Gaussian cannot have two bumps — and spends the rest of itself on what it costs to fix that.

What a mixture buys, and what it costs

	one Gaussian	a mixture of $K$
parameters, $D = 1$, $K = 3$	$2$	$8$
modes	always $1$	between $1$ and $K$
fit on the kind of data Figure 11.1 shows	—	$1.388610$ nats per point better
the maximum likelihood estimate	sample mean and sample variance, Equation 11.11	does not exist
finding the parameters	one line	Sections 11.2, 11.3 and 11.4

The whole chapter follows from one structural fact. Equation 11.10 is

$$L = \sum_{n=1}^{N}\log\sum_{k=1}^{K}\pi_k\,\mathcal{N}(\mathbf{x}_n\mid\boldsymbol\mu_k,\boldsymbol\Sigma_k)$$

and the logarithm sits outside the sum over components. At $K = 1$ it lands directly on the Gaussian and the answer is closed-form — confirmed against an optimiser to $6\times10^{-8}$. At $K > 1$ it cannot be moved inside, so the chain rule drags $1/p(\mathbf{x}_n\mid\boldsymbol\theta)$ into every derivative, and every parameter’s stationarity condition mentions every other parameter.

Equation 11.20 is therefore a fixed point, not a formula. Measured: feeding the means back into their own update moves them by $4.295713$ on the first round, then $0.130775$, then $0.018414$. A formula would move them by zero.

One quantity, six appearances

The thread that runs through the chapter is a single ratio. Following it is most of understanding Chapter 11:

where it appears	equation	page	what it is called there
the factor the chain rule drags into every derivative	11.16	1102	nothing yet — it has no name
defined and named	11.17	1103	the responsibility $r_{nk}$
a softmax of minus the energies, matched to $1.1\times10^{-16}$	—	1103	a soft assignment
the weights in all three updates	11.20, 11.30, 11.42	1104–1106	importance weights
the E-step	11.53	1107	the E-step
the posterior over the latent $\mathbf{z}$, matched to $0.0$	11.69, 11.72b	1108	a posterior probability

§11.2 discovers it as an algebraic nuisance. §11.4 shows it was a posterior all along, which is what retroactively licenses everything §11.2 did with it — summing responsibilities as if they were counts, differentiating a soft assignment, alternating at all.

Three updates, one derivation

	§11.2.2 the means	§11.2.3 the covariances	§11.2.4 the weights
the update	$\frac{1}{N_k}\sum_n r_{nk}\mathbf{x}_n$	$\frac{1}{N_k}\sum_n r_{nk}(\mathbf{x}_n-\boldsymbol\mu_k)(\mathbf{x}_n-\boldsymbol\mu_k)^\top$	$N_k/N$
a weighted average of	the data	the squared deviations	nothing
needs a Lagrange multiplier	no	no	yes — $\lambda = -N$
reads the data values	yes	yes	no
nats gained on the book’s example	$12.32$	$1.46$	$0.14$

The three are the same argument at three moments. Only the weights are constrained — they live on a simplex — which is why only they need a multiplier. Contrast §10.2, where the multiplier was the answer: an eigenvalue, equal to the variance retained. Here $\lambda = -N$ is the normalising constant and carries no information at all.

Where the measuring pays off

Every printed number in the book’s running example reproduces — $28.3 \to 14.4$, the responsibility matrix, all three update examples, “after five iterations”. Six things that turned up beyond them:

The maximum likelihood estimate does not exist. §11.5 says the likelihood “approaches infinity” when a component collapses onto a data point. Measured, it reaches $+16.377668$ at $\sigma^2 = 10^{-30}$ and keeps going. Of $400$ restarts on the book’s seven points, $\mathbf{218}$ — $54.5\%$ — collapse a component, and every one reports a higher likelihood than every genuine fit. So the whole chapter is an algorithm for maximising something with no maximum, and page 1109 prices the usual patch: a variance floor buys exactly $\tfrac12\ln 10 = 1.1513$ nats per decade.

The book’s own initialisation lands in the worse of two basins. Among the honest fits there are exactly two optima. Example 11.6 converges to $-13.973323$; another basin reaches $-13.906162$, a better non-degenerate fit by $0.067161$ nats.

One entry of Equation 11.19 disagrees with the arithmetic. At $x = 0$ the book prints $0.001$ and $0.999$; the computed values are $0.000150$ and $0.999844$. The largest disagreement across the printed matrix is $0.001$ — a rounding artefact, but the responsibility matrix is the one table in the chapter a reader is most likely to reproduce by hand.

Equation 11.30 does not say which mean it uses, and it matters by a factor of $13.0878$. The old means give $1.83$, $0.60$, $19.98$; the just-updated means give the book’s $0.14$, $0.44$, $1.53$. The M-step’s ordering is the answer, and §11.3 states it only in the order the equations happen to appear.

Two conservation laws the chapter never states. After any M-step, $\sum_k N_k\boldsymbol\mu_k = \sum_n \mathbf{x}_n$ exactly — the mixture’s mean is pinned to the sample mean. Stronger: the mixture’s variance equals the sample variance exactly, measured to $3.6\times10^{-15}$ over $20{,}000$ arbitrary responsibility matrices and every $K$ from $2$ to $10$. EM cannot make the model wider or narrower than the data — it only redistributes spread between “within components” and “between components”, which is page 1101’s decomposition in motion.

The monotonicity guarantee, measured to the last bit. Over $180{,}000$ EM steps, $11{,}163$ register a negative change in $L$. None exceeds $8.9\times10^{-15}$, and the median decrease is $1.776\times10^{-15}$ — exactly one unit in the last place of a log-likelihood near $-14$. The theorem is about real numbers; a convergence test must compare against a tolerance and never against zero.

The pages

#	page	book section	the measured claim
1101	The Gaussian Mixture Model	§11.1	two Gaussians merge into one bump at exactly $2\sigma$ apart
1102	Maximum Likelihood and Its Obstacle	§11.2	$17$ optima on $7$ points; $54.5\%$ of restarts collapse
1103	Responsibilities	§11.2.1	Equation 11.17 as written returns $21$ NaNs of $21$
1104	Updating the Means	§11.2.2	$\sum_k N_k\boldsymbol\mu_k = \sum_n\mathbf{x}_n$ to $3.6\times10^{-15}$
1105	Updating the Covariances	§11.2.3	the mixture’s variance is the sample variance, always
1106	Updating the Mixture Weights	§11.2.4	the multiplier is exactly $-N$, deviation $0$
1107	The EM Algorithm	§11.3	$11{,}163$ of $180{,}000$ steps go down, by one ULP
1108	The Latent Variable Perspective	§11.4	the M-step is the exact argmax of $Q$, to $5.3\times10^{-15}$
1109	Chapter 11 Worked Problems	§11.5	eight problems, this module’s own
1110	Chapter 11 Formula Sheet	—	every equation and every measured constant

Chapter 11 has no end-of-chapter exercises

Like Chapters 8, 9 and 10, it runs straight from §11.5 into Chapter 12. Page 1109’s problems are this module’s own, built from claims the chapter makes, and should not be attributed to Deisenroth, Faisal and Ong.

About the example

The book runs two datasets: the two-dimensional cloud of Figure 11.1, and — for every number it actually prints — the seven points of Figure 11.3, $\mathcal{X} = \{-3, -2.5, -1, 0, 2, 4, 5\}$, with $K = 3$ started deliberately badly at $\boldsymbol\mu = (-4, 0, 8)$, $\boldsymbol\sigma^2 = (1, 0.2, 3)$ and $\boldsymbol\pi = (\tfrac13, \tfrac13, \tfrac13)$.

These pages use those seven points wherever the book does, so every printed value can be checked against the source. Where seven points are too few to show something — convergence rates, choosing $K$, the behaviour of a variance floor — the pages generate data from a mixture whose parameters are known, and say so.

What only the latent-variable view can do

§11.4 arrives after the algorithm already works, which makes it easy to skip. It is not optional:

what §11.2 has	what §11.4 adds	measured
$r_{nk}$, a ratio that appeared in a derivative	$r_{nk} = p(z_k=1\mid\mathbf{x}_n)$, a posterior	agreement $0.0$
three weighted averages that work	the exact argmax of $Q(\boldsymbol\theta\mid\boldsymbol\theta^{(t)})$	$5.3\times10^{-15}$ over $40$ restarts
”$L$ does not decrease” as an assertion	$L = Q + H(\mathbf{r})$, so $Q$ is a tight lower bound	$1.1\times10^{-14}$
a fitted density	a generative process — and therefore a truth to recover	errors fall $10\times$, $20\times$, $11\times$ as $N$ grows

That last row is the one that matters most in practice. Without a generative story you can measure a likelihood but you cannot ask whether the parameters are right. With one, you can generate data from known parameters, fit it, and watch the error fall — which is how every claim on pages 1107 and 1109 was checked.

What the chapter assumes, and what those assumptions cost

§11.5 is a page of caveats. Page 1109 runs each one:

the assumption	measured
“the number of components $K$ is known”	held-out likelihood, BIC and AIC pick $3$, $3$ and $4$ on one table
— and as $N$ grows	BIC reaches $20/20$; held-out likelihood peaks at $19/20$ and falls back to $14/20$
— and on data that is not a mixture of Gaussians	a uniform asks for $5$ or $6$; a Student-$t$ asks for $3$ that mean nothing
the likelihood has a maximum	it does not, and a floor only prices the singularity
the components are distinguishable	every optimum has $K!$ identical copies, spread $0.000\times10^{0}$
the non-parametric alternative	a KDE stores $600$ points to finish $13.7$ nats behind $8$ numbers

The last two rows say something worth carrying forward. A GMM’s $K$ is a count only when the data really is made of groups; otherwise it is a budget for approximating a shape, and no criterion in the chapter can tell the difference. And the clustering reading of the GMM — component $k$ is a group, $r_{nk}$ is a soft membership — is an interpretation the mathematics does not supply. §11.5’s own comparison to K-means is measured on page 1103: from the same starting means the two methods land $1.504119$ apart and split seven points $3$-$2$-$2$ against effectively $2$-$2$-$3$, because K-means has no variances with which to weigh a tight cluster against a loose one.

Where it goes next

§11.5’s pointer	and where it already appeared
K-means — the hard-assignment limit	page 1103 drove the variances to zero and measured the disagreement
nested cross-validation for choosing $K$	page 1109 ran it, and found where it stops working
a Bayesian prior on the parameters	removes the singularity page 1102 measured; gives the model evidence BIC approximates
variational inference for the resulting posterior	Chapter 8’s §8.4, and the marginal likelihood of page 908
EM for general latent-variable models	page 1108’s $Q$ and $H(\mathbf{r})$ never mention Gaussians
kernel density estimation	page 1109 put it on the same held-out set

And the last pillar: Chapter 12 turns to classification, with support vector machines.

Recall card

• Chapter 11 estimates a density, the third pillar, and starts by admitting a single Gaussian often cannot do it.
• A mixture buys multimodality cheaply — 1.388610 nats per point for twelve extra parameters — and pays with the closed form.
• The logarithm in Equation 11.10 sits outside a sum over components, so it cannot reach the Gaussians, and every parameter’s equation ends up mentioning every other.
• So Equation 11.20 is a fixed point, not a formula. Feeding it back into itself moves the means by 4.295713 on the first round.
• One ratio appears six times under five names — a nuisance factor in a derivative, the responsibility, a softmax, an importance weight, the E-step, and finally a posterior.
• Section 11.4 is what licenses Section 11.2, retroactively: summing responsibilities as counts and differentiating a soft assignment are only legitimate because the responsibility is a posterior.
• The three updates are one derivation run at three moments, and only the mixture weights need a Lagrange multiplier because only they are constrained.
• EM conserves the data’s mean and its variance exactly, after every M-step, for every K. It only moves spread between within-component and between-component.
• The maximum likelihood estimate does not exist. The likelihood is unbounded above, 54.5 percent of restarts on seven points collapse a component, and every collapse outscores every honest fit.
• The monotonicity guarantee holds to one unit in the last place, so convergence must be tested against a tolerance rather than against zero.
• Overlap sets the convergence rate — 1045 iterations at 53 percent ambiguous against 3 at none — and a K-means initialisation removes the long tail.
• The chapter’s heaviest assumption is that K is known. Held-out likelihood is not even a consistent estimator of it, and on data that is not a mixture of Gaussians K stops being a count at all.

Start here: The Gaussian Mixture Model