3. Classification: Supervised

Nearest neighbour, linear classifiers, Haar features, SVM, kernels, AdaBoost, sliding window detection

1. Supervised Classification

In supervised learning, every training example has both an input vector (image) and a target label. The algorithm learns a mapping from inputs to labels that generalizes to unseen examples.

Supervised learning: labeled data, direct feedback, goal is to predict outputs. Unsupervised: no labels, find hidden structure.

Data-Driven Approach Pipeline

1. Collect a dataset of images and assign labels.
2. Train a classifier using machine learning.
3. Evaluate on a new, unseen set of images.

There is no hardcoded function that can classify images — visual concepts are too variable and complex to specify with simple rules. Machine learning is essential.

Example training set: labeled images from multiple categories. Each image is manually annotated.

2. The Semantic Gap and Classification Challenges

A 600x400 color image is stored as 600x400x3 integers. The computer has no built-in notion of "cat-ness."

Why Pixel-Level Matching Fails

3. Nearest Neighbour Classifier

The simplest possible classifier: memorize all training images, then classify a test image by finding the most similar training image.

Distance Metrics

L1 Manhattan distance computation between two pixel vectors.

L1 distance: compute absolute difference at each pixel position and sum. Example yields L1 = 456.

Decision Regions: Voronoi Diagram

Nearest Neighbour creates a Voronoi diagram: each region is assigned the label of the nearest training point.

CIFAR-10 Results

CIFAR-10 has 10 classes, 50,000 training images, and 10,000 test images (32×32 color).

CIFAR-10: 10 classes (airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck).

NN on CIFAR-10: each row shows a test image (left) and its 10 nearest training neighbors. Many neighbors come from wrong classes — pixel similarity does not capture semantic meaning.

4. K-Nearest Neighbour (K-NN) Classifier

Instead of using the single nearest neighbor, find the K closest training points and use majority voting:

Decision boundaries for K=1 (jagged Voronoi), K=3 (smoother), and K=5 (smoothest). White regions = no majority class.

5. Linear Classifiers

Instead of comparing images by distance, linear classifiers use a parametric model — a mathematical function with learnable parameters.

For a 32x32x3 CIFAR-10 image: x is 3072x1, W is 10x3072, output is 10 class scores.

Multi-Class Example

Weight matrix W with 3 rows (cat, dog, ship) and 4 columns (one weight per pixel).

Class scores for a 4-pixel input: Cat = -96.8, Dog = 437.9, Ship = 61.95. Prediction: Dog (highest score).

6. Haar-like Features

Raw pixel values change with viewpoint and lighting. Haar-like features encode local structural patterns (edges, lines, rectangles) that are more robust to such variations.

Types of Haar-like Features

(a) Edge features: adjacent white/black rectangles. (b) Line features: 3 alternating rectangles. (c) Four-rectangle features: 2x2 checkerboard.

Computing Haar Features

1. Assign weight +1 to white pixels in the mask, -1 to black pixels.
2. Slide the mask over the image at every possible position.
3. At each position, compute the weighted sum (white sum − black sum).
4. If $|\text{white sum} - \text{black sum}| > \tau$ (threshold), a Haar feature is detected.

Image patch:        Mask:
 2  3  2  3        +1 +1 +1 +1
 2  2  3  3        +1 +1 +1 +1
 8  9  8  7        -1 -1 -1 -1
 7  8  9  8        -1 -1 -1 -1

White sum = 2+3+2+3+2+2+3+3 = 20
Black sum = 8+9+8+7+7+8+9+8 = 64
Response = |20 - 64| = 44 > threshold (5) --> Feature DETECTED

Haar Features in a Linear Classifier

Each Haar feature type becomes one dimension of the feature vector. The linear classifier learns weights $W_{C,i}$ for each feature $x_i$ per class $C$:

AdaBoost selects Haar features in stages: Stage 0 uses the 3 most powerful, Stage 1 adds ~10 more, Stage 21 uses 200+.

7. Dataset Splitting for Machine Learning

Three-way split: training set (fit parameters), validation set (tune hyperparameters), test set (final evaluation, used once).

8. Support Vector Classifier (Linear)

The SVC finds the optimal separating hyperplane between two classes by maximizing the margin — the distance between the hyperplane and the nearest data points of each class.

1D Case: Hard vs Soft Margins

For binary classification on a 1D feature: a naive threshold at the midpoint between nearest opposite-class samples fits the training data perfectly (low bias) but may generalize poorly (high variance) because outliers can pull it off.

Soft margins: allow omission of $n$ outliers closest to the boundary. Wider margins = better generalization.

Hyperplane Mathematics

Multi-Dimensional SVC

In 2D (mass, height), the boundary is a line. Adding a 3rd feature (age) extends it to a plane.

In 3D, the SVC finds a plane separating the classes. In n dimensions, it finds an (n-1)-dimensional hyperplane.

Multi-Class SVM

Multi-class SVM: multiple hyperplanes partition the feature space. One-vs-Rest trains C binary classifiers; One-vs-One trains C(C-1)/2 classifiers.

9. SVM — Non-Linear Kernels

Linear SVC fails when data is not linearly separable. The kernel trick maps data to a higher-dimensional space where linear separation is possible.

1D dosage data: "cured" patients in [3,7], "not cured" at [0,2] and [8,10]. No single threshold can separate them.

Kernel Types

Different kernels produce different decision boundary shapes: linear (flat), polynomial (curved), RBF (circular/elliptical), sigmoid.

Polynomial Kernel: 1D to 2D

Map each sample $x$ to $(x, x^2)$. Mid-range "cured" values (moderate $x^2$) separate from extreme "not cured" values.

Step 1: Add a $x^2$ axis. 1D samples become 2D points $(x, x^2)$.

Step 2: In 2D space, a linear SVC can now separate the two classes with a straight line.

Polynomial Kernel: 2D to 3D

For circular boundaries in 2D: map $(x_1, x_2) \to (x_1^2, x_2^2, \sqrt{2}x_1x_2)$. In this 3D space, a flat hyperplane separates the classes. Projected back to 2D: circular boundary.

The circular 2D boundary becomes a flat separating plane in the 3D polynomial feature space.

10. AdaBoost Classifier

Naive Haar classifiers use all 100,000+ features — too slow and most are individually weak. AdaBoost (Adaptive Boosting) selects only the most powerful features and combines them into a strong classifier.

Initialization

Assign equal weights to all training images (faces and non-faces):

For Each of T Rounds

Step 1: Normalize weights to form a probability distribution: $w_{t,i} \leftarrow w_{t,i} / \sum_j w_{t,j}$

Step 2: Select best weak classifier. For each Haar feature $j$, compute weighted error:

Step 3: Update weights. Misclassified images get higher relative weights — the next round focuses on hard cases:

Final Strong Classifier

Viola-Jones AdaBoost face detector: selected Haar features and the attentional cascade structure.

11. Object Detection (Sliding Window)

Image Pyramid

Objects can appear at any scale. An image pyramid handles this: create copies of the image at decreasing resolutions (1/2, 1/4, 1/8, ...). The fixed-size detector can then find objects of any size.

Image pyramid: the original is repeatedly blurred and subsampled. A fixed-size sliding window can now detect objects of any original size.

Cascaded Detection (Attentional Cascade)

Sliding a classifier over every position at every scale is slow. Key insight: most windows contain no object — reject them early.

Cascade: sub-windows pass through increasingly complex stages. Non-face windows are rejected early; only true detections pass all stages.

Classifier Comparison Summary

Flashcards