module 08

Support Vector Machines

free pdf

A Training Algorithm for Optimal Margin Classifiers

Bernhard E. Boser et al.

Among all lines that separate two classes, pick the one with the widest gap to the nearest points. Only those nearest points matter. The paper also shows how kernels let that straight line become a curve without extra cost.

free pdf

Support-Vector Networks

Corinna Cortes & Vladimir Vapnik

Real data overlaps, so no line separates it perfectly. This paper lets some points sit on the wrong side for a price C, giving the soft-margin SVM that is used in practice.

free pdf

Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines

John C. Platt

Training an SVM means solving a big optimisation problem. SMO breaks it into tiny pieces of two variables each, which can be solved with a simple formula. No heavy solver is needed, and it is much faster.

three papers, three steps

  1. Among all lines that separate two classes, pick the one with the widest gap. Kernels let that line become a curve.
  2. Real data overlaps, so allow some points on the wrong side, at a price C.
  3. Training needs a big optimisation problem; SMO solves it two numbers at a time, with no special solver.

the widest gap

Many lines separate two clean groups. The SVM picks the one with the most room on both sides. The width of that empty band (the margin) is 2/‖w‖, so making it wide means making ‖w‖ small:

min⁡w,b  12∥w∥2such thatyi(w⋅xi−b)≥1\min_{w,b}\; \tfrac12\|w\|^2 \quad\text{such that}\quad y_i(w\cdot x_i - b) \ge 1

The answer only depends on the points that touch the edges of the band: the support vectors. Delete every other point and you get exactly the same line.

letting some points cross: the soft margin

Real data overlaps, so no line separates it perfectly. Cortes and Vapnik let points sit inside the band, or on the wrong side, if you pay a price C for each one:

min⁡  12∥w∥2+C∑iξi\min\; \tfrac12\|w\|^2 + C\sum_i \xi_i

Here ξᵢ measures how far point i crosses. Small C: crossing is cheap, so the band is wide. Large C: crossing is expensive, so the band is narrow.

the margin and the support vectors

margin 1.256 · 6 support vectors
-4-2024-3-2-10123
decision linemargin edges
medium C: a balance. only a handful of points touch or cross the margin, and only they decide where the line goes.

curves for free: kernels

Rewritten in its dual form, the problem only ever uses the data through dot products x·x'. Replace that dot product with a kernel K(x, x'), a dot product in some richer space, and the straight line becomes a curve, without ever computing that richer space.

The RBF kernel measures closeness: nearby points count a lot, far ones barely at all. gamma sets how far "nearby" reaches:

the rbf kernel and gamma

22 support vectors · train 0.985 · test 0.987

● filled class · ○ hollow class · darker background = more confident it's the filled class

the rbf kernel lets the boundary curve. gamma sets how far each point's influence reaches. small gamma: smooth circle. large gamma: every point gets its own little bump, almost every point becomes a support vector, and the test score drops.

SMO: two numbers at a time

Training means finding one weight αᵢ per training point, all tied together by one rule: Σ αᵢyᵢ = 0. Because of that rule you can't change one α alone, but you can change two. With two, the best change has a simple formula. Platt's SMO:

  1. Pick two points, preferring pairs where the step will be big.
  2. Update their two αs with the formula, clipped so they stay between 0 and C.
  3. Repeat until every point follows the optimality rules.

Each point's α tells you where it is:

α where the point is
0 safely outside the band, doesn't matter
between 0 and C exactly on the edge of the band
C inside the band or on the wrong side

how the code works

idea in svm.py
kernels linear_kernel, poly_kernel, rbf_kernel
choosing which pairs to update fit and _examine
the two-number update, with clipping _take_step
checking the answer is optimal kkt_violations(), dual_objective()
the weight vector for a straight line coef_
did it finish? converged_ (it warns if not)

what the demo checks

Run uv run python examples/08_svm.py.

  • On clean data, 3 of 100 points become support vectors. Delete 60 others and the line doesn't move.
  • The answer is provably optimal: no points break the rules, and the two forms of the problem (primal 91.5438, dual 91.5437) meet, as theory says they must.
  • On a ring inside a ring, a straight line gets 0.57; a curved kernel gets 0.986.
  • A bug found and fixed: with a large C, SMO needs many more passes. The old limit stopped it early without saying so. The limit is higher now, and SMO warns if it ever stops early.

when it goes wrong

  • Gamma too large: islands around single points, and almost every point becomes a support vector. A large support-vector count is a warning sign.
  • C too small: the band is so wide everything sits inside it.
  • Unscaled features: both the margin and kernel distances depend on scale.
  • No probabilities: the SVM's output is a distance, not a probability.