k-means · Stochastic Gradient Descent · The Recipe · The Curse of Dimensionality

§5.8.2 k-means clustering (concluded from last page)

k-means is representation learning by cluster membership: initialize k centroids $\{\boldsymbol{\mu}^{(1)}, \dots, \boldsymbol{\mu}^{(k)}\}$ , then alternate until convergence — assign each example to its nearest centroid; move each centroid to the mean of its assigned examples. The resulting code is a one-hot vector $\boldsymbol{h}$ ( $h_i = 1$ for your cluster, zeros elsewhere): an extreme sparse representation — cheap (one integer!), but it forfeits the advantages of distributed codes.

Aside — clustering is ill-posed: the red-trucks problem

There is no single criterion for how well a clustering matches the world. Cluster images of {red, gray} × {cars, trucks} into two groups: one algorithm finds cars-vs-trucks, another red-vs-gray — both valid. Ask for four clusters and similarity information vanishes: red cars are simply “different” from both gray cars and gray trucks, with no notion that they are MORE similar to gray cars. A distributed representation — one attribute for color, one for vehicle type — keeps both facts and measures fine-grained similarity. This argument returns as a pillar of deep representation learning (§15.4).

§5.9 Stochastic gradient descent

Nearly all of deep learning runs on one algorithm — SGD. The setup: costs decompose over examples as an average of a per-example loss (typically the negative log-likelihood ), so the full gradient is an average too — which a minibatch can cheaply estimate. Formally, costs decompose over examples,

Term by term

J(\boldsymbol{\theta}) = \mathbb{E}_{\mathrm{x}, \mathrm{y} \sim \hat{p}_{\mathrm{data}}} L(\boldsymbol{x}, y, \boldsymbol{\theta}) = \frac{1}{m} \sum_{i=1}^m L(\boldsymbol{x}^{(i)}, y^{(i)}, \boldsymbol{\theta})

$L$	the per-example loss, e.g. the negative conditional log-likelihood −log p(y\|x; θ)	one example
$\nabla_{\boldsymbol{\theta}} J$	full-batch gradient descent costs O(m) per step — prohibitive at billions of examples	the problem
$\mathbb{E}[\cdot]$	THE INSIGHT: the gradient is an expectation — and expectations can be estimated from small samples	the way out

Term by term

\boldsymbol{g} = \frac{1}{m'} \nabla_{\boldsymbol{\theta}} \sum_{i=1}^{m'} L(\boldsymbol{x}^{(i)}, y^{(i)}, \boldsymbol{\theta}), \qquad \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \epsilon\, \boldsymbol{g}

$\mathbb{B}, \; m'$	a MINIBATCH: m′ examples (1 to a few hundred) drawn uniformly from the training set — and m′ stays FIXED as m grows to billions	the estimate
$\boldsymbol{g}$	the minibatch gradient: a noisy but unbiased estimate of ∇J	noisy ∇J
$\epsilon$	the learning rate, as in ch. 4 — SGD is gradient descent following the ESTIMATED gradient downhill	step size

Why SGD is the scalability story

Cost per update: O(1) as a function of m. Better: as m → ∞, the model converges to its best test error before SGD has even touched every example — asymptotically, training costs O(1) total in m. Contrast kernel machines’ O(m²) Gram matrix. That asymmetry is why deep learning became the scalable way to train nonlinear models — first interesting academically (better generalization on medium data, 2006), then industrially. Gradient descent on non-convex losses was long “regarded as foolhardy”; today it demonstrably works — finding very low, if not minimal, cost fast enough to be useful. Chapter 8 is SGD grown up.

Reuse of ch. 4’s lab — SGD is THIS, with each gradient arrow perturbed by minibatch noise; smaller m′ = noisier steps, same expected direction

κ3.0ε0.70

show Newton's method (uses H⁻¹ — one jump)

step 0/36 · f = 169.33

Well-conditioned: contours are nearly circular and −∇f points almost straight at the minimum.

§5.10 The recipe

Nearly every deep learning algorithm is one instance of: dataset + cost + model + optimizer — swappable mostly independently.

Supervised AND unsupervised fit the same template. Swap the model to something nonlinear and closed forms die — an iterative optimizer (gradient descent) takes over; costs that can’t even be evaluated can still be minimized if their GRADIENTS can be approximated.

Algorithms that look hand-crafted (decision trees, k-means) fit too — they use special-case optimizers, needed because their costs have flat regions that defeat gradient methods. The recipe turns a zoo of algorithms into a taxonomy of interchangeable parts.

§5.11 → §5.11.1 The curse of dimensionality

Simple ML works widely — yet failed at the central AI problems (speech, objects). The rest of this chapter explains why, starting with the statistical wall: the curse of dimensionality — the number of distinct configurations of a variable set grows exponentially with the number of variables.

Fig 5.9 (recreated) — with d dimensions and v distinguishable values per axis, configurations explode as vᵈ.

The statistical consequence: with far more cells than examples, a typical cell contains no training data at all. Local recipes — report the most common class in your cell, average your cell’s targets — have nothing to say there. Most traditional algorithms fall back on assuming the answer at a new point matches its nearest training point: the smoothness prior, whose limits are the next section’s whole story.

Check yourself — k-means, SGD, the curse

1.The red-trucks story: why does the book prefer distributed representations over k-means' one-hot codes?

2.What is SGD's core insight, and what does it do to the cost of one update?

3.Why did SGD-trained models displace kernel machines on large datasets?

4.Name the four interchangeable parts of the ML recipe — and what breaks when the model goes nonlinear.

5.With d = 10 binary-ish dimensions at v = 10 values each, roughly how many cells must local methods cover — and what happens in a typical cell?

5 questions