Interactive demo · Statistical Learning: Theory and Methods · Chapter 2

The bias-variance trade-off for k-nearest-neighbour regression

The inputs x1, …, xN are fixed and the responses are yi = f(xi) + εi with noise variance σ2. The k-NN estimate at x0 averages the k responses nearest to x0, so its expected prediction error splits exactly into three parts (2.47): the noise σ2, the squared bias [f(x0) − average of f over the neighbours]2, which grows as the neighbourhood widens, and the variance σ2/k, which shrinks. The bottom panel averages over the design points: the training error keeps falling as the model becomes more complex (smaller k, more degrees of freedom N/k), while the test error is U-shaped (Figure 2.11).

Number of neighbours k

Target point x₀

Noise standard deviation σ

True function f

Training points N

Try these

The design is N points drawn once, uniform on (0, 1), from a seeded generator, and then held fixed, as in the derivation of (2.46); the plotted training set adds one draw of Gaussian noise. Bias, variance and the expected errors are exact (no simulation): the training error of point i has expectation bi2 + σ2(1 − 1/k) and its test error σ2 + bi2 + σ2/k, because each xi is its own nearest neighbour. Ties in distance go to the lower-numbered point.

In the lecture notes