Support vector machine · aiwiki.page

A support vector machine (SVM) is a family of machine learning models used principally for supervised learning. Its best-known form classifies observations by constructing a decision boundary with a large margin between classes, while permitting controlled violations of that margin. SVMs can produce linear boundaries or nonlinear ones through a kernel method. Related formulations estimate continuous values or identify unusual observations. The name refers to the training examples, called support vectors, that determine the fitted decision function. (scikit-learn.org)

Historical development

SVMs developed from research on optimal separating hyperplanes and statistical learning theory. In 1992, Bernhard Boser, Isabelle Guyon, and Vladimir Vapnik introduced a training approach combining optimal-margin classification with nonlinear kernels. Corinna Cortes and Vapnik’s 1995 paper, Support-vector networks, extended the approach to nonseparable training data, establishing the soft-margin formulation. This extension allowed some examples to violate the separation constraints rather than requiring perfect classification of every training observation. (homepages.math.uic.edu)

Computational advances helped make these models practical. John Platt’s 1998 sequential minimal optimization (SMO) algorithm divided the large optimization problem into small subproblems that could be solved analytically. Software libraries subsequently implemented classification, regression, multiclass strategies, and probability estimation within a common framework. (microsoft.com)

Maximum-margin classification

For binary classification, observations are represented by feature vectors $x_i$ , with labels $y_i\in\{-1,+1\}$ . A linear classifier uses

f(x)=w^\top x+b,

and predicts a class from its sign. The boundary $f(x)=0$ is a hyperplane in the input vector space. Here, $w$ determines its orientation and $b$ its offset. (homepages.math.uic.edu)

When linear separability holds, the hard-margin SVM solves

\min_{w,b}\frac12\|w\|^2 \quad\text{subject to}\quad y_i(w^\top x_i+b)\geq1.

Under this normalization, the two margin planes lie at scores $+1$ and $-1$ , and their separation is $2/\|w\|$ . Minimizing the weight norm therefore maximizes the margin. Support vectors have nonzero coefficients in the dual representation; in the hard-margin case, they lie on the margin planes. (homepages.math.uic.edu)

Soft margins and regularization

Real datasets may contain overlapping classes or mislabeled observations. The soft-margin formulation introduces nonnegative slack variables $\xi_i$ :

\min_{w,b,\xi}\frac12\|w\|^2+C\sum_i\xi_i,

subject to

y_i(w^\top x_i+b)\geq1-\xi_i.

A slack value between zero and one permits a correctly classified observation inside the margin; a value greater than one corresponds to misclassification. The parameter $C>0$ controls the penalty for violations relative to the weight-norm penalty. (csie.ntu.edu.tw)

Equivalently, the objective combines regularization with the hinge loss, $\max(0,1-y_if(x_i))$ . Larger $C$ emphasizes reducing training violations; smaller $C$ gives relatively greater weight to a smaller weight norm. This trade-off influences generalization, but does not guarantee that larger margins always yield better predictions on unseen data. Kernel choice and regularization remain important in controlling overfitting. (scikit-learn.org)

Kernels and nonlinear boundaries

A kernel evaluates an inner product in a transformed feature space:

K(x,z)=\langle\phi(x),\phi(z)\rangle.

The kernel trick allows this calculation without explicitly constructing the potentially enormous feature vectors $\phi(x)$ . The classifier can then be written as

f(x)=\sum_{i\in S}\alpha_i y_iK(x_i,x)+b,

where $S$ contains the support vectors. A hyperplane in the transformed space can correspond to a curved boundary in the original input space. (homepages.math.uic.edu)

Common kernels include the linear inner product, polynomial kernels, and the Gaussian radial basis function

K(x,z)=\exp(-\gamma\|x-z\|^2).

The latter depends on squared Euclidean distance. Its parameter $\gamma$ controls how rapidly similarity decreases with distance: larger values produce more localized influence. Standard kernel-SVM optimization assumes an appropriate positive-semidefinite kernel, preserving the convex optimization structure of the training problem. (csie.ntu.edu.tw)

Regression and other extensions

Support vector regression (SVR) adapts the framework to continuous targets. In the common $\varepsilon$ -SVR formulation, deviations within an $\varepsilon$ -wide tolerance around the prediction incur no data-fit penalty. Deviations beyond this tolerance are penalized, while regularization controls the fitted function’s complexity. Unlike linear regression fitted by least squares, this formulation does not penalize every residual quadratically. (i2pc.es)

Multiclass classification commonly combines binary models. One-versus-rest trains a model for each class against all others; one-versus-one trains models for class pairs and combines their decisions. One-class SVMs address anomaly detection by estimating a boundary around a reference distribution rather than separating two labeled classes. These extensions use related optimization machinery but solve distinct learning tasks. (scikit-learn.org)

Computation and model evaluation

Training a kernel SVM generally involves a quadratic programming problem. SMO and related decomposition methods update small groups of variables while retaining the larger problem’s constraints. Kernel caching reduces repeated computations, but nonlinear training can still become expensive as the number of observations grows. Dedicated linear solvers can avoid constructing a full pairwise kernel matrix and scale more readily to large datasets. (microsoft.com)

SVM behavior depends strongly on feature representation, feature scaling, and hyperparameters such as $C$ and $\gamma$ . Cross-validation is commonly used to compare settings. Feature scales matter because both distances and weight penalties depend on the numerical units of the inputs. (scikit-learn.org)

The raw decision score is not a class probability. Probability estimates require an additional calibration procedure, such as fitting logistic regression to the scores, known as Platt scaling. Kernel prediction costs also depend on the number of support vectors: a model retaining many training examples may require substantial storage and computation for each new observation. (scikit-learn.org)