Describe, Then Decide: k-NN, SVMs, and Bags of Features

From one example to many: supervised classification

In the last guide you recognised things by matching: you held up a template — one stored example — and slid it across the image looking for the spot that lined up best. That works when your target always looks the same, but the world rarely cooperates. A 'cat' can be ginger or grey, curled up or mid-leap, lit from the left or from the right. No single template can stand in for all of those. This guide makes the leap from comparing against one example to learning from many, which is the engine behind the classical recognition pipeline.

Here is the supervised classification frame. We start with a training set: a pile of images, each tagged with a label (this one is a cat, that one is a dog). Earlier tracks already taught us how to turn a raw image into numbers — edges, gradients, HOG-style descriptors — so we will simply assume the descriptor is given. Each image therefore becomes one feature vector: an ordered list of numbers like (0.21, 0.04, 0.88, …) that summarises what the image looks like. A whole image collapses to a single point in a high-dimensional space, and its label is the colour we paint that point.

A classifier learns a decision rule — a way to look at a brand-new feature vector and output a label. The real goal is not to ace the images we already have, but to generalize: to be right on images it has never seen. Think of studying for an exam. If you only memorise the answers to last year's paper, you will look brilliant on that paper and freeze on the fresh one. So we hide some labelled data in a test set, train only on the rest (the train set), and judge the model solely on the held-out test set — a fair stand-in for 'images from the future'. A model that does well on training but badly on test has memorised, not understood. A learner like the k-nearest-neighbors image classifier makes this split impossible to ignore.

k-Nearest Neighbours: you are who your neighbours are

The gentlest classifier is the k-nearest-neighbors image classifier (k-NN). To label a new image, it finds the k training images whose feature vectors sit closest to the new one and lets them vote. Surprisingly, there is no real 'training' at all: k-NN just keeps the entire training set in memory and does all its thinking at query time. We call this a lazy learner — it postpones every decision until you actually ask it something. The whole 'model' is the dataset itself.

Euclidean (straight-line) distance between the query vector and the i-th training vector.

'Closest' needs a distance metric, and the default is Euclidean distance. Read the formula left to right: \mathbf{x} is the query feature vector (the new image), \mathbf{x}_i is the i-th stored training vector, the index j runs over the D feature dimensions, and x_j versus x_{i,j} compares them one dimension at a time. We subtract within each dimension, square so positives and negatives both count and big gaps are punished hard, sum across all D dimensions, then take the square root to undo the squaring and return to real units — exactly the ruler-distance you would measure on paper. Tiny example in 2D: query (2,2), neighbour (3,3): \sqrt{(2-3)^2+(2-3)^2}=\sqrt{2}\approx1.41. Because every dimension is summed with equal weight, feature scaling matters enormously: if one feature ranges 0–1000 and another 0–1, the big one drowns out the small one. Standardising each feature (e.g. to zero mean, unit variance) lets every dimension speak at the same volume.

Predict the label c that wins the vote among the k nearest neighbours.

Now the voting rule. \hat{y} is the predicted label; N_k(\mathbf{x}) is the set of the k training points with the smallest distances to \mathbf{x}; c ranges over the possible classes; and \mathbb{1}[y_i=c] is an indicator that is 1 when neighbour i's label equals c and 0 otherwise. So the sum simply counts how many of the k neighbours carry each class, and \arg\max picks the class with the most votes — plain majority rule. Ties (say k=4 split 2–2) can be broken by shrinking k, by a coin flip, or, more elegantly, by weighting each vote by 1/d, so a very close neighbour counts more than a distant one. The choice of k is the crucial knob: small k (k=1) gives a jagged boundary that hugs every noisy point — high variance, overfitting; large k averages over a big crowd and smears the boundary flat — high bias, underfitting. This is the bias–variance trade-off in its purest form.

import math

# Tiny 2D example. Each sample = (feature vector, label).
train = [
    ((2, 1), "cat"),
    ((1, 2), "cat"),
    ((3, 3), "dog"),
    ((0, 0), "cat"),
    ((4, 2), "dog"),
]
query = (2, 2)
k = 3

def dist(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

# rank training points by distance, keep the k closest
ranked = sorted(train, key=lambda s: dist(query, s[0]))
neighbours = ranked[:k]   # (2,1)cat d=1.00, (1,2)cat d=1.00, (3,3)dog d=1.41

votes = {}
for vec, label in neighbours:
    votes[label] = votes.get(label, 0) + 1

prediction = max(votes, key=votes.get)  # cat: 2 votes beats dog: 1 vote
print(prediction, votes)                # -> cat {'cat': 2, 'dog': 1}

Support Vector Machines: find the widest street

The support vector machine (SVM) was the workhorse classical classifier. Picture two classes scattered on a page; infinitely many straight lines separate them. Which is best? Vladimir Vapnik's answer was the widest street: of all the separating lines, choose the one with the largest margin — the widest empty buffer with no points inside, on both sides. A fat buffer means you can wiggle a new point a long way before it crosses to the wrong side, which is exactly what makes the rule generalize. The handful of points that touch the edges of the street and pin it in place are the support vectors; remarkably, the whole boundary depends only on them and ignores the rest.

The linear decision function and its sign-based classification rule.

The boundary is a line (in 2D) or hyperplane (in higher dimensions) described by this decision function. \mathbf{x} is the feature vector you want to classify; \mathbf{w} is the weight vector, which points perpendicular (normal) to the boundary and sets its orientation; b is the bias, which slides the boundary toward or away from the origin; and \mathbf{w}\cdot\mathbf{x}=\sum_j w_j x_j is the dot product. The boundary itself is the set of points where f(\mathbf{x})=0. To classify, take \operatorname{sign}(f(\mathbf{x})): positive means one class, negative the other. Concretely, with \mathbf{w}=(2,0), b=-3, a point \mathbf{x}=(2,5) gives f=2\cdot2+0\cdot5-3=1>0 (class +1), while \mathbf{x}=(1,9) gives f=2-3=-1<0 (class −1). Notice the second feature was irrelevant here because its weight was 0 — the weights encode which features matter.

The width of the street, set entirely by the length of the weight vector.

Here is the elegant twist. SVMs scale \mathbf{w} and b so that the support vectors sit exactly at f(\mathbf{x})=+1 and f(\mathbf{x})=-1. The perpendicular gap between those two edges then works out to 2/\lVert\mathbf{w}\rVert, where \lVert\mathbf{w}\rVert=\sqrt{\sum_j w_j^2} is the length of the weight vector. Read it carefully: the margin is inversely proportional to \lVert\mathbf{w}\rVert, so a wider street means a shorter \mathbf{w}. That is why 'maximise the margin' is the very same task as 'minimise \lVert\mathbf{w}\rVert' — a clean optimisation we can actually solve. Numerically, halving \lVert\mathbf{w}\rVert from 2 to 1 doubles the street from 1 to 2.

Soft-margin SVM: widen the street while paying a penalty for points that intrude on it.

Real data is not perfectly separable, so SVMs use a soft margin that lets a few points sit inside the street, or even on the wrong side, for a price. Term by term: \tfrac{1}{2}\lVert\mathbf{w}\rVert^2 is the 'keep the street wide' part; y_i=\pm1 is the true label of example i; y_i f(\mathbf{x}_i) is positive when the prediction is correct and confidently outside the margin. The hinge loss \max(0,\,1-y_i f(\mathbf{x}_i)) is 0 when a point is safely beyond its margin (y_i f \ge 1) and grows linearly as the point pushes into or across the street. The constant C sets the exchange rate between the two goals. Large C punishes every mistake harshly → a narrow margin that bends to fit the data (overfitting); small C tolerates violations → a wide, smooth margin (more regularised, possibly underfitting). C plays for SVMs the role that k played for k-NN.

What if the two classes cannot be split by any straight line? The kernel trick lets an SVM act as though it first lifted the data into a much higher-dimensional space where a flat boundary does separate them — all without ever computing those coordinates explicitly. Pair a linear SVM with strong hand-crafted features and you get the famous HOG + SVM detector, which dominated object and pedestrian detection for the better part of a decade before deep nets: HOG turns local gradient patterns into a sturdy descriptor, and the SVM draws the widest possible street between 'object' and 'not object'.

One vector per image: the bag of visual words

There is a mismatch we have quietly ignored. Local-feature methods (SIFT-like keypoints, patches) produce a variable number of descriptors per image — a cluttered photo might yield 2,000, a plain one 50. But k-NN and SVM both demand a fixed-length vector, the same size every time, so a point lives in one consistent space. How do we squeeze a wildly varying set of descriptors into a single fixed vector without throwing the information away?

The trick is borrowed from text. To compare two documents you do not need their word order — you can describe each by which words appear and how often: a 'bag of words'. ('the cat sat' and 'sat the cat' give the same bag.) Computer vision copies this idea exactly. We build a vocabulary of recurring visual words — characteristic little patches like a corner, an eye-like blob, a bit of stripe — and describe each image by how many of each visual word it contains. The order and position are dropped; only the counts remain.

1. Extract many local descriptors across all training images (thousands per image, millions in total).
2. Cluster that ocean of descriptors with k-means into K groups; each cluster centre becomes one visual word. This is exactly dictionary learning — the K centres are the learned codebook (vocabulary).
3. For each descriptor in an image, assign it to its nearest visual word (vector quantization).
4. Build a histogram: count how many descriptors landed in each of the K words, then normalize.
5. Feed that fixed-length histogram to an SVM or k-NN as the image's feature vector.

Vector quantization: snap each descriptor to its nearest codebook centre.

Step 3 is vector quantization, and this little formula is all it is. \mathbf{d} is one local descriptor (a vector); \mathbf{c}_k is the centre of the k-th cluster from k-means — the k-th visual word in the codebook; \lVert\mathbf{d}-\mathbf{c}_k\rVert is the Euclidean distance we already met. The \arg\min returns the index k of the closest centre, so q(\mathbf{d}) is the word ID that descriptor gets stamped with. In effect we replace a rich, continuous descriptor with a single integer — 'this patch is word #37' — exactly the way you would round 3.8 to the nearest whole number. We trade precision for a tidy, countable representation.

The normalized bag-of-words histogram: the fraction of descriptors assigned to word i.

Step 4 turns the word IDs into the image's final vector h. It has K slots, one per visual word. N is the number of descriptors found in this image; \mathbb{1}[q(\mathbf{d}_n)=i] is 1 when the n-th descriptor was quantized to word i and 0 otherwise, so the sum simply counts how many descriptors landed in word i. The 1/N factor normalizes by total count: without it, a busy image with 2,000 descriptors would have huge bars and a sparse one with 50 tiny bars, and they would look incomparable even if they showed the same object. Dividing by N turns raw counts into proportions that sum to 1, so 'mostly stripes' looks the same whether the image is cluttered or clean. Example: 100 descriptors, 30 fall into word #5 → h_5=0.30. Every image, regardless of how many descriptors it had, is now one fixed K-length vector ready for a classifier.

from sklearn.cluster import KMeans
import numpy as np

# 1) collect local descriptors from ALL training images (e.g. SIFT/HOG patches)
all_descriptors = np.vstack([describe(img) for img in training_images])  # (M, D)

# 2) learn the visual vocabulary: K cluster centres = the codebook (dictionary)
K = 200
codebook = KMeans(n_clusters=K).fit(all_descriptors)

def bag_of_words(img):
    desc = describe(img)                # (n, D) -- variable count per image
    words = codebook.predict(desc)      # 3) nearest visual word for each descriptor
    hist = np.bincount(words, minlength=K).astype(float)  # 4) count per word
    return hist / hist.sum()            # normalize -> fixed-length, scale-free vector

Putting location back: spatial pyramid matching

The bag-of-words weakness is now glaring: it is blind to layout. Sky-blue patches at the top and grey-road patches at the bottom give the very same global histogram as the two swapped — yet one is a normal outdoor scene and the other is upside down. Spatial pyramid matching (SPM) rescues us by re-introducing some geometry, without going all the way back to rigid templates.

The recipe is beautifully simple. Lay a series of ever-finer grids over the image: level 0 is the whole image (1×1, the plain bag of words), level 1 splits it into 2×2 = 4 cells, level 2 into 4×4 = 16 cells. Compute a bag-of-words histogram inside each cell, then concatenate all of them into one long vector. The coarse level carries 'what is in the image overall'; the finer levels add 'and roughly where each thing sits'. The same dictionary learning codebook is reused in every cell, so the words are comparable across levels.

The pyramid match kernel: a weighted sum of histogram-intersection scores across levels.

To compare two images, SPM uses the pyramid match kernel K, a single similarity score. Symbol by symbol: l is the pyramid level, running from the coarsest l=0 up to the finest l=L; I_l is the histogram-intersection similarity computed by summing, cell by cell, the element-wise minimum of the two images' word counts — exactly the colour-histogram-intersection measure from Guide 1, now applied per cell and summed; and w_l=1/2^{\,L-l} is the weight given to level l. Check the weights for L=2: w_0=1/2^2=0.25, w_1=1/2^1=0.5, w_2=1/2^0=1. Finer levels get larger weights. The reason: a match at a fine level means the two images agree on both what and where, which is stronger evidence than a coarse match that only agrees on what — yet the coarse level still contributes, so the score degrades gracefully rather than demanding perfect alignment.

Picture a scene classifier deciding 'beach' versus 'street'. Plain bag of words might confuse them if both contain blue and grey patches. With a pyramid, 'beach' reliably has sand/water words in the bottom cells and sky words in the top cells, while 'street' has buildings up the sides — and those positional patterns are now part of the vector. This concatenate-coarse-with-fine idea was a major pre-deep-learning benchmark winner on scene and object datasets, and the very same instinct — keep a coarse summary plus a few levels of finer spatial detail — quietly survives inside the pooling pyramids of modern networks.

Did it actually work? Honest evaluation

A classifier is only as trustworthy as the way you measured it, so this section is the most reusable in the whole track. The cardinal rule is train/validation/test discipline. Train on the training set. Tune your knobs — k for k-NN, C for the SVM, the codebook size K — on a separate validation set. Touch the test set exactly once, at the very end, to report the final number. The moment you peek at the test set and adjust anything, it stops measuring the future and starts flattering you — you have quietly trained on it, and your reported score becomes a lie.

The obvious score is accuracy = fraction of predictions that are correct. It has a famous trap on imbalanced data. Suppose 1 image in 100 contains a rare defect. A lazy model that screams 'no defect!' every single time is 99% accurate and 100% useless — it never catches the thing you care about. To see past this we lay out the confusion matrix: a small table of true class against predicted class, whose four cells for a yes/no task are true positives, false positives, false negatives, and true negatives. Every richer metric is built from those four counts.

Precision and recall, each built from the confusion-matrix counts.

Precision asks: of everything I flagged as positive, how much was actually positive? Recall asks: of everything that truly is positive, how much did I catch? Here TP (true positives) are correct positive flags, FP (false positives) are false alarms, and FN (false negatives) are real positives that slipped through. Worked example: a cancer screen tests 100 patients; 10 truly have the disease. The model flags 12 positive — of those, 8 are correct (TP=8) and 4 are false alarms (FP=4); it misses 2 sick patients (FN=2). Then Precision =8/(8+4)=0.67 and Recall =8/(8+2)=0.80. The two trade off: flag everyone and recall hits 1.0 but precision collapses; flag only your single most certain case and precision is 1.0 but recall is dismal. Which one you fight for depends on the cost of each error. A spam filter wants high precision (never bury a real email); a cancer screen wants high recall (never miss a sick patient, false alarms are tolerable).

The F1 score: the harmonic mean of precision (P) and recall (R).

When you need a single number, the F1 score combines precision P and recall R as their harmonic mean. The reason it is the harmonic mean rather than the plain average is that the harmonic mean is dragged toward the smaller of the two, so it punishes a lopsided score. Take P=1.0 but R=0.0 (you flagged one thing, got it right, missed everything else): the plain average is a flattering 0.5, but F1 =2(1)(0)/(1+0)=0 — correctly brutal. For our cancer example, F_1=2(0.67)(0.80)/(0.67+0.80)=0.73, sitting honestly between the two. F1 only climbs high when both precision and recall are decent, which is exactly what we want from a summary number.

Finally, these metrics let you diagnose the bias–variance failures from earlier. Overfitting shows up as near-perfect training scores beside poor validation scores — the model memorised noise (k too small for k-NN, C too large for the SVM). Underfitting shows up as mediocre scores on both — the model is too rigid to capture the pattern (k too large, C too small). You diagnose on validation, pick the knob that minimises validation error, and only then read the test set once for an honest final verdict.