Concept35 minBefore this:Logistic Regression

Support Vector Machines

Of all the lines that separate the data, why pick the one with the widest street?

The situation

Many lines separate your pass and fail parts perfectly, but a little sensor noise pushes parts over some of those lines. The interviewer asks:

What does an SVM optimise, and what are support vectors?

Running example: a factory's quality check with two sensor readings per part (both standardised), labelled pass (+1) or fail (−1). Three simulated versions of it appear: a clean batch where the classes don't overlap (24 parts), a noisy batch where they do (80 parts), and a batch with a curved boundary (120 parts, "two moons"). Every model on this page is trained live in your browser by a small SMO solver, and test accuracy uses fresh simulated parts.

Infinitely many lines separate the data. Which one?

When two classes can be split by a straight line, there are usually infinitely many such lines. Some pass a hair away from a training point; nudge that part's readings slightly (sensor noise) and it lands on the wrong side. We want the line that is least fragile: the one that stays as far as possible from both classes. That one idea, plus two extensions (forgiving some mistakes, and bending the boundary), is the whole SVM.

The idea

Think of laying the widest possible road between two groups of houses. Only the houses right at the road's edge decide where it can go. Move any other house, and the road doesn't change.

Illustrative. The ringed points on the edges are the support vectors.

Play

Try to break it. Push γ up to 100 and watch the boundary. Then bring it down to 0.1 and compare the test accuracy.

The RBF kernel

γ sets how far each support vector reaches

The RBF (Gaussian) kernel K(x, z) = exp(−γ‖x − z‖²) is the default in scikit-learn's SVC. The score becomes a sum of bumps centred on support vectors. scikit-learn: "gamma defines how much influence a single training example has. The larger gamma is, the closer other examples must be to be affected" SVM guide.

support vectors (of 120)

–

training accuracy

–

test accuracy (1,000 new)

–

Pale band: inside the street (|f| < 1). Try γ = 0.1 (bumps so wide the boundary is nearly straight: underfits), γ = 1 (follows the moons), γ = 100 (a bump around nearly every point: overfits).

At C = 1 on this batch: γ = 0.1 gives 80.7% test accuracy, γ = 1 gives 89.3%, and γ = 100 gives 99% training but only 79.8% test, with 115 of the 120 points as support vectors. A support-vector count close to n is itself a warning sign of overfitting. C and γ interact (a large γ with a small C can still be smooth), so scikit-learn advises searching them together, "spaced exponentially far apart" SVM guide.

What breaks without scaling

The RBF kernel uses Euclidean distance, so a feature measured in large units dominates every distance and the others are ignored; the margin in a linear SVM is also distorted. scikit-learn: "Support Vector Machine algorithms are not scale invariant, so it is highly recommended to scale your data", with the same scaling applied to test data, easiest inside a Pipeline(StandardScaler(), SVC()) SVM guide. The k-NN lesson measures the damage on the same moons data.

Now say why: why does a huge γ score well on training parts but worse on new ones, and what happens to the support-vector count?

Maths

In one breath

Many lines separate two classes; an SVM picks the one with the widest street (margin) between them. Only the points on the edge of the street, the support vectors, decide where it goes. Real data overlaps, so a soft margin lets some points break the rule at a price set by C (small C: wide, forgiving street; large C: narrow, strict). The kernel trick swaps every dot product for a similarity K(x, z), which is the same as drawing a straight street in a richer feature space without ever building that space; with the RBF kernel, γ sets how far each point's influence reaches. Scale your features, tune C and γ together on a log grid, and remember that training cost grows between n² and n³.What you'll be able to do after this: derive the margin, explain C and γ, read the hinge loss, explain the kernel trick on a 1-D example, and say when an SVM is (and isn't) the right tool.

class +1class −1boundary & marginsupport vectors (ringed)numbersviolations / failure

A linear score, and the distance to the line

A linear classifier computes a score f(x) = w·x + b and predicts the class by its sign. The boundary is where f(x) = 0. The margin of a point is how far it sits from that boundary, measured on the correct side:

Standard geometry; see Cortes & Vapnik (1995), §2 Machine Learning 20.

Because w and b can be rescaled freely, SVMs fix the scale by asking the closest points to have score exactly ±1. Then the street between the lines w·x + b = +1 and w·x + b = −1 has width 2 / ‖w‖. A wide street means a short w.

One principle

Widest street; only the edge points matter

Swipe sideways to see the whole diagram.

Seven passing parts, six failing parts, cleanly separable.
Many lines separate them. Each one is a valid classifier with zero training error.
The SVM chooses the line with the widest empty street around it. The street's edges are where the score is +1 and −1; its width is 2/‖w‖.
Only three parts touch the edges of the street. These are the support vectors: the solution is a weighted sum of them alone.
Move any other part (without crossing into the street) and the line doesn't move at all. That's why SVMs are "memory efficient": the model keeps only the support vectors.

Maximising 2/‖w‖ is the same as minimising ½‖w‖², which gives a clean convex problem, the hard-margin SVM:

The optimal-margin classifier of Boser, Guyon & Vapnik (1992); Cortes & Vapnik (1995) Eq. 1–4 Machine Learning 20.

Soft margin

Real data overlaps: pay for each violation

On the noisy batch, no line separates the classes, so the hard-margin problem has no solution. Cortes & Vapnik's fix (the paper that named it the "support-vector network") gives every point a slack ζ_i: how far it is allowed to cross its edge of the street, at a cost:

scikit-learn's primal SVC problem (with φ(x) = x for the linear case) SVM guide; Cortes & Vapnik (1995) §3.

C (log scale)

street half-width 1/‖w‖

–

support vectors (of 80)

–

training accuracy

–

test accuracy (400 new)

–

Ringed points are support vectors: every point on or inside the street, plus every misclassified one. Small C: a wide street with many support vectors (each paying a little). Large C: a narrow street that tries to fix individual violations.

On this batch, support vectors fall from 65 at C = 0.01 to about 25 at C = 1, and test accuracy sits in a narrow band (83–87%), best near C = 1. The noise sets a ceiling no C can beat. scikit-learn's advice: "C is 1 by default and it's a reasonable default choice. If you have a lot of noisy observations you should decrease it" SVM guide.

Same thing, as a loss

The hinge loss: only the street pulls

At the optimum each slack equals exactly max(0, 1 − y_if(x_i)). Substituting turns the soft-margin SVM into ordinary regularised loss minimisation, the form SGDClassifier(loss="hinge") uses:

A point's margin y·f(x)

Both hinge and logistic loss are convex stand-ins for the 0–1 loss (the thing we actually count). The difference: logistic loss is never exactly zero, so every training point keeps pulling a little. Hinge loss is exactly zero past the street, so far-away points drop out of the solution. That is where the sparsity (support vectors) comes from. my take

The kernel trick

Bend the boundary by lifting the data

Swipe sideways to see the whole diagram.

One sensor reading. Parts in the middle pass; extreme readings on either side fail. No single threshold works.
Add a feature: x². Each point is lifted onto a parabola. The middle points stay low; the extremes rise.
In this two-feature space, one straight line separates them perfectly.
Projected back to the original line, that straight line becomes two thresholds: a non-linear rule from a linear model.
The trick: the SVM's training and prediction only ever use dot products between points. Replace each dot product with a function K(x, z) that equals φ(x)·φ(z), and you never compute φ at all. The RBF kernel's φ is infinite-dimensional, yet K costs one exponential.

Why do only dot products appear? Solving the soft-margin problem through its dual gives w = Σ α_iy_ix_i, a weighted sum of training points with α_i > 0 only for support vectors. Plug that into the score:

scikit-learn's decision function for SVC, and its kernel list (linear, polynomial, RBF, sigmoid) SVM guide. The kernel idea for maximum-margin classifiers is from Boser, Guyon & Vapnik (1992).

Go deeper: the dual problem and what makes a valid kernel

The Lagrangian dual of the soft-margin SVM is: maximise Σα_i − ½ΣΣ α_iα_jy_iy_jK(x_i, x_j) subject to 0 ≤ α_i ≤ C and Σα_iy_i = 0. The data appear only through K. A function is a valid kernel (it equals φ(x)·φ(z) for some φ) when every Gram matrix it produces is symmetric positive semi-definite (Mercer's condition). The sigmoid "kernel" can fail this, which is one reason it's rarely used.

The SMO algorithm (Platt, 1998), the basis of libsvm, solves the dual by repeatedly optimising two α's at a time in closed form. The solver on this page is a simplified SMO.

In practice

Where SVMs sit among linear classifiers

Method	Loss it minimises	What you get
Perceptron	Mistakes only (any separating line)	Some line; depends on order
Logistic regression	Log loss: every point pulls a little	Calibrated-ish probabilities
Linear SVM	Hinge loss + ‖w‖²: only points inside the street pull	The max-margin line; sparse in the data (support vectors)
Kernel SVM	Same, with K(x, z) instead of x·z	Curved boundaries; cost grows ~n² to n³

In scikit-learn: SVC (libsvm, any kernel), LinearSVC (liblinear, linear only, scales to large n) and SGDClassifier(loss="hinge") for very large or streaming data SVM guide.

The practical limits

Training cost, and scores that aren't probabilities

Training cost

Kernel SVMs solve a quadratic program over n points. scikit-learn: the libsvm solver "scales between O(n_features × n_samples²) and O(n_features × n_samples³)" SVM guide. Double the data, roughly 4–8× the training time; past a few hundred thousand rows kernel SVC becomes impractical. Linear SVMs (liblinear, SGD) scale roughly linearly, and kernel approximations (Nyström, random Fourier features) feed a linear SVM.

No native probabilities

The SVM score is a distance, not a probability. With probability=True, scikit-learn fits Platt scaling (a logistic regression on the scores) with an extra cross-validation, which is expensive, and "the probability estimates may be inconsistent with the scores": predict can say positive while predict_proba says below 0.5 SVM guide. If you only need a ranking, use decision_function.

Training an SVM, end to end

Scale every feature (StandardScaler), fitted on training data only.
Pick the kernel: linear when features are many and sparse (text, n_features ≫ n) or n is large; RBF otherwise.
Grid-search C and γ on a log scale (e.g. C ∈ 10^−2…3, γ ∈ 10^−4…1) with cross-validation.
Imbalanced classes: class_weight="balanced" scales C per class.
Need probabilities? Calibrate separately (CalibratedClassifierCV) or use decision_function for ranking.
Check the support-vector count: close to n means overfitting or a poor kernel.

Multi-class: SVC trains one-vs-one classifiers (k(k−1)/2 of them); LinearSVC uses one-vs-rest SVM guide.

When to use it

Use an SVM when

n is small to medium (up to tens of thousands) and you want a strong, tunable model
Features are many and sparse (text): a linear SVM is fast and strong
You need a margin-based, convex, reproducible model

Reach for something else when

Millions of rows: linear models, SGD, or gradient boosting
Mixed-type tabular data: gradient-boosted trees are the default
Images, audio, raw text: deep networks
You need calibrated probabilities: logistic regression or a calibrated model

The answer that sounds right

The trap

"Any line that separates the training data is fine"

The perceptron (Rosenblatt, 1958) does exactly this: it nudges the line whenever a point is on the wrong side, and stops at the first line with zero training errors. Which line it stops at depends on the order it sees the parts. Shuffle the order and look:

perceptron: closest point's distance

–

perceptron: test accuracy

–

max margin: half-width of street

–

max margin: test accuracy

–

Dashed red: perceptron line. Violet: the maximum-margin line and its street. Both have 100% training accuracy. Test accuracy uses 3,000 new parts.

Over 30 shuffles, the perceptron's test accuracy ranged from 94.5% to 98.9% (mean 97.4%); the maximum-margin line scored 98.5%, and 8 of the 30 perceptron lines happened to beat it. So the honest claim is not "max margin always wins on test". It's that max margin gives one unique answer that never hugs a training point, which removes the worst cases. The theory backs this up: a wider margin means a smaller capacity term in the generalisation bound Cortes & Vapnik 1995. my take

Caveats

Strengths

Convex problem: one global optimum, no random restarts
"Effective in high dimensional spaces", even when features outnumber samples (scikit-learn)
Sparse solution: prediction uses only support vectors
Kernels give flexible boundaries with two knobs (C, γ)

Weaknesses

n² to n³ training: slow beyond ~10⁵ rows for kernel SVC
Needs feature scaling and a joint C/γ search
No native probabilities; Platt scaling is costly and can disagree with predict
A kernel model is hard to interpret; you can't read feature effects off it

Say it

What does an SVM optimise, and what are support vectors?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

An SVM finds the separating hyperplane with the largest margin.
Only the points on or inside the margin, the support vectors, determine the solution.
The soft margin adds slack penalised by C, which equals hinge loss plus L2.
Small C gives a wide, smooth margin, while large C fits the training points.
The kernel trick gives non-linear boundaries without building the feature map.
You scale features, tune C and γ together, and note training is quadratic to cubic in n.