ML6.1 · LESSON 1 OF 6

Nearest neighbors

Compare nearest-neighbor, naive Bayes and margin-based predictions using their actual assumptions.

THE IDEA

Predicting by looking at neighbours

Most models learn a rule and then forget the data. k-nearest neighbours (k-NN) does the opposite: it keeps all the training examples and, when asked about a new point, finds the k stored points closest to it and lets them vote. The assumption is simple: points that are close together tend to share a label.

Step 1 of 4

Store everything. "Training" is just keeping the 60 labelled points. No parameters are fitted and no loss is minimised.

Because nothing is fitted, a prediction costs a pass over the stored data: about n distances in d dimensions, so O(n·d) work for every query. Doubling the data doubles the wait. That is the price of having no training step.

Drag the query and change k

Below, 60 stored points from two interleaved moons, with some noise. The tinted background shows what class a query would get at every spot. Drag the query (or use the sliders): the dashed lines go to its k neighbours, and the vote is shown on the right. Then move the k slider and watch the boundary.

class 0class 1

query x = 1.5query y = 4.5

k (neighbours that vote) = 5

Votes: class 0: 5, class 1: 0. Prediction: class 0.

nearest distance: 0.2302
farthest of the 5: 0.672

Training accuracy 86.7% (a training point counts itself as a neighbour)
Validation accuracy 91% (100 unseen points)

k	1	3	5	7	9	11	15	21	31	41	59
train	100	92	87	88	90	88	87	83	82	78	80
valid.	83	86	91	90	92	89	87	85	79	78	73

Blue is class 0, orange is class 1. The ring around the query takes the colour of the winning vote. Ringed training points are its neighbours.

k is a dial between memorising and ignoring

With k = 1 every training point carves out its own little territory, so one noisy point creates an island of the wrong class. Training accuracy is 100%, because each stored point is its own nearest neighbour, yet accuracy on 100 unseen points is only 83%. That gap is overfitting. At k = 9 the boundary is smoother and validation accuracy rises to 92%. If k grows towards the size of the training set, the vote turns into "whatever class is most common overall", and validation accuracy falls to 73% at k = 59.

Predict first. A query lands next to one stray orange point that sits inside a blue region. What do k = 1 and k = 9 predict?

Predict first. Which k always gets 100% accuracy on the training set itself?

The common mistake

Chapter context

Different model families turn different notions of similarity into predictions. A geometric distance, a conditional-independence assumption and a kernel are distinct modeling decisions rather than variations of the same formula.

TRY IT YOURSELF

Part 1. Do it on the plot

Each task ticks from the real state of the playground and stays ticked once earned. The validation accuracy comes from 100 points the model never stored.

class 0class 1

query x = 1query y = 5

k (neighbours that vote) = 5

Votes: class 0: 5, class 1: 0. Prediction: class 0.

nearest distance: 0.8016
farthest of the 5: 1.3367

Training accuracy 86.7% (a training point counts itself as a neighbour)
Validation accuracy 91% (100 unseen points)

k	1	3	5	7	9	11	15	21	31	41	59
train	100	92	87	88	90	88	87	83	82	78	80
valid.	83	86	91	90	92	89	87	85	79	78	73

To do: Drag the query to a spot where k = 1 and k = 9 predict different classes
To do: Choose the k whose training accuracy is exactly 100%
To do: Choose the k with the best validation accuracy
To do: Choose a k so large that validation accuracy drops below 75%

Part 2. Do it in code

pairwise_distances(A, B) returns the matrix D with D[i, j] = Euclidean distance between row i of A and row j of B. No Python loops over rows.
knn_predict(X_train, y_train, X_query, k) returns one label per query row: the majority label among its k nearest training rows.
Distances that tie are ordered by the lower training index. If k is larger than the number of training rows, use all of them.
If two labels tie on votes, pick the label of the nearest neighbour among those with the top count (walk the neighbours nearest first).

import numpy as np

def pairwise_distances(A, B):
    # return an array of shape (len(A), len(B))
    pass

def knn_predict(X_train, y_train, X_query, k):
    # return a numpy array with one predicted label per query row
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does k=1 fit parameters by minimizing a differentiable loss?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

\|x-y\|_2^2=\sum_j(x_j-y_j)^2,\quad K(x,y)=\exp(-\gamma\|x-y\|^2),\;\gamma>0.

For SVM canonical boundary planes $w^Tx+b=\pm1$ , their separation is $2/\|w\|$ . A naive-Bayes posterior is proportional to $P(c)\prod_jP(x_j\mid c)$ .

A numerically convenient naive-Bayes decision rule is

\hat c=\arg\max_c\left[\log P(c)+\sum_j\log P(x_j\mid c)\right].

This avoids multiplying many small probabilities, but it does not remove the need to handle zero likelihoods or choose an appropriate feature distribution.

Worked example

For query [1,1], squared distances to [0,0], [2,1] and [3,3] are 2, 1 and 8. The nearest point is [2,1]. Separately, a canonical SVM with w=[3,4] has norm 5 and margin width 2/5=0.4.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import sqrt, isclose
q = [1,1]
points = [[0,0],[2,1],[3,3]]
distances = [sum((a-b)**2 for a,b in zip(q,p)) for p in points]
assert distances == [2,1,8]
assert distances.index(min(distances)) == 1
assert isclose(2/sqrt(3**2+4**2), .4)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Changing feature scale can change neighbors. Kernel similarity is not automatically calibrated probability. The SVM margin formula assumes a particular normalization of the separating planes.