Support Vector Machine — Support Vector Machine

Summary

The Support Vector Machine (SVM), or machine à vecteurs de support, is one of the most powerful and elegant supervised classification algorithms in machine learning. Invented by Vladimir Vapnik and Alexey Chervonenkis in the 1960s, then popularized in the 1990s, SVM is based on a simple but mathematically profound principle: finding the hyperplane that separates two classes by maximizing the margin — the distance between the hyperplane and the closest points in each class. Unlike many other algorithms, SVM depends only on these critical points, called support vectors, making it robust and efficient even in high-dimensional spaces. Thanks to the kernel trick, it can also solve non-linearly separable problems by implicitly projecting the data into a higher-dimensional space.

Mathematical Principle

The Separating Hyperplane

At the heart of SVM lies the search for a separating hyperplane. In an n-dimensional space, this hyperplane is defined by the equation:

$$\mathbf{w} \cdot \mathbf{x} + b = 0$$

where w is the normal vector to the hyperplane (it determines the orientation), b is the bias (it determines the position), and x is a data point. The hyperplane divides the space into two half-spaces: on one side, all points are classified as belonging to class +1; on the other, they are classified as belonging to class −1. The decision function is written:

$$f(\mathbf{x}) = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b)$$

The Margin

The key to SVM lies in the concept of the margin. The margin is the distance between the separating hyperplane and the closest data points from each class. Maximizing this margin is equivalent to maximizing classification confidence: the larger the margin, the more robust the classifier is when faced with new data.

Mathematically, the margin equals:

$$\text{margin} = \frac{2}{|\mathbf{w}|}$$

The correct classification constraints are written:

$$y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 \quad \forall i$$

where yᵢ ∈ {−1, +1} is the label of the i-th point.

Primal Optimization Problem

The SVM optimization problem consists of finding the values of w and b that minimize the norm of w while satisfying the classification constraints:

$$\min_{\mathbf{w}, b} \frac{1}{2} |\mathbf{w}|^2$$

$$\text{subject to: } y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 \quad \forall i$$

This formulation is a quadratic convex optimization problem with linear constraints. Solving it guarantees the existence of a unique global minimum.

Dual Formulation with Lagrange Multipliers

By introducing Lagrange multipliers αᵢ ≥ 0 for each constraint, we obtain the dual problem:

$$\max_{\alpha} \sum_{i=1}^{n} \alpha_i – \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j)$$

$$\text{subject to: } \alpha_i \geq 0 \quad \text{and} \quad \sum_{i=1}^{n} \alpha_i y_i = 0$$

The points for which αᵢ > 0 are precisely the support vectors — the only points that influence the position of the hyperplane. All other points have αᵢ = 0 and have no impact on the final model. This sparsity property gives SVM its remarkable memory efficiency.

The Kernel Trick

When the data is not linearly separable in the original space, SVM uses the kernel trick. The idea is to project the data into a higher-dimensional (potentially infinite) space via a transformation function φ, then search for a separating hyperplane there.

The crucial point is that we never need to explicitly compute φ(x). We only need to compute the dot product in the transformed space via a kernel function:

$$K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)$$

The most common kernels are:

• Linear kernel: K(xᵢ, xⱼ) = xᵢ · xⱼ — equivalent to standard SVM without transformation
• Polynomial kernel: K(xᵢ, xⱼ) = (γ · xᵢ · xⱼ + coef0)^d — captures polynomial interactions of degree d
• RBF kernel (Radial Basis Function): K(xᵢ, xⱼ) = exp(−γ ||xᵢ − xⱼ||²) — the most widely used, creates complex non-linear decision boundaries
• Sigmoid kernel: K(xᵢ, xⱼ) = tanh(γ · xᵢ · xⱼ + coef0) — analogous to a single-layer neural network

Geometric Intuition

Imagine you need to draw a road between two enemy villages — the blue dots and the red dots. You want this road to be as wide as possible, so that the inhabitants of each village stay as far as possible from the border and from conflict. The houses that directly touch the edge of the road, on either side, are the support vectors. They are the only houses that matter in determining where the central road runs. All the other houses, those far from the border, have no influence on the layout at all.

This is exactly the principle of SVM: it seeks the widest possible boundary between two classes, and only the points that are “stuck” to this margin — the support vectors — determine the final decision. This intuition explains why SVM is so robust: even if you add or remove points far from the boundary, the hyperplane does not move.

If the two villages are mixed together and no straight road can separate them, the kernel trick is like lifting the terrain into a third dimension: by projecting the data upward along a curve, we can often find a separating plane in this elevated space. It’s as if, by adding a dimension, we make possible what was not possible in the original space.

Python Implementation

Linear SVM with scikit-learn

from sklearn import datasets
from sklearn.svm import SVC, LinearSVC
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report, confusion_matrix
import numpy as np

# Load the Iris dataset (binary for demonstration)
iris = datasets.load_iris()
X = iris.data[:, :2]  # Keep 2 features for visualization
y = (iris.target != 0).astype(int)  # Binary classification: setosa vs non-setosa

# Train/test split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y
)

# Standardization — crucial for SVM!
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Linear SVM
svm_linear = SVC(kernel="linear", random_state=42)
svm_linear.fit(X_train_scaled, y_train)

# Predictions and evaluation
y_pred = svm_linear.predict(X_test_scaled)
print("Confusion matrix (Linear SVM):")
print(confusion_matrix(y_test, y_pred))
print(f"\nSupport vectors: {svm_linear.n_support_}")

RBF vs Polynomial Comparison

import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

# Create a grid for visualization
def plot_decision_boundary(model, X, y, title):
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))

    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    cmap = ListedColormap(["#FFAAAA", "#AAAAFF"])
    plt.contourf(xx, yy, Z, alpha=0.3, cmap=cmap)

    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=ListedColormap(["#FF0000", "#0000FF"]),
                edgecolors="k", s=50)

    # Highlight support vectors
    sv = model.support_vectors_
    plt.scatter(sv[:, 0], sv[:, 1], s=150, facecolors="none",
                edgecolors="gold", linewidths=2, label="Support Vectors")

    plt.title(title, fontsize=14)
    plt.xlabel("Feature 1")
    plt.ylabel("Feature 2")
    plt.legend()
    plt.tight_layout()
    plt.show()

# SVM with RBF kernel (default)
svm_rbf = SVC(kernel="rbf", C=1.0, gamma="scale", random_state=42)
svm_rbf.fit(X_train_scaled, y_train)

# SVM with polynomial kernel
svm_poly = SVC(kernel="poly", degree=3, C=1.0, gamma="scale", coef0=1, random_state=42)
svm_poly.fit(X_train_scaled, y_train)

# Visualization
fig, axes = plt.subplots(1, 3, figsize=(18, 5))

# Linear plot
plot_decision_boundary(svm_linear, X_train_scaled, y_train, "Linear SVM")
# RBF plot
plot_decision_boundary(svm_rbf, X_train_scaled, y_train, "SVM RBF (gamma=scale)")
# Polynomial plot
plot_decision_boundary(svm_poly, X_train_scaled, y_train, "SVM Polynomial (degree=3)")

Impact of the C Parameter

The C parameter controls the tradeoff between a wide margin and a low number of classification errors on the training data:

# Comparing different C values
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
C_values = [0.1, 1.0, 100.0]

for i, C_val in enumerate(C_values):
    svm = SVC(kernel="rbf", C=C_val, gamma="scale", random_state=42)
    svm.fit(X_train_scaled, y_train)

    x_min, x_max = X_train_scaled[:, 0].min() - 0.5, X_train_scaled[:, 0].max() + 0.5
    y_min, y_max = X_train_scaled[:, 1].min() - 0.5, X_train_scaled[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))
    Z = svm.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    axes[i].contourf(xx, yy, Z, alpha=0.3, cmap=ListedColormap(["#FFAAAA", "#AAAAFF"]))
    axes[i].scatter(X_train_scaled[:, 0], X_train_scaled[:, 1], c=y,
                    cmap=ListedColormap(["#FF0000", "#0000FF"]), edgecolors="k", s=50)
    axes[i].set_title(f"C = {C_val} | Support vectors: {svm.n_support_}")

plt.tight_layout()
plt.show()

• Small C (0.1): wide margin, tolerance for errors — more general model, risk of underfitting
• Medium C (1.0): good balance — often a good starting point
• Large C (100.0): narrow margin, strict classification — risk of overfitting

Impact of the gamma Parameter (RBF)

The gamma parameter of the RBF kernel controls the influence of each training point:

fig, axes = plt.subplots(1, 3, figsize=(18, 5))
gamma_values = [0.01, 1.0, 10.0]

for i, g in enumerate(gamma_values):
    svm = SVC(kernel="rbf", C=1.0, gamma=g, random_state=42)
    svm.fit(X_train_scaled, y_train)

    x_min, x_max = X_train_scaled[:, 0].min() - 0.5, X_train_scaled[:, 0].max() + 0.5
    y_min, y_max = X_train_scaled[:, 1].min() - 0.5, X_train_scaled[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))
    Z = svm.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    axes[i].contourf(xx, yy, Z, alpha=0.3, cmap=ListedColormap(["#FFAAAA", "#AAAAFF"]))
    axes[i].scatter(X_train_scaled[:, 0], X_train_scaled[:, 1], c=y,
                    cmap=ListedColormap(["#FF0000", "#0000FF"]), edgecolors="k", s=50)
    axes[i].set_title(f"gamma = {g} | Support vectors: {svm.n_support_}")

plt.tight_layout()
plt.show()

• Small gamma (0.01): large influence per point — smooth boundary, risk of underfitting
• Medium gamma (1.0): localized influence — good compromise
• Large gamma (10.0): very local influence — highly irregular boundary, risk of overfitting

LinearSVC for Large Datasets

For large datasets, LinearSVC is more efficient than SVC(kernel="linear") because it uses the liblinear algorithm instead of libsvm:

from sklearn.svm import LinearSVC

# LinearSVC — faster on large datasets
linear_svc = LinearSVC(C=1.0, max_iter=10000, random_state=42)
linear_svc.fit(X_train_scaled, y_train)

print(f"Coefficients: {linear_svc.coef_}")
print(f"Bias (intercept): {linear_svc.intercept_}")
print(f"Test accuracy: {linear_svc.score(X_test_scaled, y_test):.4f}")

Hyperparameters

SVM has several key hyperparameters that are essential to understand and tune:

Tuning via Grid Search

from sklearn.model_selection import GridSearchCV

param_grid = {
    "C": [0.1, 1, 10, 100],
    "gamma": ["scale", "auto", 0.1, 0.01],
    "kernel": ["rbf", "poly", "linear"]
}

grid_search = GridSearchCV(SVC(random_state=42), param_grid,
                           cv=5, scoring="accuracy", n_jobs=-1)
grid_search.fit(X_train_scaled, y_train)

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

Advantages and Limitations

Advantages

• Effective in high dimensions: SVM remains performant even when the number of features exceeds the number of samples
• Robust against overfitting: thanks to margin maximization, it generalizes well to new data
• Versatile through kernels: the kernel trick allows handling both linear and non-linear problems
• Sparse: the decision depends only on support vectors, not the entire training dataset
• Guaranteed convexity: unlike neural networks, the optimization is convex — there is no risk of getting stuck in a local minimum
• Works well on small datasets: excellent performance even with a few hundred samples

Limitations

• Slow on large datasets: training complexity is O(n²) to O(n³), making SVM impractical beyond ~100,000 samples
• Sensitive to outliers: a misplaced outlier can strongly influence the position of the hyperplane
• No direct probabilities: SVM does not naturally produce probabilities (requires recalibration via cross-validation with probability=True)
• Difficult to interpret: with an RBF kernel, the decision boundary is a complex function impossible to visualize in high dimensions
• Mandatory standardization: features must be scaled, otherwise SVM gives poor results
• Not natively multi-class: SVM is fundamentally binary; multi-class requires one-vs-one or one-vs-rest strategies

4 Concrete Use Cases

1. Text Classification and Spam Filtering

SVM excels at text document classification tasks. By combining a linear SVM with a TF-IDF representation, you get an extremely performant spam classifier. The features are very numerous (one word = one dimension), but this is precisely the domain where SVM shines. Foundational work by Thorsten Joachims demonstrated that linear SVMs often outperform probabilistic methods like Naive Bayes on this type of task.

2. Image Recognition and Computer Vision

Before the advent of deep neural networks, SVMs were the dominant approach for image classification. They are still used today in combination with feature extractors such as HOG (Histogram of Oriented Gradients) or SIFT. For example, pedestrian detection in ADAS systems of autonomous vehicles often uses SVMs as the final classifier after feature extraction.

3. Bioinformatics and Gene Classification

In genomics, we often seek to classify samples (healthy vs. diseased) based on the expression of thousands of genes. With typically a few dozen samples and thousands of features — a scenario where n ≤ p — the linear SVM is the algorithm of choice. Its ability to generalize effectively in this regime makes it indispensable for identifying tumor markers and personalized medicine.

4. Anomaly Detection (One-Class SVM)

The One-Class SVM is a variant that learns the distribution of a “normal” class and detects deviations. It is used for bank fraud detection, industrial monitoring (fault detection), and cybersecurity (intrusion detection). Instead of separating two classes, it learns a compact boundary around the normal data and flags everything outside it.

See Also

• What? Where? When? Mastering Python Programming: Complete Guide for Beginners
• Master Bucket Sort in Python: Complete Guide for Beginners