Support Vector Machine

A Support Vector Machine (SVM) is a supervised statistical learning model in computation and algorithms used for binary classification, multi-class categorization, and continuous function estimation (support vector regression). Grounded in the Structural Risk Minimization (SRM) framework developed by Soviet mathematicians Vladimir N. Vapnik and Alexey Ya. Chervonenkis beginning in 1963—and extended to nonlinear kernel spaces by Bernhard Boser, Isabelle Guyon, and Vapnik in 1992 and to non-separable soft-margin problems by Corinna Cortes and Vapnik in 1995—an SVM identifies the unique separating hyperplane that maximizes the geometric distance (margin) to the nearest training observations of any class. Because the decision boundary is determined only by the boundary-defining training points known as support vectors, support vector machines resist overfitting in high-dimensional spaces (p ≫ n), such as transcriptomic expression profiles, protein sequence homology classification, and neuroimaging analysis.

Separating Hyperplanes and the Geometric Margin

Consider a binary classification dataset of n labeled training examples {(x_i, y_i)}_i=1ⁿ, where each feature vector x_i ∈ R^p is paired with a class label y_i ∈ {−1, +1}. A linear classifier partitions R^p via an affine hyperplane defined by normal weight vector w ∈ R^p and scalar bias b ∈ R:

f(x) = w^Tx + b = 0, with predicted label ŷ = sign(w^Tx + b)

When the training set is linearly separable, the hard-margin SVM selects the hyperplane that maximizes the perpendicular Euclidean distance to the closest training examples. By rescaling w and b so that the canonical functional margin of the closest points satisfies y_i(w^Tx_i + b) = 1, the two parallel margin boundaries w^Tx + b = +1 and w^Tx + b = −1 are separated by a total geometric margin:

γ = 2 / ‖w‖₂

Maximizing γ = 2 / ‖w‖₂ is equivalent to minimizing the convex quadratic objective (1/2)‖w‖₂² subject to n linear inequality constraints:

min_{w, b} (1/2) ‖w‖₂², subject to y_i (w^Tx_i + b) ≥ 1 for all i = 1, ..., n

Cortes–Vapnik Soft-Margin Formulation and Hinge Loss

When class distributions overlap due to measurement noise, the hard-margin constraints become infeasible. Cortes and Vapnik (1995) introduced non-negative slack variables ξ_i ≥ 0 controlled by a regularization penalty C > 0:

min_{w, b, ξ} (1/2) ‖w‖₂² + C ∑_i=1ⁿ ξ_i, subject to y_i(w^Tx_i + b) ≥ 1 − ξ_i and ξ_i ≥ 0

Eliminating ξ_i = max(0, 1 − y_i(w^Tx_i + b)) shows that the soft-margin SVM solves an L₂-regularized empirical risk minimization problem under the hinge loss:

L_SVM(w, b) = (1/2) ‖w‖₂² + C ∑_i=1ⁿ max(0, 1 − y_i(w^Tx_i + b))

Large C penalizes slack violations heavily (narrow margin), whereas small C prioritizes a wide margin (small ‖w‖₂), contrasting with the smooth binomial log-likelihood penalty of Logistic Regression.

Lagrangian Duality and Complementary Slackness

Introducing Lagrange multipliers α_i ≥ 0 and μ_i ≥ 0 and setting the primal derivatives ∂L_P/∂w = 0, ∂L_P/∂b = 0, and ∂L_P/∂ξ_i = 0 yields the Karush–Kuhn–Tucker (KKT) stationarity conditions w = ∑_i=1ⁿ α_iy_ix_i, ∑_i=1ⁿ α_iy_i = 0, and 0 ≤ α_i ≤ C. Substituting these into the Lagrangian produces the Wolfe dual quadratic program:

max_α ∑_i=1ⁿ α_i − (1/2) ∑_i=1ⁿ ∑_j=1ⁿ α_i α_j y_i y_j (x_i^Tx_j), subject to 0 ≤ α_i ≤ C and ∑_i=1ⁿ α_i y_i = 0

John Platt's 1998 Sequential Minimal Optimization (SMO) algorithm solves this dual problem by analytically optimizing pairs of multipliers (α_i, α_j) at each iteration.

By KKT complementary slackness, α_i[y_i(w^Tx_i + b) − 1 + ξ_i] = 0 and (C − α_i)ξ_i = 0, partitioning the observations into three groups:

• Non-Support Vectors (α_i = 0): Points outside the margin slab (y_if(x_i) > 1); removing them leaves the hyperplane unchanged.
• Margin Support Vectors (0 < α_i < C): Points lying on the margin boundaries y_i(w^Tx_i + b) = 1 (ξ_i = 0).
• Bounded Support Vectors (α_i = C): Points violating the margin (ξ_i > 0).

Reproducing Kernel Hilbert Spaces (RKHS)

When class boundaries are nonlinear in R^p, Boser, Guyon, and Vapnik (1992) mapped inputs into a feature space H via Φ: R^p → H. Because both the dual objective and the prediction rule f(x) = ∑_i∈*SV* α_iy_i⟨Φ(x_i), Φ(x)⟩_H + b depend on the data only through inner products, coordinates of Φ(x) are never evaluated explicitly; instead, inner products are computed via a kernel function K(x_i, x_j) = ⟨Φ(x_i), Φ(x_j)⟩_H. By Mercer's Theorem (1909), a symmetric function K corresponds to an inner product in a Reproducing Kernel Hilbert Space (RKHS) if and only if its n × n Gram matrix K_ij = K(x_i, x_j) is positive semi-definite (c^TKc ≥ 0), ensuring a convex dual program.

Vapnik–Chervonenkis (VC) Dimension

The generalization capacity of an SVM is governed by the Vapnik–Chervonenkis (VC) dimension h_VC—the size of the largest point set that the classifier family can shatter (assign all 2^h_VC binary labelings). Vapnik proved that for data contained in a ball of radius R, canonical hyperplanes with margin γ have VC dimension bounded by:

h_VC ≤ min(⌈R² / γ²⌉, p) + 1 = min(⌈R² ‖w‖₂² / 4⌉, p) + 1

Minimizing ‖w‖₂² directly bounds h_VC independently of the ambient dimension of the RKHS—explaining why a Gaussian RBF SVM generalizes in an infinite-dimensional Hilbert space, alongside kernel Principal Component Analysis. For calibrated posterior probabilities P(y = +1 | x), Platt scaling fits a sigmoid 1 / [1 + exp(Af(x) + B)] to out-of-fold decision values, connecting maximum-margin classification to Bayesian Inference.

Why does an SVM only depend on support vectors rather than all training points?

The SVM hinge loss max(0, 1 − y_if(x_i)) is zero whenever y_if(x_i) > 1. By complementary slackness, any point outside the margin slab receives dual multiplier α_i = 0 and exerts zero pull on the decision boundary.

How do Support Vector Machines handle multi-class classification?

Multi-class problems with K > 2 classes are decomposed into binary subproblems using either One-vs-Rest (OvR) (K classifiers separating each class from the rest) or One-vs-One (OvO) (K(K − 1)/2 pairwise classifiers combined by majority vote).

When is a linear SVM preferred over a Gaussian RBF kernel SVM?

When the number of features p exceeds the sample size n (as in whole-genome SNP arrays or transcriptomics), data are typically linearly separable in the native space, allowing a linear SVM to train in O(np) time with accuracy comparable to an RBF kernel.

1. Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT), 144–152. https://doi.org/10.1145/130385.130401
2. Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. https://doi.org/10.1007/BF00994018
3. Vapnik, V. N. (1999). An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5), 988–999. https://doi.org/10.1109/72.788640
4. Schölkopf, B., Smola, A. J., Williamson, R. C., & Bartlett, P. L. (2000). New support vector algorithms. Neural Computation, 12(5), 1207–1245. https://doi.org/10.1162/089976600300015565
5. Leslie, C., Eskin, E., & Noble, W. S. (2002). The spectrum kernel: A string kernel for SVM protein classification. Pacific Symposium on Biocomputing, 7, 564–575. https://doi.org/10.1142/9789812799623_0053