Underfitting and OverfittingK-Nearest Neighbors
Neha's estate has a second problem: blister blight, a fungus that spreads between neighbouring bushes. She has checked 36 bushes. Is an unchecked bush likely to be blighted?
A simple method is to ask its k nearest neighbours and take a majority vote. This is k-nearest neighbours (KNN). With a bush simply copies its closest checked neighbour; with , the majority of its five closest neighbours decides. Once again is a hyperparameter, and a dial between bias and variance.
Large k
With a very large , every bush listens to almost the whole estate, and the local pattern is lost. The map turns into one colour: high
Small k
With , every odd bush rules a little island around itself, and the map becomes a patchwork: high variance.
Below is the estate map. The dots are the checked bushes — healthy green, blighted purple — and the shading shows what KNN predicts for every spot. The hollow rings are 12 new bushes checked later; a red circle marks each one KNN gets wrong. Drag k and complete the missions.
Neighbours: k =
At the model is right about every bush it knows — each bush is its own nearest neighbour — but wrong about a third of the new ones: overfitting. At it is poor everywhere: underfitting. On the chart, the known bushes line falls as k grows, while the new bushes line rises, peaks at k = 5 and falls again.
What About Double Descent?
Note
In very large modern models, such as deep neural networks with millions of numbers, something surprising happens: as the model grows far beyond the point where it fits every training example, the test error can fall a second time. This is called double descent. It does not break the ideas of this chapter — bias and variance still decide the error — but explaining it needs much more mathematics than this course uses.