Machine Learning

Machine learning builds programs that improve at a task from examples instead of following rules a person wrote down. Nobody can write the rule that separates photographs of cats from photographs of dogs pixel by pixel, but a learning algorithm given thousands of labelled photographs can find a function that does it, and that function will also label photographs it has never seen. Most of modern computer vision works this way: image classification, object detection, segmentation, depth estimation and tracking all rely on models whose parameters were fitted to data, from the support vector machines that scored hand-designed HOG features to the convolutional networks and vision transformers that learn their features from pixels.

This article is the hub for the ideas those methods share: what it means to learn from data, why the goal is low error on new images rather than on the training images, what controls the difference between the two, which assumptions about images make learning possible, the main kinds of learning problems, the move in vision from designed features to learned representations, and how learned models are evaluated. It summarizes the articles that treat each in depth and links to them. Statistical learning and pattern recognition are closely related names, used by different communities, for much of the same material.

Definition

Machine learning is the study of algorithms that improve their performance on a task through experience, where the experience is usually a set of examples. Goodfellow, Bengio and Courville (2016, §5.1) quote Mitchell’s (1997) definition: a program learns from experience $E$ with respect to a class of tasks $T$ and a performance measure $P$ if its performance at the tasks in $T$, as measured by $P$, improves with $E$. For a classifier of shapes in images, $T$ is assigning a class to each image, $P$ the fraction of new images labelled correctly, and $E$ a set of labelled images.

A learning algorithm combines four ingredients, which Goodfellow and colleagues (§5.10) describe as a recipe that most machine learning algorithms follow: a dataset, a model (a family of functions with adjustable parameters), a cost function or loss that scores the parameters on the data, and an optimization procedure that searches for good parameters. Each can be changed largely independently of the others, which is why so many algorithms exist. The aim of the whole construction is generalization: good performance on new inputs drawn from the same source as the training examples, not only on the examples themselves (§5.2).

Intuition

A student who memorizes the answers to last year’s exam scores perfectly on that exam and learns nothing about the subject. A learning algorithm faces the same temptation. A model flexible enough can reproduce every training label exactly, including the wrong ones and the accidents of each particular image: the noise pattern, the position of the object, the background. What it should learn instead is whatever the training images have in common with the images it will meet later.

Two forces pull against each other. A model that is too rigid, for example one that can only draw a straight boundary between classes that a straight boundary cannot separate, underfits: it is wrong on the training images and on new ones alike. A model that is too flexible for the amount of data overfits: it fits the training images well and new ones badly. Between the two lies a model flexible enough to capture the real structure but not so flexible that the data cannot pin it down. More data moves that balance point toward more flexible models, because each additional example rules out functions that merely happen to fit the others.

The third ingredient is prior knowledge. No finite set of examples determines how to label an image unlike any of them. A learner generalizes only because it prefers some functions over others, for example functions that do not change their answer when an object moves a few pixels. When these preferences match how images actually vary, learning needs fewer examples; when they do not, no amount of tuning recovers.

Formal Definition

Risk and empirical risk minimization

Let images and labels $(\mathbf{x}, y)$ be drawn from an unknown distribution $p(\mathbf{x}, y)$, let $f$ be a predictor from a hypothesis space $\mathcal{H}$ (the functions the model can represent), and let $\ell(y, f(\mathbf{x}))$ be a loss, such as the 0–1 loss $\mathbb{1}[y \ne f(\mathbf{x})]$ for classification or the squared error $(y - f(\mathbf{x}))^2$ for regression. What we want to minimize is the risk (also called the expected risk, population risk or generalization error),

$$R(f) = \mathbb{E}_{(\mathbf{x}, y) \sim p}\big[\ell(y, f(\mathbf{x}))\big].$$

The distribution is unknown; only a training set $\{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ is available, stored, as in scikit-learn, as a data matrix $X \in \mathbb{R}^{n \times d}$ with one image per row and a label vector $\mathbf{y}$. Replacing the expectation by the average over the training set gives the empirical risk, and choosing the predictor that minimizes it is empirical risk minimization (ERM; Murphy, 2022, §5.4.1; Goodfellow et al., §8.1.1):

$$\hat{R}_n(f) = \frac{1}{n}\sum_{i=1}^{n} \ell\big(y_i, f(\mathbf{x}_i)\big), \qquad \hat{f} = \arg\min_{f \in \mathcal{H}} \hat{R}_n(f).$$

In practice a penalty $\lambda\,\Omega(f)$ is usually added, giving the regularized empirical risk of the loss function and regularization articles; with a negative log-likelihood loss and a negative log-prior penalty, minimizing it is MAP estimation (Murphy, §5.4.1.2), which the maximum likelihood estimation article describes. When the loss of interest cannot be minimized efficiently, as the expected 0–1 loss typically cannot, training minimizes a surrogate loss instead, typically the negative log-likelihood of the correct class, the cross-entropy loss (Goodfellow et al., §8.1.2).

The generalization gap

The difference $R(\hat{f}) - \hat{R}_n(\hat{f})$ is the generalization gap (Murphy, §1.2.3, §5.4.1). For a fixed $f$ chosen before seeing the data, $\hat{R}_n(f)$ is an unbiased estimate of $R(f)$. For $\hat{f}$, which was chosen because it does well on these particular examples, it is not: the expected test error is at least the expected training error (Goodfellow et al., §5.2; Hastie, Tibshirani and Friedman, 2009, pose the proof for least squares as Exercise 2.9). The gap is estimated by evaluating $\hat{f}$ on held-out images that played no part in choosing it, which is the job of the test set.

How large can the gap be? For a finite hypothesis space of binary classifiers, the 0–1 loss and $n$ training examples drawn independently from $p$, Hoeffding’s inequality and a union bound give (Murphy, Theorem 5.4.1)

$$P\Big(\max_{h \in \mathcal{H}} \big|R(h) - \hat{R}_n(h)\big| > \epsilon\Big) \le 2\,|\mathcal{H}|\,e^{-2n\epsilon^2},$$

so, setting the right-hand side to $\delta$ and solving for $\epsilon$ (our algebra), with probability at least $1 - \delta$ every $h \in \mathcal{H}$, including the one ERM picks, has a gap of at most $\sqrt{(\ln|\mathcal{H}| + \ln(2/\delta))/(2n)}$. The bound grows with the size of the hypothesis space and shrinks with the number of examples, the pattern that statistical learning theory extends to infinite spaces through capacity measures such as the Vapnik–Chervonenkis dimension, the largest number of points that some placement allows a family of binary classifiers to label in every possible way. Goodfellow and colleagues (§5.2) note that such bounds justify learning in principle but are rarely used in deep learning, being loose and hard to compute for deep networks.

The best possible predictor and two kinds of error

Under the 0–1 loss, the predictor with the smallest possible risk assigns each image to its most probable class,

$$f^{\ast}(\mathbf{x}) = \arg\max_{k} P(y = k \mid \mathbf{x}),$$

the Bayes classifier; its error, the Bayes error or Bayes rate, is the floor that no method can beat, and it is above zero whenever the same image can carry different labels (Hastie et al., §2.4, eq. 2.23; Goodfellow et al., §5.2). The probability and statistics article builds a Bayes classifier for skin pixels from colour histograms.

Murphy (§5.4.1.1) splits the excess risk of the ERM solution $\hat{f}$ over the best possible predictor $f^{\ast}$ into two terms, with $f^{\ast}_{\mathcal{H}}$ the best predictor in the hypothesis space:

$$\mathbb{E}\big[R(\hat{f})\big] - R(f^{\ast}) = \underbrace{R(f^{\ast}_{\mathcal{H}}) - R(f^{\ast})}_{\text{approximation error}} + \underbrace{\mathbb{E}\big[R(\hat{f}) - R(f^{\ast}_{\mathcal{H}})\big]}_{\text{estimation error}},$$

the expectation taken over training sets. A richer hypothesis space lowers the approximation error and usually raises the estimation error, the error from picking a function with finite data.

For squared-error regression with $y = f(\mathbf{x}) + \varepsilon$, $\mathbb{E}[\varepsilon] = 0$ and $\operatorname{Var}(\varepsilon) = \sigma_\varepsilon^2$, the expected error at an input $\mathbf{x}_0$ splits in the same spirit into the bias–variance decomposition (Hastie et al., §7.3, eq. 7.9):

$$\mathbb{E}\big[(y - \hat{f}(\mathbf{x}_0))^2 \mid \mathbf{x} = \mathbf{x}_0\big] = \sigma_\varepsilon^2 + \big[\mathbb{E}\hat{f}(\mathbf{x}_0) - f(\mathbf{x}_0)\big]^2 + \mathbb{E}\big[\hat{f}(\mathbf{x}_0) - \mathbb{E}\hat{f}(\mathbf{x}_0)\big]^2,$$

irreducible noise plus squared bias plus variance, where the expectations average over training sets. Typically, the more complex the model, the lower its bias and the higher its variance (§2.9, §7.3). The decomposition holds for squared error. For the 0–1 loss, Hastie and colleagues (§7.3.1) show by simulation that the error is no longer the sum of squared bias and variance: an estimate of a class probability that is biased but stays on the right side of the decision boundary costs nothing, so the two interact.

Properties

Capacity, underfitting and overfitting

The capacity of a model is, informally, its ability to fit a wide variety of functions (Goodfellow et al., §5.2). It is set by the hypothesis space, for example by the degree of a polynomial, the depth of a decision tree or the number of hidden units, and limited further by what the optimizer actually finds, so that a model’s effective capacity can be less than its representational capacity. Goodfellow and colleagues name the two central challenges of machine learning after the two ways capacity can be wrong: underfitting, when the training error itself is too high, and overfitting, when the gap between training and test error is too large.

As capacity grows, the training error typically falls toward its minimum, often zero, while the test error first falls and then rises: the U-shaped curve of the classical picture (Goodfellow et al., §5.2, Figure 5.3; Hastie et al., §2.9, Figure 2.11, and §7.2, Figure 7.1). The training error is therefore useless for choosing capacity, since it always prefers the most flexible model (Hastie et al., §2.9); a validation set or cross-validation is used instead. A model with enough capacity can push its training error below the Bayes error by memorizing particular examples, which no model can do on new data (Goodfellow et al., §5.2, Figure 5.4). The first example below shows all three effects.

Two refinements matter for vision. First, the expected test error never increases with more training data, and the capacity that minimizes it grows with the size of the training set until it is enough for the task (Goodfellow et al., §5.2, Figure 5.4); the second example traces such learning curves. Second, very large networks complicate the U shape. Image classifiers can fit randomly relabelled training images perfectly and still generalize well on real labels, and test error can peak near the size at which a model first fits its training set exactly and fall again as the model grows, a pattern called double descent; the regularization article summarizes this evidence and the implicit regularization of the optimizer that is thought to explain part of it.

Inductive bias and the no free lunch theorem

Inferring a general rule from finitely many examples is not logically valid (Goodfellow et al., §5.2.1), so a learner must assume something about the examples it has not seen. The set of assumptions that makes one function preferable to another is its inductive bias (Murphy, §1.2.4). The no free lunch theorem makes the necessity precise. Wolpert (1996) studied the error on inputs outside the training set and showed, loosely speaking in his abstract’s words, that for any two learning algorithms there are “as many” targets on which the first has the lower expected error as on which the second does, for losses such as the 0–1 loss; this holds even when one algorithm chooses among learning algorithms by cross-validation and the other picks the one with the largest cross-validation error. Goodfellow and colleagues (§5.2.1) put the consequence this way: averaged over all possible data-generating distributions, every classification algorithm has the same error on unobserved points, but the result holds only for that average, and assumptions about which distributions occur in practice allow algorithms that do well on them. The goal is therefore not a universal learner but learners whose preferences match the data, which for vision means the structure of images (§5.2.2; Murphy, §1.2.4).

The inductive biases vision uses

• Smoothness. A small change to an image should rarely change its label. Goodfellow and colleagues (§5.11.2) call this the smoothness or local-constancy prior and show why it is not enough on its own: methods that rely only on it, such as nearest-neighbour rules and decision trees, need roughly one example per region of input space they distinguish, and in high dimensions the number of regions grows exponentially, the curse of dimensionality (§5.11.1).
• Concentration on a manifold. Images of real scenes occupy a negligible fraction of all possible pixel arrays: uniformly random pixels look like static, never like a face. The manifold hypothesis holds that natural images lie near low-dimensional sets traced out by changes of lighting, position, pose and colour (Goodfellow et al., §5.11.3), which is why representations with far fewer numbers than pixels, from principal components to learned embeddings, can describe them.
• Locality and translation equivariance. Nearby pixels are related more strongly than distant ones, and an object means the same thing wherever it appears. Convolutional networks build both into every layer by applying the same small filters at every position.
• Invariance by construction or by data. Hand-designed features build tolerance in by design: HOG normalizes contrast over blocks of cells and changes little under translations much smaller than a cell, and SIFT describes each keypoint in its own rotated and scaled frame. Data augmentation teaches a network the same invariances by showing it transformed copies of the training images, which must not change the correct answer.
• Priors from other data. Starting from weights trained on a large dataset, by transfer learning or self-supervised learning, carries what was learned from many images into a task with few.

How much bias to build in is a trade-off with data. The vision transformer drops most of the convolutional biases; its authors found it trailed comparable CNNs when trained on ImageNet alone and became competitive or better when pre-trained on 14 to 300 million images, where scale outweighed the missing bias.

The i.i.d. assumption

The link between training and test error rests on assumptions about how the data are collected: that the examples are independent, and that training and test examples are drawn from the same distribution, the i.i.d. assumptions (Goodfellow et al., §5.2). Vision breaks them routinely. Frames of one video are not independent, which lets near-duplicates leak across a split, and deployed systems meet new cameras, lighting, viewpoints and object positions. A model can score well on a held-out set from its own distribution and fail on a slightly different one, as the third example below shows; image classification describes dataset bias, distribution shift and shortcut learning in real benchmarks.

Learning Paradigms

Learning problems are grouped by the kind of experience the algorithm receives. Goodfellow and colleagues (§5.1.3) stress that the categories are not formally defined and that their boundaries blur, since a joint distribution can be factored into conditional ones and vice versa.

• Supervised learning learns to predict a label or target $y$ from an input $\mathbf{x}$, usually by estimating $p(y \mid \mathbf{x})$, from labelled examples; Hastie and colleagues (§14.1) call it learning with a teacher. Classification predicts a discrete class (the object in an image, defective or not); regression predicts a continuous quantity (depth, a bounding-box coordinate, a camera’s pose). Structured outputs such as segmentation masks are predicted the same way, one output per pixel.
• Unsupervised learning observes only inputs and learns properties of their distribution $p(\mathbf{x})$ (§5.1.3; Hastie et al., §14.1): density estimation models the distribution itself, clustering divides the data into groups of similar examples, and dimensionality reduction finds a few coordinates that describe most of the variation. Its evaluation is harder, because there are no correct answers to compare with (Murphy, §1.3.4).
• Self-supervised learning creates a supervised task from unlabelled data, such as predicting a colour image from its grayscale version (Murphy, §1.3.3) or which two crops come from the same photograph, to learn a representation for later tasks; the self-supervised learning article covers its methods for images.
• Semi-supervised learning combines a few labelled examples with many unlabelled ones, learning the structure of the data from the unlabelled images and the task details from the labelled ones (Murphy, §19.3).
• Reinforcement learning learns a policy that chooses actions from observations, for example from the frames of a video game, guided by an occasional reward rather than by correct answers (Murphy, §1.4).

The classical methods most used in vision illustrate the first two paradigms. The k-nearest-neighbour classifier labels an image by a vote among the $k$ most similar training images under a chosen distance. Logistic regression models class probabilities as a softmax of linear functions of the features, fitted by maximum likelihood. The support vector machine finds the linear boundary with the largest margin between classes, and with kernels a nonlinear one. Principal component analysis finds the orthogonal directions along which a set of images or descriptors varies most, the basis of eigenfaces and of descriptor compression. Among clustering methods, k-means alternates between assigning points to the nearest of $k$ centres and moving each centre to the mean of its points, the method behind visual vocabularies and colour quantization; a Gaussian mixture model assigns points softly to Gaussian components, usually fitted by the expectation–maximization algorithm; and mean shift climbs the gradient of a kernel density estimate to its modes, which serves for segmentation and tracking. Boosting combines many weak classifiers into a strong one, as in the face detector of Viola and Jones. Neural networks, trained by stochastic gradient descent on large labelled or unlabelled image collections, now serve in every paradigm.

Features and Learned Representations

A pixel array is a poor input for a simple classifier: the same object produces very different pixels under changes of position, scale, lighting and viewpoint. For most of the history of vision, people therefore designed features, fixed functions of the pixels meant to keep what matters for the task and discard what does not, and trained a classifier on them. Image classification describes the three-stage pipeline in use before 2012: local descriptors such as SIFT or HOG, an encoding into one fixed-length vector per image such as a bag of visual words histogram or a Fisher vector, and a linear classifier, usually a support vector machine. HOG scored by a linear SVM, introduced by Dalal and Triggs in 2005 for detecting people, and its descendants, the deformable part models, were the detectors that the first large deep-learning result in detection was measured against. Only the classifier was learned; the features embodied years of design.

Representation learning learns the features too. A convolutional neural network maps pixels to class scores through many layers trained end to end, so that its early layers learn edge and colour detectors and its later layers parts and objects. The decisive demonstration came on ImageNet: in the 2012 challenge, AlexNet reached a top-5 test error of 15.3% against 26.2% for the second-best entry, which used Fisher vectors, and the organizers called that year a turning point, after which the vast majority of entries used deep CNNs. Three things had changed together, as those articles describe: a labelled training set of about 1.2 million images; GPU implementations that made training a network of 60 million parameters feasible; and defences against overfitting, still a serious problem with that many images, among them dropout and data augmentation. Learned features also transferred: a network pretrained on ImageNet became the usual starting point for detection, segmentation and other tasks with less data (transfer learning).

Designed features remain useful when labelled data are scarce, computation is limited or interpretability matters, which the second example below illustrates in miniature.

The Evaluation Workflow

Because the training error is optimistic, a learned model is judged on data it has not seen. The training, validation and test sets article covers the standard arrangement: the training set fits the parameters, the validation set guides choices such as capacity and regularization strength (model selection), and the test set, used once at the end, estimates the finished model’s error on new data (model assessment), a distinction Hastie and colleagues (§7.2) draw. When labelled images are too few for a separate validation set, cross-validation rotates which part of the data is held out and averages the scores, with nested cross-validation keeping selection and assessment apart. Across a research community, reusing one fixed test set for years can in principle inflate scores; the replication studies summarized in benchmark overfitting found that accuracies did drop on fresh test sets, but mostly for reasons other than test-set reuse. Which number to report, accuracy, precision and recall or a calibrated probability, and whether a difference between two models is real (statistical significance) are questions of their own.

Examples

The three examples use one synthetic dataset with exactly known ground truth: $24 \times 24$ grayscale images of a disk, a square or an upright triangle, with random size (a size parameter of 5–8 pixels: the disk’s radius, from which the square and triangle are scaled), position, contrast (0.5–1.0 on a background of 0) and Gaussian noise of standard deviation 0.2. Each image is one row of the data matrix. Two representations are compared: the 576 raw pixel values, and a hand-designed feature, a 12-bin histogram of gradient orientations weighted by gradient magnitude and pooled over the whole image, which by construction ignores where the shape is. The outputs came from NumPy 2.3.5, SciPy 1.16.3 and scikit-learn 1.7.2, whose defaults are used unless the code says otherwise.

Capacity and overfitting

The first block varies the capacity of a decision tree, a classifier that splits the feature space by a sequence of threshold tests, through its maximum depth. It trains on 300 images, 10% of whose labels have been replaced by another class at random, and measures the error on 5,000 fresh images from the same distribution, labels equally noisy, which stands in for the risk. It repeats this for five independent datasets.

import numpy as np
from scipy import ndimage
from sklearn.tree import DecisionTreeClassifier

S = 24                                          # image size (pixels)
yy, xx = np.mgrid[0:S, 0:S] + 0.5               # pixel-centre coordinates

def render(cls, rng, x_range=(0.0, 1.0)):
    """A 24x24 grayscale image of a disk (0), square (1) or upright triangle (2) of
    random size, position and contrast, plus Gaussian noise. x_range limits where the
    shape's centre may fall, as a fraction of the allowed horizontal range."""
    r = rng.uniform(5.0, 8.0)
    lo, hi = r + 1, S - r - 1
    cy = rng.uniform(lo, hi)
    cx = rng.uniform(lo + x_range[0] * (hi - lo), lo + x_range[1] * (hi - lo))
    dy, dx = yy - cy, xx - cx
    if cls == 0:
        mask = dy**2 + dx**2 < r**2
    elif cls == 1:
        mask = (np.abs(dy) < 0.85 * r) & (np.abs(dx) < 0.85 * r)
    else:
        mask = (dy < 0.7 * r) & (dy > -r + 1.8 * np.abs(dx))
    return rng.uniform(0.5, 1.0) * mask + rng.normal(0, 0.2, (S, S))

def dataset(n, rng, flip=0.0, x_range=(0.0, 1.0)):
    """n images with labels; a fraction `flip` of labels is replaced by another class."""
    y = rng.integers(0, 3, n)
    X = np.stack([render(c, rng, x_range).ravel() for c in y])   # one image per row
    wrong = rng.random(n) < flip
    return X, np.where(wrong, (y + rng.integers(1, 3, n)) % 3, y)

def orientation_histogram(X, bins=12):
    """Hand-designed feature: gradient orientations (mod 180 degrees), weighted by
    gradient magnitude and pooled over the whole image, so position is discarded."""
    F = []
    for x in X:
        g = ndimage.gaussian_filter(x.reshape(S, S), 1.0)
        gy, gx = ndimage.sobel(g, 0), ndimage.sobel(g, 1)
        mag, ang = np.hypot(gx, gy).ravel(), np.mod(np.arctan2(gy, gx), np.pi).ravel()
        h = np.bincount((ang / np.pi * bins).astype(int) % bins, weights=mag, minlength=bins)
        F.append(h / h.sum())
    return np.array(F)

# Capacity sweep: decision trees of growing depth on the 12 orientation features,
# 300 training images with 10% wrong labels, error measured on 5,000 fresh images
# from the same distribution (labels equally noisy). Five independent datasets.
depths = [1, 2, 3, 4, 5, 6, 8, 10, None]
err = np.zeros((5, len(depths), 2))
for seed in range(5):
    rng = np.random.default_rng(seed)
    X_tr, y_tr = dataset(300, rng, flip=0.1)
    X_te, y_te = dataset(5000, rng, flip=0.1)
    F_tr, F_te = orientation_histogram(X_tr), orientation_histogram(X_te)
    for j, d in enumerate(depths):
        tree = DecisionTreeClassifier(max_depth=d, random_state=0).fit(F_tr, y_tr)
        err[seed, j] = 1 - tree.score(F_tr, y_tr), 1 - tree.score(F_te, y_te)

print("max_depth  training error  test error  gap    test error over 5 datasets")
for j, d in enumerate(depths):
    tr, te = err[:, j, 0], err[:, j, 1]
    print(f"{str(d):>9}  {tr.mean():14.3f}  {te.mean():10.3f}  {te.mean() - tr.mean():5.3f}"
          f"  {te.min():.3f} to {te.max():.3f}")
best = err[:, :, 1].argmin(axis=1)
print("depth with the lowest test error, per dataset:", [str(depths[b]) for b in best])

Output:

max_depth  training error  test error  gap    test error over 5 datasets
        1           0.389       0.425  0.036  0.403 to 0.450
        2           0.233       0.293  0.060  0.283 to 0.301
        3           0.186       0.273  0.087  0.256 to 0.287
        4           0.137       0.257  0.120  0.244 to 0.272
        5           0.103       0.263  0.160  0.240 to 0.300
        6           0.071       0.279  0.208  0.263 to 0.306
        8           0.032       0.298  0.266  0.282 to 0.325
       10           0.011       0.310  0.299  0.284 to 0.334
     None           0.000       0.312  0.312  0.289 to 0.339
depth with the lowest test error, per dataset: ['5', '4', '5', '5', '4']

The training error falls steadily to zero as depth grows, while the test error traces the U of the classical picture: shallow trees underfit, with high error on both sets, and deep trees overfit, with a gap that keeps widening. Because each label is replaced with probability 0.10 independently of the image, by another class, no class has probability above 0.90 given any image, so by our reasoning no classifier can have an expected error below 0.10 on this distribution; predicting the true class reaches that floor wherever the image determines the class. Trees of depth 6 and more nevertheless reach training errors below 0.10, so they are memorizing wrong labels, the memorization below the Bayes error that Goodfellow and colleagues describe. The best depth differs between datasets drawn from the same distribution, which is why capacity is chosen on a validation set or by cross-validation for the data at hand rather than fixed in advance.

Learning curves, features and pixels

The second block, which continues from the first, trains three classifiers on nested training sets of 10 to 10,000 clean images and tests each on 3,000 fresh images: a linear classifier (multinomial logistic regression with scikit-learn’s default L2 penalty, C=1.0, on standardized inputs) on the raw pixels; the same linear classifier on the 12 orientation features; and a multilayer perceptron with one hidden layer of 256 units on the raw pixels, trained with scikit-learn’s default Adam optimizer and penalty. It repeats this for three datasets and prints the mean errors and the spread of the test error, maximum minus minimum. It takes about half a minute on a laptop.

import warnings
from sklearn.exceptions import ConvergenceWarning
from sklearn.linear_model import LogisticRegression
from sklearn.neural_network import MLPClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
warnings.filterwarnings("ignore", category=ConvergenceWarning)

def models(seed):
    return {
        "linear, raw pixels":     (False, make_pipeline(StandardScaler(), LogisticRegression(max_iter=5000))),
        "linear, orientations":   (True,  make_pipeline(StandardScaler(), LogisticRegression(max_iter=5000))),
        "MLP (256), raw pixels":  (False, MLPClassifier(hidden_layer_sizes=(256,), max_iter=300, random_state=seed)),
    }

sizes = [10, 30, 100, 300, 1000, 3000, 10000]
names = list(models(0))
err = np.zeros((3, len(names), len(sizes), 2))
for seed in range(3):
    rng = np.random.default_rng(100 + seed)
    X_pool, y_pool = dataset(sizes[-1], rng)      # training sets are nested prefixes
    X_te, y_te = dataset(3000, rng)               # clean labels this time
    F_pool, F_te = orientation_histogram(X_pool), orientation_histogram(X_te)
    for i, (use_feat, model) in enumerate(models(seed).values()):
        A, A_te = (F_pool, F_te) if use_feat else (X_pool, X_te)
        for j, n in enumerate(sizes):
            model.fit(A[:n], y_pool[:n])
            err[seed, i, j] = 1 - model.score(A[:n], y_pool[:n]), 1 - model.score(A_te, y_te)

for i, name in enumerate(names):
    print(name)
    print("  n train:      " + "".join(f"{n:>7}" for n in sizes))
    print("  train error:  " + "".join(f"{e:7.3f}" for e in err[:, i, :, 0].mean(0)))
    print("  test error:   " + "".join(f"{e:7.3f}" for e in err[:, i, :, 1].mean(0)))
    print("  test spread:  " + "".join(f"{e:7.3f}" for e in err[:, i, :, 1].max(0) - err[:, i, :, 1].min(0)))

Output:

linear, raw pixels
  n train:           10     30    100    300   1000   3000  10000
  train error:    0.000  0.000  0.000  0.000  0.000  0.180  0.269
  test error:     0.591  0.487  0.456  0.434  0.433  0.397  0.328
  test spread:    0.114  0.029  0.012  0.030  0.042  0.014  0.024
linear, orientations
  n train:           10     30    100    300   1000   3000  10000
  train error:    0.000  0.000  0.047  0.056  0.059  0.062  0.063
  test error:     0.148  0.104  0.075  0.064  0.062  0.061  0.061
  test spread:    0.059  0.030  0.017  0.011  0.010  0.004  0.009
MLP (256), raw pixels
  n train:           10     30    100    300   1000   3000  10000
  train error:    0.000  0.000  0.000  0.000  0.000  0.000  0.000
  test error:     0.623  0.557  0.496  0.405  0.263  0.123  0.043
  test spread:    0.069  0.039  0.018  0.030  0.025  0.010  0.006

The linear classifier on raw pixels has 577 parameters per class, so it fits every training set of up to 1,000 images, to three decimals of training error, and still mislabels more than four test images in ten: a large gap, overfitting from too little data for the model’s capacity. With 3,000 and 10,000 images it can no longer fit the training set and the gap narrows, but its test error stays far above the other two, which is approximation error: in our reading, a linear function of pixel values cannot recognize a shape regardless of where it lies. The orientation histogram has the opposite profile. Its designed invariance makes ten examples enough for an error under 15%, and its curve flattens from about 300 images on, with training and test error meeting at a floor set by what the twelve numbers can express. The perceptron has the most capacity of the three and memorizes every training set; with up to 100 images it is the worst of the three, and by 10,000 images it beats the designed feature. The three curves are, in miniature, the history of the previous section: designed features win when labelled data are scarce, and a flexible model learned from pixels overtakes them once there is enough data to pin it down. A convolutional network builds in locality and translation equivariance; the convolutional neural network article compares one with a fully connected network of the same size on digit images, including shifted ones.

When the i.i.d. assumption fails

The third block, which continues from the second, trains the same three models on 3,000 images in which every shape lies in the left part of the frame, then tests them on fresh images from the same distribution and on images in which every shape lies in the right part.

# Train on 3,000 images whose shapes lie in the left part of the frame; test on
# fresh images from the same distribution and on images with shapes on the right.
res = np.zeros((3, 3, 2))
for seed in range(3):
    rng = np.random.default_rng(200 + seed)
    X_tr, y_tr = dataset(3000, rng, x_range=(0.0, 0.5))
    X_same, y_same = dataset(3000, rng, x_range=(0.0, 0.5))
    X_shift, y_shift = dataset(3000, rng, x_range=(0.5, 1.0))
    for i, (use_feat, model) in enumerate(models(seed).values()):
        f = orientation_histogram if use_feat else (lambda X: X)
        model.fit(f(X_tr), y_tr)
        res[seed, i] = 1 - model.score(f(X_same), y_same), 1 - model.score(f(X_shift), y_shift)

print("                         test error, shapes left   test error, shapes right")
for i, name in enumerate(names):
    a, b = res[:, i, 0], res[:, i, 1]
    print(f"{name:<24} {a.mean():.3f} ({a.min():.3f} to {a.max():.3f})"
          f"       {b.mean():.3f} ({b.min():.3f} to {b.max():.3f})")

Output:

                         test error, shapes left   test error, shapes right
linear, raw pixels       0.265 (0.259 to 0.269)       0.663 (0.653 to 0.673)
linear, orientations     0.065 (0.060 to 0.069)       0.061 (0.055 to 0.064)
MLP (256), raw pixels    0.084 (0.079 to 0.089)       0.644 (0.639 to 0.655)

On held-out images from its own distribution the perceptron looks like a good shape classifier, with under 10% error. Moved to the other side of the frame, the same shapes are classified at about chance, which for three balanced classes is an error of 0.667: what the network learned is tied to pixel positions it saw in training, and nothing in a fully connected layer relates one position to another. The linear classifier on pixels fails in the same way. The orientation histogram is unaffected, because its invariance to position holds by construction rather than being learned from examples. A held-out test set measures generalization only to the distribution it was drawn from; data augmentation with shifts, or an architecture with the right equivariance, is how vision models are given the invariance the training images did not show them.

Common Misconceptions

• “Low training error means a good model.” Training error measures fit, not generalization; a sufficiently flexible model reaches zero training error even on wrong labels, as the first example shows. Only error on data that played no part in fitting or choosing the model estimates performance on new images.
• “More capacity always overfits.” Whether capacity is too much depends on the amount of data: the perceptron in the second example overfits badly at 100 images and is the best model at 10,000. Very large networks can also generalize well while fitting their training sets exactly, as the double-descent evidence summarized in regularization shows.
• “Some learning algorithm is best for everything.” The no free lunch theorem rules this out once nothing is assumed about the data; a method is good for images because its inductive biases suit images.
• “Learned features made prior knowledge unnecessary.” The prior knowledge moved into the architecture (convolutions), the training data, the augmentations and the pretraining, and the amount of data needed grows as built-in assumptions are removed, as the vision transformer illustrates.
• “A high score on a held-out test set guarantees performance in deployment.” The guarantee holds only for new data from the same distribution as the test set; the pixel-based models in the third example fail completely under a shift their test set did not contain.
• “Machine learning and optimization are the same thing.” Training is posed as an optimization problem, but the quantity minimized, the empirical risk of a surrogate loss, is not the one that matters, the expected error on new data; Goodfellow and colleagues (§5.2, §8.1.1–§8.1.2) draw this distinction, and note that training usually halts by early stopping on a validation measure while the surrogate loss still has large derivatives.

Where It Is Used

• Recognition: image classification, object detection, face recognition and image retrieval learn classifiers or embeddings from labelled or unlabelled images; earlier systems paired HOG or bag-of-visual-words features with support vector machines, and the Viola–Jones detector used boosting.
• Dense prediction: image segmentation, depth estimation and optical flow predict one output per pixel with convolutional networks and vision transformers.
• Representation learning: self-supervised learning, contrastive learning, autoencoders and metric learning learn features without, or with weak, labels, which transfer learning reuses for new tasks.
• Classical pipelines: clustering descriptors into visual vocabularies, reducing descriptors’ dimension, modelling background colours with Gaussian mixtures and segmenting images by mean shift all apply unsupervised learning.
• Training and evaluation: neural network training minimizes a loss function with stochastic gradient descent and regularization, and the train/validation/test split, cross-validation and the study of benchmark overfitting measure how well the result generalizes.