Support Vector Machines (SVM)

Vladimir Vapnik & Alexey Chervonenkis

The story of Support Vector Machines begins in the 1960s in the Soviet Union, where Vladimir Vapnik and Alexey Chervonenkis were developing the mathematical foundations of statistical learning theory. Their work addressed a fundamental question: how can a learning algorithm generalize well from a finite training set to unseen data?

In 1963, Vapnik and Chervonenkis proposed the original linear classifier that would evolve into the modern SVM. Their key insight was that among all possible decision boundaries that separate two classes, the one with the maximum margin -- the greatest distance to the nearest training points -- would generalize best to new data.

VC Dimension and Structural Risk Minimization

Vapnik and Chervonenkis introduced the concept of VC dimension (Vapnik-Chervonenkis dimension), a measure of the capacity or complexity of a family of classifiers. A model with high VC dimension can fit more complex patterns but is also more prone to overfitting. This led to the principle of Structural Risk Minimization (SRM):

Instead of simply minimizing the training error, SRM seeks a balance between training accuracy and model complexity. The SVM embodies this principle perfectly -- by maximizing the margin, it implicitly controls model complexity and achieves better generalization bounds.

Where \( R(\alpha) \) is the true risk, \( R_{\text{emp}}(\alpha) \) is the empirical risk, \( h \) is the VC dimension, \( n \) is the number of training samples, and \( \eta \) is a confidence parameter.

The Evolution of SVMs

From a theoretical curiosity to one of the most widely used classifiers in machine learning, SVMs have had a remarkable journey:

The Maximum Margin Classifier

Imagine you have two groups of points on a 2D plane -- red and blue. There are infinitely many lines that can separate them. Which line should you choose? The SVM answers: choose the line that maximizes the margin -- the distance between the decision boundary and the nearest data points from either class.

Think of it as building the widest possible road between two territories. The wider the road, the more confident you are that new points falling on either side truly belong to that territory. Points that are far from the boundary are easy to classify; it is the points near the boundary that matter most.

Why Maximum Margin Works

The Geometry of the Decision Boundary

The SVM defines a hyperplane in the feature space that separates the two classes. In 2D, this hyperplane is a line; in 3D, it is a plane; in higher dimensions, it is a hyperplane. The hyperplane is defined by:

Where \( \mathbf{w} \) is the weight vector (normal to the hyperplane), \( \mathbf{x} \) is the input feature vector, and \( b \) is the bias term. Points on one side of the hyperplane satisfy \( \mathbf{w} \cdot \mathbf{x} + b > 0 \) and belong to class +1; points on the other side satisfy \( \mathbf{w} \cdot \mathbf{x} + b < 0 \) and belong to class -1.

Interactive SVM Decision Boundary

Adjust the weights and bias to see how the hyperplane and its margin change. The dashed lines show the margin boundaries where support vectors lie.

Distance from a Point to the Hyperplane

The distance from a point \( \mathbf{x}_i \) to the hyperplane \( \mathbf{w} \cdot \mathbf{x} + b = 0 \) is given by:

For correctly classified points with labels \( y_i \in \{-1, +1\} \), we can write:

The margin is defined as twice the distance from the hyperplane to the nearest point. If we scale \( \mathbf{w} \) and \( b \) so that the nearest points satisfy \( y_i(\mathbf{w} \cdot \mathbf{x}_i + b) = 1 \), then:

The Primal Optimization Problem

Maximizing the margin \( \frac{2}{\|\mathbf{w}\|} \) is equivalent to minimizing \( \|\mathbf{w}\|^2 \). The SVM optimization problem in primal form is:

Subject to the constraints:

This is a convex quadratic programming problem with linear constraints, which guarantees a unique global solution. The constraint ensures that every training point is correctly classified and lies at least a distance of \( \frac{1}{\|\mathbf{w}\|} \) from the hyperplane.

The Dual Form with Lagrange Multipliers

Introducing Lagrange multipliers \( \alpha_i \geq 0 \) for each constraint, we form the Lagrangian:

Taking derivatives and setting them to zero yields the conditions:

Substituting back gives the dual formulation:

Subject to \( \alpha_i \geq 0 \) and \( \sum_{i=1}^{n} \alpha_i y_i = 0 \). The dual form is critical because it depends on the data only through dot products \( \mathbf{x}_i \cdot \mathbf{x}_j \), which opens the door to the kernel trick.

Making Predictions

Once the optimal \( \alpha_i \) values are found, the decision function for a new point \( \mathbf{x} \) is:

Since most \( \alpha_i = 0 \), the sum only involves the support vectors, making prediction efficient even with large training sets.

Margin Width for Different Regularization Strengths

The chart below illustrates how the margin width varies as we change the regularization parameter C. Lower C values produce wider margins (more regularization), while higher C values produce narrower margins (less regularization, tighter fit).

Hard Margin SVM

The formulation we saw in the previous section is the hard margin SVM. It requires that every training point be correctly classified with a margin of at least \( \frac{1}{\|\mathbf{w}\|} \). The constraint is strict:

This works perfectly when the data is linearly separable -- when a hyperplane can perfectly divide the two classes. However, real-world data is rarely perfectly separable. Even a single outlier or mislabeled point can make the hard margin problem infeasible (no solution exists).

Soft Margin SVM -- Introducing Slack Variables

In 1995, Cortes and Vapnik introduced slack variables \( \xi_i \geq 0 \) to allow some training points to violate the margin or even be misclassified. Each slack variable measures how far a point is from the correct side of the margin:

• \( \xi_i = 0 \): The point is correctly classified and outside the margin
• \( 0 < \xi_i < 1 \): The point is correctly classified but inside the margin (margin violation)
• \( \xi_i = 1 \): The point is exactly on the decision boundary
• \( \xi_i > 1 \): The point is misclassified

The Soft Margin Optimization

The soft margin SVM balances two competing objectives: maximizing the margin and minimizing the total amount of slack (violations). The optimization problem becomes:

Subject to \( y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i \) and \( \xi_i \geq 0 \) for all \( i \).

The parameter C controls the trade-off:

The Hinge Loss Perspective

The soft margin SVM can also be understood through the lens of hinge loss. The hinge loss for a single point is:

This loss is zero when the point is correctly classified with margin at least 1, and grows linearly as the point moves further into the wrong side. The soft margin SVM minimizes:

This is the regularized empirical risk minimization form. The first term is the regularizer (controlling complexity), and the second term is the data-fitting loss.

Interactive: Effect of C Parameter

See how the regularization parameter C controls the trade-off between a wider margin and fewer misclassifications.

The Problem with Linear Boundaries

Many real-world datasets are not linearly separable. Consider the classic XOR problem: no single straight line can separate the two classes. The solution is to map the data into a higher-dimensional space where a linear separator exists.

For example, consider 2D data points that lie on concentric circles. In the original space, no line can separate the inner circle from the outer circle. But if we add a third dimension \( z = x_1^2 + x_2^2 \), the data becomes separable by a plane in 3D space.

The mapping function \( \phi \) transforms the input from the original \( d \)-dimensional space to a much higher \( D \)-dimensional feature space.

The Kernel Function

Computing \( \phi(\mathbf{x}) \) explicitly can be extremely expensive or even impossible when \( D \) is infinite. The kernel trick avoids this by noting that the dual SVM formulation only uses dot products \( \mathbf{x}_i \cdot \mathbf{x}_j \). A kernel function computes the dot product in the high-dimensional space without ever computing the mapping:

We simply replace every dot product \( \mathbf{x}_i \cdot \mathbf{x}_j \) in the dual form with \( K(\mathbf{x}_i, \mathbf{x}_j) \). The dual becomes:

And the decision function becomes:

Why the Kernel Trick is Brilliant

Interactive: Kernel Transformation

See how the RBF kernel maps non-linearly separable data into a space where a linear boundary works. Adjust gamma to control the kernel's reach.

Linear Kernel

The simplest kernel -- just the standard dot product with no mapping:

Use when the data is linearly separable or when you have many features relative to samples (e.g., text classification with thousands of word features). The linear kernel is the fastest to train and the most interpretable. It is equivalent to a standard linear SVM without any feature mapping.

Polynomial Kernel

Maps data into a polynomial feature space of degree \( d \):

Where \( \gamma \) is a scaling factor, \( r \) is the coefficient (often 0 or 1), and \( d \) is the polynomial degree. The polynomial kernel implicitly computes all polynomial combinations of features up to degree \( d \). A degree-2 polynomial kernel on 2D data \( (x_1, x_2) \) implicitly creates features like \( x_1^2, x_2^2, x_1 x_2, x_1, x_2, 1 \).

Use when: Interactions between features matter, data has moderate nonlinearity, or you need more expressive power than a linear kernel.

RBF (Radial Basis Function) Kernel -- Gaussian Kernel

The most popular and versatile kernel. It measures similarity based on the Euclidean distance between points:

Where \( \gamma > 0 \) controls the width of the Gaussian. The RBF kernel maps data to an infinite-dimensional feature space, yet the computation remains efficient. The kernel value ranges from 0 (points infinitely far apart) to 1 (identical points).

The parameter \( \gamma \) controls the influence radius of each support vector:

• Large \( \gamma \): Each support vector has a small radius of influence. The decision boundary becomes highly local and irregular, potentially overfitting
• Small \( \gamma \): Each support vector has a wide radius of influence. The decision boundary becomes smoother but may underfit

Sigmoid Kernel

Inspired by neural networks, the sigmoid kernel is:

Where \( \gamma \) and \( r \) are parameters. The sigmoid kernel is related to a two-layer perceptron neural network. However, it is not always positive semi-definite (violates Mercer's condition for certain parameter values), so it should be used with care. In practice, the RBF kernel is almost always preferred over the sigmoid kernel.

RBF Kernel Response at Different Gamma Values

The chart below visualizes how the RBF kernel response \( K(\mathbf{x}, \mathbf{0}) \) changes as a function of distance \( \|\mathbf{x}\| \) for different values of gamma. Higher gamma values create sharper, more localized responses.

What Are Support Vectors?

Support vectors are the training points that lie exactly on the margin boundaries (or inside the margin in the soft margin case). Formally, they are the points with Lagrange multipliers \( \alpha_i > 0 \). These are the hardest-to-classify points -- the ones closest to the decision boundary.

The decision boundary is entirely determined by the support vectors. If you removed all other training points and retrained, you would get the exact same decision boundary. This is a remarkable property that no other classifier shares.

Why Only Support Vectors Matter

Support Vectors in the Soft Margin Case

In the soft margin SVM with parameter \( C \), the Lagrange multipliers satisfy \( 0 \leq \alpha_i \leq C \). This creates three categories of training points:

• \( \alpha_i = 0 \): Non-support vectors. Correctly classified and outside the margin. No influence on the boundary.
• \( 0 < \alpha_i < C \): Free support vectors. Lie exactly on the margin. These are used to compute the bias \( b \).
• \( \alpha_i = C \): Bounded support vectors. Lie inside the margin or are misclassified. They are at the maximum allowed influence.

The number of support vectors serves as a rough indicator of model complexity. If nearly all training points are support vectors, the model may be underfitting (C too small) or the data may be inherently difficult to separate.

The Epsilon-Insensitive Loss

Support Vector Regression (SVR) adapts the SVM framework for continuous output. Instead of finding a maximum margin between classes, SVR finds a function that deviates from the actual target values \( y_i \) by at most \( \varepsilon \). Errors within this epsilon tube are ignored entirely.

The epsilon-insensitive loss is zero when the prediction is within \( \varepsilon \) of the true value, and grows linearly beyond that threshold.

SVR Optimization Problem

The SVR optimization with slack variables \( \xi_i, \xi_i^* \) for deviations above and below the tube:

Subject to:

The parameter \( \varepsilon \) controls the width of the tube (tolerance for errors), and \( C \) controls the trade-off between flatness of \( f(\mathbf{x}) \) and tolerance for deviations larger than \( \varepsilon \).

Kernel SVR

Just like classification SVMs, SVR can use the kernel trick for nonlinear regression. The prediction function becomes:

Where \( \alpha_i, \alpha_i^* \) are the dual variables corresponding to deviations above and below the tube. Points inside the tube have \( \alpha_i = \alpha_i^* = 0 \) and are not support vectors. Only the points on or outside the tube boundary influence the regression function.

C -- The Regularization Parameter

The parameter \( C \) controls the trade-off between achieving a wide margin and minimizing classification errors on the training data:

• Large C (e.g., 1000): The model prioritizes correct classification of every training point. Narrow margin, low bias, high variance. Risk of overfitting.
• Small C (e.g., 0.01): The model prioritizes a wide margin and tolerates more misclassifications. Wide margin, high bias, low variance. Risk of underfitting.
• Optimal C: Found through cross-validation. Typical search range: \( C \in \{0.001, 0.01, 0.1, 1, 10, 100, 1000\} \).

Gamma -- The RBF Kernel Width

For the RBF kernel \( K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma\|\mathbf{x} - \mathbf{x}'\|^2) \), the parameter \( \gamma \) controls the reach of each training example:

• Large gamma: Each training example has a small radius of influence. The decision boundary is highly irregular and wraps tightly around individual points. This leads to overfitting -- the model memorizes the training data.
• Small gamma: Each training example has a wide radius of influence. The decision boundary is very smooth and may fail to capture the true class structure. This leads to underfitting.
• Default: scikit-learn uses \( \gamma = \frac{1}{n_{\text{features}} \cdot \text{Var}(X)} \) (the 'scale' option), which is a good starting point.

Degree -- The Polynomial Kernel Parameter

For the polynomial kernel \( K(\mathbf{x}, \mathbf{x}') = (\gamma \, \mathbf{x} \cdot \mathbf{x}' + r)^d \), the degree \( d \) controls the complexity of the decision boundary:

• \( d = 1 \): Equivalent to a linear kernel (with an additional bias term depending on \( r \))
• \( d = 2 \): Quadratic decision boundaries -- can model ellipses, parabolas, and hyperbolas
• \( d = 3 \): Cubic decision boundaries -- more expressive but slower to compute
• High \( d \): Very expressive but prone to overfitting and numerically unstable (large values raised to high powers can overflow)

In practice, degrees 2 and 3 are most common. Higher degrees are rarely beneficial and significantly increase computation time.

Practical Tuning Strategy

Where SVMs Excel

SVM Classification Playground

Click to add data points and watch SVM find the maximum margin boundary. Blue = Class -1, Orange = Class +1.

SVM Kernel Accuracy Comparison on Sample Data

The chart below compares classification accuracy of different SVM kernels on a sample dataset. Performance varies depending on the data structure, reinforcing the importance of kernel selection and hyperparameter tuning.

Basic SVM Classification

The simplest way to get started with SVM in Python using scikit-learn. We use the Iris dataset with an RBF kernel.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.metrics import classification_report

# Load data
X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

# IMPORTANT: Always scale features for SVM
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Train SVM with RBF kernel
model = SVC(kernel='rbf', C=1.0, gamma='scale')
model.fit(X_train_scaled, y_train)

# Evaluate
y_pred = model.predict(X_test_scaled)
print(classification_report(y_test, y_pred))
print(f"Number of support vectors: {model.n_support_}")

Comparing Different Kernels

Test multiple kernels on the same dataset to find the best fit. Always use cross-validation for reliable comparison.

from sklearn.svm import SVC
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import load_breast_cancer

# Load data
X, y = load_breast_cancer(return_X_y=True)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Compare kernels
kernels = ['linear', 'rbf', 'poly', 'sigmoid']
for kernel in kernels:
    model = SVC(kernel=kernel, C=1.0, gamma='scale', degree=3)
    scores = cross_val_score(model, X_scaled, y, cv=5,
                             scoring='accuracy')
    print(f"{kernel:10s} | Accuracy: {scores.mean():.4f} "
          f"(+/- {scores.std():.4f})")

Hyperparameter Tuning with GridSearchCV

A production-ready pipeline with feature scaling and exhaustive hyperparameter search.

from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.datasets import load_digits

# Load handwritten digits dataset
X, y = load_digits(return_X_y=True)

# Build pipeline: scale then classify
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('svm', SVC())
])

# Define parameter grid
param_grid = {
    'svm__kernel': ['rbf', 'linear'],
    'svm__C': [0.1, 1, 10, 100],
    'svm__gamma': ['scale', 'auto', 0.001, 0.01],
}

# Grid search with 5-fold cross-validation
grid_search = GridSearchCV(
    pipeline, param_grid, cv=5,
    scoring='accuracy', n_jobs=-1, verbose=1
)
grid_search.fit(X, y)

print(f"Best parameters: {grid_search.best_params_}")
print(f"Best CV accuracy: {grid_search.best_score_:.4f}")

# Access the best model
best_model = grid_search.best_estimator_
print(f"Support vectors per class: "
      f"{best_model.named_steps['svm'].n_support_}")

Support Vector Regression (SVR)

Using SVR for nonlinear regression with the RBF kernel.

import numpy as np
from sklearn.svm import SVR
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error, r2_score

# Generate nonlinear data
np.random.seed(42)
X = np.sort(5 * np.random.rand(200, 1), axis=0)
y = np.sin(X).ravel() + np.random.normal(0, 0.1, X.shape[0])

# Split and scale
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s = scaler.transform(X_test)

# Train SVR with RBF kernel
svr = SVR(kernel='rbf', C=100, gamma=0.1, epsilon=0.1)
svr.fit(X_train_s, y_train)

# Evaluate
y_pred = svr.predict(X_test_s)
print(f"MSE:  {mean_squared_error(y_test, y_pred):.4f}")
print(f"R^2:  {r2_score(y_test, y_pred):.4f}")
print(f"Support vectors: {len(svr.support_)}/{len(X_train)}")

Text Classification with Linear SVM

Linear SVM is the gold standard for text classification. Combined with TF-IDF, it delivers excellent results with minimal tuning.

from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.svm import LinearSVC
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report

# Load subset of 20 Newsgroups
categories = ['sci.med', 'sci.space', 'rec.sport.hockey']
train = fetch_20newsgroups(subset='train', categories=categories)
test = fetch_20newsgroups(subset='test', categories=categories)

# Build pipeline with TF-IDF and Linear SVM
pipeline = Pipeline([
    ('tfidf', TfidfVectorizer(
        stop_words='english', max_features=10000
    )),
    ('svm', LinearSVC(C=1.0, max_iter=10000))
])

# Train and evaluate
pipeline.fit(train.data, train.target)
y_pred = pipeline.predict(test.data)
print(classification_report(
    test.target, y_pred,
    target_names=test.target_names
))