support vector machine

Overview

A support vector machine (SVM) is a supervised machine learning model used for classification and regression analysis. It works by finding the optimal hyperplane that separates data points of different classes with the maximum margin, making it particularly effective for high-dimensional spaces. SVMs can handle both linear and non-linear problems through the use of kernel functions, which implicitly map input data into higher-dimensional feature spaces. The model is widely applied in pattern recognition, bioinformatics, and text categorization due to its robustness and theoretical foundation in statistical learning theory.

1 Core Concepts

1.1 Definition and Mathematical Formulation

A support vector machine is a binary linear classifier defined by a separating hyperplane. Given a set of training examples, each marked as belonging to one of two categories, an SVM training algorithm builds a model that assigns new examples to one category or the other. The mathematical formulation seeks to maximize the margin between the two classes while minimizing classification error. The decision function is expressed as \( f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b \), where \(\mathbf{w}\) is the weight vector and \(b\) is the bias.

1.2 Hyperplane and Margin

1.2.1 Separating Hyperplane

A separating hyperplane is a decision boundary that partitions the feature space into regions corresponding to different classes. In a \(d\)-dimensional space, the hyperplane is a \((d-1)\)-dimensional affine subspace. For linearly separable data, there exists a hyperplane that correctly separates all training points.

1.2.2 Maximum Margin Classifier

1.3 Support Vectors

1.3.1 Role in Determining the Decision Boundary

Support vectors are the training examples that lie closest to the decision boundary. They are the critical elements that define the hyperplane’s position and orientation. Removing other points does not change the decision boundary, but removing a support vector does.

1.3.2 Duality and Lagrange Multipliers

The SVM optimization problem is typically solved in its dual form, where the weight vector \(\mathbf{w}\) is expressed as a linear combination of support vectors: \(\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i\). The Lagrange multipliers \(\alpha_i\) are non-zero only for support vectors. This duality introduces the kernel trick and reduces the computational complexity.

2 Linear SVM

2.1 Hard-Margin SVM

2.1.1 Primal Formulation

2.1.2 Dual Formulation

The dual problem is: maximize \(L(\alpha) = \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j)\) subject to \(\sum_i \alpha_i y_i = 0\) and \(\alpha_i \geq 0\). The solution provides the Lagrange multipliers that define the support vectors.

2.1.3 Karush–Kuhn–Tucker (KKT) Conditions

The KKT conditions for optimality in SVM include: primal feasibility, dual feasibility, and complementary slackness. For each training point, the condition \(\alpha_i [y_i(\mathbf{w} \cdot \mathbf{x}_i + b) - 1] = 0\) must hold. This ensures that only points on the margin boundary have \(\alpha_i > 0\).

2.2 Soft-Margin SVM

2.2.1 Slack Variables

To handle non-separable data, slack variables \(\xi_i\) are introduced. They allow some points to lie on the wrong side of the margin or hyperplane. The constraint becomes \(y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i\), with \(\xi_i \geq 0\).

2.2.2 Regularization Parameter C

The parameter \(C\) controls the trade-off between maximizing the margin and minimizing the sum of slack variables. A larger \(C\) penalizes misclassifications more heavily, leading to a narrower margin. A smaller \(C\) allows more misclassifications but yields a wider margin.

2.2.3 Hinge Loss Function

3 Non-Linear SVM and Kernel Methods

3.1 The Kernel Trick

3.1.1 Feature Mapping

When data is not linearly separable in the original space, a mapping \(\phi(\mathbf{x})\) transforms the input into a higher-dimensional feature space where linear separation is possible. The decision function then becomes \(f(\mathbf{x}) = \mathbf{w} \cdot \phi(\mathbf{x}) + b\).

3.1.2 Inner Product in Higher Dimension

The kernel trick avoids explicit computation of \(\phi(\mathbf{x})\) by using a kernel function \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)\). The dual formulation only depends on inner products, so the kernel is substituted directly, enabling non-linear separation without increasing computational cost.

3.2 Common Kernel Functions

3.2.1 Polynomial Kernel

\(K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i \cdot \mathbf{x}_j + r)^d\), where \(d\) is the polynomial degree, \(\gamma\) a scaling parameter, and \(r\) a coefficient.

3.2.2 Radial Basis Function (RBF) Kernel

3.2.3 Sigmoid Kernel

\(K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i \cdot \mathbf{x}_j + r)\), resembling a two-layer neural network. It satisfies Mercer’s condition only for certain parameters.

3.3 Choosing a Kernel and Tuning Parameters

3.3.1 Cross-Validation Strategies

Cross-validation, particularly k-fold cross-validation, is used to evaluate kernel performance. The data is partitioned into folds; the model is trained on k-1 folds and tested on the remaining one. This process repeats, and average accuracy guides kernel selection.

3.3.2 Hyperparameter C and Gamma

For the RBF kernel, the main hyperparameters are \(C\) (regularization) and \(\gamma\) (kernel width). Grid search combined with cross-validation is standard: a logarithmic grid of values for both parameters is evaluated, and the combination yielding the best validation score is selected.

4 Extensions and Variants

4.1 Support Vector Regression (SVR)

4.1.1 Epsilon-Insensitive Loss

SVR extends SVM to regression by introducing an \(\epsilon\)-insensitive tube around the predictions. Points within the tube have zero loss, while those outside incur a loss linear in their distance to the tube boundary.

4.1.2 SVR Optimization

4.2 Multiclass SVM

4.2.1 One-vs-One (OvO)

OvO constructs \(k(k-1)/2\) binary SVMs for \(k\) classes, each trained to distinguish between a pair of classes. A new point is classified by majority vote among all classifiers.

4.2.2 One-vs-Rest (OvR)

OvR builds \(k\) binary SVMs, each separating one class from the rest. The class with the highest decision function value is assigned. OvR is simpler and scales linearly with \(k\), but can suffer from class imbalance.

4.3 One-Class SVM

4.3.1 Outlier Detection

One-class SVM learns a boundary that encloses the majority of training points. Points outside the boundary are considered outliers. It is trained only on normal data and is used in anomaly detection.

4.3.2 Novelty Detection

Similar to outlier detection but assumes the training data is free of outliers (novelty detection). The model identifies new points that differ significantly from the training distribution.

5 Training Algorithms

5.1 Sequential Minimal Optimization (SMO)

5.1.1 Decomposition Strategy

SMO breaks the large quadratic programming (QP) problem into a series of smallest possible subproblems, each involving only two Lagrange multipliers. It solves each subproblem analytically, avoiding numerical optimization.

5.1.2 Convergence Criteria

SMO iterates until the KKT conditions are satisfied for all points within a tolerance. Heuristics choose which two multipliers to optimize at each step to maximize progress.

5.2 Subgradient Methods

Subgradient methods optimize the primal SVM objective directly using gradient descent. They are simpler to implement and scale to large datasets, but converge more slowly than SMO.

5.3 Online and Large-Scale Learning

For massive datasets, online SVM variants (e.g., Pegasos, LASVM) process data in mini-batches or sequentially. These methods use stochastic gradient descent or incremental updates, enabling SVM training that scales linearly with the number of samples.

6 Applications

6.1 Text Classification and Spam Filtering

SVMs are highly effective for text classification due to high-dimensional feature spaces (e.g., bag-of-words). They achieve strong performance in spam filtering, topic categorization, and sentiment analysis.

6.2 Image Recognition

SVMs are used in image classification tasks such as object detection and face recognition. With features like histograms of oriented gradients (HOG) or deep learning representations, SVMs provide robust classifiers.

6.3 Bioinformatics and Genomics

Applications include protein fold recognition, gene expression classification, and drug discovery. SVMs handle the large number of features (e.g., microarray data) relative to sample size.

6.4 Handwriting Recognition

SVMs have been applied to digit and character recognition (e.g., the MNIST dataset). They perform well with pixel intensity features and are used in postal sorting and document processing.

7 Advantages and Limitations

7.1 Strengths

7.1.1 Effectiveness in High Dimensions

SVMs are well-suited for high-dimensional data because the margin maximization provides regularization, reducing overfitting even when the number of features exceeds the number of samples.

7.1.2 Memory Efficiency via Support Vectors

The decision boundary depends only on a subset of training points (support vectors), making the model memory-efficient after training. Predictions for new points are fast.

7.2 Weaknesses

7.2.1 Computational Complexity for Large Datasets

Training can be computationally intensive for datasets with many samples. Standard QP solvers have time complexity between \(O(n^2)\) and \(O(n^3)\), where \(n\) is the number of training points.

7.2.2 Sensitivity to Noisy Data and Parameter Selection

Performance degrades in the presence of overlapping classes or outliers. Choosing the right kernel and hyperparameters (particularly \(C\) and \(\gamma\)) often requires careful tuning via cross-validation and domain knowledge.