Eight points lie in the plane. Four belong to class $+1$: $(3, 2)$, $(2, 3)$, $(4, 4)$ and $(5, 3)$. Four belong to class $-1$: $(1, 1)$, $(0, 1)$, $(1, 0)$ and $(0, 0)$. Infinitely many straight lines separate the two groups, since any line that passes between them, at any slight tilt, classifies all eight points correctly. They are not equally good. A line that grazes $(1, 1)$ leaves no room for error: a new class $-1$ point slightly to the upper right of $(1, 1)$ would land on the wrong side. The line that seems most trustworthy is the one that stays as far as possible from both groups, $x_1 + x_2 = 3.5$, which keeps a distance of $1.5/\sqrt{2} = 1.061$ from the nearest point of each class.
A support vector machine (SVM) is built on that idea. It chooses the separating boundary with the widest margin, the empty band between the classes, and it extends the idea in two directions: to classes that overlap, by allowing some points inside the band at a price, and to curved boundaries, by drawing the band in a transformed space through a device called a kernel. This article derives the method in that order, following Hastie, Tibshirani and Friedman (2009, §§4.5.2, 12.2 and 12.3), James, Witten, Hastie and Tibshirani (2021, ch. 9) and the paper that gave the method its modern form, Cortes and Vapnik (1995).
A short history
The pieces arrived over three decades. Cortes and Vapnik (1995, §1) date the optimal hyperplane, the separating hyperplane with the largest margin, to Vapnik's work of 1965, and note the result that made it attractive: for separable data, the expected error rate on new cases is bounded by the expected number of support vectors, the training points that fix the boundary, divided by the number of training points. Their eq. 5 has no term for the number of dimensions, which suggested that a margin classifier could work in a very high-dimensional space. Constructing nonlinear boundaries through kernels is credited by Cortes and Vapnik to Boser, Guyon and Vapnik (1992). Cortes and Vapnik's own contribution was the soft margin, which handles data that no hyperplane separates without error. The resulting "support-vector network" was tested on handwritten digits, where it matched the best methods of the time.
Hyperplanes
In $p$ dimensions a hyperplane is the set of points satisfying one linear equation,
$$\{x : w \cdot x + b = 0\},$$
where $w = (w_1, \dots, w_p)$ is a vector of weights, $w \cdot x = w_1 x_1 + \dots + w_p x_p$ is the dot product, and $b$ is a number called the bias or intercept. In two dimensions it is a line, in three a plane, and in general a flat surface of dimension $p - 1$. A curved surface is not a hyperplane, and neither is a line in three dimensions, which takes two equations to describe. A hyperplane divides the space in two: points with $w \cdot x + b > 0$ lie on one side and points with $w \cdot x + b < 0$ on the other. A linear classifier predicts the class by that sign:
$$\hat{y} = \operatorname{sign}\bigl(f(x)\bigr), \qquad f(x) = w \cdot x + b,$$
with the classes coded $+1$ and $-1$.
The value of $f$ also measures distance. The vector $w$ is perpendicular to the hyperplane: for two points $x$ and $x'$ on it, $w \cdot x + b = w \cdot x' + b = 0$, so $w \cdot (x - x') = 0$ for every direction $x - x'$ lying within the hyperplane. To find the distance from a point $x$ to the hyperplane, drop a perpendicular to its foot $x_0$, so that $x = x_0 + t\, w/\|w\|$, where $\|w\| = \sqrt{w \cdot w}$ is the length of $w$ and $t$ is the signed distance. Then $f(x) = w \cdot x_0 + b + t\, w \cdot w / \|w\| = 0 + t \|w\|$, so
$$t = \frac{w \cdot x + b}{\|w\|}.$$
For a correctly classified point with label $y_i \in \{+1, -1\}$, the product $y_i f(x_i)$ is positive, and $y_i f(x_i)/\|w\|$ is its distance from the boundary (Hastie et al., 2009, §4.5).
The maximal margin classifier
Suppose the two classes can be separated by a hyperplane. The margin of a separating hyperplane is the distance from it to the nearest training point, and the maximal margin classifier is the separating hyperplane that makes this as large as possible. Written as an optimization problem, the task is to choose $w$ and $b$ to maximize $M$ subject to every training point lying at least $M$ from the hyperplane on its own side:
$$\max_{w,\,b} M \quad \text{subject to} \quad \frac{y_i (w \cdot x_i + b)}{\|w\|} \ge M, \quad i = 1, \dots, n.$$
The pair $(w, b)$ is not unique: multiplying both by any positive number describes the same hyperplane. That freedom can be used to fix the scale so that the nearest points have $y_i(w \cdot x_i + b) = 1$ exactly. Then $M = 1/\|w\|$, and maximizing $M$ is the same as minimizing $\|w\|$, or, more conveniently, $\frac{1}{2}\|w\|^2$:
$$\min_{w,\,b}\ \tfrac{1}{2}\|w\|^2 \quad \text{subject to} \quad y_i (w \cdot x_i + b) \ge 1, \quad i = 1, \dots, n.$$
This is the standard form (Hastie et al., 2009, eq. 12.4; Cortes and Vapnik, 1995, eqs. 10 to 13). The two hyperplanes $w \cdot x + b = +1$ and $w \cdot x + b = -1$ bound the margin. By the distance formula, their points lie at signed distances $+1/\|w\|$ and $-1/\|w\|$ from the boundary, so the distance between them, the full width of the empty band, is
$$\frac{2}{\|w\|}.$$
The problem has a quadratic objective and linear constraints, so it is a convex quadratic program: it has a single minimum, and standard algorithms find it.
Solved on eight points
For the eight points of the opening, the solution is $w = (2/3, 2/3)$ and $b = -7/3$, so the boundary is $\frac{2}{3}x_1 + \frac{2}{3}x_2 - \frac{7}{3} = 0$, the line $x_1 + x_2 = 3.5$. Then $\|w\| = \frac{2}{3}\sqrt{2} = 0.9428$, and the full width of the margin is $2/\|w\| = 3/\sqrt{2} = 2.121$, twice the distance 1.061 of the opening. scikit-learn's solver, run with a very large cost so that no violations are allowed, returns these values to six decimals.
| Point | Class | $y_i f(x_i)$ |
|---|---|---|
| (3, 2) | +1 | 1 |
| (2, 3) | +1 | 1 |
| (4, 4) | +1 | 3 |
| (5, 3) | +1 | 3 |
| (1, 1) | −1 | 1 |
| (0, 1) | −1 | 5/3 |
| (1, 0) | −1 | 5/3 |
| (0, 0) | −1 | 7/3 |
Every constraint holds, and three hold with equality: $(3, 2)$ and $(2, 3)$ lie on the line $f = +1$, and $(1, 1)$ on the line $f = -1$. These three are the support vectors. The width 2.121 is also the distance from $(1, 1)$ to the nearest point of the segment joining $(3, 2)$ and $(2, 3)$, which is $(2.5, 2.5)$: $\sqrt{1.5^2 + 1.5^2} = 2.121$. The maximal margin is the gap between the two classes at their narrowest.
The other five points play no part. Delete them, or move them anywhere on their own side of the margin, and the solution is the same. This is what makes the classifier sensitive only to the cases near the boundary, in contrast with methods such as linear discriminant analysis, whose boundary depends on the class means and covariances computed from every point (Hastie et al., 2009, §12.2).
The dual problem
The constraints can be folded into the objective with Lagrange multipliers, one number $\alpha_i \ge 0$ for each training point. The Lagrangian is
$$L(w, b, \alpha) = \tfrac{1}{2}\|w\|^2 - \sum_{i=1}^{n} \alpha_i \bigl[y_i (w \cdot x_i + b) - 1\bigr].$$
Each bracket is nonnegative for a feasible $(w, b)$, so subtracting it can only lower $L$; at the solution the multipliers balance the pull of the objective against the constraints that bind. Setting the derivatives with respect to $w$ and $b$ to zero gives
$$w = \sum_{i=1}^{n} \alpha_i y_i x_i, \qquad \sum_{i=1}^{n} \alpha_i y_i = 0.$$
Substituting these back eliminates $w$ and $b$ and leaves the dual problem, a quadratic program in the multipliers alone:
$$\max_{\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\, (x_i \cdot x_j) \quad \text{subject to} \quad \alpha_i \ge 0,\ \ \sum_{i} \alpha_i y_i = 0$$
(Hastie et al., 2009, eqs. 12.9 to 12.13, with the cost $C$ set to infinity; Cortes and Vapnik, 1995, Appendix A.1). At the solution the Karush-Kuhn-Tucker conditions include complementary slackness: $\alpha_i [y_i (w \cdot x_i + b) - 1] = 0$ for every $i$. Either a point lies exactly on the margin, or its multiplier is zero. So $w$ is a weighted sum of the support vectors only, which is where they get their name: they are the vectors that support, or determine, the solution.
For the eight points, solving the dual numerically, independently of scikit-learn, gives $\alpha = 2/9$ for $(3, 2)$ and for $(2, 3)$, $\alpha = 4/9$ for $(1, 1)$, and zero for the other five. The two conditions check by hand:
$$w = \tfrac{2}{9}(3, 2) + \tfrac{2}{9}(2, 3) - \tfrac{4}{9}(1, 1) = \bigl(\tfrac{6}{9}, \tfrac{6}{9}\bigr) = \bigl(\tfrac{2}{3}, \tfrac{2}{3}\bigr), \qquad \tfrac{2}{9} + \tfrac{2}{9} - \tfrac{4}{9} = 0.$$
The intercept follows from any support vector: $(1, 1)$ needs $\frac{4}{3} + b = -1$, so $b = -\frac{7}{3}$. The dual objective is $\sum \alpha_i - \frac{1}{2}\|w\|^2 = \frac{8}{9} - \frac{4}{9} = \frac{4}{9}$, equal to the primal objective $\frac{1}{2}\|w\|^2 = \frac{4}{9}$, as it must be at the optimum of a convex problem like this one.
The dual matters for a reason beyond computation. The training points enter it only through the dot products $x_i \cdot x_j$, and the classifier can be written the same way:
$$f(x) = w \cdot x + b = \sum_{i=1}^{n} \alpha_i y_i\, (x_i \cdot x) + b.$$
Nothing in the method needs the coordinates of the points, only their dot products. That observation is the basis of kernels, below.
The soft margin
Real classes usually overlap, and then no hyperplane separates them and the problem above has no solution. Cortes and Vapnik (1995, §3) relaxed the constraints with slack variables $\xi_i \ge 0$, one per point, which let a point fall short of its margin:
$$y_i (w \cdot x_i + b) \ge 1 - \xi_i.$$
A point with $\xi_i = 0$ is on the correct side of its margin. A point with $0 < \xi_i < 1$ is inside the margin but still correctly classified, one with $\xi_i = 1$ lies on the boundary, and one with $\xi_i > 1$ is on the wrong side of it. Slack is charged for in the objective:
$$\min_{w,\,b,\,\xi}\ \tfrac{1}{2}\|w\|^2 + C \sum_{i=1}^{n} \xi_i \quad \text{subject to} \quad y_i (w \cdot x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0.$$
This is the support vector classifier (Hastie et al., 2009, eq. 12.8). The cost $C > 0$ sets the exchange rate between a wide margin, small $\|w\|$, and few violations, small $\sum \xi_i$. A large $C$ makes violations expensive, so the margin narrows to avoid them; a small $C$ tolerates violations in return for a wider margin. The separable problem is the limit $C \to \infty$. Cortes and Vapnik wrote the penalty more generally as $C\,F(\sum \xi_i^\sigma)$ with $F$ increasing and convex. Small values of $\sigma$ approximate counting training errors, and minimizing that count is in general NP-complete, so they took $\sigma = 1$, the smallest value for which the problem has a unique solution, and in their experiments used $F(u) = u^2$; they also show (Appendix A.2) that $F(u) = u$, the form above and the one used by software today, leads to the dual problem below.
Two conventions for $C$ are in use, and they point in opposite directions. In the form above, and in scikit-learn, $C$ multiplies the total slack, so larger $C$ means a narrower margin and fewer violations. James et al. (2021, §9.2.2) instead define $C$ as a budget that the total slack may not exceed, so that larger $C$ means a wider margin and more violations. The two describe the same family of classifiers.
The dual of the soft-margin problem is the dual above with one change: each multiplier is capped, $0 \le \alpha_i \le C$ (Hastie et al., 2009, eq. 12.13). The complementary slackness conditions now sort the training points into three groups. Points outside their margin have $\alpha_i = 0$ and do not affect the solution. Points exactly on the margin have $0 < \alpha_i < C$. Points inside the margin or misclassified have $\alpha_i = C$. The support vectors are the last two groups (Hastie et al., 2009, §12.2.1).
Breast cancer, two inputs
The Wisconsin breast cancer data (Wolberg, Mangasarian, Street and Street, 1993) describe 569 breast masses by 30 measurements of cell nuclei; 212 were malignant. Using the split of Loss Functions for Classification, 379 masses for training and 190 for testing (stratified, seed 742), and two inputs, the mean radius and mean texture of the nuclei, standardized with the training means and standard deviations, a linear support vector classifier was fitted for a range of costs:
| $C$ | $\|w\|$ | Margin width $2/\|w\|$ | Support vectors | On margin ($0 < \alpha < C$) | Training accuracy | Test accuracy |
|---|---|---|---|---|---|---|
| 0.001 | 0.202 | 9.89 | 282 | 0 | 0.628 | 0.632 |
| 0.01 | 0.864 | 2.31 | 206 | 2 | 0.873 | 0.847 |
| 0.1 | 1.474 | 1.36 | 124 | 3 | 0.894 | 0.858 |
| 1 | 2.174 | 0.92 | 102 | 3 | 0.902 | 0.863 |
| 10 | 2.192 | 0.91 | 99 | 3 | 0.900 | 0.863 |
| 100 | 2.258 | 0.89 | 97 | 3 | 0.897 | 0.858 |
| 1000 | 2.258 | 0.89 | 97 | 3 | 0.897 | 0.858 |
At $C = 0.001$ violations are so cheap that the margin is almost ten standard deviations wide, 282 of the 379 training masses fall short of their margin, and the classifier predicts benign for every mass: its accuracy, 0.628, is the share of benign masses. As $C$ rises the margin narrows and the support vectors fall from 282 to 97. Beyond $C = 1$ little changes. The classes overlap, so some 95 points stay inside the margin or beyond it however expensive violations become, and the solution settles where shrinking the margin further no longer reduces the slack. Ten-fold cross-validation on the training masses rates every $C$ from 0.1 upward between 0.889 and 0.892, and chooses $C = 10$.
At $C = 1$ the Karush-Kuhn-Tucker conditions can be checked point by point. Of the 379 training masses, 277 have $\alpha_i = 0$, and all lie outside their margin (the smallest $y_i f(x_i)$ among them is 1.042). Three have $0 < \alpha_i < C$, and all three have $y_i f(x_i) = 1.0000$, exactly on the margin. The other 99 have $\alpha_i = C$, and all have $y_i f(x_i) < 1$, inside the margin or beyond it; 37 of them are misclassified.
The hinge loss view
At the solution of the soft-margin problem, each slack is as small as its constraint allows: $\xi_i = \max(0, 1 - y_i f(x_i))$. Substituting this removes the constraints and gives an equivalent unconstrained problem,
$$\min_{w,\,b}\ \sum_{i=1}^{n} \max\bigl(0,\ 1 - y_i f(x_i)\bigr) + \frac{\lambda}{2}\|w\|^2, \qquad \lambda = \frac{1}{C}$$
(Hastie et al., 2009, eq. 12.25, after dividing the objective by $C$). The first term is the hinge loss, the training loss of the support vector machine, and the second is a penalty on the size of the coefficients, the same kind of penalty that ridge regression and penalized logistic regression use. A support vector classifier is a linear model fitted by minimizing a loss plus a penalty. On the breast cancer fit at $C = 1$, the objective computed this way, $\frac{1}{2}\|w\|^2 + C\sum$ hinge, is 98.2343, and the dual objective is also 98.2343.
Loss Functions for Classification compares the hinge loss with the losses of logistic regression and boosting as functions of the margin $y f(x)$. The hinge loss and the logistic loss have similar shapes, both growing linearly for badly misclassified points, which is why the two methods often give similar boundaries (James et al., 2021, §9.5). They differ at the other end. The hinge loss is exactly zero once $y_i f(x_i) \ge 1$, so well-classified points drop out of the fit entirely, which is what produces support vectors. The logistic loss is never exactly zero, so every point has some influence. And the hinge loss is minimized by the sign of $\Pr(Y = 1 \mid x) - \frac{1}{2}$ rather than by a function of the probability (Hastie et al., 2009, Table 12.1), so a support vector machine produces scores, not probabilities. scikit-learn's SVC(probability=True) adds probabilities after the fact by Platt scaling, fitting a logistic curve to the scores with an internal five-fold cross-validation, and its documentation warns that the resulting predict_proba may disagree with predict (scikit-learn developers, 2024).
Kernels
A linear boundary cannot separate classes that need a curve. The standard remedy, used throughout regression, is to add transformed inputs. Fourteen points on a line, with class $+1$ at both ends and class $-1$ in the middle, cannot be separated by any single threshold; adding $x^2$ as a second input lifts them onto a parabola, where a straight line separates them. A linear boundary in the enlarged space is a curve, here a pair of thresholds, in the original one.
In general, a feature map $\phi$ sends each input vector $x$ to a longer vector $\phi(x)$ of transformed features, and a support vector classifier is fitted to the $\phi(x_i)$. The difficulty is size. All products of up to $d$ inputs, which a polynomial boundary of degree $d$ needs, number $\binom{p + d}{d}$ including the constant: 496 for degree 2 in 30 inputs, 5,456 for degree 3, and 324,632 for degree 5. For the 16 by 16 pixel digits of Cortes and Vapnik, 256 inputs, a degree-4 polynomial would need about 186 million features.
The dual removes the difficulty. The fitted classifier and the dual problem use the transformed points only through dot products $\phi(x_i) \cdot \phi(x_j)$. If a function $K$ can compute those dot products directly from the original inputs,
$$K(x, z) = \phi(x) \cdot \phi(z),$$
then the transformed vectors never need to be formed. This is the kernel trick, and $K$ is a kernel. The support vector machine then fits
$$f(x) = \sum_{i=1}^{n} \alpha_i y_i\, K(x_i, x) + b,$$
by solving the same dual problem with $x_i \cdot x_j$ replaced by $K(x_i, x_j)$ (Hastie et al., 2009, §12.3.1; Cortes and Vapnik, 1995, §4). Not every function of two vectors is a dot product in some feature space. Mercer's condition, which Cortes and Vapnik state, characterizes those that are; in practice, a kernel must give a positive semidefinite matrix $K(x_i, x_j)$ on every set of points.
The polynomial kernel, checked
The polynomial kernel of degree $d$ is $K(x, z) = (1 + x \cdot z)^d$. For two inputs and $d = 2$, expanding the square shows which feature map it computes:
$$(1 + x_1 z_1 + x_2 z_2)^2 = 1 + 2x_1 z_1 + 2x_2 z_2 + x_1^2 z_1^2 + x_2^2 z_2^2 + 2 x_1 x_2 z_1 z_2,$$
which is $\phi(x) \cdot \phi(z)$ for the six features
$$\phi(x) = \bigl(1,\ \sqrt{2}\,x_1,\ \sqrt{2}\,x_2,\ x_1^2,\ x_2^2,\ \sqrt{2}\,x_1 x_2\bigr)$$
(Hastie et al., 2009, eq. 12.23). Take $x = (1, 2)$ and $z = (3, 1)$. The kernel needs one dot product, $x \cdot z = 3 + 2 = 5$, and one square: $(1 + 5)^2 = 36$. The long way builds $\phi(x) = (1, 1.4142, 2.8284, 1, 4, 2.8284)$ and $\phi(z) = (1, 4.2426, 1.4142, 9, 1, 4.2426)$ and multiplies term by term: $1 + 6 + 4 + 9 + 4 + 12 = 36$. The answers agree, and the gap in work grows quickly with $p$ and $d$: the kernel always costs one dot product of length $p$, while the feature vectors have $\binom{p + d}{d}$ entries.
The radial basis function kernel
The most widely used kernel is the radial basis function (RBF) or Gaussian kernel,
$$K(x, z) = \exp\bigl(-\gamma \|x - z\|^2\bigr), \qquad \gamma > 0$$
(Hastie et al., 2009, eq. 12.22; James et al., 2021, eq. 9.24). It is 1 when $x = z$ and falls toward 0 as the points move apart, so it behaves like a similarity. Its feature space has infinitely many dimensions. In one dimension this can be seen directly by factoring the exponent, $-\gamma(x - z)^2 = -\gamma x^2 - \gamma z^2 + 2\gamma x z$, and expanding the last factor as a power series:
$$e^{-\gamma (x - z)^2} = e^{-\gamma x^2} e^{-\gamma z^2} \sum_{k=0}^{\infty} \frac{(2\gamma)^k x^k z^k}{k!}.$$
Each term is a product of a function of $x$ and the same function of $z$, so the kernel is a dot product of feature vectors with one coordinate, $e^{-\gamma x^2}\sqrt{(2\gamma)^k / k!}\, x^k$, for every power $k = 0, 1, 2, \dots$ For $x = 1$, $z = 2$ and $\gamma = 0.5$ the kernel is $e^{-0.5} = 0.606531$. The prefactor is $e^{-0.5} e^{-2} = 0.082085$, and the partial sums of the series, after one to nine terms, are 0.0821, 0.2463, 0.4104, 0.5199, 0.5746, 0.5965, 0.6038, 0.6059 and 0.6064: every coordinate adds a little, and no finite number of them gives the exact value. The kernel computes the infinite dot product in one evaluation.
The fitted function $f(x) = \sum \alpha_i y_i K(x_i, x) + b$ is a weighted sum of bumps centered on the support vectors, and $\gamma$ sets their width. A large $\gamma$ makes each bump narrow, so the boundary can wrap tightly around individual points; a small $\gamma$ makes them broad, and the boundary smooth. With $C$, it is the second tuning parameter, and the two are normally chosen together by cross-validation.
On a problem with a known answer
Introduction to Supervised Learning defined a simulated two-class problem whose classes are each a mixture of three clusters, with a curved Bayes decision boundary and a Bayes error rate of 0.1816: no classifier can do better on average. Support vector machines with four kernels were fitted to training sets of 200 instances, with $C$ (and $\gamma$ for the RBF kernel) chosen by ten-fold cross-validation on each training set, and tested on 20,000 new instances. Polynomial kernels were used in the form $(1 + x \cdot z)^d$.
| Classifier | Mean test error, 30 training sets (SD) |
|---|---|
| linear SVM | 0.2648 (0.0064) |
| polynomial SVM, degree 2 | 0.2426 (0.0086) |
| polynomial SVM, degree 3 | 0.2089 (0.0148) |
| RBF SVM | 0.2037 (0.0145) |
| Bayes classifier | 0.1816 |
A straight line cannot follow the boundary, and neither can a conic section well enough; degree 3 and the RBF kernel come within about two to three points of the Bayes error rate, close to the 0.1997 that 15-nearest neighbors averaged on the same problem. The linear machine's 0.2648 is also lower than the 0.2928 of logistic regression in Introduction to Supervised Learning, although both draw a straight line. When no straight line matches the Bayes boundary, the hinge loss and the logistic loss each pick the line that is best by their own measure, these are different lines, and neither loss counts errors directly. The similar boundaries the two methods often give, noted in the hinge loss section above, are not guaranteed when the linear form is wrong. On the first training set, cross-validation chose $C = 100$ and $\gamma = 0.1$ for the RBF kernel, which kept 101 of the 200 points as support vectors and had a test error of 0.1963.
Holding $C = 1$ and varying $\gamma$ on the same training set shows the bias-variance tradeoff in its geometric form:
| $\gamma$ | Training error | Test error | Support vectors |
|---|---|---|---|
| 0.1 | 0.270 | 0.2391 | 132 |
| 1 | 0.175 | 0.1929 | 113 |
| 10 | 0.120 | 0.2269 | 163 |
| 100 | 0.005 | 0.3459 | 198 |
At $\gamma = 0.1$ the bumps are too broad for the boundary to bend around the middle cluster. At $\gamma = 100$ each training point has its own tiny region, the training error is almost zero, and the test error is worse than a straight line's; 198 of 200 points are support vectors. Hastie et al. (2009, §12.3) note that early claims that kernels let support vector machines escape the curse of dimensionality are not true. Like any flexible method, a kernel machine can overfit, and its cost and kernel parameters have to be tuned.
Breast cancer, all 30 inputs
On the full breast cancer data, with the same 379 training and 190 test masses, each model's tuning parameters were chosen by ten-fold cross-validation on the training masses:
| Model | Chosen parameters | CV accuracy | Test accuracy | Support vectors |
|---|---|---|---|---|
| linear SVM, standardized | $C = 1$ | 0.974 | 0.953 | 27 |
| RBF SVM, standardized | $C = 10$, $\gamma = 0.01$ | 0.976 | 0.958 | 40 |
| RBF SVM, raw inputs | $C = 1000$, $\gamma = 10^{-5}$ | 0.966 | 0.916 | 36 |
| logistic regression, L2 penalty | $C = 1$ | 0.979 | 0.958 |
The linear and RBF machines and penalized logistic regression are within one error of each other on the test set, 9, 8 and 8 errors out of 190. The boundary between malignant and benign masses is close to linear in these 30 measurements, and on such problems the choice among good linear methods matters little. The linear machine is described by 27 support vectors, 7.1% of the training masses.
The third row shows why scaling matters. The kernel and the margin are both defined by Euclidean distance, so an input measured in large units dominates them: the mean area of the nuclei runs into the thousands, while their smoothness is measured in hundredths. Without standardization, the best RBF machine the grid could find had 16 test errors, twice as many; with scikit-learn's default settings ($C = 1$, $\gamma$ set from the overall variance of the inputs), the accuracy on raw inputs was 0.868 against 0.953 on standardized ones. Standardizing the inputs, with means and standard deviations computed on the training data only, is a routine first step for any support vector machine, as for nearest neighbors.
The support vector count gives a quick check on generalization. Leaving out a point that is not a support vector does not change the solution, and that point is classified correctly, so the leave-one-out error is at most the fraction of support vectors (Hastie et al., 2009, §12.2.2); Cortes and Vapnik's bound for separable data rests on the same reasoning. For the linear machine on the training masses, the fraction is 0.071 and the actual leave-one-out error is 0.026. The bound holds, but, as Hastie et al. note, it tends to be too high to be useful for choosing $C$.
More than two classes
A support vector machine separates two classes. For $K$ classes there are two standard reductions (James et al., 2021, §9.4). One-versus-one fits a machine to each of the $K(K-1)/2$ pairs of classes and predicts the class that wins most pairwise contests; scikit-learn's SVC always trains this way (scikit-learn developers, 2024). One-versus-rest fits $K$ machines, each separating one class from all the others, and predicts the class whose machine gives the largest score; Cortes and Vapnik (1995, §6.2) classified digits this way, with ten separators. On the three-cultivar wine data (Aeberhard and Forina, 1992), with standardized inputs and $C = 1$, ten-fold cross-validated accuracy is 0.955 for a linear machine and 0.983 with the RBF kernel.
Results on handwritten digits
Cortes and Vapnik (1995, Table 2) report the experiment that showed what the combination of margins and kernels could do. On a US Postal Service set of 7,300 training and 2,000 test digits, 16 by 16 pixels, a linear machine had a test error of 12.0%, and polynomial kernels of degrees 2 to 7 had errors from 4.7% down to 4.2%, while the dimension of the implicit feature space grew by many orders of magnitude. The average number of support vectors per classifier stayed between 127 and 190, and the error barely changed with the degree. The authors' reading was that the margin, not the dimension of the space, controlled generalization. On a larger set of 60,000 training digits from the NIST database, a degree-4 polynomial machine reached 1.1% test error. The benchmark compared it with a linear classifier, a 3-nearest-neighbor classifier and two neural networks designed for digit recognition, LeNet1 and LeNet4, and its organizers' report, which Cortes and Vapnik quote, singled out the support-vector network's accuracy as remarkable because, unlike the other strong entries, it used no knowledge of the images' geometry: it would do as well if the pixels were shuffled by a fixed random permutation.
Strengths and limitations
The method's strengths follow from its construction. The training problem is convex, so the solution does not depend on a random start. Only support vectors enter the fitted classifier, which makes it compact when they are few. Kernels give flexible boundaries without forming large feature vectors.
The limitations are as clear. Training cost grows quickly with the number of cases: scikit-learn's documentation says that SVC's fit time "scales at least quadratically with the number of samples and may be impractical beyond tens of thousands of samples" (scikit-learn developers, 2024). For large datasets with a linear boundary, specialized linear solvers such as scikit-learn's LinearSVC are faster. Results depend on scaling and on two or more tuning parameters. The scores are not probabilities without an extra calibration step. And a kernel machine is hard to interpret: its boundary is a weighted sum of similarities to dozens or hundreds of training cases, which says little about how any single input affects the outcome.
In Python
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import GridSearchCV, StratifiedKFold, train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
data = load_breast_cancer()
X, y = data.data, 1 - data.target # malignant = 1
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=1/3, stratify=y, random_state=742)
model = make_pipeline(StandardScaler(), SVC(kernel='rbf'))
grid = {'svc__C': [0.1, 1, 10, 100, 1000],
'svc__gamma': [0.0003, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3]}
search = GridSearchCV(model, grid, cv=StratifiedKFold(10, shuffle=True, random_state=0))
search.fit(X_tr, y_tr)
print(search.best_params_) # {'svc__C': 10, 'svc__gamma': 0.01}
print(search.score(X_te, y_te)) # 0.958
svc = search.best_estimator_[-1]
print(len(svc.support_)) # 40 support vectors
print(svc.dual_coef_[0][:5]) # alpha_i * y_i for the first five
kernel is 'linear', 'poly' (with degree, and coef0=1 for the form $(1 + x \cdot z)^d$ used here, scaled by gamma), or 'rbf'. support_ holds the indices of the support vectors, dual_coef_ the products $\alpha_i y_i$, and decision_function the score $f(x)$. Placing the scaler in a pipeline means that within each cross-validation fold it is fitted to the training part only. The numbers in this article are computed by tools/experiments/data-science/support-vector-machines.py in the site's repository.
References
- Aeberhard, S., and Forina, M. (1992). Wine [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5PC7J record · 8 pages
- Boser, B. E., Guyon, I. M., and Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT 1992), 144–152. https://doi.org/10.1145/130385.130401. Cited by attribution (Cortes and Vapnik, 1995). record
- Cortes, C., and Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. record · 2 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
- James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
- scikit-learn developers (2024). sklearn.svm.SVC. scikit-learn 1.6 documentation. https://scikit-learn.org/1.6/modules/generated/sklearn.svm.SVC.html record
- Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages