Support Vector Machines

The SVM (Cortes & Vapnik, 1995) crowned the statistical learning era: a classifier derived from a clean geometric principle — maximize the margin — with rigorous theory behind it, and a trick that lets a linear method draw wildly nonlinear boundaries. Before deep learning, SVMs were the state of the art nearly everywhere; they remain excellent on small-to-medium, high-dimensional problems.

Maximum margin

Many hyperplanes separate two separable classes; which is best? Vapnik's answer: the one farthest from the closest points of both classes — the widest "street." A wide margin means small perturbations of the data don't flip predictions: better generalization, provably.

For hyperplane \(w^\top x + b = 0\), scale \(w, b\) so the closest points satisfy \(\lvert w^\top x + b \rvert = 1\) (the dashed lines). The street width is \(2 / \lVert w \rVert\), so maximizing margin = minimizing \(\lVert w \rVert\):

A convex quadratic program — one global optimum. The circled points touching the dashed lines are the support vectors: they alone determine the solution. Move or delete any other point and nothing changes — the model compresses the dataset down to its critical boundary cases.

Soft margin: tolerating imperfection

Real data is not separable. Introduce slack \(\xi_i \geq 0\) (how far point \(i\) violates its margin) and charge for it:

\(C\) is the bias–variance knob, and it works like logistic regression's C (both are inverse regularization):

• large \(C\): violations are expensive → narrow, strict margin → risk of overfitting;
• small \(C\): violations are cheap → wide, tolerant margin → smoother, simpler boundary.

Equivalently: SVM minimizes hinge loss \(\max(0,\, 1 - y_i(w^\top x_i + b))\) plus an L2 penalty — same "loss + regularization" template as Ridge, with a loss that ignores points comfortably beyond the margin.

The kernel trick

The dual form of the optimization depends on the data only through inner products \(x_i^\top x_j\), and prediction likewise:

So: map data to a higher-dimensional space \(\phi(x)\) where it becomes linearly separable — but never compute \(\phi\) explicitly. Just replace every inner product with a kernel function

computed directly in the original space. Linear machinery, nonlinear boundary, no exponential cost.

For RBF, \(\gamma\) sets each support vector's radius of influence: large \(\gamma\) → tight islands around points (overfit); small \(\gamma\) → broad, smooth influence (underfit). \(C\) and \(\gamma\) are tuned together on a log grid (GridSearchCV). The right panel of the figure shows RBF drawing a circular boundary no hyperplane could — in the implicit space, the circles are linearly separable.

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

svm = make_pipeline(StandardScaler(),                    # SVMs are distance-based
                    SVC(kernel='rbf', C=1.0, gamma='scale'))
svm.fit(X_train, y_train)

Training, in essence

Solvers optimize the dual (e.g. SMO — Sequential Minimal Optimization, Platt 1998 — which iteratively optimizes pairs of \(\alpha_i\)). A pseudocode sketch of the idea:

initialize all α_i = 0
repeat until KKT conditions hold (within tolerance):
    pick a pair (α_i, α_j) violating the conditions      # heuristic choice
    optimize the objective over that pair analytically    # closed form for 2 vars
    clip to 0 ≤ α ≤ C, update b
points ending with α_i > 0 are the support vectors

Complexity is roughly \(O(n^2)\)–\(O(n^3)\) in samples — the reason SVMs shine at \(n \sim 10^3\)–\(10^5\) but yield to gradient boosting and neural networks on millions of rows. (For linear kernels, LinearSVC/SGDClassifier scale much further.)

Practical profile

Class materials

Videos

• SVM — Support Vector Machines: Fundamentos e prática — in Portuguese
• 16. Learning: Support Vector Machines — MIT OpenCourseWare, Patrick Winston

Further reading

• Wikipedia — Quadratic programming
• Wikipedia — Sequential minimal optimization (SMO)

Quiz