Support Vector Machines

This page focuses on Support Vector Classification. Support Vector Regression is a related method. It is not derived here. One-class SVM is also outside the derivation.

A support vector classifier is a supervised binary learning machine. Training observations carry class labels. Cortes and Vapnik constructed a two-class decision function by finding an optimal separating hyperplane with a large margin, then extending the construction to non-separable training data and to kernel inner products. The classifier assigns a new observation according to the sign of a decision score. That score is not a probability.

The mathematical derivation uses labels $y_i\in \{-1,+1\}$. Software may accept arbitrary class labels. Those software labels are mapped internally. They are not the same object as the $\pm 1$ coding used in the margin equations.

The optimization taught below is C-support vector classification with an L1 slack penalty. That is the formulation implemented by scikit-learn SVC and used as the boxed dual in the Brereton and Lloyd tutorial. Cortes and Vapnik introduced the two-class maximum-margin machine, the canonical unit-margin constraints, slack variables, the penalty constant $C$, and kernel inner products. Their 1995 main-text dual for the non-separable case used a squared slack penalty. It is not the boxed L1 dual written in the Mathematics section.

Let $x_i\in {\mathbb{R}}^p$ be training predictors and $y_i\in \{-1,+1\}$ the corresponding labels, $i=1,\dots ,n$. A linear decision function is

$f(x)=w^{\mathsf{T}}x+b$.

The predicted label under the $\pm 1$ coding is $\hat{y}=\mathrm{sign}(f(x))$. The set $\{x:w^{\mathsf{T}}x+b=0\}$ is the separating hyperplane. The vector $w$ is its normal.

Canonical scaling of $w$ and $b$ makes correctly separated training observations satisfy

$y_i(w^{\mathsf{T}}{x}_i+b)\ge 1$ for all $i$. The $\pm 1$ labels collapse the two one-sided inequalities into that single product form. Cortes and Vapnik call the unique hyperplane that separates the training data with maximal margin the optimal hyperplane. Under that canonical scaling the full geometric margin, the distance between the two support hyperplanes $w^{\mathsf{T}}x+b=\pm 1$, is $2/\Vert w{\Vert }_2$. The distance from the decision hyperplane to either of those support hyperplanes is $1/\Vert w{\Vert }_2$. On this page, "margin" without qualification means that full width $2/\Vert w{\Vert }_2$.

For linearly separable data the hard-margin problem minimizes $\frac{1}{2}\Vert w{\Vert }_2^2$ subject to the canonical constraints $y_i(w^{\mathsf{T}}{x}_i+b)\ge 1$. Minimizing $\Vert w{\Vert }_2^2$ is equivalent to maximizing the full margin $2/\Vert w{\Vert }_2$. The quadratic form is the convex program used for computation.

The hard-margin constraints require a feasible separating solution. If any training observation violates the unit-margin inequality, the constraint set is empty. Real chemical data need not be linearly separable in the original predictors. That is a feasibility statement. It is not a claim that hard-margin SVM cannot be used whenever noise is present, nor that a kernel representation is automatically separable without cost.

Brereton and Lloyd describe hard-margin SVM as requiring a space in which the two classes are perfectly separable, equivalently an infinite value of $C$ in the soft-margin parameterization, so that misclassifications are not tolerated. With an RBF kernel a separating feature-space solution can always be forced. Forcing that solution can overfit. Soft-margin SVM is the usual practical formulation.

Slack variables ${\xi }_i\ge 0$ relax the unit-margin constraints to

$y_i(w^{\mathsf{T}}{x}_i+b)\ge 1-{\xi }_i$.

The C-SVC primal minimizes

$\frac{1}{2}\Vert w{\Vert }_2^2+C{\sum }_{i=1}^n{\xi }_i$

subject to those inequalities and ${\xi }_i\ge 0$. scikit-learn writes the same primal with feature map $\varphi$ in place of the original $x$. The penalty $C$ is strictly positive. It trades the squared-norm term on $w$ against the total slack. A larger $C$ weights slack more heavily relative to $\frac{1}{2}\Vert w{\Vert }_2^2$. A smaller $C$ weights the margin term more heavily. Those are statements about the objective. They are not laws that large $C$ always overfits or that small $C$ always underfits. Selection of $C$ belongs to validation. The software default $C=1$ in scikit-learn SVC and the MATLAB default box constraint of 1 are implementation defaults. They are not scientifically optimal values.

If ${\xi }_i=0$, observation $i$ satisfies the canonical unit-margin constraint. If ${\xi }_i>0$, it violates that constraint. scikit-learn describes ${\xi }_i$ as a distance from the correct margin boundary and states that a penalty is incurred when a sample is misclassified or lies within the margin. This page keeps that general reading. It does not publish geometric cases that split $0<{\xi }_i\le 1$ from ${\xi }_i>1$ as a separate theorem.

The same primal can be written with hinge loss $\max (0,1-y_{i}f(x_i))$ in place of explicit slack. scikit-learn records that equivalent regularized-loss form. The slack primal remains the page definition. Do not mix it with other regularizers such as $\lambda \Vert w{\Vert }_2^2$ without converting parameters.

After the dual problem is solved, the linear weight has the expansion $w={\sum }_{i=1}^n{\alpha }_i{y}_i{x}_i$. Only observations with ${\alpha }_i>0$ contribute. Those observations are the support vectors of the fitted solution. Numerical solvers return coefficients that are zero within a solver tolerance. The mathematical definition is a nonzero dual coefficient, not a software threshold.

For the hard-margin problem Cortes and Vapnik term support vectors the training points that meet $y_i(w^{\mathsf{T}}{x}_i+b)=1$. In the soft-margin C-SVC problem the support vectors are the observations with active dual coefficients. scikit-learn describes them as the samples that lie within the margin, because the dual coefficients vanish for the remaining samples. They are not defined merely as "the closest points to the hyperplane" in every soft-margin geometry.

The decision function therefore depends on a subset of the training set. That is a property of the dual expansion. It is not a claim that SVM is automatically immune to high dimensionality or to small-sample overfitting.

The dual objective depends on inner products $x_i^{\mathsf{T}}{x}_j$. A kernel replaces those products by $K(x_i,x_j)$. When $K$ is a valid kernel it equals an inner product $\varphi (x_i{)}^{\mathsf{T}}\varphi (x_j)$ in a feature space. The map $\varphi$ need not be formed explicitly. That is the computational content of the kernel representation. It is not the claim that every similarity function is a valid SVM kernel, and it is not the claim that a kernel "sends data to higher dimensions" as a physical operation.

Linear SVM uses a linear decision function in the original predictors. Kernel SVM can produce a nonlinear boundary in the input space while remaining linear in the feature space of $\varphi$. A nonlinear kernel is not automatically better. Kernel choice is a model-development decision and is evaluated by validation.

The linear kernel is $K(x,z)=x^{\mathsf{T}}z$. The RBF kernel taught here is

$K(x,z)=\exp (-\gamma \Vert x-z{\Vert }_2^2)$,

matching scikit-learn. The parameter $\gamma$ must be positive. Larger $\gamma$ makes the kernel decay faster with squared Euclidean distance. That is a statement about the kernel values. It is not a law that large $\gamma$ always overfits.

scikit-learn's polynomial kernel is

$K(x,z)=(\gamma x^{\mathsf{T}}z+r{)}^d$

with $\gamma$ from gamma, $r$ from coef0, and $d$ from degree. That parameterization is a scikit-learn convention. It is not the unique polynomial kernel used in all software. MATLAB documents $(1+x_j^{\mathsf{T}}{x}_k{)}^q$ for its polynomial kernel, after any KernelScale division of the predictors.

Equations 1 to 4 are the linear decision function and the canonical hard-margin geometry of Cortes and Vapnik. Equation 5 is the hard-margin objective constrained by Equation 3. Equations 6 and 7 are the C-SVC L1-slack primal implemented by scikit-learn SVC. scikit-learn writes the dual as a minimization of $\frac{1}{2}{\alpha }^{\mathsf{T}}Q\alpha -e^{\mathsf{T}}\alpha$. Equation 8 is the equivalent maximization, with the dual constraints in Equation 9. Equation 10 reconstructs $w$ in the original space when the kernel is linear. Equation 11 is the kernel decision function. Equation 12 is the RBF kernel.

The algorithm is the C-SVC workflow. It does not specify a numerical quadratic-programming solver. Sequential Minimal Optimization is an implementation technique used by some libraries. It is not taught here.

Scientific hyperparameters of this page are $C$, the kernel family, and the kernel parameters of that family. For RBF those kernel parameters reduce to $\gamma$. Polynomial kernels add degree and, in scikit-learn, coef0. Solver tolerances, cache size, and shrinking are implementation controls. They are not chemometric model choices in the same sense.

For RBF SVM both $C$ and $\gamma$ affect the fitted classifier. Tuning one while treating the other as universally optimal is not a complete model-development procedure. scikit-learn advises considering both and documents grid search over exponentially spaced values as one practical option. Grid search is not the only valid search.

Choose kernel, $C$, kernel parameters, preprocessing, and any PCA or wavelength selection inside validation. Do not use the final test set to pick them. If unbiased performance is required after tuning, use nested cross-validation or an untouched external test set. When comparing candidate settings, use the same cross-validation splits where practical. See Cross-Validation.

SVM algorithms are not scale invariant. Inner products and RBF distances change if predictor units change. scikit-learn therefore recommends scaling, for example to mean 0 and variance 1, and applying the same transform to new data through a Pipeline. That is not a claim that autoscaling is universally required for spectra. Spectroscopic preprocessing can be scientifically specific. If scaling parameters are estimated from data, estimate them on the training fold only. The same rule applies to PCA and to feature selection. See Normalization & Scaling.

scikit-learn's default gamma="scale" uses $1/(p\cdot \mathrm{Var}(X))$, where $p$ is the number of features. That expression is a software heuristic. It is not a chemometric recommendation. The alternative gamma="auto" uses $1/p$.

The primary SVM formulation is binary. Multiclass classification requires a strategy that combines binary machines, or a different multiclass formulation. The binary optimization equations do not become multiclass by rewriting the labels alone.

scikit-learn SVC trains multiclass problems by one-versus-one: $K(K-1)/2$ binary classifiers for $K$ classes. The constructor argument decision_function_shape does not change that training strategy. The default "ovr" transforms the returned decision function to shape (n_samples, n_classes). Setting "ovo" returns the original one-versus-one scores of shape (n_samples, K(K-1)/2). An ovr-shaped decision function is not evidence that the underlying libsvm training was one-versus-rest. LinearSVC is a different implementation. It uses liblinear, squared-hinge loss by default, and a one-versus-rest multiclass strategy. This page uses SVC(kernel="linear") for linear C-SVC.

MATLAB fitcsvm trains one-class or two-class SVM. It is not a multiclass trainer. Multiclass SVM in MATLAB uses fitcecoc. For in-memory data the documented default is $K(K-1)/2$ binary SVM learners with one-versus-one coding. A templateSVM sets kernel, box constraint, and standardization for those binary learners.

SVM decision scores are not automatically probabilities. scikit-learn decision_function returns scores. Setting probability=True in sklearn 1.6 enables Platt scaling through an additional five-fold cross-validation on the training data. That procedure is computationally extra. The documentation states that predict and the argmax of predict_proba can disagree. If scores are enough, keep probability=False and use decision_function. Those scores can enter ROC and AUROC on the Classification Metrics page. They remain scores, not posterior probabilities.

Brereton and Lloyd review SVM as a learning-machine approach to classification and regression in chemometrics. This page uses that review for classification. Their experimental illustrations include mass spectrometry of environmental samples, near-infrared analysis of food, thermal analysis of polymers, and UV/visible spectra of polycyclic aromatic hydrocarbons. In those illustrations they sometimes project onto principal components for display. They state that they do not advocate PCA as a required prelude to classification. High-dimensional chemical data have been classified with SVM. That history does not make SVM immune to the curse of dimensionality, and it does not remove the need for validation.

Devos, Ruckebusch, Durand, Duponchel, and Huvenne treat SVM for NIR classification with explicit attention to meta-parameter optimization and to interpretation of support vectors. They note that regularization and kernel parameters must be optimized to control overfitting and boundary complexity, and that SVM is often treated as a black box when those steps are omitted. Their practical response is a grid search that watches classification error and the number of support vectors. Those are NIR-specific modelling recommendations from that paper. They are not a claim that one grid is optimal for every spectrum.

Relative to LDA, SVM does not use a shared-covariance Gaussian class model. It uses a maximum-margin decision function. That is a different inductive structure, not an assumption-free method. Relative to k-NN, SVM learns a global decision function determined by support vectors rather than predicting from local neighbor labels. Relative to PLS-DA, SVM is not a latent-variable method. Relative to SIMCA, ordinary SVM classification is discriminant. It does not provide independent class-acceptance regions of the SIMCA type. None of these comparisons identifies a universally better classifier.

The first Python listing implements the verified kernel formulas and the dual decision score $f(x)={\sum }_i(y_i{\alpha }_i)K(x_i,x)+b$. It does not solve the quadratic program. Production classification uses scikit-learn SVC. Linear examples use SVC(kernel="linear"). Numeric $C$ and $\gamma$ in the sklearn listing are illustrative. scikit-learn stores $y_i{\alpha }_i$ in dual_coef_. Binary predict follows the sign of decision_function with the positive side corresponding to classes_[1].

MATLAB binary training uses fitcsvm. The two-class default kernel is linear. The penalty analog is BoxConstraint. For RBF, MATLAB divides predictors by KernelScale and then uses $G(x_j,x_k)=\exp (-\Vert x_j-x_k{\Vert }_2^2)$. If that scale factor is $\sigma$, the resulting RBF equals the sklearn form with $\gamma =1/{\sigma }^2$ on the same unscaled matrix. The two software parameters are not the same quantity. Do not set MATLAB KernelScale equal to sklearn gamma. MATLAB Standardize centers and scales each predictor by a weighted column mean and standard deviation. That is not claimed to be numerically identical to sklearn StandardScaler. Multiclass MATLAB examples use templateSVM with fitcecoc. sklearn and MATLAB fitted models need not match unless kernel, penalty, scale parameterization, preprocessing, and solver are aligned.

import numpy as np  def _validate_matrix(X):    X = np.asarray(X, dtype=float)    if X.ndim != 2:        raise ValueError("X must be a 2D array of samples by variables.")    if min(X.shape) == 0:        raise ValueError("X must have at least one row and one column.")    if not np.all(np.isfinite(X)):        raise ValueError("X must contain only finite values.")    return X  def encode_binary_pm1(y, positive_label=None):    y = np.asarray(y).reshape(-1)    labels = np.unique(y)    if labels.shape[0] != 2:        raise ValueError("Binary encoding requires exactly two class labels.")    if positive_label is None:        positive = labels[-1]    else:        positive = positive_label        if positive not in labels:            raise ValueError("positive_label must be one of the two class labels.")    y_pm1 = np.where(y == positive, 1.0, -1.0)    return y_pm1, labels, positive  def pairwise_sqeuclidean(X, Z):    X = _validate_matrix(X)    Z = _validate_matrix(Z)    if X.shape[1] != Z.shape[1]:        raise ValueError("X and Z must have the same number of variables.")    xx = np.sum(X ** 2, axis=1)[:, None]    zz = np.sum(Z ** 2, axis=1)[None, :]    return np.maximum(xx + zz - 2.0 * (X @ Z.T), 0.0)  def linear_kernel(X, Z):    X = _validate_matrix(X)    Z = _validate_matrix(Z)    if X.shape[1] != Z.shape[1]:        raise ValueError("X and Z must have the same number of variables.")    return X @ Z.T  def polynomial_kernel_sklearn(X, Z, gamma, coef0, degree):    gamma = float(gamma)    coef0 = float(coef0)    degree = int(degree)    if degree < 0:        raise ValueError("degree must be a non-negative integer.")    return (gamma * linear_kernel(X, Z) + coef0) ** degree  def rbf_kernel(X, Z, gamma):    gamma = float(gamma)    if gamma <= 0:        raise ValueError("gamma must be positive.")    return np.exp(-gamma * pairwise_sqeuclidean(X, Z))  def rbf_kernel_matlab_scale(X, Z, kernel_scale):    sigma = float(kernel_scale)    if sigma <= 0:        raise ValueError("kernel_scale must be positive.")    return rbf_kernel(X, Z, 1.0 / (sigma ** 2))  def kernel_decision_scores(K, dual_coef, intercept):    K = np.asarray(K, dtype=float)    dual_coef = np.asarray(dual_coef, dtype=float).reshape(-1)    if K.ndim != 2:        raise ValueError("K must be a 2D array of queries by support vectors.")    if K.shape[1] != dual_coef.shape[0]:        raise ValueError("K must have one column per dual coefficient.")    return K @ dual_coef + float(intercept)  def predict_from_scores(scores, negative_label, positive_label):    scores = np.asarray(scores, dtype=float).reshape(-1)    return np.where(scores >= 0.0, positive_label, negative_label) 

1. 1.

   Cortes, C., & Vapnik, V. (1995). Support-Vector Networks. Machine Learning, 20, 273-297.

   doi:10.1007/BF00994018
2. 2.

   Brereton, R. G., & Lloyd, G. R. (2010). Support Vector Machines for classification and regression. Analyst, 135, 230-267.

   doi:10.1039/B918972F
3. 3.

   Devos, O., Ruckebusch, C., Durand, A., Duponchel, L., & Huvenne, J.-P. (2009). Support vector machines (SVM) in near infrared (NIR) spectroscopy: Focus on parameters optimization and model interpretation. Chemometrics and Intelligent Laboratory Systems, 96(1), 27-33.

   doi:10.1016/j.chemolab.2008.11.005
4. 4.

   scikit-learn Developers (n.d.). SVC and Support Vector Machines user guide, including kernel functions and C-SVC mathematical formulation. scikit-learn 1.6 documentation.

5. 5.

   The MathWorks, Inc. (n.d.). fitcsvm, ClassificationSVM, predict, templateSVM, fitcecoc, and ClassificationECOC. MATLAB documentation.