module 08
Support Vector Machines
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.
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.
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
- Among all lines that separate two classes, pick the one with the widest gap. Kernels let that line become a curve.
- Real data overlaps, so allow some points on the wrong side, at a price
C. - 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:
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:
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
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
● filled class · ○ hollow class · darker background = more confident it's the filled class
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:
- Pick two points, preferring pairs where the step will be big.
- Update their two
αs with the formula, clipped so they stay between 0 andC. - 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.