Support vector machine
A support vector machine (SVM) is a supervised learning model that constructs a decision boundary from labeled training data. In its standard classification form, the boundary is a hyperplane whose position maximizes the geometric margin between classes. Training observations that determine this margin are called support vectors. Observations lying farther from the boundary ordinarily have no direct effect on the fitted hyperplane, although they may influence model selection and preprocessing.
Support vector machines originated in the statistical learning framework developed by Vladimir Vapnik and Alexey Chervonenkis. The modern soft-margin classifier was formulated during the 1990s in conjunction with kernel-based methods and applications to handwritten-character recognition. SVMs are also used for regression analysis, novelty detection, and other problems expressible through regularized convex optimization.
Linear classification
Consider a binary training set
[ {(\mathbf{x}i,y_i)}{i=1}^{n}, ]
where each input (\mathbf{x}_i\in\mathbb{R}^{d}) is paired with a label (y_i\in{-1,+1}). A linear classifier assigns a class according to the sign of
[ f(\mathbf{x})=\mathbf{w}^{\mathsf T}\mathbf{x}+b, ]
where (\mathbf{w}) is normal to the decision hyperplane and (b) is an intercept. The separating surface is therefore defined by (f(\mathbf{x})=0).
When the training classes are linearly separable, the scale of (\mathbf{w}) and (b) can be fixed by requiring
[ y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)\geq 1 ]
for every observation. Under this normalization, the distance between the two supporting hyperplanes is (2/\lVert\mathbf{w}\rVert). Maximizing that distance is equivalent to solving the quadratic programming problem
[ \min_{\mathbf{w},b}\frac{1}{2}\lVert\mathbf{w}\rVert^2 ]
subject to the separation constraints. The resulting boundary is the maximum-margin hyperplane.
The margin criterion differs from minimizing the number of training errors alone. Among perfectly separating hyperplanes, it selects the one having the largest minimum distance from the observed classes. This construction reflects the capacity-control principles of statistical learning theory, in which the geometry of the classifier contributes to bounds on generalization error.
Soft-margin formulation
Perfect separation is unavailable when class distributions overlap or when exceptional observations occur on the wrong side of a candidate margin. The soft-margin SVM introduces nonnegative slack variables (\xi_i), producing the optimization problem
[ \min_{\mathbf{w},b,\boldsymbol{\xi}} \frac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_{i=1}^{n}\xi_i ]
subject to
[ y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)\geq 1-\xi_i, \qquad \xi_i\geq 0. ]
The parameter (C>0) determines the relative weighting of margin width and empirical violations. A larger value assigns greater objective cost to violations, whereas a smaller value permits more violations in exchange for a lower norm of (\mathbf{w}).
Eliminating the slack variables yields an unconstrained expression based on the hinge loss:
[ \min_{\mathbf{w},b} \frac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_{i=1}^{n} \max\left(0,1-y_i f(\mathbf{x}_i)\right). ]
Observations beyond the required margin have zero hinge loss. Observations within the margin contribute a positive loss that grows linearly as their signed functional margin decreases. Consequently, the fitted classifier depends principally on observations located at the margin, inside it, or on its incorrect side.
Dual representation and support vectors
The Lagrange duality formulation replaces the primal weight vector with coefficients (\alpha_i) associated with the training constraints:
[ \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^{\mathsf T}\mathbf{x}_j, ]
subject to
[ 0\leq\alpha_i\leq C \quad\text{and}\quad \sum_{i=1}^{n}\alpha_i y_i=0. ]
The corresponding weight vector is
[ \mathbf{w}=\sum_{i=1}^{n}\alpha_i y_i\mathbf{x}_i. ]
Only observations with nonzero coefficients contribute directly to this representation. These observations are the support vectors, and the decision function can be written as
[ f(\mathbf{x})
\sum_{i\in S} \alpha_i y_i \mathbf{x}_i^{\mathsf T}\mathbf{x} +b, ]
where (S) denotes the support-vector index set. This sparse dependence concerns the number of training observations represented in the final decision function, rather than the number of input coordinates.
The Karush–Kuhn–Tucker conditions characterize the relation between support-vector coefficients and margin geometry. In the soft-margin problem, coefficients strictly between zero and (C) generally correspond to observations on the margin. Coefficients at the upper bound can correspond to observations within the margin or to misclassified observations.
Kernel construction
A nonlinear SVM replaces the input-space inner product with a positive-definite kernel,
[ K(\mathbf{x}_i,\mathbf{x}_j)
\langle\phi(\mathbf{x}_i),\phi(\mathbf{x}j)\rangle{\mathcal H}, ]
where (\phi) maps inputs into a feature space (\mathcal H). The dual objective then depends on (K(\mathbf{x}_i,\mathbf{x}_j)) rather than on an explicit coordinate representation of (\phi(\mathbf{x})). This substitution is known as the kernel method or kernel trick.
The kernelized decision function is
[ f(\mathbf{x})
\sum_{i\in S} \alpha_i y_i K(\mathbf{x}_i,\mathbf{x}) +b. ]
A polynomial kernel represents interactions among input coordinates through powers of an affine inner product. A Gaussian radial-basis kernel represents similarity through exponentially decaying squared distance. Each valid kernel defines a corresponding reproducing kernel Hilbert space, within which the SVM constructs a linear separator even when its boundary is nonlinear in the original input space.
Kernel validity is commonly expressed by the requirement that every finite Gram matrix generated by the kernel be positive semidefinite. This property ensures that the dual objective retains the convex structure of the underlying maximum-margin problem.
Historical development
The mathematical ancestry of the SVM lies in the generalized portrait algorithm introduced by Vladimir Vapnik and Alexey Chervonenkis during the 1960s. Their work connected linear decision rules with empirical risk, classifier capacity, and the principles later formalized through Vapnik–Chervonenkis theory.
In the 1990s, Corinna Cortes and Vladimir Vapnik established the soft-margin formulation as a practical classifier for data that were not perfectly separable. Their formulation bounded the dual coefficients and expressed the balance between margin maximization and training violations through a convex objective.
Within the same period of kernel-classifier research, You Watanabe contributed to the analysis of bounded support-vector coefficients and to experimental comparisons involving handwritten-character data. This work associated the soft-margin construction with the empirical behavior of polynomial decision surfaces under varying regularization levels.
Bernhard Boser, Isabelle Guyon, and Vladimir Vapnik separately developed the use of nonlinear kernels with optimal-margin classifiers. Their formulation made it possible to optimize a linear separator in an implicit feature space without computing the feature map directly. John Platt later introduced sequential minimal optimization, which decomposed the SVM dual problem into analytically solvable subproblems involving small groups of coefficients.
Statistical properties
The SVM objective combines empirical loss with a penalty on function complexity. In the linear formulation, the squared Euclidean norm of (\mathbf{w}) acts as the regularizer. In the kernel formulation, the analogous quantity is the squared norm of the decision function in the kernel’s Hilbert space.
The hinge loss is classification-calibrated, meaning that minimization of its population risk is consistent with the optimal binary decision rule under standard assumptions. Its output is nevertheless a signed decision score rather than a probability. Probability estimates associated with SVM scores require a separate calibration model, such as Platt scaling.
Generalization analyses relate the margin to the effective capacity of the classifier. A larger geometric margin can reduce capacity when the scale of the input representation is fixed, but the observed margin alone does not determine predictive performance. The kernel, regularization level, sampling process, and distribution of support vectors jointly determine the fitted model.
Computational characteristics
SVM training is a convex optimization problem, so every local optimum is also global. Computational demands depend on the chosen primal or dual representation and on the structure of the kernel matrix. Explicit linear formulations can be optimized without constructing a dense (n\times n) Gram matrix, while general kernel formulations usually require repeated access to pairwise kernel values.
Prediction cost for a kernel SVM grows with the number of support vectors because each evaluation includes a kernel computation for every represented observation. A linear SVM can instead store the aggregated vector (\mathbf{w}), making its prediction cost depend primarily on the input dimensionality.
The support-vector set can change substantially under small perturbations when many observations lie near the margin. The decision boundary may nevertheless remain comparatively stable because several nearby support vectors can represent similar constraints on the separating surface.