Module 2 · Foundations
Two poles of prediction
Almost every supervised method sits somewhere on a line between two extremes. At one end, the linear model: assume the answer is a weighted sum of the inputs, estimate a handful of weights by least squares, and accept that if the truth isn't linear you'll be systematically wrong (bias). At the other end, k-nearest neighbors: assume nothing, and answer every query by a majority vote among the closest training points — perfectly adaptable, but the answer wobbles with every noisy point that happens to be nearby (variance).
The ideal predictor, if you knew the data-generating process, would be the conditional expectation f(x) = E[Y | X = x]— for classification, “pick the most probable class at x.” Both extremes are estimates of it: the linear model pools all the data through a rigid formula, kNN pools only a local ball. The dial between them is effective degrees of freedom — roughly N/k for kNN — and the test-error curve against that dial is U-shaped, always, for every method family in this curriculum.
🎛 kNN vs linear lab
Linear · train err
14.2%
Linear · test err
12.7%
9-NN · train err
15.8%
9-NN · test err
15.0%
Training data + linear boundary
k-NN error vs effective flexibility (N/k)
Left: the linear rule draws one straight line, no matter what the data look like. Right: k-NN's flexibility is N/k effective parameters — at k=1 (right edge) training error is zero by construction while test error climbs; at huge k (left edge) it underfits toward the majority class. The U-shape in the red curve is the whole subject in one picture. Educational tool.
The bias–variance decomposition
Expected test error at a point splits cleanly into three parts:
E[(y − f̂(x))²] = Bias²(f̂(x)) + Var(f̂(x)) + σ² rigidity wobble noise floor
Flexibility moves the first two in opposite directions — that's the whole tradeoff. The linear model is high-bias / low-variance; 1-NN is zero-bias / high-variance. Neither is “better”; the winner depends on the truth's shape, the noise, and how much data you have.
The curse of dimensionality
kNN's premise is that “nearby” points are informative. In 2 dimensions, fine. In 100 dimensions, geometry turns hostile: to capture even 10% of the data around a query point, a neighborhood must stretch across most of each axis — it stops being local. Distances concentrate (the nearest and farthest points become nearly equidistant), and every query sits near the boundary of the data cloud. This is why high-dimensional problems (Module 18) push you back toward structured, biased models: structure is what substitutes for the neighbors you no longer have.
Things to try
- • Follow the red test-error curve from left (huge k) to right (k=1): under-smoothed, sweet spot, over-memorized. Note the blue training curve is flat zero at k=1 — and lying to you.
- • Push class separation to 3: nearly any method wins, and the linear rule is as good as the best k. Easy problems don't reward flexibility.
- • Push overlap up instead: the classes interleave and the linear line can't follow the seams — a well-chosen k now beats it clearly.