Generalization requires prior beliefs about which function to learn — sometimes explicit distributions over parameters (MAP), sometimes beliefs about the function itself, sometimes purely implicit biases baked into the algorithm. The most widely used implicit prior of traditional ML is the smoothness (local constancy) prior smoothness prior f(x) ≈ f(x+ε): the implicit prior of k-NN/local kernels/trees — needs O(k) examples for O(k) regions and can't extrapolate a checkerboard; DL's composition assumption gets O(2ᵏ). defined in ch. 5 — open in glossary :
Term by term
| the function to be learned — assumed not to change much within small regions | the belief | |
| a small perturbation: a good answer at a training point is presumed good in its neighborhood; several nearby answers get averaged/interpolated | local |
Who relies on it, and how hard:
- k-NN — the extreme case: literally constant on each region sharing the same k neighbors; for k = 1, no more distinguishable regions than training examples (fig 5.10’s Voronoi cells below).
- Kernel machines with local kernels — interpolate between nearby training outputs; a local kernel (large at u = v, decaying with distance) is a similarity-based template matcher. Much of deep learning’s motivation came from studying where local template matching fails.
- Decision trees — one output per leaf: a target needing n leaves needs at least n examples (a multiple of n for any statistical confidence).
Fig 5.10 (recreated) — nearest-neighbor regions form a Voronoi diagram: each example governs one contiguous region, so regions cannot outnumber examples. Every purely-local learner behaves this way at heart.
The accounting: distinguishing O(k) regions costs these methods O(k) examples (and O(k) parameters). Can a function with many more regions than examples be learned at all? Not from smoothness alone — the book’s checkerboard makes it visceral:
predicted board accuracy: 48%
The smoothness prior copies the nearest blue-dotted example: correct only near examples, and each example teaches at most its own square — ~one example per region needed.
blue dots: revealed training cells · red slash: wrong prediction · truth is an 8×8 checkerboard
With only the local prior, an example teaches you its own square and nothing beyond; extending the pattern to unvisited squares is exactly what locality cannot license.
The escape — and deep learning’s bet
The answer to “can we do better?” is yes: O(2ᵏ) regions CAN be pinned down by O(k) examples — if assumptions introduce dependencies between regions. Task-specific assumptions work (assume periodicity and the checkerboard falls to one example) but don’t transfer. Deep learning’s wager is a general-purpose assumption: the data was generated by a composition of factors, potentially hierarchical — mild-sounding, yet it buys exponential gains in regions-per-example (made precise in §6.4.1, §15.4 and §15.5), directly countering the curse of dimensionality.
One more generalization-rescuing idea remains — that real data doesn’t fill its space at all: the manifold hypothesis.
Check yourself — the smoothness prior
1.In the CheckerboardLab with the smoothness prior, m = 6 examples. Predict the accuracy pattern.
2.Toggling 'assume periodic structure' gets 100% from m = 1. What is the catch?
3.Why do k-NN, local kernels and decision trees share one budget: O(k) examples for O(k) regions?
4.What makes O(2ᵏ) regions from O(k) examples possible at all?
5.A Gaussian-kernel machine is described as a 'template matcher'. Why does that framing predict its limits on AI tasks?