Least squares versus nearest neighbours

Quant research is mostly prediction: tomorrow’s return, this order’s fill probability, a house’s price. This part follows The Elements of Statistical Learning, the book researchers reach for first. It opens with the two simplest predictors there are, because between them they show every trade-off that comes later.

The linear model

Given inputs $X = (X_1, \dots, X_p)$ , predict the output with a weighted sum plus an intercept:

\hat Y = \hat\beta_0 + \sum_{j=1}^{p} X_j\,\hat\beta_j .

Fit it by least squares: choose $\beta$ to minimise the residual sum of squares,

\operatorname{RSS}(\beta) = \sum_{i=1}^{N} \big(y_i - x_i^{\top}\beta\big)^2 .

RSS is not an arbitrary choice. The best possible predictor of $Y$ under squared error is the conditional expectation function $E[Y \mid X]$ , and least squares gives the best linear approximation to it. For classification, code the two classes as 0 and 1, fit, and predict class 1 when $\hat Y > 0.5$ : the decision boundary is a straight line.

Nearest neighbours

Instead of fitting a formula, keep the training data and average the $k$ closest examples:

\hat Y(x) = \frac{1}{k}\sum_{x_i \in N_k(x)} y_i .

There is nothing to fit except the choice of $k$ . With $k = 1$ the decision regions form a Voronoi tessellation: every training point owns the patch of space closest to it, so the boundary is jagged and full of islands. Larger $k$ smooths it. Although $k$ is a single number, the model behaves as if it had about $N/k$ parameters, one per neighbourhood, so small $k$ means a very flexible model.

Kernel methods refine this by weighting neighbours by distance with a smooth kernel instead of counting the nearest $k$ equally (we’ll use one to price opera seats in lesson 15).

Figure 8.1The classifier as terrain

Height is the predicted probability of the blue class over the two inputs; points sit at 1 (blue) or 0 (orange). k = 1 is a field of spikes that touches every training point; larger k erodes it into hills; least squares is one tilted plane. The glass sheet is the 0.5 decision threshold.

Figure 8.2Decision-boundary painter, from above

Two classes, each a mixture of ten Gaussian blobs, as in ESL chapter 2. Switch between the least-squares line and k-nearest neighbours, and slide k. The chart below plots error on training data (dashed) and on 1,000 fresh test points (red) as k varies. k = 1 is perfect on training data and worse on new data.

Rigid versus flexible

	Linear model (least squares)	Nearest neighbours
Bias and variance	high bias, low variance	low bias, high variance
Assumptions	the relationship is (close to) linear	almost none
Works best when	each class is roughly one Gaussian blob	each class is a mixture of many blobs
Dimensions	copes well with many inputs	needs low dimensions and lots of data

The next lesson makes “bias” and “variance” precise and explains the last row: the curse of dimensionality.

In code

import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.neighbors import KNeighborsClassifier

rng = np.random.default_rng(6)
def blobs(n, centre):
    means = centre + rng.standard_normal((10, 2))
    return means[rng.integers(0, 10, n)] + rng.standard_normal((n, 2)) * np.sqrt(0.2)

X = np.vstack([blobs(100, [1, 0]), blobs(100, [0, 1])]); y = np.r_[np.zeros(100), np.ones(100)]
Xt = np.vstack([blobs(500, [1, 0]), blobs(500, [0, 1])]); yt = np.r_[np.zeros(500), np.ones(500)]

lin = LinearRegression().fit(X, y)
print("linear test error", np.mean((lin.predict(Xt) > 0.5) != yt))
for k in (1, 15, 101):
    knn = KNeighborsClassifier(k).fit(X, y)
    print(k, "train", 1 - knn.score(X, y), "test", 1 - knn.score(Xt, yt))

Check yourself

Which model is guaranteed to have zero training error (assuming no two identical inputs with different labels)?