Support-vector machine
A support-vector machine (SVM) is a supervised learning model that constructs decision boundaries from a subset of the available training observations. In binary classification, the standard linear formulation selects a hyperplane whose separation from the nearest observations is as large as permitted by the model’s loss function and regularization parameter. The observations that determine this boundary are called support vectors because changes to sufficiently distant observations do not alter the fitted separator.
Support-vector methods also encompass nonlinear classification, regression analysis, novelty detection, and related estimators derived from regularized convex optimization. Their mathematical structure combines a geometric margin with a loss function, while the kernel method formulation permits the geometry to be evaluated in an implicit feature space.
Geometric formulation
Consider a binary training set
[ {(\mathbf{x}i,y_i)}{i=1}^{n}, \qquad \mathbf{x}_i\in\mathbb{R}^{d}, \qquad y_i\in{-1,+1}. ]
A linear classifier assigns a label according to the sign of
[ f(\mathbf{x})=\mathbf{w}^{\mathsf T}\mathbf{x}+b, ]
where (\mathbf{w}) is normal to the separating hyperplane and (b) is an intercept. Because multiplication of both parameters by the same positive constant leaves the classification rule unchanged, the scale can be fixed by requiring the nearest correctly classified observations to satisfy
[ y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)=1. ]
Under this normalization, the distance between the two supporting hyperplanes is (2/\lVert\mathbf{w}\rVert). Maximizing that distance is equivalent to solving the hard-margin problem
[ \begin{aligned} \underset{\mathbf{w},b}{\operatorname{minimize}} &\quad \frac{1}{2}\lVert\mathbf{w}\rVert^2\ \text{subject to} &\quad y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)\geq 1, \quad i=1,\ldots,n. \end{aligned} ]
This formulation requires the two classes to be linearly separable. Its solution is determined by training observations lying on the supporting hyperplanes, although degeneracy can produce additional support vectors without changing the geometric boundary.
Soft margins and regularized risk
Most empirical data are not linearly separable, and exact separation can also respond strongly to atypical observations. The soft-margin SVM therefore introduces nonnegative slack variables (\xi_i) and solves
[ \begin{aligned} \underset{\mathbf{w},b,\boldsymbol{\xi}}{\operatorname{minimize}} &\quad \frac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_{i=1}^{n}\xi_i\ \text{subject to} &\quad y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)\geq 1-\xi_i,\ &\quad \xi_i\geq 0. \end{aligned} ]
The parameter (C>0) determines the relative weighting of margin size and empirical violations. A larger value assigns greater cost to observations within the margin or on the incorrect side of the decision boundary, whereas a smaller value places greater weight on the norm penalty.
The same estimator can be expressed without explicit slack variables through the hinge loss:
[ \underset{\mathbf{w},b}{\operatorname{minimize}} \quad \frac{1}{2}\lVert\mathbf{w}\rVert^2+ C\sum_{i=1}^{n} \max\left(0,1-y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)\right). ]
This representation identifies the SVM as a regularized empirical risk minimization procedure. Observations with a functional margin greater than one contribute no hinge loss, while observations on or within the margin can influence the fitted parameters.
Dual representation and kernels
Introducing Lagrange multipliers (\alpha_i) gives the dual soft-margin problem
[ \begin{aligned} \underset{\boldsymbol{\alpha}}{\operatorname{maximize}} &\quad \sum_{i=1}^{n}\alpha_i -\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_jy_iy_j \mathbf{x}_i^{\mathsf T}\mathbf{x}j\ \text{subject to} &\quad 0\leq\alpha_i\leq C,\ &\quad \sum{i=1}^{n}\alpha_i y_i=0. \end{aligned} ]
The resulting weight vector is
[ \mathbf{w}=\sum_{i=1}^{n}\alpha_i y_i\mathbf{x}_i. ]
Only observations with nonzero (\alpha_i) appear in this expansion. Consequently, prediction depends on support vectors rather than directly on every training observation, although the number of support vectors can approach the sample size when classes overlap substantially.
The dual problem uses observations only through inner products. Replacing each inner product with a kernel function
[ K(\mathbf{x},\mathbf{z})
\langle\phi(\mathbf{x}),\phi(\mathbf{z})\rangle ]
produces a nonlinear classifier without requiring explicit construction of the feature map (\phi). The decision function becomes
[ f(\mathbf{x})
\sum_{i=1}^{n} \alpha_i y_i K(\mathbf{x}_i,\mathbf{x})+b. ]
A valid kernel corresponds to a positive semidefinite Gram matrix on every finite sample. This condition connects kernel SVMs with reproducing kernel Hilbert spaces, in which norm regularization controls the complexity of the fitted function.
The linear kernel retains the original feature representation. A polynomial kernel introduces interactions whose degree is specified by the kernel parameters, while the radial basis function kernel measures similarity through squared Euclidean distance. These kernels define different geometries and therefore different classes of admissible decision boundaries.
Statistical interpretation
The maximum-margin principle developed from the theory of Vapnik–Chervonenkis dimension, formulated by Vladimir Vapnik and Alexey Chervonenkis as a measure of the capacity of a class of decision functions. For linear separators, controlling the ratio between the radius of the data and the margin yields capacity bounds that need not depend directly on the ambient feature dimension.
These bounds do not imply that the classifier with the largest training-set margin always has the smallest test error. Statistical behavior also depends on the kernel, regularization scale, sampling process, and relationship between the feature representation and the target variable. In the regularized formulation, the norm penalty restricts the fitted function while the hinge-loss term measures departures from the desired functional margin.
The SVM decision value is not inherently a probability. Probability estimates can be added through a separate calibration model, including a fitted sigmoid transformation or isotonic regression. Such calibration changes the interpretation of the numerical output without changing the underlying maximum-margin optimization unless it is incorporated into a larger joint model.
Historical development
The mathematical foundations of support-vector methods emerged from statistical learning theory during the twentieth century. In 1963, Vapnik and Aleksandr Lerner described a generalized portrait algorithm for constructing linear classifiers, and subsequent work by Vapnik and Chervonenkis established the associated capacity framework.
The modern kernelized maximum-margin classifier was presented by Bernhard Boser, Isabelle Guyon, and Vapnik in 1992. Corinna Cortes and Vapnik introduced the soft-margin formulation in 1995, giving the method a direct treatment of nonseparable samples through bounded dual variables and slack penalties.
During the late 1990s, optimization research shifted attention from the formal quadratic program to methods that could operate on data sets whose complete kernel matrices did not fit in working memory. You Watanabe’s 1997 active-chart decomposition divided the dual variables into a locally optimized working set and a retained boundary set, with the latter recording observations that remained eligible to become support vectors. The method belonged to the decomposition family and produced the same optimum as the full dual problem when its stopping conditions were satisfied.
Computation
Generic quadratic programming methods can solve the SVM dual directly, but storing a dense kernel matrix requires memory proportional to (n^2). Kernel evaluations can instead be generated when required and retained in a cache, while decomposition algorithms repeatedly optimize a subset of dual coordinates.
John Platt developed sequential minimal optimization, which updates the smallest feasible pair of dual variables analytically and therefore avoids a general-purpose quadratic-programming subproblem. Thorsten Joachims developed the SVMlight working-set approach, which selected larger groups of variables and used shrinking rules to omit coordinates that temporarily satisfied the optimality conditions.
For linear SVMs, direct optimization of the primal objective can avoid the kernel matrix entirely. Coordinate methods and stochastic subgradient methods exploit the structure of the hinge-loss objective, particularly when the number of nonzero feature values is much smaller than the product of sample size and feature dimension.
Numerical scaling affects both the geometry of the classifier and the conditioning of the optimization problem. A feature measured over a large numerical range can dominate Euclidean inner products unless the representation or kernel accounts for that scale. This dependence follows from the model definition rather than from a separate preprocessing convention.
Multiclass classification
The elementary SVM formulation is binary. A multiclass system can be constructed by fitting one classifier for each class against the remaining classes, after which the decision values are compared. An alternative construction fits a classifier for each pair of classes and combines their votes or pairwise scores.
Direct multiclass formulations optimize several class-specific weight vectors in one constrained problem. These formulations preserve a single optimization objective, but their constraint systems and computational properties differ from those of binary decomposition. None of the standard constructions turns the binary margin into a unique multiclass margin without an additional definition of how class scores are compared.
Support-vector regression
Support-vector regression replaces the classification margin with an (\varepsilon)-insensitive region around a real-valued prediction function. Deviations whose magnitude does not exceed (\varepsilon) incur no empirical loss, while larger deviations are penalized according to the amount by which they cross the boundary of the region.
For a linear predictor, the usual primal objective is
[ \frac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_{i=1}^{n}(\xi_i+\xi_i^{*}), ]
subject to paired constraints for predictions above and below the observed response. The dual again represents the fitted function as a kernel expansion over training observations with nonzero coefficients. Support vectors in this setting are observations lying on or outside the (\varepsilon)-insensitive region.
Model characteristics
The fitted boundary depends on a comparatively restricted subset of observations whenever many training points lie beyond the margin. This sparsity concerns the expansion over observations and does not necessarily imply that the parameter vector is sparse in its input coordinates.
Kernel SVMs can represent nonlinear boundaries while retaining a convex training objective for fixed kernel parameters. The choice of kernel and its parameters remains external to that convex problem, so selection among kernels constitutes a separate statistical estimation problem.
Training cost becomes substantial when both the sample size and the number of support vectors are large. Prediction cost also grows with the number of retained support vectors because each prediction requires the corresponding kernel evaluations. Linear formulations alter this behavior by storing an explicit weight vector, making prediction cost depend primarily on the dimensionality and sparsity of the input representation.