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.

\[\text{Acc}(f) = \frac{1}{N} \sum _ {x, y \in \mathcal D} [y = f(x)]\]

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

  1. Find its embedding with $\phi$
  2. Look up nearest neighbours in the embedding space
  3. 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?

\[f(x) = \text{softmax}(f _ 1(x), \ldots, f _ K(x))\]

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 design), which jointly fits a calibrated $K$-way distribution.

Bite-sized

The softmax function with temperature $\tau$ is

\[\mathrm{softmax}_k(\hat Y, \tau) = \class{cloze}{\dfrac{\exp(\hat Y_k / \tau)}{\sum_j \exp(\hat Y_j / \tau)}}\]

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.

Source: Lecture 6, Temperature slide.

@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 recall) which distinguish the four cell types of the confusion matrix.

Source Lecture 6, Precision and Recall slide.

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).

Source: Lecture 6, Supervised Learning - Data slide.

@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.

Source Lecture 6, Maximum Margin and Linear Support Vector Machine slides.

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).

Source: Lecture 6, Training SVMs slide.

@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.

Source Lecture 6, Multi-Class Classification – Vector Form slide.

The cross-entropy loss for soft-max classification simplifies to

\[\mathcal L(\pmb x, y_{GT}) = \class{cloze}{-\log p(C_{GT} \mid \pmb x) = -f_{GT}(\pmb x) + \log \sum_j \exp(f_j(\pmb x))}\]

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$.

Source: Lecture 6, Cross-Entropy Loss – Simplified slide.

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.

Source: Lecture 6, Image Classification in 2 Steps and Image Classification in 2 Steps (Revisited) slides.

@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.

Source Lecture 6, $k$-NN Summary slide.

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.

Source: Lecture 6, ImageNet Classification Challenge slide.