Support Vector Machines

The Margin Idea

Any line can separate two linearly-separable classes, but logistic regression picks one somewhat arbitrarily. SVMs are principled: they find the unique hyperplane that maximises the margin — the gap between the boundary and the nearest points of each class.

Wider margin = better generalisation. This is the core geometric insight behind SVMs.

Hard-Margin SVM

Hard-Margin Primal$$\min_{\mathbf{w},b}\frac{1}{2}\|\mathbf{w}\|^2 \quad\text{s.t.}\quad y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\geq 1\;\forall i$$Margin width = $2/\|\mathbf{w}\|$. Maximising margin ↔ minimising $\|\mathbf{w}\|^2$. Convex QP — guaranteed global optimum.

Soft-Margin SVM (C-SVM)

Real data is rarely perfectly separable. Soft-margin SVMs allow violations with slack variables $\xi_i \geq 0$:

Soft-Margin Primal$$\min_{\mathbf{w},b,\boldsymbol{\xi}}\;\frac{1}{2}\|\mathbf{w}\|^2+C\sum_i\xi_i \quad\text{s.t.}\quad y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\geq 1-\xi_i,\;\xi_i\geq 0$$$C$: regularisation. Large $C$ → small margin, few violations. Small $C$ → large margin, more violations. Always tune via cross-validation.

💡

Support Vectors are the training points that lie exactly on the margin boundaries ($y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)=1$). They're the only points that influence the boundary — all others can be removed without changing the model. This sparsity is why SVMs generalise well even in high dimensions.

The Kernel Trick

Many datasets aren't linearly separable. We can map inputs to a higher-dimensional space $\phi(\mathbf{x})$ where a linear separator exists. The kernel trick computes inner products in that space without ever computing $\phi$ explicitly:

Kernel Function$$K(\mathbf{x},\mathbf{x}')=\phi(\mathbf{x})^\top\phi(\mathbf{x}')$$

Linear$K(\mathbf{x},\mathbf{x}')=\mathbf{x}^\top\mathbf{x}'$. Best for high-dim sparse data (text).

Polynomial$K=(\gamma\mathbf{x}^\top\mathbf{x}'+r)^d$. Polynomial boundary of degree $d$.

RBF / Gaussian$K=\exp(-\gamma\|\mathbf{x}-\mathbf{x}'\|^2)$. Infinite-dimensional mapping. Most powerful and commonly used default.

Sigmoid$K=\tanh(\gamma\mathbf{x}^\top\mathbf{x}'+r)$. Neural network analogy; rarely preferred over RBF.

Python

import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
from sklearn.datasets import make_circles, make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import Pipeline

# Non-linearly separable data
X, y = make_moons(n_samples=300, noise=0.2, random_state=42)

# Visualise kernels side-by-side
kernels = [("Linear",     {"kernel":"linear",      "C":1.0}),
           ("Poly (d=3)", {"kernel":"poly",         "C":1.0, "degree":3, "gamma":"scale"}),
           ("RBF",        {"kernel":"rbf",          "C":10,  "gamma":"scale"})]

fig, axes = plt.subplots(1, 3, figsize=(15, 4))
scaler = StandardScaler().fit(X)
X_s = scaler.transform(X)
xx, yy = np.meshgrid(np.linspace(X_s[:,0].min()-0.3, X_s[:,0].max()+0.3, 200),
                     np.linspace(X_s[:,1].min()-0.3, X_s[:,1].max()+0.3, 200))

for ax, (name, params) in zip(axes, kernels):
    svm = SVC(**params).fit(X_s, y)
    Z = svm.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
    ax.contourf(xx, yy, Z, alpha=0.3, cmap=plt.cm.RdYlGn)
    ax.scatter(X_s[:,0], X_s[:,1], c=y, cmap=plt.cm.RdYlGn, s=20, edgecolors="white", lw=0.3)
    # Highlight support vectors
    sv = svm.support_vectors_
    ax.scatter(sv[:,0], sv[:,1], s=80, facecolors="none", edgecolors="black", lw=1.5)
    ax.set_title(f"{name}  ({svm.n_support_.sum()} SVs)")
plt.tight_layout(); plt.show()

Hyperparameter Tuning

Python

from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import Pipeline
from sklearn.svm import SVC

pipe = Pipeline([("scaler", StandardScaler()), ("svm", SVC(probability=True))])
param_grid = {
    "svm__kernel": ["rbf", "poly"],
    "svm__C":      [0.1, 1, 10, 100],
    "svm__gamma":  ["scale", "auto", 0.001, 0.01],
}
gs = GridSearchCV(pipe, param_grid, cv=5, scoring="roc_auc", n_jobs=-1, verbose=1)
gs.fit(X, y)
print(f"Best params: {gs.best_params_}")
print(f"Best AUC:    {gs.best_score_:.4f}")

SVM for Regression (SVR)

SVM extends to regression via Support Vector Regression (SVR): instead of maximising the margin between classes, we find a function that fits within an $\epsilon$-tube around the data. Points outside the tube incur a penalty.

Python

from sklearn.svm import SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

svr = Pipeline([("scaler", StandardScaler()),
                ("svr",    SVR(kernel="rbf", C=100, epsilon=0.1, gamma="scale"))])
svr.fit(X_train_reg, y_train_reg)
print(f"SVR R²: {svr.score(X_test_reg, y_test_reg):.4f}")

Summary

SVM maximises the margin between classes. Margin = $2/\|\mathbf{w}\|$. Convex QP — global optimum guaranteed.
Soft-margin ($C$): balance between margin size and misclassification tolerance.
Kernel trick: compute high-dimensional dot products cheaply. RBF is the default kernel.
Always scale features before SVM. Tune $C$ and $\gamma$ via cross-validation.