Classification

K-Nearest Neighbors (kNN)

kNN classifies a test point $x$ by finding its $k$ closest points in the training set and letting them vote on the label. There is no “training” stage: kNN is a non-parametric lazy learner that just memorizes the dataset.

With kNN, when we want to produce an output $y$ for a new test input $x$, we find the $k$-nearest neighbours to $x$ in the training data $X$, and the neighbours “vote” on the label of $x$. Majority wins for classification; for regression, average the labels.

See also https://cs231n.github.io/classification/.

Bayes Optimal Classifier

The optimal classification rule (minimum error) is the Bayes classifier: $f^{\ast }(x)=\arg {\max }_c{\mathrm{Pr}}_{y\sim D_{Y|X=x}}[y=c]$

This requires knowing the true data distribution $D$. kNN is an approximation to the Bayes classifier that only uses the training data.

The kNN Assumption

If feature vectors $x$ and $x^{\prime }$ are close, then their labels $y,y^{\prime }$ are likely the same: ${\mathrm{Pr}}_{y\sim D_{Y|X=x}}[y=c]\approx {\mathrm{Pr}}_{y^{\prime }\sim D_{Y|X=x^{\prime }}}[y^{\prime }=c]\text{ when }x\approx x^{\prime }$

Distance and aggregation are underspecified: typically ${\ell }_2$ distance and majority vote.

Intuition

kNN is non-parametric because the decision boundary is implicit in the training points themselves, not summarized by a fixed-size weight vector. More data means a more flexible boundary. $k$ controls smoothness: $k=1$ gives a jagged boundary that memorizes noise, large $k$ smooths everything toward the majority class.

Time and Space Complexity

• Training: $O(1)$ time, $O(nd)$ space (just store the dataset). Compare with perceptron or linear regression at $O(d)$ space
• Test-time classification: $O(nd)$ naively for each query
• Better options:
  • Voronoi diagrams: $O(d\log n)$ time but $n^{O(d)}$ space (good in low dimensions)
  • Approximate nearest neighbours (e.g., FLANN, FAISS, HNSW), accuracy-speed tradeoff

Theoretical Guarantee (Cover-Hart ‘67)

As $n\to \infty$: $L_{1NN}\le 2L_{\text{Bayes}}(1-L_{\text{Bayes}})$.

• If Bayes error is 0, 1NN has 0 error (with infinite data)
• If Bayes error is 0.1, 1NN has $\le 0.18$ error

Remarkable: 1NN, despite its simplicity, is within a factor of 2 of the best possible classifier given infinite data. The catch (below) is that “infinite” can mean exponential in $d$.

Caveat

$n$ may have to be exponentially large in $d$. This is the Curse of Dimensionality.

Practical Recipe

1. Preprocess your data: normalize features to zero mean and unit variance
2. For high-dimensional data, reduce dimensionality first with PCA, NCA, or Random Projection
3. Sweep $k$ (odd values to avoid ties) and distance types (${\ell }_1$, ${\ell }_2$, ${\ell }_{\infty }$) on validation or via Cross Validation
4. Lock in hyperparameters, then report test accuracy once

Distance Metrics on Images

From CS231n Lec 2, kNN is introduced as the first classifier, not because it’s good for images (it isn’t), but because it makes the train/predict API concrete.

L1 (Manhattan) distance, coordinate-dependent (changes if you rotate the axes): $d_1(I_1,I_2)={\sum }_p|I_1^p-I_2^p|$

L2 (Euclidean) distance, rotation-invariant: $d_2(I_1,I_2)=\sqrt{{\sum }_p(I_1^p-I_2^p{)}^2}$

The choice of L1 vs L2 reshapes decision boundaries: L1 boundaries align with the coordinate axes, L2 boundaries don’t. Pick L1 when individual feature dimensions have semantic meaning (then axis-aligned splits are natural).

Hyperparameters: $k$ and the distance metric

$k$ and the distance metric are hyperparameters: choices about the algorithm itself, not learned from data. Bad ways to set them:

1. Pick what works best on the training set, always picks $k=1$ (memorizes)
2. Pick what works best on the test set, leaks the test set so you no longer have an unbiased generalization estimate

Right way: split into train / validation / test. Tune on validation, evaluate once on test. For small datasets, use $k$-fold cross-validation.

Why kNN is never used for images in practice

1. Test-time is slow, $O(nd)$ per query, exactly the wrong end of the tradeoff for deployment
2. Pixel distances are not perceptually meaningful, the slides show four CIFAR images all at the same L2 distance from the original (one shifted, one tinted, one boxed) that a human would never confuse
3. Curse of dimensionality, to densely cover a $d$-dimensional unit cube you need $n$ exponential in $d$. CIFAR is $d=3072$

Related

• Classification
• Curse of Dimensionality
• Cross Validation
• Image Classification
• CS480
• CS231n