A Comprehensive Guide to Support Vector Machines and Kernels

Support Vector Machines (SVMs) are a core machine learning technique that has stood the test of time. First developed in the 1990s, SVMs remain popular today due to their strong theoretical foundations, practical success across many domains, and appealing geometric intuition. In this guide, we‘ll thoroughly explore how SVMs work, with a particular emphasis on kernel functions that allow SVMs to tackle non-linear problems. We‘ll go beyond the basics to discuss theoretical and practical nuances, compare SVMs to other methods, and survey some current research directions.

The Maximum Margin Principle

The key idea behind SVMs is the maximum margin principle. Suppose we have a binary classification problem with classes that are linearly separable by some hyperplane. While many such separating hyperplanes may exist, the maximum margin hyperplane is the one that maximizes the minimum distance to the training examples. This hyperplane bisects the shortest line connecting the convex hulls of the two classes.

[Insert image illustrating linear separability and the maximum margin hyperplane]

Why seek the maximum margin? Intuitively, this hyperplane is the most "robust" separator – slight perturbations of the data points are least likely to change the classification. Theoretically, the margin is related to an upper bound on the expected generalization error. Thus, maximizing the margin can be seen as minimizing an estimate of the true risk.

Finding the maximum margin hyperplane leads to a constrained quadratic optimization problem:

$\min_{w,b} \frac{1}{2} ||w||^2$
subject to $y_i(w^Tx_i – b) \ge 1$ for $i=1,…,n$

Here, $w$ and $b$ define the separating hyperplane $w^Tx – b = 0$, and $y_i \in {-1, 1}$ are the class labels. The constraints enforce that each training point is correctly classified with a functional margin of at least 1. The objective aims to maximize the geometric margin $\frac{1}{||w||}$. This is a convex problem with a unique global solution.

Soft Margin SVMs and the C Hyperparameter

Real datasets are rarely perfectly linearly separable. Noise, outliers, and class overlap can make enforcing hard margin constraints problematic. Soft margin SVMs introduce slack variables $\xi_i$ to allow some points to violate the margin constraint:

$\min{w,b,\xi} \frac{1}{2} ||w||^2 + C \sum{i=1}^n \xi_i$
subject to $y_i(w^Tx_i – b) \ge 1 – \xi_i$ and $\xi_i \ge 0$ for $i=1,…,n$

The $C$ hyperparameter controls the tradeoff between maximizing the margin and minimizing the slack. Large $C$ heavily penalizes margin violations, leading to a narrower margin but more emphasis on classifying training points correctly. Small $C$ allows more margin violations, trading off training accuracy for a wider margin. $C$ can be selected by cross-validation.

Kernel Functions and the Kernel Trick

Linear SVMs are effective for many problems, but some datasets are fundamentally not linearly separable. The solution is to map the input data into a higher (possibly infinite) dimensional space, where a linear separator may exist. For example, a 2D dataset with concentric circular classes could be mapped to 3D where the circles become separable by a plane.

Explicitly computing such transformations could be computationally intractable. However, SVMs can use kernel functions to implicitly compute inner products in the higher dimensional space, without needing the explicit transformed coordinates. This kernel trick allows efficiently solving the SVM optimization problem in the high dimensional space.

A kernel function $K(x,y)$ is a positive semidefinite function that corresponds to an inner product $\langle\phi(x),\phi(y)\rangle$ in some transformed space. Common kernel functions include:

• Linear: $K(x,y) = x^Ty$
• Polynomial of degree $d$: $K(x,y) = (x^Ty + c)^d$
• Radial Basis Function (RBF) or Gaussian: $K(x,y) = \exp(-\gamma ||x-y||^2)$
• Sigmoid: $K(x,y) = \tanh(\gamma x^Ty + c)$

The polynomial kernel features all monomials up to degree $d$, allowing more flexible decision boundaries than the linear kernel. The RBF kernel maps to an infinite dimensional space, enabling highly non-linear boundaries. The $\gamma$ hyperparameter controls the kernel width. Small $\gamma$ leads to wide kernels and smoother decision boundaries, while large $\gamma$ yields compact kernels and more wiggly boundaries.

[Insert visualization comparing decision boundaries for different kernels]

Multiclass SVMs

SVMs are inherently binary classifiers, but multiclass problems can be handled via pairwise or one-vs-all coupling schemes. In pairwise coupling, an $N$ class problem is decomposed into $\binom{N}{2}$ binary subproblems, one for each pair of classes. A voting scheme then assigns the class with the most "wins" across subproblems. In one-vs-all, $N$ binary SVMs are trained, each treating one class as positive and the rest as negative. The class with the highest score function value is predicted.

More sophisticated multiclass SVM formulations optimize all class boundaries simultaneously while enforcing pairwise or one-vs-all margin constraints. These tend to improve on coupling approaches, at the cost of a larger, more complex optimization problem.

SVMs in Practice

SVMs have been successfully applied to a wide range of real-world problems, including:

• Text classification: SVMs with bag-of-words or more sophisticated NLP features achieve state-of-the-art results on tasks like sentiment analysis, spam filtering, and topic categorization. The high dimensionality and sparsity of text data play to the strengths of SVMs.

• Bioinformatics: SVMs are popular for tasks like protein function prediction, cancer classification from gene expression profiles, and DNA splice site detection. The ability to handle high-dimensional, noisy omics data is valuable.

• Computer vision: SVMs have been used for object detection, face recognition, image segmentation, and content-based image retrieval. Kernel SVMs can effectively capture complex visual patterns.

• Intrusion detection: SVMs have been used to detect network intrusions and malware based on system call sequences, network packet features, etc. The ability to learn a tight boundary around normal behavior makes SVMs suitable for anomaly detection.

Some practical tips for training SVMs:

• Scale input features to a common range (e.g. [0,1] or [-1,1]) to avoid features with larger numeric ranges dominating
• Use cross-validation to select hyperparameters C and kernel parameters
• Start with a linear SVM, and only move to kernels if necessary
• RBF kernel is a good general-purpose kernel to try first
• Primal formulation is more efficient for n >> d (many samples, low dimension), dual formulation for d >> n
• Several efficient implementations exist, including LIBSVM, LIBLINEAR, SVMLight, and scikit-learn

How do SVMs compare to other classifiers? Some general characteristics:

• Strengths:
  • Effective in high dimensional spaces
  • Still effective with unbalanced and nonlinearly separable datasets
  • Flexibility from different kernels
  • Robust against overfitting (especially with small C)
• Weaknesses:
  • Do not directly provide probability estimates
  • Not scalable to very large datasets
  • Sensitive to noise and overlapping classes
  • Require careful normalization and hyperparameter tuning

Empirically, SVMs often produce accuracies comparable to state-of-the-art neural networks, while being much less computationally intensive to train. They may be preferred when interpretability is important, since the support vectors represent key prototypical and boundary instances. Random forests or gradient boosted trees sometimes outperform SVMs, especially on very large, noisy datasets.

Research Extensions

SVMs have inspired many lines of research that extend or build upon the original formulation. Some notable examples:

• Transductive SVMs: Aim to leverage unlabeled data to improve performance on a specific test set, as opposed to an inductive SVM that learns a general decision function.

• Structured output SVMs: Learn functions that map inputs to structured outputs such as sequences, trees, or graphs. Involves optimizing over joint input-output feature spaces.

• Multiple kernel learning: Optimize both a linear combination of multiple kernels and the SVM model simultaneously. Allows automated selection and weighting of different kernels.

• Bayesian SVMs: Provide a probabilistic interpretation of SVMs by treating the weights as random variables with prior distributions. Allows estimating uncertainty in predictions.

• One-class SVMs: Learn a boundary around a single positive class, to detect anomalies or outliers. Useful when negative examples are unavailable or poorly defined.

• Least-squares SVMs: Reformulate the SVM problem as a set of linear equations, allowing very efficient training. Loses sparsity of the standard SVM solution.

• SVM+: Learns an additional set of virtual examples to help improve the margin of standard SVMs. Related to transductive and semi-supervised learning.

As machine learning continues to advance, it‘s likely that SVMs will continue to play an important theoretical and practical role, or inspire new approaches that combine their geometric insights with modern large-scale optimization and representation learning techniques.