26  Support Vector Machines

Support vector machines (SVMs) classify by finding the boundary between classes that is farthest from the nearest training cases, and extend to nonlinear boundaries through kernels, functions that compute inner products in a high-dimensional feature space without constructing it. This chapter develops the maximal margin classifier, its soft-margin generalization, the hinge loss view that connects it to regularized linear models, kernels, and support vector regression.

26.1 The maximal margin classifier

For a binary outcome coded \(y_i \in \{-1, +1\}\), a linear classifier predicts the sign of \(f(x) = \beta_0 + x^\top \beta\). If the classes can be separated by a hyperplane, many hyperplanes separate them. The margin of a separating hyperplane is the distance from it to the nearest training case (AMDS: Projection). The maximal margin classifier chooses the hyperplane with the largest margin:

\[ \min_{\beta_0, \beta} \frac{1}{2}\lVert\beta\rVert^2 \quad \text{subject to} \quad y_i (\beta_0 + x_i^\top \beta) \ge 1, \quad i = 1, \dots, n . \tag{26.1}\]

The constraints require every case to be on the correct side at a distance of at least \(1/\lVert\beta\rVert\) from the hyperplane, so minimizing \(\lVert\beta\rVert\) maximizes the margin, \(2/\lVert\beta\rVert\) between the two parallel boundaries. The solution depends only on the cases that lie on the margin boundaries, the support vectors (Boser et al. 1992). This is a convex quadratic program with inequality constraints, solved through its dual (AMDS: Inequality constraints and the KKT conditions; Duality).

26.2 The soft margin

When the classes overlap, no separating hyperplane exists. The support vector classifier allows violations of the margin through slack variables \(\xi_i \ge 0\), with a cost \(C\) per unit of violation (Cortes and Vapnik 1995):

\[ \min_{\beta_0, \beta, \xi} \frac{1}{2}\lVert\beta\rVert^2 + C \sum_{i=1}^{n} \xi_i \quad \text{subject to} \quad y_i (\beta_0 + x_i^\top \beta) \ge 1 - \xi_i, \quad \xi_i \ge 0 . \tag{26.2}\]

Cases with \(\xi_i > 0\) lie inside the margin or on the wrong side of the boundary, and are also support vectors. \(C\) is a hyperparameter. A large \(C\) penalizes violations heavily and produces a narrow margin determined by few cases: low bias, high variance. A small \(C\) tolerates violations and produces a wide margin supported by many cases: higher bias, lower variance.

Figure 26.1 shows a support vector classifier fitted to two overlapping simulated classes.

Figure 26.1: A support vector classifier with \(C = 1\) for two simulated classes. The dark gray line is the decision boundary \(f(x) = 0\); the light gray lines are the margin boundaries \(f(x) = \pm 1\). Support vectors are the cases on or inside the margin, or misclassified.

Of the 60 cases, 16 are support vectors. The others could be moved anywhere outside the margin on their own side without changing the fit.

26.3 The hinge loss

The soft-margin problem is equivalent to minimizing a penalized loss,

\[ \min_{\beta_0, \beta} \sum_{i=1}^{n} \max\left(0, 1 - y_i f(x_i)\right) + \frac{\lambda}{2} \lVert\beta\rVert^2, \tag{26.3}\]

with \(\lambda = 1/C\). The hinge loss \(\max(0, 1 - y f(x))\) is zero for cases classified correctly beyond the margin, and grows linearly with the violation. The support vector classifier is therefore a ridge-penalized linear model (Section 18.2) with a loss that differs from the log loss of logistic regression mainly in ignoring well-classified cases (Figure 26.2). The two methods usually produce similar linear boundaries.

Figure 26.2: Loss as a function of the margin \(y f(x)\): zero–one loss, hinge loss, and the log loss of logistic regression scaled to pass through 1 at 0.

The SVM output \(f(x)\) is a score, not a probability. Probability estimates are obtained by fitting a logistic regression of the outcome on \(f(x)\), using internal cross-validation, a procedure called Platt scaling (Platt 1999).

26.4 Kernels

The solution of the SVM problem can be written as

\[ f(x) = \beta_0 + \sum_{i \in S} \alpha_i y_i \langle x, x_i \rangle , \tag{26.4}\]

where \(S\) is the set of support vectors and the \(\alpha_i\) are coefficients of the dual problem. The data enter only through inner products \(\langle x, x_i \rangle\) (AMDS: The dot product). Replacing the inner product by a kernel \(K(x, x')\), a function that equals the inner product of \(x\) and \(x'\) after a mapping \(\phi\) into another feature space, fits a linear boundary in that space, which is nonlinear in the original one (Schölkopf and Smola 2001). The mapping need not be computed. Common kernels are:

Table 26.1: Common kernels

Kernel	\(K(x, x')\)	Hyperparameters
Linear	\(\langle x, x' \rangle\)	—
Polynomial	\((1 + \langle x, x' \rangle)^d\)	degree \(d\)
Radial basis function (RBF)	\(\exp\left(-\gamma \lVert x - x' \rVert^2\right)\)	\(\gamma > 0\)

The RBF kernel corresponds to an infinite-dimensional feature space. It measures similarity by distance, as nearest neighbors do, and requires standardized features (Section 24.2). \(\gamma\) sets the width of the similarity: large \(\gamma\) makes each support vector influence only its immediate neighborhood, producing a flexible, high-variance boundary; small \(\gamma\) produces a smooth one. \(C\) and \(\gamma\) interact and are tuned together, on logarithmic grids.

26.5 Support vector regression

Support vector regression (SVR) replaces the hinge loss by the \(\varepsilon\)-insensitive loss, \(\max(0, \lvert y - f(x) \rvert - \varepsilon)\), which ignores errors smaller than \(\varepsilon\) and grows linearly beyond. Cases with residuals inside the \(\varepsilon\) band do not affect the fit; the others are the support vectors. With a kernel, SVR fits nonlinear functions, with \(C\), \(\varepsilon\) and the kernel parameters as hyperparameters.

26.6 Summary

• The maximal margin classifier separates the classes with the hyperplane farthest from the nearest cases, the support vectors.
• The soft margin allows violations at a cost \(C\), which controls the bias–variance tradeoff.
• The support vector classifier minimizes the hinge loss with a ridge penalty; probability estimates require an additional calibration step.
• Kernels fit linear boundaries in an implicit feature space, nonlinear in the original features; the RBF kernel’s \(\gamma\) controls their flexibility.
• Support vector regression uses the \(\varepsilon\)-insensitive loss.

26.7 Further reading

• AMDS: Constrained Optimization (KKT conditions and duality), Vectors (inner products and projection).
• Boser et al. (1992) and Cortes and Vapnik (1995) on support vector machines; Schölkopf and Smola (2001) on kernel methods; Platt (1999) on probability outputs.
• Hastie et al. (2009), chapter 12; James et al. (2021), chapter 9.
• Wikipedia: Support vector machine, Hinge loss, Kernel method, Radial basis function kernel.

Boser, Bernhard E., Isabelle M. Guyon, and Vladimir N. Vapnik. 1992. “A Training Algorithm for Optimal Margin Classifiers.” Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT92, 144–52. https://doi.org/10.1145/130385.130401.

Cortes, Corinna, and Vladimir Vapnik. 1995. “Support-Vector Networks.” Machine Learning 20 (3): 273–97. https://doi.org/10.1007/bf00994018.

Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning. In Springer Series in Statistics. Springer New York. https://doi.org/10.1007/978-0-387-84858-7.

James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2021. An Introduction to Statistical Learning: With Applications in r. In Springer Texts in Statistics. Springer US. https://doi.org/10.1007/978-1-0716-1418-1.

Platt, John C. 1999. “Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods.” In Advances in Large Margin Classifiers, edited by Alexander J. Smola, Peter Bartlett, Bernhard Schölkopf, and Dale Schuurmans. MIT Press.

Schölkopf, Bernhard, and Alexander J. Smola. 2001. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press. https://doi.org/10.7551/mitpress/4175.001.0001.