Dictionary of Applied Machine Learning

support vector machine

Typeset PDF version — the authoritative form of this entry

Python demo — a script that recomputes what this entry states and prints one line per check

The support vector machine (SVM) is a binary classification method that learns a linear classifier by regularized empirical risk minimization (RERM), combining the hinge loss with a squared-norm penalty term. For a linearly separable training set and sufficiently weak regularization, the solution is the maximum-margin separating hyperplane. This hyperplane is fully determined by the feature vectors closest to it, which are called support vectors. The kernel SVM is obtained by combining the basic SVM with a feature transformation derived from a kernel function.

Definition

The support vector machine (SVM) is a binary classification method for data points with feature space $\featurespace=\reals^{\nrfeatures}$. In its simplest form, the SVM learns a linear classifier with decision boundary \[\{ \featurevec \in \reals^{\nrfeatures} : \weights^{\top} \featurevec + \offset = 0 \}.\] The linear classifier is parameterized by a nonzero vector $\weights \in \reals^{\nrfeatures} \setminus \{\mathbf{0}\}$ and an offset $\offset \in \reals$. The vector $\weights$ is the normal vector to the decision boundary and the offset $\offset$ shifts the decision boundary away from the origin.

For a data point with feature vector $\featurevec$ and label $\truelabel \in \{-1, +1\}$, the SVM delivers the prediction $\predictedlabel = \operatorname{sign}(\weights^{\top} \featurevec + \offset)$. SVMs have been applied to text classification, where each document is first represented by a numeric feature vector of word frequencies and then categorized by topic. Another application is handwritten digit recognition, where digit images are classified from pixel-level features (Cristianini and Shawe-Taylor, 2000).

P-nonsepThe SVM can be formulated as an instance of regularized empirical risk minimization (RERM) for learning a linear classifier from a training set that consists of $\samplesize$ data points. The model parameters $(\widehat{\weights}, \widehat{\offset})$ of the linear classifier are obtained as \begin{equation} \label{eq:svm_rerm} (\widehat{\weights}, \widehat{\offset}) = \argmin_{\weights \in \reals^{\nrfeatures},\, \offset \in \reals} \underbrace{\frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \max\{0,\, 1 - \truelabel^{(\sampleidx)} (\weights^{\top} \featurevec^{(\sampleidx)} + \offset)\} + \regparam \normgeneric{\weights}{2}^{2}}_{\defeq f(\weights, \offset)}\text{.} \end{equation} The SVM objective function consists of the average hinge loss on the training set plus a penalty term $\regparam \normgeneric{\weights}{2}^{2}$ with regularization parameter $\regparam > 0$ (Hastie et al., 2009, Sect. 12.3.2, p. 426; Shalev-Shwartz and Ben-David, 2014, Sect. 15.2, Eq. (15.5)). The penalty term in \(\eqref{eq:svm_rerm}\) is the scaled squared Euclidean norm $\regparam \normgeneric{\weights}{2}^{2}$, the same penalty term as in ridge regression. It does not involve the model parameter $\offset$, which is therefore left unpenalized.

In linear regression, the penalty term can be interpreted as an estimate of how much higher the loss is on data points outside the training set than on it (Hastie et al., 2009, Ch. 7; see linear regression). This interpretation rests on the quadratic structure of the squared error loss and does not carry over to the hinge loss.

For the SVM, the penalty term instead controls the generalization gap: the hinge loss is Lipschitz continuous in $\weights$, with a constant given by the Euclidean norm of the feature vector. Adding the penalty term $\regparam \normgeneric{\weights}{2}^{2}$ to the average hinge loss has two effects: First, it makes the overall objective function in \(\eqref{eq:svm_rerm}\) strongly convex in $\weights$, so that its solution $\widehat{\weights}$ is unique. Second, it controls how much that solution varies if the data points in the training set change.

If the feature vectors in the training set have bounded Euclidean norm, the expectation of the difference between the risk and the empirical hinge loss of the learned linear classifier decreases in proportion to $1/(\regparam \samplesize)$ (Shalev-Shwartz and Ben-David, 2014, Cor. 13.6, Cor. 15.7). The penalty term also has a geometric role: a small norm $\normgeneric{\widehat{\weights}}{2}$ corresponds to a large margin $1/\normgeneric{\widehat{\weights}}{2}$ of the learned linear classifier, as discussed below.

Like logistic regression and linear regression, the SVM learns the model parameters $(\weights, \offset)$ of a linear model. In contrast to logistic regression and linear regression, the SVM objective function $f(\weights, \offset)$ is non-smooth because of the hinge loss. However, since the SVM objective function is convex, the optimization problem \(\eqref{eq:svm_rerm}\) can be solved by convex optimization methods. One such method is subgradient descent, which is obtained from gradient descent (GD) by replacing the gradient of the objective function with a subgradient (Shor, 1985; Bertsekas, 2016; Boyd and Vandenberghe, 2004).

Starting from an initial choice $\weights^{(0)}, \offset^{(0)}$ of the model parameters, subgradient descent repeatedly applies the update \[ \big(\weights^{(\iteridx+1)}, \offset^{(\iteridx+1)}\big) = \big(\weights^{(\iteridx)}, \offset^{(\iteridx)}\big) - \lrate^{(\iteridx)} \vg^{(\iteridx)} \text{, for } \iteridx = 0,1,\ldots \text{,} \] with a step size $\lrate^{(\iteridx)} > 0$ and a subgradient $\vg^{(\iteridx)} \in \partial f\big(\weights^{(\iteridx)}, \offset^{(\iteridx)}\big)$ of the SVM objective function \(\eqref{eq:svm_rerm}\). Inserting the SVM objective function \(\eqref{eq:svm_rerm}\) into the generic update yields the explicit update \[ \begin{aligned} \weights^{(\iteridx+1)} &= \big(1 - 2 \lrate^{(\iteridx)} \regparam\big) \weights^{(\iteridx)} + \frac{\lrate^{(\iteridx)}}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \expcoeff^{(\iteridx)}_{\sampleidx} \truelabel^{(\sampleidx)} \featurevec^{(\sampleidx)} \text{,} \\ \offset^{(\iteridx+1)} &= \offset^{(\iteridx)} + \frac{\lrate^{(\iteridx)}}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \expcoeff^{(\iteridx)}_{\sampleidx} \truelabel^{(\sampleidx)} \text{,} \end{aligned} \] with expansion coefficients $\expcoeff^{(\iteridx)}_{\sampleidx} \in [0, 1]$, for $\sampleidx = 1, \ldots, \samplesize$. The coefficient $\expcoeff^{(\iteridx)}_{\sampleidx}$ is nonzero only for data points that satisfy $\truelabel^{(\sampleidx)} \big( \big(\weights^{(\iteridx)}\big)^{\top} \featurevec^{(\sampleidx)} + \offset^{(\iteridx)} \big) \leq 1$, i.e., data points on which the hinge loss is nonzero or non-differentiable at the current model parameters. Each iteration scales $\weights^{(\iteridx)}$ by the factor $1 - 2 \lrate^{(\iteridx)} \regparam$ (the effect of the penalty term) and adds corrections $\truelabel^{(\sampleidx)} \featurevec^{(\sampleidx)}$ only from these data points. In particular, for the initialization $\weights^{(0)} = \mathbf{0}$, every iterate $\weights^{(\iteridx)}$ is a weighted sum $\sum_{\sampleidx=1}^{\samplesize} \expcoeff_{\sampleidx} \truelabel^{(\sampleidx)} \featurevec^{(\sampleidx)}$ of the feature vectors in the training set. The solution $\widehat{\weights}$ of \(\eqref{eq:svm_rerm}\) admits the same expansion, with coefficients that are nonzero only for the data points satisfying the same condition $\truelabel^{(\sampleidx)} \big( \widehat{\weights}^{\top} \featurevec^{(\sampleidx)} + \widehat{\offset} \big) \leq 1$ (see the discussion of support vectors below). For a suitably diminishing step size, e.g., $\lrate^{(\iteridx)} = 1/(\iteridx+1)$, the iterates $\big(\weights^{(\iteridx)}, \offset^{(\iteridx)}\big)$ converge to a solution of \(\eqref{eq:svm_rerm}\) (Shor, 1985).

P-svThe solution of \(\eqref{eq:svm_rerm}\) has a clear geometric meaning when the training set is linearly separable, i.e., there is some choice for $(\weights, \offset)$ such that $\operatorname{sign}(\weights^{\top} \featurevec^{(\sampleidx)} + \offset) \truelabel^{(\sampleidx)}=1$ for $\sampleidx=1, \ldots, \samplesize$. For a sufficiently small $\regparam$, the solution of \(\eqref{eq:svm_rerm}\) determines the separating hyperplane that is farthest from the feature vectors in the training set (see Fig. 1). The distance between this hyperplane and the nearest feature vectors, which are precisely the support vectors discussed below, is referred to as the margin and is given by $1/\normgeneric{\widehat{\weights}}{2}$ (Boser et al., 1992; Cortes and Vapnik, 1995; Cristianini and Shawe-Taylor, 2000).

Figure 1 of the entry svm
Figure 1: Maximum-margin separation for a linearly separable training set. The decision boundary $\widehat{\weights}^{\top}\featurevec + \widehat{\offset} = 0$ (solid line) lies halfway between two parallel hyperplanes $\widehat{\weights}^{\top}\featurevec + \widehat{\offset} = \pm 1$ (dashed lines). The support vectors (open square and filled circle inside red rings) are the feature vectors that lie on these hyperplanes. The margin $\gamma = 1/\normgeneric{\widehat{\weights}}{2}$ is the distance from the decision boundary to the support vectors. Data points with label $\truelabel=+1$ are drawn as filled circles, those with $\truelabel=-1$ as open squares. The dashed circle of radius $\gamma$ shows that any support vector can be displaced by a perturbation with Euclidean norm less than $\gamma$ without crossing the decision boundary
The margin of the learned hyperplane measures robustness against perturbations of the features of a data point. Perturbing a feature vector $\featurevec$ by a vector $\boldsymbol{\delta}$ changes the score $\widehat{\weights}^{\top}\featurevec + \widehat{\offset}$ by $\widehat{\weights}^{\top}\boldsymbol{\delta}$, whose magnitude is at most $\normgeneric{\widehat{\weights}}{2} \normgeneric{\boldsymbol{\delta}}{2}$ by the Cauchy-Schwarz inequality. A data point therefore stays correctly classified under every feature perturbation with $\normgeneric{\boldsymbol{\delta}}{2} < \gamma$, as illustrated by the dashed circle around a support vector in Fig. 1. Data points whose feature vectors lie farther from the decision boundary tolerate even larger perturbations: the tolerated radius equals the distance of the feature vector from the decision boundary, which is at least $\gamma$ and equals $\gamma$ precisely for the support vectors. Maximizing the margin maximizes this worst-case tolerated radius, so the maximum-margin classifier is the separating classifier that is robust against the largest feature perturbations (Xu et al., 2009).

P-violWhile the above discussion only applies when the SVM training set is linearly separable, every solution of the SVM problem \(\eqref{eq:svm_rerm}\) has a structure that holds in general. In particular, \[\widehat{\weights} = \sum_{\sampleidx=1}^{\samplesize} \expcoeff_{\sampleidx} \truelabel^{(\sampleidx)} \featurevec^{(\sampleidx)}\] with expansion coefficients $0 \leq \expcoeff_{\sampleidx} \leq 1/(2 \regparam \samplesize)$ that are nonzero only for the feature vectors with \[\truelabel^{(\sampleidx)} (\widehat{\weights}^{\top} \featurevec^{(\sampleidx)} + \widehat{\offset}) \leq 1.\] These feature vectors are referred to as support vectors since they entirely determine the SVM solution $(\widehat{\weights}, \widehat{\offset})$ (Boser et al., 1992; Cortes and Vapnik, 1995). Applying a perturbation to any feature vector which is not a support vector leaves $\widehat{\weights}$, $\widehat{\offset}$ unchanged, provided the perturbation is small enough to preserve the strict inequality $\truelabel (\widehat{\weights}^{\top} \featurevec + \widehat{\offset}) > 1$ (see Fig. 2).

Figure 2 of the entry svm
Figure 2: Non-separable training set of $\samplesize = 7$ data points in feature space $\reals^{2}$. The solution of the SVM problem \(\eqref{eq:svm_rerm}\) places the decision boundary $\widehat{\weights}^{\top}\featurevec + \widehat{\offset} = 0$ between the two hyperplanes $\widehat{\weights}^{\top}\featurevec + \widehat{\offset} = \pm 1$ at distance $\gamma = 1/\normgeneric{\widehat{\weights}}{2}$. These two hyperplanes contain four of the support vectors (red rings), given by the data points with margin equal to $\gamma$. The outlier, labeled $+1$, is also a support vector; it is misclassified beyond the opposite margin: $\truelabel(\widehat{\weights}^{\top}\featurevec + \widehat{\offset}) = -2 < -1$, with hinge loss value $\xi$. The two data points (open square and filled circle not inside red rings) farther from the decision boundary than the margin $\gamma$ are not support vectors. Data generated by pythondemos/svm.py
An overly large regularization parameter $\regparam$ makes the SVM underfit: the above expansion of $\widehat{\weights}$ implies $\normgeneric{\widehat{\weights}}{2} \leq \rho/(2\regparam)$, with $\rho$ the largest Euclidean norm of a feature vector in the training set, so $\widehat{\weights}$ shrinks toward $\mathbf{0}$.

P-alphaConsider a training set with unequal class sizes. For sufficiently large $\regparam$, the predictions approach the constant majority-class prediction $\operatorname{sign}(\widehat{\offset})$ and every data point of the minority class is a misclassified support vector. The training set of Fig. 2 also has unequal class sizes, four data points labeled $\truelabel = +1$ and three labeled $\truelabel = -1$, but with the value $\regparam = 1/14$ used there, the SVM misclassifies one data point which can be considered an outlier. Increasing the value of $\regparam$ to $50$ for that training set shrinks $\normgeneric{\widehat{\weights}}{2}$, makes every prediction on the training set equal to $+1$, and misclassifies all three data points of the minority class.

P-kernelThe basic SVM \(\eqref{eq:svm_rerm}\) learns a linear classifier on the feature space $\featurespace = \reals^{\nrfeatures}$. It can be generalized to a classification method for data points whose feature vectors lie in an arbitrary feature space $\featurespace$ by first applying a feature transformation $\featuretrafo: \featurespace \to \featurespace'$ with $\featurespace' = \reals^{\nrfeatures}$ and then learning a linear classifier on the transformed feature vectors. By choosing $\featuretrafo$ (and $\nrfeatures$) appropriately, any given training set can be made linearly separable in $\featurespace'$ (Cortes and Vapnik, 1995; Cristianini and Shawe-Taylor, 2000). A principled construction of a feature transformation $\featuretrafo$ is via a kernel $\kernel: \featurespace \times \featurespace \to \reals$. In this construction, the transformed feature space is, in general, not $\reals^{\nrfeatures}$ but a Hilbert space $\hilbertspace$, which can be infinite-dimensional (see kernel method). The resulting method is then referred to as a kernel SVM (Schölkopf and Smola, 2002).

Synonyms: maximum-margin classifier.

See also: binary classification, linear model, classifier, hinge loss, margin, hyperplane, decision boundary, robustness, ridge regression, least absolute shrinkage and selection operator, kernel, kernel method, subgradient descent.

References

  1. Cristianini and Shawe-Taylor (2000). An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge Univ. Press. doi.org/10.1017/cbo9780511801389
  2. Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science+Business Media. doi.org/10.1007/978-0-387-84858-7
  3. Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press. doi.org/10.1017/cbo9781107298019
  4. Shor (1985). Minimization Methods for Non-differentiable Functions. Springer. doi.org/10.1007/978-3-642-82118-9
  5. Bertsekas (2016). Nonlinear Programming. Athena Scientific.
  6. Boyd and Vandenberghe (2004). Convex Optimization. Cambridge Univ. Press. doi.org/10.1017/CBO9780511804441
  7. Boser et al. (1992). A Training Algorithm for Optimal Margin Classifiers. Proc. 5th Annual Workshop on Computational Learning Theory (COLT). doi.org/10.1145/130385.130401
  8. Cortes and Vapnik (1995). Support-vector networks. Machine learning. doi.org/10.1007/BF00994018
  9. Xu et al. (2009). Robustness and Regularization of Support Vector Machines. J. Mach. Learn. Res.. www.jmlr.org/papers/v10/xu09b.html
  10. Schölkopf and Smola (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press. doi.org/10.7551/mitpress/4175.001.0001

Cite this entry

@misc{dictml_svm,
  author = {Jung, Alexander},
  title = {support vector machine},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-08-21},
  url = {https://dictionaryofml.org/terms/svm.html}
}