Support Vector Machines: Maximum-Margin Classification

Before deep learning's rise, Support Vector Machines were the state of the art for many classification problems — handwriting, text categorisation, bioinformatics. They combine an elegant geometric idea, a convex optimisation problem with a unique solution, and strong theoretical generalisation guarantees. Vladimir Vapnik and colleagues developed them from statistical learning theory, and they remain a valuable tool for medium-sized, high-dimensional problems.

The geometric idea: maximise the margin#

For linearly separable data there are infinitely many separating hyperplanes $\mathbf{w}^\top\mathbf{x} + b = 0$. Which is best? SVMs choose the one that maximises the margin — the distance to the nearest training points of either class. Intuitively, a wide margin leaves room for noise in future data: small perturbations of test points will not cross the boundary.

The distance from point $\mathbf{x}_i$ to the hyperplane is $\frac{|\mathbf{w}^\top\mathbf{x}_i + b|}{\|\mathbf{w}\|}$. Because $(\mathbf{w}, b)$ can be rescaled freely, we fix the scale so that the closest points satisfy $y_i(\mathbf{w}^\top\mathbf{x}_i + b) = 1$. The margin width is then $\frac{2}{\|\mathbf{w}\|}$.

Hard-margin SVM#

Maximising $2/\|\mathbf{w}\|$ is equivalent to minimising $\frac{1}{2}\|\mathbf{w}\|^2$:

This is a convex quadratic program with a unique global solution.

Soft-margin SVM#

Real data is rarely perfectly separable, and forcing separation makes the model a hostage to outliers. Introduce slack variables $\xi_i \ge 0$ that allow violations:

• $\xi_i = 0$: correctly classified, outside the margin.
• $0 < \xi_i \le 1$: inside the margin but correct.
• $\xi_i > 1$: misclassified.

The hyperparameter $C$ controls the trade-off:

• Large $C$: violations are expensive → narrow margin, fits training data closely → low bias, high variance.
• Small $C$: violations are cheap → wide margin, more regularised → higher bias, lower variance.

The hinge-loss view#

At the optimum $\xi_i = \max(0, 1 - y_if(\mathbf{x}_i))$, so the soft-margin SVM is equivalent to

— hinge loss plus L2 regularisation. Compare with logistic regression, which uses the logistic loss $\ln(1 + e^{-yf})$. Both are convex surrogates for the 0–1 loss. The hinge loss is exactly zero for points beyond the margin, which is why SVM solutions depend only on a subset of points.

Support vectors#

From the dual (see the Lagrange multipliers lecture), the solution is

Only points with $\alpha_i > 0$ — those on or inside the margin, or misclassified — contribute. These are the support vectors. Removing any other training point leaves the model unchanged. The number of support vectors also bounds the leave-one-out error, one of several theoretical results linking sparsity to generalisation.

import numpy as np
from sklearn.datasets import make_blobs
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import GridSearchCV

X, y = make_blobs(n_samples=400, centers=2, cluster_std=2.2, random_state=4)
for C in [0.01, 1, 100]:
    clf = SVC(kernel="linear", C=C).fit(X, y)
    margin = 2 / np.linalg.norm(clf.coef_)
    print(f"C={C:>6}: support vectors={clf.n_support_.sum():>3}  margin width={margin:.3f}  "
          f"train acc={clf.score(X, y):.3f}")

grid = GridSearchCV(make_pipeline(StandardScaler(), SVC(kernel="linear")),
                    {"svc__C": np.logspace(-3, 3, 13)}, cv=5).fit(X, y)
print("best C:", grid.best_params_)

Small $C$ gives a wide margin with many support vectors; large $C$ a narrow margin with fewer.

Practical considerations#

• Scale features — SVMs are distance-based.
• Probabilities: SVMs output signed distances, not probabilities. Platt scaling (probability=True) fits a sigmoid on top, at extra cost.
• Multiclass: typically one-vs-one (scikit-learn's SVC) or one-vs-rest (LinearSVC).
• Scaling to large data: kernel SVM training scales between $O(n^2)$ and $O(n^3)$; for large linear problems, use LinearSVC or SGD with hinge loss, which scale linearly.
• Imbalanced data: use class_weight="balanced".