Computer Vision MT25, Image classification
Flashcards
General classification
Suppose:
- $f$ is a classifier
- $\mathcal D = ((x _ i, y _ i))^N _ {i=1}$ is some dataset
@Define the accuracy and expected accuracy.
If the classifier predicts probabilities, then the expected accuracy is given by
\[\text{EAcc}(f) = \frac{1}{N} \sum _ {x, y \in D} f _ y(x)\]where $f _ y(x)$ is the predicted probability of $x$ belonging to class $y$.
Image embeddings
@Define a feature extractor.
A map from images to image embeddings, e.g.
\[\phi : \mathbb R^{H \times W \times 3} \to \mathbb R^d\]Name some @example image embeddings, and some example classifiers that could be used on these embeddings.
- Image embeddings
- Fourier transform
- Bag of visual words (SIFT)
- Histogram of gradients
- Classifiers
- SVMs
- Kernel SVMs
- Random forests
Suppose $\phi : \mathbb R^{H \times W \times 3} \to \mathbb R^d$ is a feature extractor that maps images to embeddings. Briefly explain the @algorithm for classifying an image using nearest neighbour classification.
Given an image
- Find its embedding with $\phi$
- Look up nearest neighbours in the embedding space
- The predicted class is the majority vote of the neighbourhood
Suppose that a $k$-NN classifier is used to classify images of boats and deer. @Visualise what the accuracy on a validation set might look like as you increase $k$, and why it’s not a good idea to make $k$ as high possible.
There is a healthy balance to be struck: if $k$ is all images, then this just classifies images based on the proportion of each class in the training set.
Multi-class classification
Suppose you are classifying a data set into $K$ classes, and have trained $K$ 1-vs-all classifiers $f _ 1, \ldots, f _ K$. How can you create an overall classifier $f : X \to \mathbb R^K$ which outputs a probability distribution over the classes?
This gives a valid distribution but the probabilities are not properly calibrated: each $f _ k$ was trained independently on a different binary problem, so their outputs are not on a common scale. The principled alternative is to train a single softmax classifier with cross-entropy loss end-to-end (see Notes - Computer Vision MT25, Loss function designU), which jointly fits a calibrated $K$-way distribution.
Bite-sized
The softmax function with temperature $\tau$ is
\[\mathrm{softmax} _ k(\hat Y, \tau) = <span class="cloze" tabindex="0">\dfrac{\exp(\hat Y _ k / \tau)}{\sum _ j \exp(\hat Y _ j / \tau)}</span>\]As $\tau \to \infty$, the output approaches a uniform distribution; as $\tau \to 0$, it approaches a one-hot argmax. Temperature preserves the relative ordering of inputs and so is monotonic.
@Justify why accuracy can be misleading as a classifier metric when classes are imbalanced, and give a concrete example.
If 90% of test samples belong to class 0, then a trivial classifier that always predicts class 0 achieves 90% accuracy without learning anything useful. Accuracy rewards majority-class predictions and is insensitive to errors on minority classes.
The fix is to use class-aware metrics such as precision, recall, and AP (see Notes - Computer Vision MT25, Precision and recallU) which distinguish the four cell types of the confusion matrix.
The standard educational classification benchmark used in the lecture is CIFAR-10 (Krizhevsky 2009): 60{,}000 colour images of size $32 \times 32$ in 10 classes, with 50{,}000 training and 10{,}000 test images (6{,}000 per class).
@Describe the maximum margin idea behind linear support vector machines, including the role of support vectors.
Given a binary classification dataset $(\pmb x _ i, y _ i)$ with $y _ i \in \{-1, +1\}$ that is linearly separable, there are infinitely many separating hyperplanes. The maximum-margin idea is to place the decision boundary as far from the data as possible.
For a linear classifier $f(\pmb x) = \pmb w^\top \pmb x + b$, the margin is $2 / \|\pmb w\|$ (the gap between the two parallel hyperplanes $f = \pm 1$). Maximising the margin amounts to minimising $\|\pmb w\|^2$ subject to all training points satisfying $y _ i f(\pmb x _ i) \ge 1$.
Support vectors are the training points that lie exactly on the margin (i.e. $y _ i f(\pmb x _ i) = 1$) — they “support” the placement of the decision boundary. All other points have $y _ i f(\pmb x _ i) > 1$ and could be moved around without changing the solution. This sparsity is one of the appealing features of SVMs.
The SVM training loss combines the hinge loss with an $L _ 2$ regulariser:
\[\mathcal L(\pmb w, b) = \tfrac{1}{n}\sum _ i \max(0, 1 - y _ i (\pmb x _ i^\top \pmb w + b)) + \lambda \ \vert \pmb w\ \vert ^2\]The hinge loss is a convex upper bound on the 0-1 loss — its gradient is $-y _ i \pmb x _ i$ for points violating the margin (driving the boundary away from them) and zero for points already correctly classified beyond the margin (so they no longer influence training).
@State the multi-class linear classifier in vector form given $K$ binary 1-vs-all classifiers $f _ k(\pmb x) = \pmb w _ k^\top \pmb x + b _ k$.
Stack the per-class weights into a matrix $\mathbf W \in \mathbb R^{K \times d}$ with row $k$ equal to $\pmb w _ k^\top$, and the per-class biases into $\pmb b \in \mathbb R^K$. Then
\[\hat{\pmb Y} = f(\pmb x) = \mathbf W \pmb x + \pmb b \in \mathbb R^K.\]To predict a single class, take $\arg\max _ k \hat Y _ k$; to produce a probability distribution, apply softmax: $p(C _ k \mid \pmb x) = \mathrm{softmax} _ k(\hat{\pmb Y})$.
The softmax-with-cross-entropy alternative is to jointly fit the $\{\pmb w _ k\}$ end-to-end rather than training $K$ independent binary classifiers — this gives properly calibrated probabilities.
The cross-entropy loss for soft-max classification simplifies to
\[\mathcal L(\pmb x, y _ {GT}) = <span class="cloze" tabindex="0">-\log p(C _ {GT} \mid \pmb x) = -f _ {GT}(\pmb x) + \log \sum _ j \exp(f _ j(\pmb x))</span>\]because the ground-truth distribution is one-hot, so the full cross-entropy $-\sum _ k p _ {GT}(C _ k) \log p(C _ k \mid \pmb x)$ collapses to a single term at $k = GT$.
The two-step image classification pipeline of Lecture 6 is (1) compute an image embedding $\phi(\pmb x)$, then (2) learn a classifier on those embeddings. Pre-deep-learning embeddings include FFT, BoW, HOG, Fisher Vectors; classifiers include linear regression, SVMs, kernel SVMs, random forests. Deep learning combines both steps and learns them end-to-end.
@Justify the appeal of $k$-NN classification as a baseline despite being conceptually trivial.
- No training: amortised at inference, with the trade-off of slower (potentially $O(N)$) predictions per query. Fast NN-lookup structures (e.g. kd-trees, FAISS) reduce this to $O(\log N)$ or sublinear.
- Naturally multi-class: no architectural change to support more classes; just add more training points with new labels.
- Single hyperparameter $k$: easy to tune by cross-validation.
- Non-linear decision surfaces: piecewise-constant Voronoi-like regions in feature space.
- Quality improves automatically with data: more training points densely cover the feature space, so the nearest neighbours are typically closer and more relevant.
So $k$-NN gives a strong baseline that any specialised classifier should at least match before being considered useful.
The ImageNet Large Scale Visual Recognition Challenge (ILSVRC) saw a dramatic drop in error rate in 2012, when AlexNet (Krizhevsky, Sutskever, Hinton) became the first deep-learning entry to win and reduced top-5 error from ~26% to ~16%, decisively beating the prior SIFT-based methods. Error continued to drop to ~5% by 2015 with deeper architectures.