A support vector machine (SVM) is a supervised machine learning model used for classification, regression, and outlier detection. It works by finding a hyperplane that best separates data into classes in a high-dimensional space, maximizing the margin between the closest points (support vectors) of each class. SVMs are particularly effective for binary classification and can handle non‑linear decision boundaries through the kernel trick, making them a fundamental tool in information technology and statistical learning theory.
1 Mathematical formulation
The mathematical foundation of SVMs rests on constructing an optimal separating hyperplane that maximizes the margin between classes, often in a transformed feature space.
1.1 Linear SVM
In the linear case, the decision boundary is a hyperplane defined by \(\mathbf{w} \cdot \mathbf{x} + b = 0\), where \(\mathbf{w}\) is the normal vector and \(b\) is the bias. The goal is to maximize the margin, the distance between the hyperplane and the nearest points of either class.
1.1.1 Hard‑margin classification
Hard‑margin SVM assumes the data are perfectly linearly separable. The constraints are \(y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \ge 1\) for all \(i\), where \(y_i \in \{-1, +1\}\). The margin is \(\frac{2}{\|\mathbf{w}\|}\), so maximizing it is equivalent to minimizing \(\frac{1}{2}\|\mathbf{w}\|^2\) subject to those constraints. This is a convex quadratic optimization problem with a unique global minimum.
1.1.2 Soft‑margin classification (slack variables)
Real‑world data are rarely perfectly separable. Soft‑margin SVM introduces slack variables \(\xi_i \ge 0\) that allow some points to lie within the margin or on the wrong side. The objective becomes \(\frac{1}{2}\|\mathbf{w}\|^2 + C \sum_i \xi_i\), with constraints \(y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \ge 1 - \xi_i\). The parameter \(C\) controls the trade‑off between margin width and misclassification penalty.
1.2 Non‑linear SVM and the kernel trick
When data are not linearly separable in the input space, SVMs project the data into a higher‑dimensional feature space via a mapping \(\phi(\mathbf{x})\). The kernel trick allows the dot product \(\phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)\) to be computed implicitly using a kernel function \(K(\mathbf{x}_i, \mathbf{x}_j)\), avoiding explicit construction of the high‑dimensional space.
1.2.1 Kernel functions
A kernel function must be symmetric and positive semi‑definite (Mercer’s condition). Common choices allow SVMs to model a wide variety of decision boundaries.
1.2.1.1 Polynomial kernel
\(K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j + r)^d\) where \(d\) is the degree and \(r\) is a coefficient. This kernel creates polynomial decision boundaries of degree \(d\).
1.2.1.2 Radial basis function (RBF) kernel
\(K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)\) with \(\gamma > 0\). The RBF kernel maps data into an infinite‑dimensional space and is a default choice for many applications because of its flexibility.
1.2.1.3 Sigmoid kernel
\(K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\kappa \mathbf{x}_i \cdot \mathbf{x}_j + \theta)\) for parameters \(\kappa\) and \(\theta\). This kernel mimics the activation of a neural network, but it is not positive semi‑definite for all parameter values.
1.3 Dual formulation
Solving the SVM primal problem (with or without kernels) is often more efficient via its dual. The dual optimization problem is a quadratic program: maximize \(\sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j K(\mathbf{x}_i, \mathbf{x}_j)\) subject to \(\sum_i \alpha_i y_i = 0\) and \(0 \le \alpha_i \le C\). The support vectors are those examples with \(\alpha_i > 0\) (or \(\alpha_i = C\) for soft‑margin). The decision function becomes \(f(\mathbf{x}) = \sum_i \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b\).
2 Optimization and algorithms
Solving the SVM dual requires specialized optimization methods due to its quadratic programming nature and large‑scale dataset demands.
2.1 Quadratic programming formulation
The dual problem is a convex quadratic program (QP) with a dense Hessian matrix of size equal to the number of training examples. Standard QP solvers (e.g., interior‑point methods) are impractical for more than a few thousand points, motivating more efficient algorithms.
2.2 Sequential minimal optimization (SMO)
SMO breaks the QP into a series of smallest possible sub‑problems, each involving only two Lagrange multipliers. By solving these analytically and updating the multipliers sequentially, SMO avoids large matrix operations. It is the core algorithm used in many SVM implementations, such as LIBSVM.
2.3 Subgradient methods
For very large datasets, stochastic subgradient methods approximate the SVM objective (e.g., the primal soft‑margin problem) by updating the weight vector incrementally. Pegasos (Primal Estimated sub‑GrAdient SOlver for SVM) is a notable example that processes one sample per iteration and converges quickly to a good solution, especially when a moderate accuracy is acceptable.
3 Applications
SVMs have been successfully applied across many domains, especially where clear class boundaries and moderate dataset sizes are present.
3.1 Image classification
SVMs are used for object recognition, scene classification, and face detection. With features such as histograms of oriented gradients (HOG) or scale‑invariant feature transforms (SIFT), the SVM can learn high‑level patterns. In the early 2000s, SVMs were state‑of‑the‑art for several image classification benchmarks.
3.2 Text categorization
SVM text classifiers, often with bag‑of‑words or TF‑IDF features, are highly effective for tasks like spam detection, sentiment analysis, and document categorization. The linear kernel is commonly used because text data have many features and are often approximately linearly separable.
3.3 Bioinformatics (e.g., protein fold recognition)
SVMs are applied to classify biological sequences and structures. For protein fold recognition, SVMs use features derived from amino acid composition or evolutionary profiles. They have also been used for cancer classification from gene expression data and for detecting splice sites in DNA.
3.4 Handwriting recognition
SVMs have been employed to recognize handwritten digits and characters, most famously on the MNIST dataset. With RBF kernels, SVMs achieve high accuracy and have been used in postal sorting and bank check reading systems.
4 Extensions and variants
The basic SVM framework has been extended to handle a broader range of tasks and data types.
4.1 Support vector regression (SVR)
SVR adapts the SVM principle to regression. Instead of a classification margin, SVR defines an \(\epsilon\)-insensitive tube around the true values: errors within \(\epsilon\) are ignored, and a penalty is incurred only for points outside the tube. The dual formulation is analogous, using a kernel to model non‑linear relationships.
4.2 Multiclass SVM (one‑vs‑one, one‑vs‑rest)
SVMs are inherently binary classifiers. For \(K\) classes, two common decomposition strategies exist. One‑vs‑rest trains \(K\) SVMs, each separating one class from the rest. One‑vs‑one trains \(\binom{K}{2}\) SVMs, one for every pair of classes, and uses majority voting. The one‑vs‑one approach is more popular because it reduces class imbalance and is easier to calibrate.
4.3 ν‑SVM and ν‑SVR
The ν‑SVM variant replaces the penalty parameter \(C\) with a parameter \(\nu \in (0,1]\) that controls the number of support vectors and margin errors. In classification, ν‑SVM ensures that at most a fraction \(\nu\) of training examples are margin errors and at least a fraction \(\nu\) are support vectors. ν‑SVR similarly bounds the fraction of points outside the \(\epsilon\)-tube.
4.4 Structured SVM
Structured SVMs (SSVMs) extend SVMs to predict complex outputs such as sequences, trees, or graphs. They use a joint feature map over inputs and outputs and learn a discriminative function via a margin‑based objective. SSVMs are applied in natural language processing (e.g., parsing, named entity recognition) and computer vision (e.g., object detection with structured labels).
5 Limitations and practical considerations
Despite their strong theoretical foundation, SVMs have several limitations in practical use.
5.1 Scalability with large datasets
Classical SVM training scales between \(O(n^2)\) and \(O(n^3)\) with the number of examples \(n\), making it challenging for datasets with millions of points. While algorithms like SMO and stochastic methods alleviate this, deep neural networks often outpace SVMs in ultra‑large‑scale settings.
5.2 Choice of kernel and hyperparameters
Performance heavily depends on selecting the right kernel function and tuning its parameters (e.g., \(\gamma\) for RBF, degree for polynomial) as well as the regularization \(C\) (or \(\nu\)). Improper choice leads to overfitting or underfitting. Grid search or random search with cross‑validation is typically required, which can be computationally expensive.
5.3 Interpretability vs. performance
SVMs produce decision boundaries that are often not directly interpretable, especially with non‑linear kernels. The weight vector has no intuitive meaning in the feature space, and the support vectors may be numerous. For high‑stakes applications requiring explainable decisions, tree‑based models or linear models with sparse features are often preferred.
6 Related concepts
Several theoretical and mathematical concepts underpin the SVM framework.
6.1 Maximum margin hyperplane
The maximum margin hyperplane is the decision boundary that maximizes the distance to the nearest training point of any class. This geometric intuition is central to SVM: a larger margin reduces the VC dimension and improves generalization.
6.2 Reproducing kernel Hilbert space (RKHS)
A kernel corresponds to an inner product in a Hilbert space of functions, called the reproducing kernel Hilbert space (RKHS). The solution to the SVM lives in this RKHS, and the representer theorem ensures that the optimal function can be expressed as a linear combination of kernel evaluations on training points.
6.3 Vapnik–Chervonenkis (VC) dimension
The VC dimension measures the capacity of a classifier. For SVMs, the margin directly bounds the VC dimension: a large margin reduces the effective capacity, leading to better generalization. This connection provides a theoretical justification for the SVM’s strong out‑of‑sample performance.