§5.7.3 Other simple supervised learners
k-nearest neighbors k-nearest neighbors Non-parametric: output the (average) label of the k closest training points; 1-NN approaches 2× Bayes error asymptotically; can't learn feature relevance. defined in ch. 5 — open in glossary barely has a training stage at all: at test time, find the k nearest training points and return the average of their y values (for classification: average one-hot codes → a distribution over classes). As a non-parametric method its capacity is enormous — asymptotically, 1-NN converges to twice the Bayes error (the excess comes from random tie-breaking; voting over all zero-distance neighbors recovers the Bayes rate). The costs: heavy computation, and terrible behavior on small datasets.
Aside — the failure that motivates learned features
k-NN cannot learn that one feature matters more than another. Take isotropic Gaussian with exactly: the nearest neighbor of most points is decided by the 99 irrelevant features, drowning the one that matters — outputs on small training sets are essentially random. Distance in RAW input space is the wrong notion of similarity; representation learning exists to fix the space itself.
Decision trees decision tree Axis-aligned recursive splits of input space, one output per leaf region; struggles with diagonal boundaries. defined in ch. 5 — open in glossary also carve the input into regions with per-region parameters — by recursive, typically axis-aligned splits (fig 5.7):
Fig 5.7 (recreated) — each leaf needs ≥ 1 training example, so the tree cannot have more output regions than examples. And with axis-aligned splits, a diagonal truth like “positive when x₂ > x₁” forces an endless staircase of back-and-forth cuts — trivial for logistic regression, awkward for trees.
Both remain useful when computation is constrained — and as intuition baselines for what sophisticated algorithms improve on.
§5.8 Unsupervised learning: the best representation
Unsupervised learning ≈ extracting information from a distribution without human-annotated examples: density estimation, sampling, denoising, manifold-finding, clustering. Its classic task: find the “best” representation of the data — one preserving as much information as possible while being simpler than the original. Three recurring meanings of simpler:
Not mutually exclusive: shrinking a representation forces redundancy out, which already weakens dependencies.
§5.8.1 PCA as representation learning
Chapter 2 derived PCA principal components analysis Lossy linear compression: encode c = Dᵀx, decode Dc; optimal D = top-l eigenvectors of XᵀX. defined in ch. 2 — open in glossary as lossy compression; here it returns wearing the representation-learning hat: it learns a representation lower-dimensional than the input whose elements have no linear correlation — a first step toward independence (full independence must also remove nonlinear dependencies). The mechanism, via the SVD:
step 1/4: Center the data (E[x] = 0 by preprocessing); the unbiased sample covariance (§5.4.2’s m−1!) is XᵀX rescaled.
total squared error: 42.4
variance captured: 77.2%
Rotate d and watch the arg-min from the derivation: error is minimized exactly when d is the eigenvector of XᵀX with the largest eigenvalue.
Correlation is only linear dependence — disentangling the more complicated dependencies of real data needs more than any linear map can do. That “more” is most of Part III; the immediate next step is a representation built from cluster membership: k-means, then SGD.
Check yourself — neighbors, trees, PCA
1.Asymptotically, how does 1-NN relate to the Bayes error — and where does the excess come from?
2.y = x₁ exactly, but x ∈ ℝ¹⁰⁰ isotropic Gaussian. Why does nearest-neighbor regression fail on small samples?
3.Why do standard decision trees struggle when the positive class is exactly where x₂ > x₁?
4.The three 'simple representation' criteria are…
5.What exactly does PCA's z = Wᵀx achieve, and what does it NOT achieve?