Support vector machines: maximum-margin classifiers and kernels
Support vector machines (SVMs) are supervised learning models that separate classes by the hyperplane with the largest margin. Kernel functions allow SVMs to handle non-linear data by implicitly mapping inputs to higher-dimensional spaces. The closest training points, called support vectors, determine the decision boundary.
Maximum-margin separation
A support vector machine finds a hyperplane that separates classes with the largest margin, as described in Cornell's lecture notes on support vector machines. The margin is the distance to the closest points from either class, and these points are called support vectors because they determine the maximal margin. The hyperplane is chosen to maximize that margin, ensuring good generalization to new data.
The optimal hyperplane is found by solving a constrained optimization problem: minimize the squared norm of the weight vector while keeping every training point on the correct side of the hyperplane. This is a quadratic program with linear constraints, and it has a unique solution when a separating hyperplane exists. In practice, the decision function is a linear mapping of the input features, similar to the score function described in Stanford's CS231n notes on linear classification, where a linear classifier computes f(x) = Wx + b.
Hard and soft margins
Soft-margin classification introduces slack variables to tolerate some errors, and a hyperparameter C balances margin width against misclassification. A larger C narrows the margin to reduce errors, while a smaller C widens the margin and allows more misclassification, as described in IBM's article on support vector machines. Nonlinear SVMs use kernel functions, such as polynomial, radial basis function, and sigmoid, to project data into a higher-dimensional space for linear separation.
Hard-margin classification is used when data are perfectly separable, but it is sensitive to outliers. In practice, soft-margin SVMs are more common because real data are rarely perfectly separable. The choice of kernel and C typically requires cross-validation to find a good balance.
Kernels and the kernel trick
To handle non-linear boundaries, one can explicitly transform input features into a higher-dimensional space via a basis function, but this becomes computationally expensive because the dimensionality grows quickly. The kernel trick avoids computing the transformed vectors directly. Instead, it replaces dot products in the original space with a kernel function that computes inner products in the high-dimensional space, as shown in Cornell's lecture notes on kernels.
Because support vector machines can be expressed entirely in terms of inner products between training samples, the kernel trick allows the model to learn in the high-dimensional space without ever computing the full mapping. This makes the computation efficient even when the transformed space is very large. The choice of kernel, such as linear, polynomial, RBF, or sigmoid, depends on the data characteristics and the specific task.
Practical considerations
Scikit-learn's guide to support vector machines explains that SVC and NuSVC implement one-versus-one multi-class classification, while LinearSVC uses one-versus-rest, and that advantages include effectiveness in high-dimensional spaces, memory efficiency through support vectors, and custom kernel flexibility; disadvantages include the need for careful kernel and regularization tuning and the cost of probability estimates via five-fold cross-validation.
Model performance is often measured by accuracy, which the Google Machine Learning Glossary defines as the number of correct predictions divided by the total number of predictions. For classification tasks, accuracy is a common metric, though it can be misleading on class-imbalanced datasets, as the glossary notes.
| Type | Use case | Approach |
|---|---|---|
| Linear SVM | Linearly separable data | Finds maximum margin hyperplane without transformation |
| Nonlinear SVM | Data not linearly separable | Applies kernel functions to map data to higher-dimensional space |
| Support vector regression (SVR) | Regression with continuous outcomes | Finds hyperplane with maximum margin for continuous prediction |
Frequently asked questions
What is a support vector machine?
A support vector machine is a supervised learning algorithm that finds a hyperplane to separate classes by maximizing the margin between the closest points of each class.
What are support vectors?
Support vectors are the training data points closest to the hyperplane; they define the margin and the decision boundary.
What is the kernel trick?
The kernel trick computes dot products in a high-dimensional feature space without explicitly transforming the input vectors, enabling linear separation of non-linear data efficiently.
How does soft-margin classification work?
Soft-margin classification uses slack variables to allow some misclassification and a parameter C to balance margin width against errors.
How does an SVM handle multi-class classification?
SVMs can use one-versus-one or one-versus-rest strategies; scikit-learn's SVC uses one-vs-one while LinearSVC uses one-vs-rest.