Support Vector Machine

A support vector machine (SVM) is a classifier that separates two classes by the hyperplane that leaves the widest possible gap, the margin, between them. Only the training examples on the edge of that gap or inside it, the support vectors, determine the boundary; all others could be deleted without changing it. Allowing some examples inside the gap at a price gives the soft-margin SVM, which is a linear classifier trained with the hinge loss and a squared-norm penalty. Its dual form touches the data only through inner products, so replacing them with a kernel turns it into a nonlinear classifier at no extra cost in the formulation.

From the mid-2000s to the mid-2010s the SVM was the usual classifier in vision pipelines. Dalal and Triggs scored histograms of oriented gradients with a linear SVM to find people, deformable part models generalized it to a latent SVM with movable parts, bag-of-visual-words image classifiers used it with histogram kernels, and the first R-CNN detector put one linear SVM per class on top of features from a convolutional network. This article covers the method as it is used today; the machine learning hub places it among the other classical learners, and optimization covers the convexity, Lagrange multipliers and duality it relies on.

Problem

Given $n$ training examples, stored as the rows of a matrix $X \in \mathbb{R}^{n \times d}$ (one image or image window per row, as scikit-learn stores them), and labels $y_i \in \{-1, +1\}$, find a function $f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b$ whose sign predicts the label of a new example. SVMs use $\pm 1$ labels, as Cortes and Vapnik (1995) and Bishop (2006, §7.1) do, because the product $y_i f(\mathbf{x}_i)$ is then positive exactly when example $i$ is classified correctly; logistic regression is usually written with $\{0, 1\}$ labels instead.

When the classes can be separated by a hyperplane, infinitely many hyperplanes do it. The SVM asks for the one that is farthest from the nearest training example of either class, on the grounds that a boundary with room on both sides should tolerate the small changes between a training window and a new one. When the classes overlap, as image features nearly always do, it asks for the best compromise between a wide margin and few examples on the wrong side of it.

Inputs and Outputs

Inputs: the feature matrix $X$ (a HOG descriptor, a word histogram, a CNN embedding or raw pixels for each image), the labels, a penalty $C > 0$, and for nonlinear SVMs a kernel $K(\mathbf{x}, \mathbf{x}')$ with its parameters.

Outputs: a multiplier $\alpha_i \in [0, C]$ for every training example, nonzero only for the support vectors; a bias $b$; and, for a linear kernel, the weight vector $\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i$. The trained classifier returns a real-valued score $f(\mathbf{x})$, the decision value, whose sign is the predicted class and whose size is proportional to the distance from the boundary ($f = \pm 1$ on the margin planes); it is not a probability.

Intuition

Picture the positive and negative examples as two clouds of points. A linear classifier is a line (in $d$ dimensions, a hyperplane) between them. Thicken the line into a slab and widen it until it touches points on both sides: the SVM picks the line whose slab can be made widest. The points touching the slab hold it in place, as nails hold a plank, and moving any other point, as long as it stays outside the slab, changes nothing. Boyd and Vandenberghe’s version of this picture, finding the thickest slab between two separable point sets and its dual as the distance between their convex hulls, is summarized in the optimization article.

Real data rarely leave an empty slab. The soft margin lets points enter the slab or cross the line, each paying a penalty proportional to how far it intrudes; the constant $C$ sets the exchange rate between that penalty and the slab’s width. A small $C$ buys a wide slab with many intruders; a large $C$ narrows the slab until almost nobody intrudes, and for separable data it recovers the empty slab.

The kernel adds a second idea. If the classes cannot be separated by a hyperplane in the original features, they may be separable after a nonlinear map into a space of many more, even infinitely many, dimensions. The SVM never needs the mapped vectors themselves, only their inner products, and a kernel computes those inner products directly from the original features.

Algorithm

Training a soft-margin SVM:

1. Choose the features and the kernel. Scale the features (SVMs are not invariant to the scale of each feature, as the scikit-learn guide warns), choose a kernel, and compute the Gram matrix $K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)$, or the parts of it a solver requests.
2. Solve the dual problem below for the multipliers $\alpha_i$: a convex quadratic program with box constraints $0 \le \alpha_i \le C$ and one equality constraint $\sum_i \alpha_i y_i = 0$.
3. Keep the support vectors, the examples with $\alpha_i > 0$, and compute the bias $b$ from those with $0 < \alpha_i < C$, which lie exactly on the margin.
4. Classify a new example by the sign of $f(\mathbf{x}) = \sum_{i \in \mathrm{SV}} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b$; for a linear kernel, compute $\mathbf{w}$ once and evaluate $\mathbf{w}^\top \mathbf{x} + b$.
5. Choose $C$ and the kernel parameters by cross-validation or on a validation set, repeating steps 2 to 4 for each candidate.

For a linear SVM on many examples, step 2 is often replaced by a solver that works on $\mathbf{w}$ directly: coordinate descent, a Newton method or stochastic gradient descent on the hinge-loss objective.

Mathematical Formulation

The hard margin

The distance from a point $\mathbf{x}$ to the hyperplane $f(\mathbf{x}) = 0$ is $|f(\mathbf{x})| / \lVert \mathbf{w} \rVert$ (Bishop, §7.1). Scaling $\mathbf{w}$ and $b$ by the same factor does not move the hyperplane, so they can be scaled until the closest examples satisfy $y_i f(\mathbf{x}_i) = 1$. The two planes $f(\mathbf{x}) = \pm 1$ then bound an empty slab of width $2 / \lVert \mathbf{w} \rVert$, which Cortes and Vapnik call the margin (their Eq. 13); Bishop calls half of it, the distance from the boundary to the closest example, the margin. Maximizing it is the hard-margin problem

$$\min_{\mathbf{w}, b} \ \tfrac{1}{2} \lVert \mathbf{w} \rVert^2 \quad \text{subject to} \quad y_i (\mathbf{w}^\top \mathbf{x}_i + b) \ge 1, \quad i = 1, \dots, n,$$

a quadratic program with a convex objective and linear constraints, whose solution Cortes and Vapnik call the optimal hyperplane and describe as unique. It exists only if the data are linearly separable.

The soft margin and the hinge loss

For overlapping classes, each constraint gets a slack variable $\xi_i \ge 0$ that measures how far example $i$ falls short of the margin:

$$\min_{\mathbf{w}, b, \boldsymbol{\xi}} \ \tfrac{1}{2} \lVert \mathbf{w} \rVert^2 + C \sum_{i=1}^{n} \xi_i \quad \text{subject to} \quad y_i (\mathbf{w}^\top \mathbf{x}_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0.$$

An example with $\xi_i = 0$ is on or outside its margin plane, one with $0 < \xi_i \le 1$ is inside the margin but still on the correct side, and one with $\xi_i > 1$ is misclassified, so $\sum_i \xi_i$ bounds the number of training errors from above (Bishop, §7.1.1). This is the C-support vector classification problem as LIBSVM states it (Chang and Lin, 2011, Eq. 1), citing Boser, Guyon and Vapnik (1992) and Cortes and Vapnik (1995). Cortes and Vapnik’s own paper treats a more general penalty, derives this linear form in its Appendix A.2, and used the squared total slack, $C \big(\sum_i \xi_i\big)^2$, in its experiments.

At the optimum each slack is as small as its constraint allows, $\xi_i = \max\big(0, 1 - y_i f(\mathbf{x}_i)\big)$, which turns the constrained problem into an unconstrained one (Bishop, §7.1.2, Eq. 7.44):

$$\min_{\mathbf{w}, b} \ \sum_{i=1}^{n} \max\big(0,\ 1 - y_i (\mathbf{w}^\top \mathbf{x}_i + b)\big) + \lambda \lVert \mathbf{w} \rVert^2, \qquad \lambda = \frac{1}{2C}.$$

The first term is the hinge loss, a convex upper bound on the 0–1 loss that is exactly zero for every example beyond its margin plane; the second is the squared-norm penalty of regularization, here on $\mathbf{w}$ but not on $b$. In the language of the loss function and machine learning articles, the SVM is regularized empirical risk minimization with the hinge loss as a surrogate for the 0–1 loss. Replacing the hinge by $\ln\big(1 + e^{-y f(\mathbf{x})}\big)$ gives L2-regularized logistic regression; Bishop (§7.1.2, Fig. 7.5) plots the two losses together and attributes the SVM’s sparse solutions to the flat part of the hinge. The squared hinge $\max(0, 1 - y f(\mathbf{x}))^2$, which LIBLINEAR calls the L2-loss SVM, is a differentiable alternative (Fan et al., 2008).

The dual problem

Attaching multipliers $\alpha_i \ge 0$ to the margin constraints and $\mu_i \ge 0$ to $\xi_i \ge 0$ gives the Lagrangian (Bishop, Eq. 7.22)

$$L = \tfrac{1}{2} \lVert \mathbf{w} \rVert^2 + C \sum_i \xi_i - \sum_i \alpha_i \big( y_i (\mathbf{w}^\top \mathbf{x}_i + b) - 1 + \xi_i \big) - \sum_i \mu_i \xi_i .$$

Setting its derivatives with respect to $\mathbf{w}$, $b$ and $\xi_i$ to zero gives

$$\mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i, \qquad \sum_{i=1}^{n} \alpha_i y_i = 0, \qquad \alpha_i = C - \mu_i ,$$

and substituting them back eliminates the primal variables. Because $\mu_i \ge 0$, the multipliers end up in a box, and the dual problem is

$$\max_{\boldsymbol{\alpha}} \ \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j\, \mathbf{x}_i^\top \mathbf{x}_j \quad \text{subject to} \quad 0 \le \alpha_i \le C, \quad \sum_{i=1}^{n} \alpha_i y_i = 0$$

(Bishop, Eqs. 7.29–7.34). For the hard margin the upper bound $C$ disappears. The soft-margin primal is convex with affine constraints and always feasible, which is all that the refined Slater condition asks of such a problem (Boyd and Vandenberghe, 2004, §5.2.3), so strong duality holds: the primal and dual optimal values are equal, and the KKT conditions, summarized in the optimization article, characterize the solution. Complementary slackness sorts the training examples into three groups (Bishop, §7.1.1; Platt, 1998, Eq. 12):

• $\alpha_i = 0$: $y_i f(\mathbf{x}_i) \ge 1$, on or outside the margin; the example plays no part in $f$.
• $0 < \alpha_i < C$: $y_i f(\mathbf{x}_i) = 1$, exactly on a margin plane (a free support vector).
• $\alpha_i = C$: $y_i f(\mathbf{x}_i) \le 1$, on or inside the margin or misclassified (a bounded support vector).

The bias follows from the free support vectors, for which $y_i f(\mathbf{x}_i) = 1$; Bishop (Eq. 7.37) averages the resulting values of $b$ over all of them for numerical stability.

Kernels

In the dual the training vectors appear only through inner products $\mathbf{x}_i^\top \mathbf{x}_j$, and by the expansion of $\mathbf{w}$ so does the decision function, $f(\mathbf{x}) = \sum_i \alpha_i y_i\, \mathbf{x}_i^\top \mathbf{x} + b$. Cortes and Vapnik (1995, Section 4) take exactly this step: after a map $\phi$ to a feature space the classifier depends only on the inner products $\phi(\mathbf{x}) \cdot \phi(\mathbf{x}_i)$, which they replace by a function $K(\mathbf{u}, \mathbf{v})$, so that training is unchanged except that the dual’s matrix becomes $y_i y_j K(\mathbf{x}_i, \mathbf{x}_j)$; they credit Boser, Guyon and Vapnik (1992) with this interchange of operations. With a kernel the classifier is

$$f(\mathbf{x}) = \sum_{i \in \mathrm{SV}} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b .$$

A function is a valid kernel, an inner product in some feature space, when it satisfies Mercer’s condition. Cortes and Vapnik state it, as printed, for kernels on continuous inputs: $\iint K(\mathbf{u}, \mathbf{v})\, g(\mathbf{u})\, g(\mathbf{v})\, d\mathbf{u}\, d\mathbf{v} > 0$ for every $g$ with $\int g^2(\mathbf{u})\, d\mathbf{u} < \infty$. The finite version that Bishop (§6.2) gives as necessary and sufficient is that the Gram matrix of $K$ is symmetric positive semidefinite for every finite set of inputs, which, Bishop notes (§7.1), keeps the dual problem bounded and well defined. The kernels used in vision include:

Kernel	$K(\mathbf{x}, \mathbf{x}')$	Notes
Linear	$\mathbf{x}^\top \mathbf{x}'$	$\mathbf{w}$ can be formed explicitly; the usual choice for HOG and CNN features
Polynomial	$(\gamma\, \mathbf{x}^\top \mathbf{x}' + r)^p$	Cortes and Vapnik used $(\mathbf{u} \cdot \mathbf{v} + 1)^p$ on digit images
RBF (Gaussian)	$\exp(-\gamma \lVert \mathbf{x} - \mathbf{x}' \rVert^2)$	Feature space of infinite dimension (Bishop, §6.2); scikit-learn’s default
Histogram intersection	$\sum_k \min(x_k, x'_k)$	For histograms; positive definite (Maji et al., 2008, citing earlier work)
χ²	$\sum_k 2 x_k x'_k / (x_k + x'_k)$	For histograms; positive definite in this form (Vedaldi and Zisserman, 2012)

The polynomial and RBF forms follow the scikit-learn guide, with $p$ the degree and $r$ the coef0 parameter. Vedaldi and Zisserman (§2.1) point out that some authors define the χ² kernel as the negative χ² distance, which is only conditionally positive definite, while the form in the table is positive definite; for $\ell_1$-normalized histograms the two differ by a constant. The intersection and χ² kernels are additive, sums of one function per histogram bin, the property the fast methods described under Variants exploit. The similarity and distance measures article compares the corresponding histogram distances.

Multiclass

The SVM is a two-class method, and multiclass problems are reduced to several binary ones (Bishop, §7.1.3):

• One-vs-rest trains $K$ classifiers, class $k$ against all others, and predicts the class with the largest decision value. Bishop notes two weaknesses: the $K$ decision values come from classifiers trained on different problems and need not be on comparable scales, and each binary problem is imbalanced.
• One-vs-one trains $K(K-1)/2$ classifiers, one per pair of classes, and predicts by majority vote; it is the scheme LIBSVM implements (Chang and Lin, §7), breaking ties in favour of the class listed first.
• Crammer–Singer solves one joint problem that requires the score of the correct class to exceed every other class’s score by a margin, $\mathbf{m}_{y_i}^\top \mathbf{x}_i - \mathbf{m}_r^\top \mathbf{x}_i \ge 1 - \delta_{y_i r} - \xi_i$ for all classes $r$, with one slack per example (Crammer and Singer, 2001, Eq. 7).

Parameters

• $C$ trades margin width against training errors. Large $C$ approaches the hard margin and fits the training set more closely; small $C$ regularizes more. The scikit-learn guide calls the default $C = 1$ a reasonable choice and advises decreasing it for noisy data. Its best value depends on the scale of the features and of the kernel, so it is chosen by cross-validation, typically on a logarithmic grid together with the kernel parameters.
• Kernel and its parameters: the RBF width $\gamma$ sets how far one training example’s influence reaches, small $\gamma$ giving smooth boundaries and large $\gamma$ boundaries that wrap individual examples; polynomial kernels have a degree and an offset.
• Feature scaling and normalization. The RBF and linear kernels depend on the scale of every feature. Histogram kernels expect non-negative, usually normalized histograms.
• Class weights. Using a different $C$ for each class, $C_+$ and $C_-$, counteracts imbalance, a setting LIBSVM provides (Chang and Lin, §6).
• Solver tolerance and cache. Decomposition solvers stop when the KKT conditions hold to a tolerance and cache kernel columns; both affect run time more than accuracy.

In scikit-learn 1.7.2, as its documentation and docstrings state:

Estimator	Default settings
SVC	C=1.0, kernel='rbf', gamma='scale', degree=3, coef0=0.0, shrinking=True, probability=False, tol=1e-3, cache_size=200 (MB), max_iter=-1 (no limit), decision_function_shape='ovr', break_ties=False
LinearSVC	penalty='l2', loss='squared_hinge', dual='auto', tol=1e-4, C=1.0, multi_class='ovr', fit_intercept=True, intercept_scaling=1, max_iter=1000
SGDClassifier	loss='hinge', penalty='l2', alpha=0.0001

gamma='scale' uses $1 / (d \cdot \operatorname{Var}(X))$, where $\operatorname{Var}(X)$ is the variance of all entries of the training matrix (NumPy’s X.var(), with denominator $nd$); it replaced 'auto', $1/d$, as the default in version 0.22. SVC wraps LIBSVM and always trains one-vs-one internally; decision_function_shape='ovr' only reshapes the pairwise decision values into one score per class. LinearSVC wraps LIBLINEAR, trains one-vs-rest unless multi_class='crammer_singer', and differs from SVC(kernel='linear') in two ways: it minimizes the squared hinge by default, and LIBLINEAR appends a constant feature for the intercept and so penalizes the intercept like any other weight, an effect intercept_scaling reduces. With dual='auto' it solves the dual when there are fewer samples than features and the chosen loss and penalty support it, and the primal otherwise.

Complexity

Training a kernel SVM. The dual has one variable per training example, and its matrix has $n^2$ entries, which cannot be stored for large $n$: Platt (1998) observed that it did not fit into 128 MB beyond about 4,000 examples. Decomposition methods therefore update a few multipliers at a time and compute kernel columns on demand. For LIBSVM’s SMO-type method, one iteration costs $O(n)$ when the needed kernel columns are cached and $O(nd)$ when a column must be computed, and the number of iterations, which no theory bounds for LIBSVM, may grow faster than linearly in $n$ (Chang and Lin, §5.7). The scikit-learn guide puts the resulting fit time between $O(d\, n^2)$ and $O(d\, n^3)$, depending on how well the cache works, and the SVC docstring warns that it may be impractical beyond tens of thousands of samples.

Training a linear SVM. Solvers that work with $\mathbf{w}$ avoid the Gram matrix. LIBLINEAR trained a text classifier on more than 600,000 examples in several seconds, against several hours for a general SVM solver such as LIBSVM (Fan et al., 2008), and the scikit-learn guide describes LinearSVC as scaling almost linearly to millions of samples and features.

Prediction. A linear SVM costs one inner product, $O(d)$. A kernel SVM evaluates the kernel against every support vector, $O(m d)$ for $m$ support vectors, and must store them all. Maji, Berg and Malik (2008) routinely obtained classifiers with more than 5,000 support vectors on the Daimler–Chrysler pedestrian dataset, and note, citing earlier work, that the number of support vectors grows linearly with the training set. In sliding-window detection, where each image yields thousands of windows, this cost is, in our reading, what kept most detectors linear.

Implementation

The three examples use synthetic images with exactly known labels. The first renders $32 \times 32$ grayscale windows that contain either an upright figure (a head, a body and two legs of random size, position and contrast) or clutter made of the same parts at random positions and angles, both with Gaussian noise of standard deviation 0.3. Each window is described by a HOG-like vector: unsigned gradient orientations in 6 bins, weighted by gradient magnitude and pooled over $4 \times 4$ cells of $8 \times 8$ pixels, 96 numbers normalized to unit length. A linear SVM is trained by our own NumPy implementation of SMO on the dual problem and checked against scikit-learn’s SVC. It updates the maximally violating pair of multipliers, stopping with LIBSVM’s criterion, $\max_{i \in I_\text{up}} (-y_i \nabla_i) - \min_{j \in I_\text{low}} (-y_j \nabla_j) < 10^{-3}$ for the gradient $\nabla$ of the dual objective; LIBSVM chooses the first multiplier the same way and the second with second-order information (Chang and Lin, §4.1.2). The outputs came from NumPy 2.3.5, SciPy 1.16.3 and scikit-learn 1.7.2; the three blocks together take about 10 seconds on a laptop.

A linear SVM and the effect of C

The first block trains on 600 windows and tests on 4,000 fresh ones, for five values of $C$, repeats the sweep on five independent datasets, and then compares the SMO solution at $C = 10$ with SVC and LinearSVC.

import numpy as np
from scipy import ndimage
from sklearn.svm import SVC, LinearSVC

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

def segment(img, y0, x0, y1, x1, width, value):
    """Draw a straight bar of the given width between two points."""
    dy, dx = y1 - y0, x1 - x0
    L2 = dy * dy + dx * dx
    t = np.clip(((yy - y0) * dy + (xx - x0) * dx) / L2, 0, 1)
    d = np.hypot(yy - (y0 + t * dy), xx - (x0 + t * dx))
    img[d < width / 2] = value

def window(person, rng):
    """A 32x32 grayscale window: an upright figure (head, body, two legs) or clutter.
    Clutter is made of the same parts (bars and disks) placed at random."""
    img = np.zeros((S, S))
    v = rng.uniform(0.15, 0.8)                    # contrast against the background
    if person:
        cx, top = 16 + rng.uniform(-4, 4), 4 + rng.uniform(-2, 2)
        h = rng.uniform(22, 26)                   # figure height
        img[(yy - top - 2.5)**2 + (xx - cx)**2 < 2.8**2] = v              # head
        segment(img, top + 5, cx, top + 0.6 * h, cx, 4.0, v)              # body
        for s in (-1, 1):                                                 # legs
            segment(img, top + 0.6 * h, cx, top + h, cx + s * rng.uniform(2, 5), 2.5, v)
    else:
        for _ in range(rng.integers(2, 5)):                                # random parts
            y0, x0 = rng.uniform(3, 29, 2)
            a, L = rng.uniform(0, np.pi), rng.uniform(6, 16)
            segment(img, y0, x0, y0 + L * np.sin(a), x0 + L * np.cos(a), rng.uniform(2, 4), v)
        if rng.random() < 0.5:
            y0, x0 = rng.uniform(4, 28, 2)
            img[(yy - y0)**2 + (xx - x0)**2 < 2.8**2] = v
    return img + rng.normal(0, 0.3, (S, S))       # sensor noise

def hog_like(img, cell=8, bins=6):
    """Cell histograms of unsigned gradient orientation weighted by magnitude
    (4 x 4 cells x 6 bins = 96 numbers), L2-normalized over the window."""
    g = ndimage.gaussian_filter(img, 1.0)
    gy, gx = ndimage.sobel(g, 0), ndimage.sobel(g, 1)
    mag, ang = np.hypot(gx, gy), np.mod(np.arctan2(gy, gx), np.pi)
    b = (ang / np.pi * bins).astype(int) % bins
    n = S // cell
    H = np.zeros((n, n, bins))
    for i in range(n):
        for j in range(n):
            sl = (slice(i * cell, (i + 1) * cell), slice(j * cell, (j + 1) * cell))
            H[i, j] = np.bincount(b[sl].ravel(), weights=mag[sl].ravel(), minlength=bins)
    h = H.ravel()
    return h / np.linalg.norm(h)

def dataset(n, rng):
    """n windows, half figures (+1) and half clutter (-1), as rows of a feature matrix."""
    y = np.where(np.arange(n) % 2 == 0, 1, -1)
    X = np.stack([hog_like(window(t == 1, rng)) for t in y])
    return X, y

def smo(K, y, C, tol=1e-3, max_iter=200000):
    """Solve the SVM dual  min 1/2 a^T Q a - sum(a),  Q_ij = y_i y_j K_ij,
    subject to sum(a_i y_i) = 0 and 0 <= a_i <= C, two multipliers at a time.
    The pair is the maximal violating pair; LIBSVM chooses the same i but picks j
    with second-order information. The stopping test is LIBSVM's."""
    n = len(y)
    a, G = np.zeros(n), -np.ones(n)               # multipliers and gradient Q a - 1
    for it in range(max_iter):
        up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0))     # may move "up"
        low = ((y < 0) & (a < C)) | ((y > 0) & (a > 0))    # may move "down"
        v = -y * G
        i = np.flatnonzero(up)[np.argmax(v[up])]
        j = np.flatnonzero(low)[np.argmin(v[low])]
        gap = v[i] - v[j]
        if gap < tol:                             # KKT conditions hold to tol
            break
        curv = max(K[i, i] + K[j, j] - 2 * K[i, j], 1e-12)
        t = gap / curv                            # unconstrained step along the pair
        t = min(t, C - a[i] if y[i] > 0 else a[i], a[j] if y[j] > 0 else C - a[j])
        a[i] += y[i] * t
        a[j] -= y[j] * t                          # keeps sum(a_i y_i) = 0
        G += t * y * (K[:, i] - K[:, j])
    free = (a > 1e-8) & (a < C - 1e-8)
    b = np.mean(-y[free] * G[free]) if free.any() else (v[i] + v[j]) / 2
    return a, b, it

Cs = [0.1, 1, 10, 100, 1000]
test_err = np.zeros((5, len(Cs)))
for seed in range(5):                         # five independent data sets
    rng = np.random.default_rng(seed)
    X, y = dataset(600, rng)                  # training windows
    Xt, yt = dataset(4000, rng)               # test windows
    K = X @ X.T                               # linear kernel: Gram matrix of inner products
    if seed == 0:
        print("    C   train err  test err  support vectors  (at bound C)  margin 2/||w||")
    for k, C in enumerate(Cs):
        a, b, it = smo(K, y, C)
        w = (a * y) @ X                       # w = sum_i a_i y_i x_i
        test_err[seed, k] = np.mean(np.sign(Xt @ w + b) != yt)
        if seed == 0:
            sv, bound = np.sum(a > 1e-8), np.sum(a > C - 1e-8)
            print(f"{C:6g}   {np.mean(np.sign(X @ w + b) != y):8.3f}  {test_err[0, k]:8.3f}"
                  f"  {sv:15d}  {bound:12d}  {2 / np.linalg.norm(w):14.3f}")
print("test error over 5 data sets:", "  ".join(
    f"C={C:g}: {lo:.3f}-{hi:.3f}" for C, lo, hi in zip(Cs, test_err.min(0), test_err.max(0))))
print("best C per data set:", [Cs[k] for k in test_err.argmin(1)])

rng = np.random.default_rng(0)                # back to data set 0
X, y = dataset(600, rng)
Xt, yt = dataset(4000, rng)
K = X @ X.T
# Cross-check at C = 10 against scikit-learn's libsvm-based SVC with a linear kernel.
C = 10
a, b, it = smo(K, y, C)
w = (a * y) @ X
ref = SVC(kernel="linear", C=C).fit(X, y)
f, f_ref = Xt @ w + b, ref.decision_function(Xt)
print(f"\nSMO iterations: {it}; support vectors: ours {np.sum(a > 1e-8)}, SVC {ref.n_support_.sum()}")
print(f"max |w - w_SVC| = {np.abs(w - ref.coef_[0]).max():.4f} (max |w| = {np.abs(w).max():.2f}),"
      f" b = {b:.4f} vs {ref.intercept_[0]:.4f}")
print(f"test windows labelled differently: {np.sum(np.sign(f) != np.sign(f_ref))} of {len(yt)}")
# Strong duality: primal objective (hinge-loss form) equals the dual objective at the optimum.
primal = 0.5 * w @ w + C * np.maximum(0, 1 - y * (X @ w + b)).sum()
dual = a.sum() - 0.5 * (a * y) @ K @ (a * y)
print(f"primal {primal:.4f}  dual {dual:.4f}  relative gap {(primal - dual) / primal:.1e}")
# LinearSVC's defaults (squared hinge, penalized intercept) solve a different problem.
lin = LinearSVC(C=C).fit(X, y)
print(f"LinearSVC defaults: test err {np.mean(lin.predict(Xt) != yt):.3f};"
      f" labels differing from SVC: {np.sum(lin.predict(Xt) != ref.predict(Xt))}")

Output:

    C   train err  test err  support vectors  (at bound C)  margin 2/||w||
   0.1      0.123     0.110              414           400           0.463
     1      0.077     0.076              236           201           0.214
    10      0.037     0.066              149            87           0.087
   100      0.017     0.075              107            25           0.035
  1000      0.000     0.095               91             0           0.016
test error over 5 data sets: C=0.1: 0.110-0.120  C=1: 0.076-0.084  C=10: 0.066-0.090  C=100: 0.075-0.105  C=1000: 0.095-0.120
best C per data set: [10, 10, 10, 1, 10]

SMO iterations: 1196; support vectors: ours 149, SVC 149
max |w - w_SVC| = 0.0038 (max |w| = 5.92), b = -12.3897 vs -12.3915
test windows labelled differently: 0 of 4000
primal 897.6888  dual 897.6252  relative gap 7.1e-05
LinearSVC defaults: test err 0.071; labels differing from SVC: 96

The sweep shows the trade-off that $C$ controls. At $C = 0.1$ the margin is wide and two thirds of the training windows are support vectors, almost all of them at the bound $C$, inside the margin; the classifier underfits, with training and test errors both above 0.1. As $C$ grows the margin narrows, fewer windows touch it, and the training error falls. At $C = 1000$ the training error is zero and no multiplier is at its bound, so the training set is linearly separable in the 96 features and the solution is the hard-margin SVM; its test error is higher than at $C = 10$, the overfitting end of the curve. On four of the five datasets the lowest test error came at $C = 10$, and the errors at each $C$ vary between datasets by up to 0.03, so a difference between neighbouring values of $C$ on one dataset is weak evidence; cross-validation chooses $C$ for the data at hand.

The cross-check shows that the short SMO solves the same problem as LIBSVM: the same 149 support vectors, weights that agree to within 0.004 and identical labels on all 4,000 test windows. Both solvers stop at the same tolerance, 0.001, after different sequences of steps, so they agree only to about that accuracy, and the primal hinge-loss objective is still slightly above the dual objective, as weak duality requires of any point short of the optimum. LinearSVC with its defaults reaches a similar test error but disagrees with SVC on 96 windows, because it minimizes the squared hinge with a penalized intercept, a different problem with a different solution.

Kernels: a disk of colours in a ring

The second block, which continues from the first, classifies pixels by colour. An object’s pixels have chromaticities $(r, g) = (R, G)/(R + G + B)$ within 0.04 of one colour, and the background’s pixels have chromaticities 0.07 to 0.14 away from it in every direction, so in the two chromaticity features the object is a disk surrounded by a ring of background, a set no straight line separates. Brightness varies freely and is divided out. The classifiers train on 1,000 labelled pixels of one image and are tested on every pixel of a second. The block then solves the RBF problem with the SMO of the first block on a precomputed Gram matrix, and finally returns to the windows of the first block to compare kernels for histograms.

# --- Example 2: kernels. Pixels of an object whose colours lie in a disk of
# chromaticity, on a background whose colours surround it in a ring.
def colour_image(rng, n=96):
    """RGB image in [0,1]: an elliptical object with chromaticities (r, g) = (R, G)/(R+G+B)
    within 0.04 of (0.45, 0.32), on a background whose chromaticities lie 0.07-0.14 away
    from it in every direction. Returns the image and the object mask."""
    v, u = np.mgrid[0:n, 0:n] + 0.5
    mask = ((u - 50) / 30)**2 + ((v - 45) / 22)**2 < 1
    rad = np.where(mask, 0.04 * np.sqrt(rng.random((n, n))), rng.uniform(0.07, 0.14, (n, n)))
    ang = rng.uniform(0, 2 * np.pi, (n, n))
    r, g = 0.45 + rad * np.cos(ang), 0.32 + rad * np.sin(ang)
    lum = rng.uniform(0.3, 0.9, (n, n))           # R + G + B, varies freely
    rgb = np.stack([r, g, 1 - r - g], -1) * lum[..., None]
    return np.clip(rgb + rng.normal(0, 0.005, rgb.shape), 1e-3, 1), mask

def chroma(rgb):
    s = rgb.sum(-1, keepdims=True)
    return (rgb / s)[..., :2].reshape(-1, 2)      # one pixel per row: (r, g)

rng = np.random.default_rng(1)
img, mask = colour_image(rng)
Z, t = chroma(img), np.where(mask.ravel(), 1, -1)
idx = rng.choice(len(t), 1000, replace=False)     # 1,000 labelled training pixels
Z_tr, t_tr = Z[idx], t[idx]
img2, mask2 = colour_image(rng)                   # a second image for testing
Z_te, t_te = chroma(img2), np.where(mask2.ravel(), 1, -1)

scale = 1 / (Z_tr.shape[1] * Z_tr.var())          # what gamma='scale' computes
print(f"gamma='scale' = {scale:.0f};  gamma='auto' = {1 / Z_tr.shape[1]:.1f}")
print("kernel      gamma   pixel error (test image)  support vectors")
for gamma in [None, 0.5, scale / 10, scale, scale * 10, scale * 1000]:   # 0.5 is 'auto'
    m = SVC(kernel="linear") if gamma is None else SVC(kernel="rbf", gamma=gamma)
    m.fit(Z_tr, t_tr)                             # C = 1.0, the default
    name = "linear" if gamma is None else "RBF"
    print(f"{name:<8} {'-' if gamma is None else f'{gamma:.3g}':>8}"
          f"   {np.mean(m.predict(Z_te) != t_te):23.3f}  {m.n_support_.sum():15d}")
print(f"fraction of object pixels in the test image: {np.mean(t_te > 0):.3f}")

# The same RBF problem solved by our SMO on the Gram matrix: identical decisions.
def rbf(A, B, gamma):
    d2 = (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T
    return np.exp(-gamma * np.maximum(d2, 0))
a, b, _ = smo(rbf(Z_tr, Z_tr, scale), t_tr, C=1.0)
f = rbf(Z_te, Z_tr, scale) @ (a * t_tr) + b      # f(x) = sum_i a_i y_i K(x, x_i) + b
f_ref = SVC(C=1.0).fit(Z_tr, t_tr).decision_function(Z_te)
print(f"our SMO vs SVC: max |f - f_SVC| = {np.abs(f - f_ref).max():.4f},"
      f" pixels labelled differently: {np.sum(np.sign(f) != np.sign(f_ref))} of {len(t_te)}")

# Kernels for histograms, on the windows of the first example (features >= 0).
def intersection(A, B):                           # sum_k min(a_k, b_k)
    return sum(np.minimum.outer(A[:, k], B[:, k]) for k in range(A.shape[1]))
def chi2(A, B):                                   # sum_k 2 a_k b_k / (a_k + b_k)
    return sum(2 * np.multiply.outer(A[:, k], B[:, k])
               / np.maximum(np.add.outer(A[:, k], B[:, k]), 1e-12) for k in range(A.shape[1]))
kernels = {"linear": lambda A, B: A @ B.T,
           "RBF": lambda A, B: rbf(A, B, 1 / (A.shape[1] * X.var())),
           "intersection": intersection, "chi-squared": chi2,
           "sigmoid": lambda A, B: np.tanh(2 * A @ B.T - 1)}
print("\nkernel        min/max eigenvalue of Gram matrix   test error (C=1)  (C=10)")
for name, k in kernels.items():
    Kxx = k(X, X)
    ev = np.linalg.eigvalsh(Kxx)
    errs = [np.mean(SVC(kernel="precomputed", C=C).fit(Kxx, y).predict(k(Xt, X)) != yt)
            for C in (1, 10)]
    print(f"{name:<13} {ev[0] / ev[-1]:30.1e}   {errs[0]:16.3f}  {errs[1]:6.3f}")

Output:

gamma='scale' = 55;  gamma='auto' = 0.5
kernel      gamma   pixel error (test image)  support vectors
linear          -                     0.226              461
RBF           0.5                     0.226              464
RBF          5.54                     0.226              462
RBF          55.4                     0.003              116
RBF           554                     0.004               71
RBF      5.54e+04                     0.042              931
fraction of object pixels in the test image: 0.226
our SMO vs SVC: max |f - f_SVC| = 0.0057, pixels labelled differently: 0 of 9216

kernel        min/max eigenvalue of Gram matrix   test error (C=1)  (C=10)
linear                              -1.3e-16              0.076   0.066
RBF                                  9.1e-04              0.057   0.061
intersection                         6.4e-05              0.067   0.069
chi-squared                          2.5e-09              0.064   0.079
sigmoid                             -4.4e-02              0.103   0.145

The linear SVM labels every pixel as background, so its error equals the fraction of object pixels: no line puts the disk on one side and the ring on the other, and the best a line can do here is give up on the minority class. An RBF kernel with $\gamma$ near the 'scale' value separates disk and ring almost perfectly, with 116 support vectors. The value of $\gamma$ matters as much as the kernel does. The chromaticities vary by only about 0.1, so $\gamma = 0.5$, the old 'auto' default, makes the kernel almost constant over the data and the classifier behaves like the linear one; 'scale' adapts $\gamma$ to the spread of the features, which in our reading is what makes it a safer default. At a thousand times the 'scale' value each training pixel influences only its immediate neighbourhood, almost every training pixel becomes a support vector and the test error rises again. Our SMO on the RBF Gram matrix reproduces SVC’s decisions on all 9,216 test pixels.

On the windows of the first block, the RBF, intersection and χ² kernels reach test errors within about 0.02 of the linear one, the RBF kernel lowest at 0.057, so for this HOG-like descriptor the linear SVM loses little, much as Dalal and Triggs found with real HOG features (below). The eigenvalue column checks Mercer’s condition on the 600 training windows. The linear Gram matrix has rank at most 96, so its smallest eigenvalue is zero up to rounding (the printed value changes with the BLAS build and thread count); the RBF, intersection and χ² matrices are positive semidefinite, as theory says; the sigmoid “kernel” $\tanh(2\, \mathbf{x}^\top \mathbf{x}' - 1)$, which scikit-learn offers, has a clearly negative eigenvalue, so it is not an inner product in any feature space and the dual is no longer convex. LIBSVM accepts it anyway, since its solver does not assume a positive semidefinite matrix (Chang and Lin, §4.1), but in this case it gives the worst classifier.

Hinge loss versus logistic loss, and scores versus probabilities

The third block, which continues from the second, compares the SVM with L2-regularized logistic regression at the same $C$ on the windows of the first block. It refits both on the support vectors alone, then turns the SVM’s scores into probabilities with Platt scaling.

# --- Example 3: hinge loss versus logistic loss on the windows of the first example.
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import log_loss
C = 10
svm = SVC(kernel="linear", C=C).fit(X, y)
logr = LogisticRegression(C=C, max_iter=10000).fit(X, y)   # 1/2||w||^2 + C * sum of log losses
sv = svm.support_                                          # indices of the support vectors
svm_sv = SVC(kernel="linear", C=C).fit(X[sv], y[sv])       # refit on the support vectors only
logr_sv = LogisticRegression(C=C, max_iter=10000).fit(X[sv], y[sv])
rel = lambda u, v: np.linalg.norm(u - v) / np.linalg.norm(v)
print(f"training windows: {len(y)}, support vectors: {len(sv)}")
print(f"hinge (SVM):  test err {np.mean(svm.predict(Xt) != yt):.3f};"
      f" refit on support vectors only: relative change in w {rel(svm_sv.coef_, svm.coef_):.1e},"
      f" test err {np.mean(svm_sv.predict(Xt) != yt):.3f}")
print(f"logistic:     test err {np.mean(logr.predict(Xt) != yt):.3f};"
      f" refit on the same windows:     relative change in w {rel(logr_sv.coef_, logr.coef_):.1e},"
      f" test err {np.mean(logr_sv.predict(Xt) != yt):.3f}")

# SVM scores are not probabilities. Platt scaling (probability=True) fits a sigmoid
# 1 / (1 + exp(A d + B)) to LIBSVM's decision values d from internal 5-fold cross-validation.
# For two classes scikit-learn's decision_function is f = -d, so P(y=+1 | f) = 1 / (1 + exp(A f - B)).
platt = SVC(kernel="linear", C=C, probability=True, random_state=0).fit(X, y)
f = platt.decision_function(Xt)
p = platt.predict_proba(Xt)[:, 1]
pos = (yt > 0).astype(int)
print(f"\nPlatt parameters A = {platt.probA_[0]:.2f}, B = {platt.probB_[0]:.2f};"
      f" P(figure) at f = -1, 0, +1: " + ", ".join(
          f"{1 / (1 + np.exp(platt.probA_[0] * s - platt.probB_[0])):.2f}" for s in (-1, 0, 1)))
print(f"test log loss: sigmoid of raw SVM score {log_loss(pos, 1 / (1 + np.exp(-f))):.3f},"
      f" Platt-scaled {log_loss(pos, p):.3f}, logistic regression {log_loss(pos, logr.predict_proba(Xt)[:, 1]):.3f}")
print(f"test windows where predict() and predict_proba() > 0.5 disagree: "
      f"{np.sum((platt.predict(Xt) > 0) != (p > 0.5))} of {len(yt)}")

Output:

training windows: 600, support vectors: 149
hinge (SVM):  test err 0.066; refit on support vectors only: relative change in w 7.0e-04, test err 0.066
logistic:     test err 0.066; refit on the same windows:     relative change in w 5.4e-01, test err 0.071

Platt parameters A = -1.83, B = 0.04; P(figure) at f = -1, 0, +1: 0.14, 0.51, 0.87
test log loss: sigmoid of raw SVM score 0.214, Platt-scaled 0.164, logistic regression 0.177
test windows where predict() and predict_proba() > 0.5 disagree: 1 of 4000

The two losses give the same test error, but they use the data differently. Refitting the SVM on its 149 support vectors returns the same weights to within the solver tolerance: the other 451 windows have zero hinge loss and zero multipliers, so they never affected the solution. Refitting logistic regression on the same 149 windows changes its weights by 54%, because the logistic loss is never exactly zero and every window, however well classified, pulls on the boundary. The SVM’s sparsity is what makes hard-negative mining exact, as described below.

The raw decision value is not a probability. Read as a log-odds, $P = 1/(1 + e^{-f})$, it gives a worse test log loss than either Platt scaling or logistic regression; Platt’s sigmoid stretches it (here $A \approx -1.8$), so that a window on the positive margin plane, $f = 1$, has a probability of about 0.87 of being a figure rather than 0.73. As scikit-learn documents, probability=True fits the sigmoid to decision values obtained by internal 5-fold cross-validation, which makes training slower and can make predict_proba disagree with predict, as it does here on one test window.

Properties and Behavior

• Convex training. The primal and the dual are convex quadratic programs, so every local optimum is global and the solution does not depend on initialization (Bishop, Chapter 7 introduction and §7.1.1). The decision function is unique; its expansion over support vectors need not be (Cortes and Vapnik, note 6).
• Sparsity. Only the support vectors enter the classifier, and examples beyond the margin can be removed or moved, as long as they stay outside it, without changing the solution (Bishop, §7.1). The third example shows this directly.
• Capacity control by the margin. Cortes and Vapnik motivate the margin by bounds from statistical learning theory: for separable data, the expected test error is at most the expected number of support vectors divided by the number of training examples (their Eq. 5), a bound with no explicit dependence on the dimension of the feature space.
• Kernels do not escape dimensionality. Bishop (§7.1.1) warns against reading the high-dimensional feature space as a way around the curse of dimensionality: the mapped features are constrained among themselves, so that for a quadratic kernel on two inputs the six-dimensional feature vectors lie on a two-dimensional surface.
• No probabilities. The SVM is a decision machine (Bishop, Chapter 7 introduction). Its decision values rank examples, which is all that ROC curves and precision–recall curves need; probabilities need a separate calibration fitted on data not used to train the SVM, as in the third example. For more than two classes LIBSVM combines the pairwise Platt probabilities by solving a small optimization problem (Chang and Lin, §8). The logistic regression article describes Platt scaling, and expected calibration error how calibration is measured.
• Sensitivity to outliers. The hinge penalty grows linearly with the distance of a misclassified example from the margin, so mislabelled examples far on the wrong side still pull on the boundary (Bishop, §7.1.1).

Limitations

• Cost of kernel SVMs. Training grows at least quadratically with the number of examples and prediction with the number of support vectors, as described under Complexity.
• Kernel and parameter choice. Results depend strongly on $C$, the kernel and its parameters, which have to be searched by cross-validation; in the second example a factor of 10 in $\gamma$ separates a useless classifier from a near-perfect one.
• Fixed features. The SVM learns a classifier on given features. It does not learn the features, which is the difference between the pipelines of the 2000s and convolutional networks trained end to end; even in R-CNN the SVMs only replaced the network’s last layer.
• Binary by construction. Multiclass schemes are combinations of binary problems with the scale and imbalance issues listed above, or larger joint problems.

Variants

• Squared-hinge (L2-loss) SVM. The differentiable variant that LIBLINEAR and scikit-learn’s LinearSVC use by default.
• ν-SVM. Replaces $C$ by $\nu \in (0, 1]$, an upper bound on the fraction of margin errors and a lower bound on the fraction of support vectors (Bishop, §7.1.1; Chang and Lin, §2.2).
• Error-correcting output codes, a multiclass scheme that generalizes the one-vs-one vote to other partitions of the classes (Bishop, §7.1.3).
• One-class SVM and support vector regression. The same machinery applied to estimating the support of a distribution, for novelty detection, and to regression with an $\epsilon$-insensitive loss (Bishop, §7.1.3–§7.1.4).
• Latent SVM. Felzenszwalb and colleagues score an example by the maximum of a linear function over hidden variables, such as the placement of object parts, train with the hinge loss, and alternate between fixing the positives’ latent values, which makes the objective convex, and solving the resulting SVM problem. The deformable part models and DPM paper articles describe it, together with the weak-label structural SVM of the later grammar models.
• Fast evaluation of additive kernels. Maji, Berg and Malik (2008) observed that an intersection-kernel classifier is a sum of one piecewise-linear function per histogram bin, which can be evaluated exactly in $O(d \log m)$ time with sorted support-vector values and binary search, or approximately in $O(d)$ with a lookup table; 30–50 linear segments per bin lost no accuracy in their experiments. Vedaldi and Zisserman (2012) went further and gave explicit, low-dimensional feature maps for the intersection, χ², Hellinger and Jensen–Shannon kernels, so that a linear solver trained on the mapped features approximates the kernel SVM.
• Solvers. Sequential minimal optimization (Platt, 1998) solves the dual two multipliers at a time, the smallest subproblem the equality constraint $\sum_i \alpha_i y_i = 0$ allows, analytically and with memory linear in $n$; LIBSVM uses an SMO-type method whose working-set selection, from Fan, Chen and Lin (2005), picks the second multiplier using second-order information, plus shrinking of bounded variables and a kernel cache (Chang and Lin, §4–§5). For linear SVMs LIBLINEAR uses a coordinate descent method and, for the squared hinge, also a trust-region Newton method (Fan et al., 2008); stochastic gradient methods, which Vedaldi and Zisserman list among large-scale SVM solvers, minimize the hinge objective directly, and the journal version of the DPM trained its latent SVM by stochastic subgradient descent.

Uses in Computer Vision

• Pedestrian detection with HOG. Dalal and Triggs (CVPR 2005) scored $64 \times 128$ HOG windows with a linear soft-margin SVM (SVMLight, $C = 0.01$), retrained once with the false positives found by scanning person-free training images, which improved their default detector by 5% at $10^{-4}$ false positives per window, and found a Gaussian-kernel SVM about 3% better at much higher run time. The HOG paper article reports the study, and sliding window detection the scanning and mining. Maji, Berg and Malik (2008) later trained intersection-kernel SVMs on a multi-level histogram of oriented edge energy and reported, on the INRIA person dataset, a miss rate of 0.167 at $10^{-6}$ false positives per window, which they describe as an improvement of about 13% over Dalal and Triggs’s linear detector; across their experiments, the approximate classifier was up to 2,000 times faster than a standard kernel implementation.
• Hard-negative mining. A detector sees few positive windows and millions of negative ones, almost all of them easy. Because examples beyond the margin do not affect an SVM, training on the positives plus the negatives that violate the margin gives the same solution as training on all of them. The DPM papers turned this into a caching loop that adds margin violators and drops easy examples, and the journal version proves that it ends at the solution for the full training set, as the deformable part models article describes.
• Deformable part models. The latent SVM above trained the root and part filters of the DPM, the reference method of the PASCAL VOC detection challenges from 2008 to 2012, from bounding boxes alone; a class-specific SVM with a quadratic kernel also rescored detections using the scores of other classes’ detectors.
• Bag of visual words and histogram kernels. Csurka and colleagues classified bag-of-visual-words histograms with a linear SVM, lowering the error on their seven-class dataset from 28% for naive Bayes to 15%, and later systems used intersection and χ² kernels on word histograms and spatial pyramids, as summarized in image classification. Vedaldi and Zisserman (Table 1 of the authors’ copy) report, on Caltech-101 with 15 training images per class and 4,200-dimensional spatial-pyramid histograms of dense SIFT words, a mean per-class accuracy over three runs of 64.1% for the exact χ² kernel with LIBSVM in 1,769 s of training, 64.4% for their approximate feature map with three numbers per bin and LIBLINEAR in 312 s, and 41.6% for the linear kernel.
• SVMs on CNN features. R-CNN scored the 4,096-dimensional features of each region proposal with one linear SVM per class, trained with hard-negative mining on proposals overlapping the ground truth by less than 0.3 IoU; its tech report found that using the fine-tuned network’s softmax instead lowered VOC 2007 mAP from 54.2% to 50.9%. Fast R-CNN then trained the classifier inside the network, and its successors did without post-hoc SVMs, as the two-stage object detectors article traces. Linear classifiers on frozen network features are still used to evaluate learned representations, usually as logistic regression, as the logistic regression article describes.

History

Cortes and Vapnik (1995) trace the method to the optimal hyperplane for separable classes, which they date to 1965 (citing Vapnik, 1982). After the kernel step of Boser, Guyon and Vapnik (1992), described above, their own paper added the soft margin for non-separable data and named the result the support-vector network. Platt’s SMO (1998), LIBSVM (developed since 2000, according to Chang and Lin) and LIBLINEAR (2008) made SVMs practical on larger datasets. In vision, the SVM was the usual last stage of the classification pipeline of the 2000s that image classification describes, and of window-based detectors from the HOG detector of 2005 to R-CNN in 2014.