The perceptron stops at any line that separates the data. The support vector machine asks for the best one: the line whose distance to the closest training points (the margin) is as large as possible. With a scaling trick that becomes "minimize " subject to linear constraints, a convex problem with one global solution. Only the few points touching the margin, the support vectors, decide the answer. For data that isn't separable, a soft margin lets some points break the rules at a price , and the kernel trick finds curved boundaries by quietly working in a higher-dimensional space. The professor calls SVMs the go-to classifier before deep learning, and the first thing to try if you don't need a neural network.
After this you canWhich line? The margin
When data is linearly separable, infinitely many lines separate it, and the perceptron returns whichever it hits first. The professor's argument for picking a specific one is robustness. Real measurements are noisy. Picture each training point as a ball of uncertainty. How far could a point drift before it lands on the wrong side? Exactly its distance to the line. The line is only as safe as its closest point, so we want to maximize the minimum distance.
Requiring a wide margin rules out most lines, so the model is more "constrained". Slide 5 says this lowers the VC dimension, a measure of how many patterns a model family can fit. Fewer possible fits means less room to fit noise, which means less overfitting. It's the same story as week 2.
Distance from a point to a hyperplane
SVM notation keeps the bias separate: the hyperplane is with . (Last week we folded into ; here it must stay out, because the margin depends on alone.)
- is perpendicular to the hyperplane. Take two points on it. Both satisfy ; subtracting gives . So is orthogonal to every direction lying in the plane. It's the plane's normal vector.
- Project onto the normal. The distance from to the plane is the length of along the unit normal , for any on the plane: using .
Line , point . Then , , and . Distance .
Slide 13's blue box writes . That should be , as on slide 10 and in the derivation above.
Hard-margin SVM
"Hard margin" means every training point must be classified correctly, so this assumes the data is linearly separable. With labels , "correct" is one inequality per point:
When a point is correctly classified, , so the absolute value in the distance can be dropped:
A max of a min looks hard. The professor calls the next step "a very important trick". Scaling by any gives the same hyperplane, because has the same solutions. So we're free to pick the scale, and we pick it so the closest point has
Maximizing is the same as minimizing , which is the same as minimizing (smooth, and the tidies the derivative):
This is a quadratic program (QP): a quadratic objective with linear inequality constraints. It's convex, so any solver finds the global optimum, not a local one. The professor highlights this as "another beauty of SVM". Off-the-shelf QP solvers exist in Python and MATLAB (slide 17).
Negative point , positive point . By symmetry the best line is the perpendicular bisector, so . The constraints:
: . : .
Adding them gives , so . Minimizing means taking , and then .
Result: , , margin . That's exactly half the distance between the points, , as it should be.
In this course (and on the slides), the margin is the distance from the line to the nearest point: . Géron and many other sources talk about the whole "street", from one edge to the other: . Same optimization, different number. On an exam, say which one you mean.
Support vectors
The support vectors are the training points on the edges of the street, where the constraint holds with equality:
They "support" the separator: remove any other point and the solution doesn't change at all. Move a support vector and the line moves. In the figure above, 3 of 12 points decide everything.
It's automatic data selection. With a million training points and a simple class boundary, the trained SVM might depend on only a few hundred of them. It's also a contrast with week 4: k-NN keeps every training point to make predictions, while the SVM keeps just the support vectors.
Soft margin and the C parameter
Real data is rarely perfectly separable. One mislabeled point makes the hard-margin problem impossible, or forces a terrible narrow street. The fix is to give each point a slack variable , the amount by which it's allowed to violate the margin, and to charge for it:
- point is on or outside its edge of the street (no violation)
- inside the street but still on the correct side
- misclassified
- hyperparameter: how much each unit of violation costs
The professor names the two parts. depends only on the model, not the data, so it's the regularizer (week 11 is about these). depends on the data, so it's the loss. It's still a QP.
| Large C | Small C | |
|---|---|---|
| Violations | expensive → few | cheap → many |
| Margin | narrow | wide |
| Limit | : the hard-margin SVM | : only matters, so |
| Risk | overfitting (chases noisy points) | underfitting |
This part of the lecture gets tangled ("bigger C, you allow smaller penalty..."). The clean version is the table above, which matches slide 23: large C → less tolerant of violations → smaller margin. C is a hyperparameter; pick it by cross-validation (week 2).
The hinge-loss view
This isn't spelled out on the slides, but it connects the SVM to everything from week 3. At the optimum, each slack is as small as its constraint allows: . Substituting that in removes the constraints:
The term , with , is the hinge loss.
Because this version has no constraints, you can also train it with (sub)gradient descent. The professor mentions this at 32:48, and it's how Géron's SGDClassifier(loss="hinge") works.
The dual problem
"This is somehow like homework, the reading homework for you to understand so-called kernel SVM and the dual formula for the SVM. Please read the textbook." This section and the next are that reading, condensed.
Every constrained optimization problem (the primal) has a partner, the dual, built with one Lagrange multiplier per constraint. For the SVM the two have the same solution, so you can solve either. Setting the Lagrangian's derivatives to zero (Géron, Appendix C) gives two facts:
Substituting back gives the dual, which is again a QP, now in the 's:
(For the hard margin, drop the upper bound: .) A new point is classified by
- Support vectors again: only for support vectors. Every other point has and vanishes from the sum. (This is "complementary slackness": either a constraint is tight or its multiplier is zero.)
- Only dot products appear. The data shows up in training and prediction only through . That one fact is what makes the kernel trick work.
- The dual is also faster when there are fewer training points than features (Géron).
forces . Then , and matching gives for both points. Both are support vectors, as they must be.
Géron's dual (Eq. 5-6, and C-4 in Appendix C) lists only . His own derivation one step earlier (Eq. C-3) produces , and the dual needs it whenever there's a bias term . Without it, the problem is wrong. The version above includes it.
The kernel trick
Some data can't be split by any line. The slides' example is one class inside a circle and the other outside it. The fix is to map the data into a new space where it is linearly separable, and run a linear SVM there:
The catch is that useful maps can produce a huge number of features. The kernel trick avoids ever computing them. Because the dual only needs dot products, replace every with a kernel that computes the dot product in the big space directly from the original vectors.
Take in 2-D. It equals for .
Check with , . Kernel: . Explicit: , , dot product . Same answer, without building .
| Kernel | Notes | |
|---|---|---|
| Linear | the plain linear SVM | |
| Polynomial | all feature products up to degree | |
| Gaussian RBF | the lecture's example (38:00); an infinite-dimensional ; controls how local each point's influence is |
The RBF kernel behaves a lot like a smarter k-NN: each support vector votes with a weight that fades with distance. Like C, the kernel's settings (, ) are hyperparameters to cross-validate.
Using SVMs in practice
- Scale your features. The margin is a distance, so (as with k-NN) a feature measured in big units dominates. Géron shows this explicitly: standardize first.
- Solvers: any QP solver for small problems (
cvxoptin Python,quadprogin MATLAB); in practice scikit-learn'sLinearSVC(linear, scales to big data) orSVC(kernel="rbf")(kernels; training time grows roughly between and in the number of samples, so it suits small to medium datasets). - Tune C (and for RBF) with cross-validation, usually on a log grid like 0.01, 0.1, 1, 10, 100.
- No probabilities by default. An SVM outputs a side of the line, not a probability (unlike logistic regression).
- Further reading the professor recommends: Boyd & Vandenberghe, Convex Optimization (already in the textbook folder) for QPs and duality (Ch. 4–5).
Cheat sheet
| Distance to hyperplane | |
| Margin | distance; after scaling (street width ) |
| Hard margin | s.t. ; convex QP |
| Support vectors | (hard); ; only they matter |
| Soft margin | s.t. |
| C | large → narrow margin, few violations, overfit risk; = hard; pick by CV |
| Hinge loss | ; soft SVM = hinge |
| Dual | , , |
| Recover w | ; from any support vector |
| Kernel trick | replace by ; RBF |
Practice
Q1Among all lines that separate the training data, which one does a (hard-margin) SVM choose?
Q2Distance from to the line ?
Q3A trained hard-margin SVM has . What is the margin (line to nearest point)?
Q4You delete a training point that is far from the boundary (not a support vector) and retrain. The boundary:
Q5Increasing C in a soft-margin SVM generally:
Q6What happens as ?
Q7A point has . Its hinge loss is:
Q8In the dual solution, means point is:
Q9Why does the kernel trick need the dual form?
Q10Class A fills a disk; class B surrounds it. Best SVM approach?
Problem 1: Solve the hard-margin SVM for (0,0) labeled −1, (2,0) labeled +1 and (0,2) labeled +1. Give w, b, the margin, and the α's.
The data is symmetric in , so . Constraints:
(0,0): . (2,0) and (0,2): .
We minimize , so we want as small as possible: is smallest with , giving .
, , margin . All three constraints hold with equality, so all three are support vectors.
α's: . And .
Checked with a QP solver (scikit-learn): w = (1, 1), b = −1, α = (1, 0.5, 0.5).
Problem 2: Show that for 2-D vectors equals with .
.
, which is the same three terms. ∎
The kernel costs one 2-D dot product and a square; the explicit map builds 3-D vectors. For degree in many dimensions, the gap becomes enormous.