Two groups of points, and a straight line to split them. There are many lines that make no mistakes at all, so which one should you draw? This unit's answer is simple to say: draw the widest empty street you can between the two groups, and put the line down its middle. Then we turn that sentence into mathematics. The width becomes 2/∥w∥, the search becomes a bowl with exactly one bottom, and the answer turns out to rest on a few points that touch the street. Last, we bend the street. Lift the points into a bigger space, cut them there with a flat plane, and the cut comes back down as a curve — without ever visiting the big space.
≈ 120 min read + play16 interactive widgets · 8 in 3D · a live solver you can drag20 inline checks🧾 21 proofs, folded away — open "if you want the algebra" when you are ready✍ 16 solved practice problems
It is sports day. The blue house is warming up on one side of the school field, the orange house on the other. The PT teacher must chalk one straight line between them.
Many lines would do. Any line with every blue child on one side and every orange child on the other makes no mistake today.
But a good teacher chalks it down the middle of the widest empty strip. Then a child who steps a little forward tomorrow is still on her own side.
Here is the same problem with points. Twelve points on a page: six blue ones (class +1) and six orange ones (class −1). We want a straight line with all the blue points on one side and all the orange points on the other.
Draw one such line. Now tilt it a little, or slide it a little. It still splits the points perfectly. So there are infinitely many lines with zero mistakes. Counting mistakes on the training points cannot choose between them.
What should choose, then? Think about the next point. It will land somewhere near an old point, but not exactly on top of it. A line that passes within a hair of an old point will get that neighbourhood wrong the moment a point wobbles. A line with a wide, empty buffer on both sides can absorb the wobble.
So here is the whole idea of this unit in one line: pave the widest empty street between the two groups, and draw the line down its middle. No point of either group may stand inside the street. The width of that street is called the margin.
For each tilt, there is a best street: push its two edges outwards until each one touches a point. Then change the tilt and do it again. Try it below.
The widest street, one tilt at a timeFor every tilt the street is already pushed out until it touches a point on each side. Only one tilt gives the widest street.
Try: Slide the tilt slowly and watch the ringed points: they change as the tilt changes. Then press ▶ find the widest and watch the dot on the width curve climb to its peak.
drag the picture to orbit
—
Notice two things. First, the width changes a lot with the tilt: about 0.84 at 20∘, about 1.5 at 70∘, and 2.83 at the best tilt, 45∘. Second, the ringed points change as you tilt. Which points touch the street is a result of the tilt, not something you choose.
Why is the widest street a good choice? Four reasons.
It forgives wobble. Every point can move by up to half the street width in any direction and still stay on its own side.
It picks one answer. Out of infinitely many perfect lines, "widest" picks exactly one.
It travels well to new data. There is real theory saying that the error on new points is controlled by the margin compared with how spread out the data is, not by how many features you measured.
It is cheap to keep. The answer ends up depending only on the few points that touch the street. The points deep inside each group do not matter at all. (Section 9 proves this.)
The realization
margin=2×dnearest
The margin is the width of the widest empty street: twice the distance dnearest from the line to the nearest point. Training error cannot choose between the many perfect lines. The margin can. Among all lines that make no mistake, take the one whose street is widest. Everything else in this unit is turning that sentence into mathematics and solving it.
Pause & predict
Three straight lines all split the training points with zero mistakes. Why can't the number of mistakes pick the best one?
The road ahead. The unit has four acts.
The widest street (§2–§5): measure distances to a line, find the street's width, fix a hidden scale, and write the problem down.
Prices on points (§6–§9): give every point a price, build the boundary out of those prices, solve a second problem that uses only the prices, and meet the few points that hold the street up.
The messy world (§10–§11): let a few points break the rule, pay a fine for it, and watch the hinge loss appear.
The kernel trick (§12–§15): see that the data only ever meets itself through dot products, lift the data so a flat cut becomes a curve, and do it all without visiting the big space.
In one sentence: Many lines make no mistakes, so choose the one with the widest empty street around it — it forgives wobble, it is unique, and it rests on only a few points.
2
The boundary's compass
Imagine this
A straight road runs across a field. You stand somewhere in the grass and want to know how far you are from the road.
You would not walk at a slant. You would walk straight across, at a right angle to the road. That shortest walk is your distance.
So every straight road comes with a hidden arrow: the direction that points straight across it. Know that arrow, and you can measure anything.
A straight line in the plane can be written as w⋅x+b=0. Take the line x1+2x2=6. Move the 6 across: x1+2x2−6=0. So w=(1,2) and b=−6.
For any point x, the number f(x)=w⋅x+b is its score. The score is zero on the line, positive on one side and negative on the other. The classifier says "blue" when the score is positive and "orange" when it is negative.
Fact 1: w points straight across the line. Take two points on the line, p=(6,0) and q=(0,3). Both have score 0. Subtract the two scores and b cancels: w⋅(p−q)=0. Check: p−q=(6,−3) and (1,2)⋅(6,−3)=6−6=0. The arrow p−q runs along the line, and w is at a right angle to it. So w is the "straight across" arrow — the normal.
Fact 2: b only slides the line. Change b and the line moves sideways, staying parallel. It never turns. The tilt is set by w alone.
Fact 3: the score divided by the length of w is the distance. Take the point (4.4,5.2). Its score is 4.4+10.4−6=8.8. The length of w is ∥w∥=1+4=5≈2.236. The true distance to the line is 8.8/2.236≈3.935. The score alone is not a distance; divide by ∥w∥ and it becomes one.
The distance formula, liveDrag the probe. The dashed drop is the straight-across walk, and its length is |f(x)| / ‖w‖.
Try: Drag the probe onto the line and watch the score hit 0. Then turn the b knob: the line slides but never turns. Turn w's angle: now it turns, and the green arrow w^ turns with it, always at a right angle.
drag the probe
—
Two different "margins" hide in this picture, and people mix them up.
Name
Formula
What it is
functional margin
yi(w⋅xi+b)
the raw score, made positive when the point is on its correct side. Not a distance: double w and b and it doubles.
geometric margin
yi(w⋅xi+b)/∥w∥
a real distance, in the units of your data. Double w and b and it does not change.
Multiplying by the label yi=±1 makes both numbers positive exactly when the point is on the correct side. Section 4 is all about the gap between these two.
The realization
d(z)=∥w∥w⋅z+b=∥w∥f(z)
w is the compass: it points straight across the boundary and sets its tilt. b only slides the boundary. And a score becomes a distance only after you divide by ∥w∥.
Pause & predict
How far is the point (6,3) from the line x1+2x2=6, and on which side?
Pause & predict
You keep w=(1,2) but change b from −6 to −10. What happens to the line?
If you want the algebra · 2 proofs, step by step
Prove it · w points straight across the line
Claim. For the line w⋅x+b=0, the vector w is at a right angle to every direction that runs along the line. Changing b moves the line parallel to itself.
1
Take any two points p,q on the line. Both have score zero:
w⋅p+b=0,w⋅q+b=0.Being "on the line" means exactly this.
2
Subtract the second from the first. The b cancels:
w⋅(p−q)=0.A zero dot product means a right angle. And p−q is an arrow from one point of the line to another, so it runs along the line.
3
Every direction along the line is such a difference, so w is at a right angle to all of them: w is the normal. The set {x:w⋅x=−b} for a new b has the same normal, so it is a parallel line, shifted along w.
∎Example: on x1+2x2=6, p=(6,0), q=(0,3) give (1,2)⋅(6,−3)=0.
Prove it · the distance formula
Claim. The signed distance from a point z to the line w⋅x+b=0 is t=∥w∥w⋅z+b — positive on the side w points to.
1
Walk from z straight across, along the unit normal w^=w/∥w∥, a signed distance t, landing at z−tw^. The landing point is on the line:
w⋅(z−tw^)+b=0.The shortest route to a line is the straight-across one, so this t is the distance.
2
Open the bracket, and use w⋅w^=w⋅w/∥w∥=∥w∥2/∥w∥=∥w∥:
w⋅z+b−t∥w∥=0⇒t=∥w∥w⋅z+b=∥w∥f(z).∎For (4.4,5.2) and x1+2x2=6: t=8.8/5≈3.935. The raw score and the distance differ by exactly the factor ∥w∥.
In one sentence: In w⋅x+b=0, w points straight across the line and sets its tilt, b slides it, and the score f(z) divided by ∥w∥ is the true distance.
3
How wide is the street?
Imagine this
Two rows of autos are parked on either side of a road. The road's width is the gap between the two rows.
You could measure from any auto on the left to any auto on the right. Measure at a slant and you get a bigger number. Only the straight-across measurement gives the true width.
That is the whole of this section: the slanted measurements are always at least the true width, and the straight one is exactly it.
Start from the boundary w⋅x+b=0. Push two parallel lines outwards, one to each side, until each one touches the nearest point of its group. Parallel lines share the same w and differ only in the constant:
w⋅x+b=+candw⋅x+b=−c.
Call the touching points x+ (on the +c edge) and x− (on the −c edge). Write both equations and subtract. The b cancels, which is the whole reason we subtract:
w⋅(x+−x−)=2c.
This is one number, a dot product. We want a distance. The tool is the Cauchy–Schwarz inequality: for any two arrows, ∣u⋅v∣≤∥u∥∥v∥, with equality only when they point along the same line. Use it with u=w:
2c⟹∥x+−x−∥=w⋅(x+−x−)≤∥w∥∥x+−x−∥≥∥w∥2c.
Read it in words. Any point of one edge is at least 2c/∥w∥ away from any point of the other edge. And the bound is reached — by the pair of points that face each other straight across, along w. The smallest distance between the two edges is the width of the street:
The Cauchy–Schwarz bound, liveEach point slides along its own edge. The straight-across gap stays pinned; the point-to-point distance can only be bigger.
Try: Drag the blue point along the lower edge and the orange point along the upper edge. Make the orange length as short as you can. It reaches the blue gap only when the joining line runs parallel to the green arrow w.
drag either point along its edge
—
Here w=(−21,−21), b=25, c=1: the edges are x1+x2=3 (score +1) and x1+x2=7 (score −1), so ∥w∥=0.5≈0.707 and the width is 2/0.707≈2.828.
Watch out — the step people botch
From w⋅(x+−x−)=2c it is tempting to write "x+−x−=2c/w". That is not allowed: you cannot divide by a vector. A dot product squashes two arrows into one number, and you cannot un-squash it by dividing.
The conclusion is also wrong in substance: the two touching points can be much further apart than the width. Only the inequality, or a projection onto w/∥w∥, turns the number 2c into a width.
The realization
street width=∥w∥2c
Subtracting the two edge equations kills b and leaves w⋅(x+−x−)=2c. Cauchy–Schwarz turns that single number into a distance, and tells us it is the shortest distance across — which is exactly what the width of a street means.
Pause & predict
A classmate writes: "w⋅(x+−x−)=2c, so x+−x−=2c/w, so the width is 2c/∥w∥." What is wrong?
If you want the algebra · 1 proof, step by step
Prove it · the street is 2c/‖w‖ wide
Claim. If x+ lies on w⋅x+b=c and x− on w⋅x+b=−c, then ∥x+−x−∥≥2c/∥w∥, with equality exactly when x+−x− points along w. So the smallest distance between the two edges — the width — is 2c/∥w∥.
1
Subtract the two edge equations; b cancels:
w⋅x++b−(w⋅x−+b)=c−(−c)⟹w⋅(x+−x−)=2c.
2
Cauchy–Schwarz says ∣u⋅v∣≤∥u∥∥v∥, with equality only when u and v are parallel. With u=w, v=x+−x−:
2c=∣w⋅(x+−x−)∣≤∥w∥∥x+−x−∥, so ∥x+−x−∥≥∥w∥2c.We may divide by ∥w∥, a positive number. Dividing by the vector w is what is not allowed.
3
The bound is reached. Start at any x+ and walk straight across by x−=x+−∥w∥22cw. Its score is c−∥w∥22c∥w∥2=−c, so it lies on the other edge, and its distance from x+ is ∥w∥22c∥w∥=∥w∥2c.
∎The smallest distance between the two edges is the width of the street, so the width is 2c/∥w∥. One inequality did two jobs: it gave the number, and it proved nothing is closer.
In one sentence: The street's edges are w⋅x+b=±c; subtracting leaves w⋅(x+−x−)=2c, and Cauchy–Schwarz turns that into the width 2c/∥w∥, reached only straight across.
4
The scale is yours to choose
Imagine this
A cricket pitch is 22 yards long. In feet that is 66. In inches, 792. The pitch did not change at all. Only the numbers did.
The street has the same kind of freedom. Its equations can be written with many different sets of numbers, and the street stays exactly where it is. So we may pick the most convenient numbers.
Section 3 left one loose end: the constant c. Take the three lines
w⋅x+b=+c,w⋅x+b=0,w⋅x+b=−c,
and multiply every number by k=3. The first line becomes 3w⋅x+3b=3c. Divide by 3 and you are back where you started. It is the same set of points. All three lines stay put. But every number has tripled: ∥w∥, c and every score.
Quantity
Before
After multiplying by k
Real geometry?
the three lines, as sets of points
—
identical
✔ real
∥w∥
∥w∥
k∥w∥
✘ your choice
the constant c
c
kc
✘ your choice
the scores yif(xi)
zi
kzi
✘ your choice
the width 2c/∥w∥
2c/∥w∥
2kc/(k∥w∥)=2c/∥w∥
✔ real
So c and ∥w∥ mean nothing on their own; only their ratio is geometry. Since the choice is ours, choose k=1/c. That makes the constant exactly 1:
w⋅x+b=+1,w⋅x+b=0,w⋅x+b=−1.
This is the canonical form. Two gifts follow. The width is now 2/∥w∥, so "shrink ∥w∥" finally means "widen the street". And the nearest points score exactly 1, so every point obeys a score of at least 1.
The same thing happens in three dimensions, where the street is a slab between two parallel planes. Slide k below and watch every number move while the slab stays frozen.
Rescale everything; nothing movesA slab in 3-D between the planes x₁+x₂+x₃ = 2 and = 6. Multiply w, b and c by k: the arrow for w stretches, every score changes, the slab does not.
Try: Drag k from 1 to 3. The green arrow kw grows three times longer, the scores read ±3, and the slab does not move a millimetre. Then press look edge-on: the whole 3-D picture collapses to the familiar 2-D street.
drag the picture to orbit
—
In canonical form the rule for a correct point splits by class: blue points need w⋅xi+b≥+1, orange points need w⋅xi+b≤−1. Multiply the orange rule by −1 (which flips the inequality) and it reads −(w⋅xi+b)≥1. But for an orange point yi=−1, so that is yi(w⋅xi+b)≥1. The blue rule is the same sentence with yi=+1. One inequality does the work of two:
yi(w⋅xi+b)≥1for every point i.
This is the only reason SVMs label the classes ±1 and not 0 and 1: the label does the sign-flipping for you.
One more trap. Why not simply make the smallest score as large as possible? Because of this very table. Multiply w and b by a million and every score is a million times bigger, while the line has not moved. An optimiser would run k→∞ and report infinite confidence in a line it never improved. Fixing the scale — score 1 for the nearest points, then make ∥w∥ small — is what makes the question sensible.
The realization
width=∥w∥2yi(w⋅xi+b)≥1
Scaling (w,b,c) by k changes every number but not the street. Only the ratio 2c/∥w∥ is real. Set c=1 and "widest street" becomes "smallest ∥w∥".
Pause & predict
A street in canonical form has ∥w∥=0.5. You multiply w, b and c by k=3. Which statement is true?
Pause & predict
Why do SVMs use the labels +1 and −1 instead of 1 and 0?
If you want the algebra · 2 proofs, step by step
Prove it · rescaling moves nothing
Claim. For any k>0, the triple (kw,kb,kc) describes the same three lines as (w,b,c), and the width 2c/∥w∥ is unchanged. So we may choose c=1.
1
A point x lies on the new + edge when kw⋅x+kb=kc. Divide by k>0: w⋅x+b=c. Same condition, same points. The same holds for the other two lines.
An equation and a multiple of it describe the same set.
2
The numbers change: ∥kw∥=k∥w∥, the constant becomes kc, each score yif(xi) becomes kyif(xi). But the width
∥kw∥2(kc)=k∥w∥2kc=∥w∥2c
does not.
3
Pick k=1/c. The new constant is 1, the nearest points score exactly 1, and the width is 2/∥w∥.
∎In the 3-D slab: w=(21,21,21), b=−2, ∥w∥=23, thickness 2/∥w∥=4/3≈2.309 — which is also the distance between the planes x1+x2+x3=2 and =6, namely 4/3.
Prove it · one inequality replaces two
Claim. With labels yi=±1, "w⋅xi+b≥1 for blue and ≤−1 for orange" is the same as yi(w⋅xi+b)≥1 for every i.
1
Blue, yi=+1: yi(w⋅xi+b)=w⋅xi+b, so the two statements are identical.
2
Orange, yi=−1: multiply w⋅xi+b≤−1 by −1, which flips the inequality: −(w⋅xi+b)≥1, and −(w⋅xi+b)=yi(w⋅xi+b).
∎A label of 0 would destroy this: 0× anything is 0, which can never be ≥1.
In one sentence: Multiplying (w,b,c) by any k leaves the street untouched, so we pin the nearest scores to 1; then the width is 2/∥w∥ and every point obeys yi(w⋅xi+b)≥1.
5
The problem, stated — and why we square
Imagine this
You drop a marble into a round steel bowl from Mummy's kitchen. It rolls and comes to rest at the one lowest spot. Drop it again from anywhere, and it ends up at the same spot.
Now put a few straight cardboard walls inside the bowl that the marble may not cross. It rolls until it rests against a wall. Again there is one resting place, and every drop finds it.
That is what the SVM problem looks like: a bowl, straight walls, and one answer.
Everything so far fits in one line. We want the widest street that keeps every point on its correct side and outside the street:
w,bmax∥w∥2subject toyi(w⋅xi+b)≥1 for every i.
That is correct, but the thing being maximised is awkward. Three rewrites make it pleasant, and none of them changes whichw wins:
Making 2/∥w∥ big is making ∥w∥ small. A fraction with a fixed top gets bigger as its bottom gets smaller.
Making ∥w∥ small is making ∥w∥2 small. Squaring never reorders positive numbers.
Put a 21 in front. A positive constant cannot move the lowest point, and it makes the slope come out as w instead of 2w.
The result is the form everyone actually solves, the hard-margin SVM:
w,bmin21∥w∥2subject toyi(w⋅xi+b)≥1 for every i.
The picture below makes this real for four points: blue (1,2) and (2.5,0), orange (−1,−1) and (−1,1). Fix b at its best value −0.6, so only w=(w1,w2) is free. The floor is the w-plane. The bowl above it is 21∥w∥2. Each data point's rule yi(w⋅xi+b)≥1 is a straight wall on that floor. The allowed region glows.
A bowl, four walls, one resting placeThe floor is the plane of all possible w. Each point cuts it with a straight wall; the ball rolls to the lowest allowed spot — and that spot is the SVM.
Try: Press ▶ drop the ball and watch it slide down to a wall and then along it into the corner at w=(0.8,0.4). Then press add an overlapping point: a blue point lands between the two orange ones, and the glowing region disappears.
drag the picture to orbit
—
Three objectives, one winner 1-D: ‖w‖ = |w|
Why is this such good news? The bowl 21∥w∥2 curves up the same amount in every direction, so it has exactly one bottom. Each wall is straight, and a region cut out by straight walls has no dents. A bowl over a dent-free region is called a convex quadratic program, and for these every local lowest point is the global lowest point. There are no false valleys to get stuck in. Train an SVM twice on the same data and you get exactly the same answer, every time.
Watch out — say the right reason for squaring
A common answer is "we square because 2/∥w∥ is not convex". Careful. We are maximising that, so the property we would want is not convexity anyway. And ∥w∥ itself is convex — every length is. Minimising ∥w∥ is already a fine convex problem.
The real reason: ∥w∥ has a sharp point at w=0, like the tip of a cone, where there is no slope at all. 21∥w∥2 is smooth everywhere, its slope is simply w, and that turns the problem into a quadratic program with fast, reliable solvers.
Two more things to hold on to
Support vectors are an output, never an input. You solve the problem first. Only then do you look at which points ended up exactly on the street's edges. You never pick them in advance — you could not, since you do not know them until the problem is solved.
A hard margin fails hard. If even one point sits among the other group, no line satisfies every wall. The allowed region is empty and the problem has no answer at all — not a bad one, none. Section 10 fixes that.
The realization
w,bmin21∥w∥2s.t.yi(w⋅xi+b)≥1
A bowl with straight walls. Same winner as "maximise 2/∥w∥", but smooth, with exactly one bottom. The points pressing against the walls at that bottom are the support vectors.
Pause & predict
Why do we minimise 21∥w∥2 instead of ∥w∥?
If you want the algebra · 1 proof, step by step
Prove it · the three rewrites keep the winner
Claim. Under the same constraints, max2/∥w∥, min∥w∥, min∥w∥2 and min21∥w∥2 are all won by the same (w,b).
1
Every allowed w is non-zero (with w=0 every score is yib, and b cannot be ≥1 for one class and ≤−1 for the other). On positive numbers, t↦2/t is strictly decreasing, t↦t2 is strictly increasing, and t↦21t is strictly increasing.
A strictly increasing function never changes which input is smallest; a strictly decreasing one turns the smallest into the largest.
2
So ∥w1∥<∥w2∥⟺21∥w1∥2<21∥w2∥2⟺2/∥w1∥>2/∥w2∥. Whichever w wins one contest wins all four.
The values differ; the winner does not.
3
Why the squared form is the one to solve: in one coordinate, ∣w∣ has slope −1 on the left of 0 and +1 on the right — no slope at 0. And 21∥w∥2=21∑jwj2 has partial derivatives ∂/∂wk=wk, smooth everywhere; its gradient is w itself and its second derivatives form the identity matrix, so it curves up equally in every direction and has exactly one bottom.
∎In the four-point picture: the corner w=(0.8,0.4) gives 21∥w∥2=21(0.64+0.16)=0.4 and width 2/0.8=5≈2.236, the distance between the two touching points (1,2) and (−1,1).
In one sentence: The widest street is the lowest point of the bowl 21∥w∥2 inside straight walls yi(w⋅xi+b)≥1 — a convex quadratic program with exactly one answer, and none at all if the groups overlap.
6
Every point gets a price tag
Imagine this
A crowd leans on a rope barrier at a cricket ground. People standing back from the rope put no force on it at all. Only the ones pressed right against it push.
If you want to know where the rope will settle, you do not need to know about the whole crowd. You need the few who touch it, and how hard each one pushes.
Section 5 left us with a bowl and walls. Walls are awkward to work with directly, so we do what Unit 11 taught (§8–§11): turn each wall into a price. Every training point i gets its own number αi≥0 (read "alpha"). Write each wall as "something ≥0":
gi(w,b)=yi(w⋅xi+b)−1≥0,
and fold all the walls into one expression, the Lagrangian:
L(w,b,α)=21∥w∥2−i∑αi[yi(w⋅xi+b)−1],αi≥0.
Why is this the same problem? Fix a street (w,b) and ask the prices to make L as large as they can. Look at one point:
If the point is…
its bracket is…
the best price αi is…
inside the street or on the wrong side, yif(xi)<1
negative
+∞: L blows up — this street is ruled out
comfortably outside, yif(xi)>1
positive
0: any price would only lower L
exactly on the edge, yif(xi)=1
zero
free: any αi≥0 gives the same L
So the largest L equals 21∥w∥2 for a legal street and +∞ for an illegal one. Minimising that over all streets is exactly our problem. The walls did not disappear; they became prices that punish any trespass without limit.
Read αi as how hard point i pushes on the street. A point standing back pays nothing and pushes nothing. A point pressed against an edge has a real price. Drag the points below and watch the prices.
Who is pushing the street?Twelve points and their solved street. Each point's price αᵢ is its pressure bar. A live solver re-solves the street every time you move a point.
Try: Drag a point from deep inside a group — its price stays 0 and the street does not move, until you drag it into the street. Then drag one of the gold-ringed points: the whole street follows it.
drag any point
—
At the answer, four conditions hold together. They are called the KKT conditions (after Karush, Kuhn and Tucker). For this problem the bowl is convex and the walls are straight, so they are not just necessary: any (w,b,α) that satisfies all four is the answer.
Condition
In symbols
In words
1 · stationarity
∂L/∂w=0,∂L/∂b=0
the pushes are in balance; gives w=∑iαiyixi and ∑iαiyi=0 (§7)
2 · primal feasibility
yi(w⋅xi+b)≥1
the street really is legal
3 · dual feasibility
αi≥0
a point can push the street away, never pull it in
4 · complementary slackness
αi[yi(w⋅xi+b)−1]=0
for each point, room to spare or a price — never both
Watch out — two sign conventions
You will also see L=21∥w∥2+∑iαi[1−yi(w⋅xi+b)]. It is the same function, since +α(1−z)=−α(z−1). Either is fine. Switching between them in the middle of a calculation is where sign mistakes are born. This unit uses the minus form throughout.
Every point gets a price αi: how hard it pushes on the street. Points with room to spare pay nothing. Only points pressed against an edge carry a price.
Pause & predict
At the answer, a point has score yif(xi)=2.4. What is its price αi?
If you want the algebra · 1 proof, step by step
Prove it · the prices rebuild the walls
Claim. For a fixed street (w,b), α≥0maxL(w,b,α) equals 21∥w∥2 if every yi(w⋅xi+b)≥1, and +∞ otherwise. So minw,bmaxα≥0L is exactly the hard-margin problem, and at its answer αi[yif(xi)−1]=0 for every i.
1
Write gi=yi(w⋅xi+b)−1, so L=21∥w∥2−∑iαigi. The prices enter separately, one term −αigi each, so maximise each term on its own.
No price appears in any other point's term.
2
If gi<0 (a trespasser), −αigi=αi∣gi∣ grows without limit as αi→∞. If gi>0, −αigi≤0 and the best choice is αi=0. If gi=0, the term is 0 for every αi.
3
So the maximum is +∞ as soon as one wall is broken, and otherwise it is 21∥w∥2+0. Minimising over streets never picks an infinite value, so it solves the original problem. In every case the best prices satisfy αigi=0: either gi=0 or αi=0.
∎That last line is complementary slackness, the fourth KKT condition. It came for free from "the prices try to make L as large as possible".
In one sentence: Turn each wall into a price αi≥0; the prices punish any trespass without limit, and at the answer only the points pressed against the street carry a price.
7
The boundary is built from the data
Imagine this
A tug-of-war at the village fair. The rope does not move when the two teams pull equally hard. If one side pulled harder, the rope would slide, and the match would not be over.
The street works the same way. Each price is a pull. At the answer the pulls from the two classes cancel, and the direction of the street is made of those very pulls.
Stationarity means: the slope of L is zero in every direction of w and b. Two facts do all the work, both proved in the drawer below. The slope of 21∥w∥2 is w, and the slope of w⋅x is x. So:
Read the first one slowly. The answer w is not some new direction invented from nothing. It is the training points themselves, added up with weights. Blue points (yi=+1) pull w towards themselves; orange points (yi=−1) push it away; αi says how hard.
For our twelve points only three prices are not zero: α=81 for (1,3) and (3,5), and α=41 for (4,2). Build w:
The second fact is the tug-of-war: the blue prices add to 81+81=41, the orange price is 41. Balanced. If they were not, you could slide the street sideways (change b) and do better, so it would not be the answer.
w, assembled from its support vectorsEach surviving point adds the arrow αᵢyᵢxᵢ. Laid tip to tail they land on w. The beam weighs the two classes' prices.
Try: Press ▶ build w. Then drag the orange price α3 up to 0.35: the beam tips (the pulls no longer balance) and w swings away from the true answer.
—
Why this line matters most
Sparsity. Every zero price deletes its point from the sum. Most prices are zero (§9).
Calm about far-away points. A point far on its correct side has αi=0. Move it further away and w does not change at all.
Kernels. If w is built from data points, then w⋅x is built from dot products between data points — and a dot product is something you can swap out. That is §12–§15, hiding in this one line.
The realization
w=i∑αiyixi,i∑αiyi=0
The direction of the street is a weighted sum of the training points, and the two classes' prices balance like a tug-of-war that has come to rest.
Pause & predict
A solver reports α=0.25 for (2,2) with y=+1, α=0 for (4,1) with y=+1, and α=0.25 for (0,0) with y=−1. What is w?
If you want the algebra · 4 proofs, step by step
Prove it · Lemma A: the slope of ½‖w‖² is w
Claim.∇w21∥w∥2=w.
1
Write it as a sum: 21∥w∥2=21∑j=1dwj2. Differentiate with respect to one coordinate wk: every term with j=k is a constant, and ∂(wk2)/∂wk=2wk:
∂wk∂21j∑wj2=21⋅2wk=wk.∎Stack the d answers: the gradient is (w1,…,wd)=w. This is where the 21 pays for itself. Picture: on the bowl, the uphill arrow at any point is the position arrow itself.
Prove it · Lemma B: the slope of w·x is x
Claim. For a fixed x, ∇w(w⋅x)=x.
1
w⋅x=∑jwjxj. Only the j=k term contains wk, and it is wkxk, whose slope in wk is xk. Stacking gives x.
∎
Prove it · stationarity in w
Claim.∂L/∂w=0 gives w=∑iαiyixi.
1
Open the bracket in L:
L=21∥w∥2−i∑αiyiw⋅xi−bi∑αiyi+i∑αi.The last two terms contain no w, so their slope in w is zero.
2
Lemma A on the first term, Lemma B on each term of the second (αiyi is just a number):
∂w∂L⇒w=w−i∑αiyixi=0=i∑αiyixi.∎
Prove it · stationarity in b
Claim.∂L/∂b=0 gives ∑iαiyi=0.
1
In the opened-up L, exactly one term contains b: −b∑iαiyi. It is a straight line in b, so
∂b∂L=−i∑αiyi=0⇒i∑αiyi=0.∎Physically: sliding b moves the whole street sideways. If the two classes' pushes did not cancel, sliding would still help, so it could not be the answer. In a problem with unknowns α and b, this is often the equation you are missing.
In one sentence: Setting the slopes of L to zero gives w=∑iαiyixi — the street's direction is built from the points themselves — and ∑iαiyi=0, the balance of the two classes' pushes.
8
The dual — a problem only in the prices
Imagine this
You can plan a wedding by choosing the hall, the food and the decorations. Or you can hand the whole job to a caterer and only argue about prices.
The second way can be easier — and if the deal is fair, you end up with the same wedding. The SVM has such a "prices only" version too, and it is the version everybody solves.
Take the two facts from §7 and put them back into L. Every trace of w and b disappears (the steps are in the drawer), and what is left is a problem in the prices alone — the dual:
A tiny example. Two points: (1,1) blue and (−1,−1) orange. The dot products are x1⋅x1=2, x2⋅x2=2, x1⋅x2=−2. The balance condition α1−α2=0 makes both prices equal, call it α. Then
D(α)=2α−21[α2(2)+α2(2)+2α2(−1)(−2)]=2α−4α2.
The top of this hill is where the slope 2−8α is zero: α=41, with D=21−41=41. Rebuild the street: w=41(1,1)−41(−1,−1)=(21,21). A point on the edge scores exactly 1: (21,21)⋅(1,1)+b=1 gives b=0. The width is 2/∥w∥=2/0.707=22≈2.83 — exactly the distance between the two points, as it must be.
And a free check: the primal value is 21∥w∥2=21⋅21=41. The dual peak is also 41. For a convex problem like this, the two always agree (strong duality). Compute both, and if they differ, you made a slip.
The dual objective, and the line that binds itThe height is D(α). Only the prices on the glowing balance line are allowed; the peak along it is the answer.
Try: On two points, slide α along the balance line and watch the bead climb to the peak at 41. Notice the whole ridge is equally high — only the balance line picks one point on it. Then open three points: the free peak asks for a negative price, so the answer sits on the wall α3=0.
drag the picture to orbit
—
Sit with what changed between the two versions:
Primal (street)
Dual (prices)
unknowns
w and b: one per feature, plus one
α1,…,αn: one per training point
data enters as
the coordinates of each xi
only the dot products xi⋅xj
zeros
none — w is dense
most αi come out exactly 0
That middle row is the most important line in the subject. Hand a solver the table of numbers xi⋅xj, throw the original points away, and it still finds the answer. Section 12 opens that door.
A hill in the prices alone. Its peak equals the primal minimum (a free check), and the data appears only through dot products.
Pause & predict
For the two points (1,1) blue and (−1,−1) orange, the dual along the balance line is D(α)=2α−4α2. What are α and the primal value 21∥w∥2?
If you want the algebra · 2 proofs, step by step
Prove it · from L to the dual
Claim. Substituting w=∑iαiyixi and ∑iαiyi=0 into L gives D(α)=∑iαi−21∑i,jαiαjyiyj(xi⋅xj).
1
Start from L=21w⋅w−∑iαiyi(w⋅xi)−b∑iαiyi+∑iαi. The b term is b⋅0 by the balance condition.
Without the balance condition b would still be sitting here and the substitution would fail.
2
Pull w out of the middle sum: ∑iαiyi(w⋅xi)=w⋅∑iαiyixi=w⋅w. So
L=21w⋅w−w⋅w+∑iαi=∑iαi−21w⋅w.Half minus one is minus a half: that sign flip is why the dual is a maximisation.
3
Expand w⋅w with two separate counters, because squaring a sum makes every pair meet:
w⋅w=(i∑αiyixi)⋅(j∑αjyjxj)=i,j∑αiαjyiyjxi⋅xj.∎The constraints on the prices remain: αi≥0 and ∑iαiyi=0. The dual value at any allowed α is a lower bound on the primal; at the peak the two are equal.
Prove it · the two-point shortcut
Claim. For one blue point x1 and one orange point x2, α1=α2=∥x1−x2∥22, and the width equals ∥x1−x2∥.
1
Balance gives α1=α2=α. The double sum has four terms: α2∥x1∥2+α2∥x2∥2−2α2x1⋅x2=α2∥x1−x2∥2. So
D(α)=2α−21∥x1−x2∥2α2.
2
D′(α)=2−∥x1−x2∥2α=0 gives α=2/∥x1−x2∥2. Then w=α(x1−x2), so ∥w∥=2/∥x1−x2∥ and the width 2/∥w∥=∥x1−x2∥.
∎For (1,1) and (−1,−1): ∥x1−x2∥2=8, so α=41 and the width is 8=22. Any two-point problem becomes a five-second problem.
In one sentence: Substituting w=∑αiyixi and ∑αiyi=0 back into L leaves a hill in the prices alone, whose peak equals the primal minimum and which sees the data only through dot products.
9
Support vectors — the few points holding up the street
Imagine this
A shamiana is held up by a handful of bamboo poles. The rest of the ground under it could be cleared of every chair and table, and the tent would stand exactly as before.
Pull out even one pole, though, and the roof sags into a new shape. The poles are the only things that matter.
One condition does all the interesting work — complementary slackness:
αi[yi(w⋅xi+b)−1]=0.
A product is zero only if one of its factors is. So every training point is in one of three places:
Where the point sits
score yif(xi)
price αi
effect on the street
outside the street
>1
=0
none at all — delete it and nothing moves
exactly on an edge
=1
≥0
a support vector when αi>0: it holds the street up
inside the street
<1
—
impossible with a hard margin (§10 allows it)
A support vector is a training point with αi>0. It must sit on an edge, and it is one of the points w is built from. Everything else could be deleted. To classify a new point you only need the support vectors:
f(x)=i∈SV∑αiyi(xi⋅x)+b.
This is why kernel SVMs are practical at all: a million training points, a few hundred support vectors, and prediction only looks at those.
The answer depends on a few pointsA live SVM on twenty points. Add, drag or delete points; the street re-solves as you move. Gold rings mark the support vectors, with their prices.
Try: Press delete every non-support point: seventeen points vanish and the street does not move by a hair. Then choose delete and click a gold-ringed point: now the street jumps.
click to
tap to add or delete · drag to move
—
class +1class −1support vectorstreet edgeboundary
Watch out — "on the edge" is not the same as "support vector"
Complementary slackness says: a price above zero forces the point onto an edge. It does not say the reverse. A point can sit exactly on an edge and still have αi=0. It touches the street but does not push; delete it and nothing changes.
Example: (1,1) and (2,0) blue, (0,0) orange. The answer is w=(1,1), b=−1, and all three points score exactly 1. But the prices come out α=(1,0,1): (2,0) is on the edge with a zero price. The safe sentence: support vectors are the points with αi>0; they always lie on an edge, but not every point on an edge is one.
Find the widest street → it collides with a few points → those are the support vectors → the whole model can be rebuilt from them alone. Every arrow runs forward. You never choose them; the solution hands them to you.
Pause & predict
After training, a point sits exactly on the +1 edge but its price is αi=0. Is it a support vector, and what happens if you delete it?
Pause & predict
A trained SVM has 10 000 training points and 30 support vectors. You delete the other 9 970 points and train again. What do you get?
If you want the algebra · 1 proof, step by step
Prove it · far-away points can be deleted
Claim. Let (w,b,α) be the answer on a data set. Delete any points with αi=0. The same (w,b) with the remaining prices is the answer on the smaller set.
1
Check the four KKT conditions on the smaller set. Stationarity: w=∑αiyixi and ∑αiyi=0 did not use the deleted points, since their terms were 0⋅yixi. Primal feasibility: the remaining points still score at least 1 — nothing about them changed. Dual feasibility and complementary slackness: unchanged for the points that remain.
Fewer points means fewer conditions to satisfy, and none of the remaining ones changed.
2
For a convex problem, satisfying all four KKT conditions means being the answer. So the street is the same.
∎The reverse fails: delete a point with αi>0 and stationarity breaks, so the old street is no longer the answer — it moves.
In one sentence: Complementary slackness splits the points into those with room (price 0, deletable) and those pressed on an edge; the few with a positive price — the support vectors — hold the street up on their own.
10
Soft margin — allowing a few trespassers
Imagine this
A traffic constable keeps a lane clear. In a perfect world nobody ever stops in it. In real Bengaluru, a few autos always do.
A sensible rule is not "the lane must be perfectly empty, or there is no lane". It is: stop inside if you must, but pay a fine for every metre you intrude. Now the constable can keep a wide lane and still deal with the odd rule-breaker.
The hard margin fails hard. Real data is noisy: one blue point lands among the orange ones, and suddenly no line satisfies every wall — the problem has no answer at all (§5). The fix keeps the same rule but gives every point a small allowance ξi (the Greek letter xi), its slack:
yi(w⋅xi+b)≥1−ξi,ξi≥0.
Think of ξi as a record of how far point i breaks the old rule, measured in half-street widths. Read its value like this:
ξi
the rule becomes
where the point is
0
yif(xi)≥1
the old rule: outside the street, or exactly on its edge
between 0 and 1
yif(xi)≥1−ξi>0
inside the street, but still on its own side — still classified correctly
1
yif(xi)≥0
exactly on the centre line
more than 1
the right side is negative
crossed to the wrong side — misclassified; the bigger ξi, the deeper
If slack were free, the optimiser would cheat: make every ξi huge and pave a street as wide as the world. So every unit of slack costs a fine C>0:
w,b,ξminwiden the street21∥w∥2+total fineCi∑ξis.t.yi(w⋅xi+b)≥1−ξi,ξi≥0.
Two wishes now pull against each other. The first term wants a wide street. The second wants nobody inside it. C is the exchange rate between them.
Now the surprise. Run the same Lagrangian-and-dual walk as §6–§8 with one extra family of prices μi for the rule ξi≥0. Setting the slope in ξi to zero gives αi+μi=C. Since μi≥0, that means αi≤C. Everything else is letter for letter the hard-margin dual:
The slack variables have vanished. The only change is a ceiling on every price. In a hard margin one badly placed point can push infinitely hard — that is why one outlier wrecks everything. With a soft margin nobody can push harder than C. That ceiling is the robustness.
The fine dialSix blue and six orange points, plus one rogue blue point near the orange group. Each red pillar is a point's slack ξᵢ — how far it trespasses. Turn the fine C.
Try: Sweep C from 0.01 up to 1000. At small C the street is wide and the rogue point simply stands inside it (a tall red pillar). As C grows the fine bites, the pillars shrink, and the street narrows until it honours the rogue point exactly — the hard margin.
drag the picture to orbit
—
free price, 0 < α < Cat the ceiling, α = C
small finelarge fine
Reading C. A small fine makes cheating cheap: the optimiser buys a wide street and shrugs when a few points step inside or even cross. Wide street, more support vectors, a calm boundary that ignores single points. A large fine makes every unit of slack expensive: the street narrows until nobody trespasses. As C→∞ you get the hard margin back exactly. So C runs opposite to the λ of ridge regression: big C means less smoothing, not more. In practice C is chosen by trying several values on held-out data.
Reading the prices. With the ceiling, complementary slackness gives three kinds of points:
price
slack and score
where the point is
αi=0
ξi=0, yif(xi)≥1
outside the street — not a support vector
0<αi<C
ξi=0, yif(xi)=1
exactly on an edge — a free support vector
αi=C
ξi≥0, yif(xi)≤1
on the edge, inside the street or across the line — a bounded support vector
One practical rule follows. b is found exactly as before, b=ys−∑iαiyi(xi⋅xs) — but only from a free support vector, where the score is known to be exactly 1. A bounded one may be inside the street, and would give the wrong b.
The realization
min21∥w∥2+Ci∑ξi⟺the same dual with 0≤αi≤C
Let points trespass, but fine themC per unit. In the dual the fine becomes a ceiling on how hard any one point can push. Small C: wide and forgiving. Large C: narrow and strict. C→∞: the hard margin.
Pause & predict
After training, a point has slack ξi=1.4. Where is it?
Pause & predict
You lower the fine C from 100 to 0.1. What usually happens?
If you want the algebra · 1 proof, step by step
Prove it · the soft-margin dual, in outline
Claim. The dual of min21∥w∥2+C∑iξi s.t. yi(w⋅xi+b)≥1−ξi, ξi≥0 is the hard-margin dual with the extra condition αi≤C; and the three price regimes follow.
1
Two families of walls, two families of prices: αi≥0 for the margin rule, μi≥0 for ξi≥0:
L=21∥w∥2+Ci∑ξi−i∑μiξi−i∑αi(zi−1+ξi), where zi=yi(w⋅xi+b) is point i's score.
2
The slopes in w and b are exactly as before: w=∑αiyixi, ∑αiyi=0. The only terms with ξi are Cξi−αiξi−μiξi, so
∂ξi∂L=C−αi−μi=0⇒αi+μi=C.
Since μi≥0, this says αi≤C.
3
Substitute. All the ξi terms collect into ∑iξi(C−αi−μi)=0, every b term dies by the balance condition, and the rest is the hard-margin algebra of §8. The dual is the same hill with the box 0≤αi≤C.
4
The regimes. Complementary slackness now has two parts: αi[yif(xi)−1+ξi]=0 and μiξi=0. If αi=0 then μi=C>0, so ξi=0 and yif≥1. If 0<αi<C then μi>0, so ξi=0, and the bracket is zero: yif=1. If αi=C then μi=0, ξi≥0 and yif=1−ξi≤1.
∎Only the middle case pins the score at exactly 1 — which is why b must be read off a free support vector.
In one sentence: Give each point a slack ξi, fine it C per unit, and the dual stays the same except for a ceiling 0≤αi≤C — the knob that trades a wide street against trespassers.
11
The hinge loss falls out of the slack
Imagine this
A phone plan: the first 2 GB are free. After that you pay ₹10 for every extra GB. The bill is flat at zero, then rises in a straight line.
Nobody sat down and chose that shape for the SVM. It falls out of the slack by itself — and it has exactly this "free, then a straight line" look.
Write zi=yi(w⋅xi+b) for the score of point i. The soft rule zi≥1−ξi says ξi≥1−zi. We also asked ξi≥0. So the slack has two floors, and since every unit of slack costs C, the optimiser never pays more than the higher floor:
ξi=max(0,1−zi).
This is the hinge loss. Put in a few scores:
score zi
2
1
0.5
0
−0.5
−2
hinge loss ξi
0
0
0.5
1
1.5
3
where it is
well outside
on the edge
inside, correct side
on the centre line
wrong side
wrong side, far
Put the hinge back into the problem and the constraints disappear altogether. What is left is the form most machine-learning books start from — a regulariser plus a loss, like every other classifier:
w,bmin21∥w∥2+Ci∑max(0,1−yi(w⋅xi+b)).
Drag a point across the streetLeft: a street and one point. Right: its score z on the hinge (solid) and on the "count the mistakes" loss (dashed).
Try: Drag the point from far outside, through the street, across the centre line and beyond. The hinge stays flat at 0 until the edge, then climbs one-for-one. The counting loss does nothing, then jumps.
put the score at
—
Why not simply count mistakes? Because counting is flat everywhere with a cliff at zero. A slope-following method stands on flat ground and learns nothing about which way to go. The hinge has a slope exactly where it matters — inside the street and beyond — and is exactly zero beyond the edge. That flat zero is what makes most prices vanish, and so it is what gives an SVM its few support vectors.
The realization
ξi=max(0,1−zi)zi=yi(w⋅xi+b)
The hinge loss is not a design choice. It is the cheapest slack that obeys both floors: zero when a point is safely outside the street, growing one-for-one as it walks in and across.
Pause & predict
A point has score z=0.5. What is its hinge loss, and what does the 0/1 "count the mistakes" loss say?
If you want the algebra · 1 proof, step by step
Prove it · the slack is the hinge
Claim. At the soft-margin answer, ξi=max(0,1−yi(w⋅xi+b)) for every i. So the problem equals the unconstrained min21∥w∥2+C∑imax(0,1−yif(xi)).
1
Fix (w,b) and write zi=yi(w⋅xi+b). The constraints on ξi are ξi≥1−zi and ξi≥0, that is ξi≥max(0,1−zi).
Rearranging zi≥1−ξi moves ξi to the left; the inequality keeps its direction.
2
The objective charges Cξi with C>0, and each ξi appears in nothing else. So the cheapest allowed value is the floor: ξi=max(0,1−zi). Put it in and the constraints are gone.
∎Check the table: z=2→0, z=1→0, z=0.5→0.5, z=0→1, z=−0.5→1.5, z=−2→3.
In one sentence: The cheapest slack that obeys both floors is ξi=max(0,1−zi) — the hinge loss, flat beyond the edge and a straight slope inside, which turns the SVM into "regulariser plus loss".
12
Dot products are everywhere — and the classifier is a vote
Imagine this
A new student joins the class, and the teacher must guess which house she will fit into. The teacher asks a few senior students to vote.
Each voter's say depends on three things: how important that voter is, which house the voter is in, and how similar the new student is to the voter. Add up the votes, and the sign tells you the house.
Look back at the dual (§8). The data appears only as dot productsxi⋅xj — never a single coordinate on its own. Now look at how the trained machine classifies a new point x. Put w=∑iαiyixi into f(x)=w⋅x+b:
Again, only dot products. And read it as a vote. Each support vector votes for its own side (yi=±1), with a strength set by its importance αi and by how similar the new point is to it. A dot product is a similarity score — Unit 3's "agreement" between two lists. Points with αi=0 do not vote at all.
A tiny example. The twelve points of §6 have three voters: (1,3) and (3,5) with α=81, and (4,2) with α=41, and b=0. For the new point x=(2,4):
Positive, so blue — and exactly 1, so (2,4) sits right on the blue edge of the street.
The classifier as a voteDrag the gold star. Each support vector casts a vote αᵢ · yᵢ · similarity; the votes plus b add up to f, and its sign is the answer.
Try: Drag the star towards the orange voter and watch its bar grow while the blue bars shrink. Then open a kernel machine: the same vote, but the similarity is (xi⋅x)2 — and the regions are no longer split by a straight line.
drag the star
—
The observation that makes the trick possible
Building the street (the dual) and using it (the vote) both touch the data only through dot products. So if we replace "dot product" by some other similarity score, the whole machine keeps running with no other change. The next two sections show which replacements are allowed, and what they buy.
The realization
f(x)=i∈SV∑αiyi(xi⋅x)+b
Classifying is a vote: each support vector says how similar the new point is to it, weighted by its importance, pulling towards its own side. Keep this picture — the kernel trick changes only the similarity.
Pause & predict
With the three voters above (α=81,81 blue at (1,3), (3,5); α=41 orange at (4,2); b=0), what is f(4,1)?
In one sentence: The data enters both the training and the prediction only through dot products, and f(x)=∑αiyi(xi⋅x)+b is a vote: importance × side × similarity, plus an offset.
13
When no straight line will do — lift the data
Imagine this
Blue and orange marbles lie mixed on a table, the blue ones in the middle and the orange ones around them. No straight ruler laid on the table can separate them.
Now slap the middle of the table from below. The blue marbles jump higher than the orange ones. For that instant, a flat sheet of glass slid in sideways could separate them perfectly.
An SVM can only draw a straight line (a flat plane, in more dimensions). Plenty of data refuses. Three small examples show the way out.
One dimension. Blue points at x=±1, orange points at x=±2. The blue ones sit between the orange ones, so no single threshold separates them. Add one new feature, x2. The blue points go to (±1,1) and the orange to (±2,4): the orange points have been lifted higher, and the flat line x2=2.5 separates them. Push that line back down to the original line and it becomes two thresholds, x=±2.5≈±1.58.
XOR. Blue at (1,1) and (−1,−1), orange at (1,−1) and (−1,1). Every straight line leaves one colour on both sides. Add the feature x1x2: for the blue points it is +1, for the orange ones −1. One colour rises, the other sinks, and the flat plane "height = 0" separates them. Back on the floor that plane is x1x2=0 — the pair of axes.
Rings. Blue points in an inner ring, orange points in an outer ring. Add x12+x22, the squared distance from the centre. Every point rises onto a bowl, the outer ring higher than the inner one, and a flat plane slices between them. Its shadow on the floor is a circle.
Lift, cut, look downAdd one feature, lift every point by it, slice the lifted points with a flat plane — and see what that plane looks like from the floor.
Try: Press ▶ lift and cut on each tab. Then drag the lift slider back to 0 and up again slowly: the separation only exists up there, but its shadow stays on the floor.
drag the picture to orbit
—
The realization
flat cut in the lifted space⇓‖curved rule on the floor
Take the data to a higher-dimensional space by adding new features. Up there, fit an ordinary linear SVM — a flat boundary. Its shadow back home is curved. The SVM never stopped being linear; it is linear in the higher space.
Pause & predict
In the 1-D example the cut up there is x2=2.5. What is the rule back on the original line?
In one sentence: Add features so the data rises into a higher space, cut it there with a flat plane, and the cut comes back down as a curve — the machine stays linear, just not in the space you started in.
14
The trick — similarity without visiting the big space
Imagine this
You want to know how alike two cities are across every product in their markets — lakhs of prices each. You could fly to both, write down every price, and compare them one by one.
Or someone hands you a formula that takes a two-line summary of each city and gives the same answer. You get the full comparison without ever making the trip.
Lifting works, but adding features costs time and memory. Here is the trick that avoids the cost. Take 2-D points and the quadratic lift, with one odd-looking 2:
φ(x)=(x12,2x1x2,x22).
Compute the dot product up there, coordinate by coordinate:
Read the last line slowly. The similarity in the 3-D space is the ordinary 2-D dot product, squared. You never have to build φ at all. And now the 2 makes sense: the square (a+b)2 has a middle term 2ab, and the 2 splits that 2 evenly between the x half and the z half, 2⋅2=2.
A tiny example.x=(1,2), z=(3,1). The short route: x⋅z=3+2=5, squared, 25. The long route: φ(x)=(1,22,4), φ(z)=(9,32,1), and 9+12+4=25. Same number.
So the kernel trick is one sentence: choose a function K(x,z) that equals φ(x)⋅φ(z) for some lift φ, and replace every dot product by it —
xi⋅xj⟶K(xi,xj),xi⋅x⟶K(xi,x).
The SVM then draws a flat boundary in the lifted space and a curved one down here, while all the arithmetic stays in the small space.
kernel
K(x,z)
what it means
linear
x⋅z
no lift at all: the SVM of §1–§11
polynomial, homogeneous
(x⋅z)d
all products of exactly d coordinates; d=2 is the quadratic lift above
polynomial, non-homogeneous
(x⋅z+1)d
the same plus every lower degree and a constant; for d=2 in 2-D, six features: (x12,x22,2x1x2,2x1,2x2,1)
RBF (Gaussian)
e−γ∥x−z∥2
similarity that fades with distance; its lift has infinitely many coordinates — yet the kernel costs three operations
Why may we use a kernel whose φ nobody can write down? A result called Mercer's theorem says: if K is symmetric and every kernel table it produces is positive semi-definite (no "negative lengths"), then K is a dot product in some lifted space, even an infinite one. That is what makes the RBF kernel legal. It is one of the quiet engines of applied mathematics; you only need to know it exists.
How big is the space we never visit? With n original features and degree d, the homogeneous kernel uses every product of exactly d coordinates: (dn+d−1) features. The non-homogeneous one uses every degree up to d: (dn+d). For n=2,d=2 that is 3 and 6 — the two lifts above. For n=10,d=4 it is 715 and 1001. The kernel still costs one 10-term dot product and one power.
Two routes to one numberRoute A builds the lift and takes a long dot product. Route B takes the short dot product and applies the kernel. Change x and z and watch them agree.
Try: Keep x=(1,2), z=(3,1) and switch between the kernels: both routes print 5, 25, 36. Then slide n to 100 and d to 5 in the feature counter and compare the two bars.
(, )
(, )
Route A · build φ, then dot
Route B · dot first, then the kernel
How many features are we secretly using? n original features, degree d
The realization
φ(x)⋅φ(z)=(x⋅z)2⟹xi⋅xj→K(xi,xj)
A kernel is a dot product in a bigger space, computed without going there. Swap every dot product in the dual and in the vote for K, and the linear machine draws curves — at the cost of the small space, whatever the size of the big one.
Pause & predict
For x=(1,2) and z=(3,1), what is K(x,z)=(x⋅z)2? And what goes wrong if you square the coordinates first?
Pause & predict
With n=10 features and degree d=4, how many features do (x⋅z)4 and (x⋅z+1)4 secretly use?
If you want the algebra · 3 proofs, step by step
Prove it · the quadratic kernel is a dot product upstairs
Claim. With φ(x)=(x12,2x1x2,x22), φ(x)⋅φ(z)=(x⋅z)2 for all x,z∈R2.
1
Multiply matching coordinates and add:
φ(x)⋅φ(z)=x12z12+x22z22+(2x1x2)(2z1z2)=x12z12+x22z22+2x1z1x2z2.2⋅2=2: that is the only job of the 2.
2
Regroup as a2+2ab+b2 with a=x1z1, b=x2z2: the sum is (x1z1+x2z2)2=(x⋅z)2.
∎Without the 2 the middle term would be x1z1x2z2, and the sum would not be a perfect square of anything simple.
Prove it · (x·z + 1)² uses six features
Claim. In 2-D, (x⋅z+1)2=φ(x)⋅φ(z) with φ(v)=(v12,v22,2v1v2,2v1,2v2,1).
1
Expand the square of three terms:
(x1z1+x2z2+1)2=x12z12+x22z22+1+2x1z1x2z2+2x1z1+2x2z2.
2
Write each term as "something in x" times "the same thing in z": (x12)(z12), (x22)(z22), (2x1x2)(2z1z2), (2x1)(2z1), (2x2)(2z2), (1)(1). The x-halves are φ(x).
∎So the "+1" quietly adds the two linear features and a constant to the three quadratic ones. Check with x=(2,1), z=(1,3): 4+9+12+4+6+1=36=(5+1)2.
Prove it · counting the hidden features
Claim. With n variables there are (dn+d−1) products of degree exactly d, and (dn+d) of degree at most d.
1
A product of degree d is a choice of how many times each variable appears: k1+⋯+kn=d with each ki≥0. Picture d stars split into n groups by n−1 bars: an arrangement of d+n−1 symbols, of which d are stars. There are (dn+d−1) of them.
Example: n=2,d=2: x12,x1x2,x22, and (23)=3.
2
Degree at most d: add a dummy variable x0=1. Every product of degree ≤d in x1..xn is exactly one product of degree d in x0..xn. That gives (d(n+1)+d−1)=(dn+d).
∎n=10,d=4: (413)=715 and (414)=1001. n=3,d=4: 15 and 35.
In one sentence: Because φ(x)⋅φ(z)=(x⋅z)2, a kernel gives the similarity of the lifted points from the small space alone — so we swap every dot product for K and never build the huge (even infinite) lift.
15
A kernel SVM, start to finish
Imagine this
A good recipe for dal is a fixed order of steps: wash, soak, boil, temper. Follow the order and it comes out right every time, whoever is cooking.
A kernel SVM on paper has the same kind of recipe. Eight steps, always in the same order.
The recipe.
Kernel table. Dot products first, then apply the kernel to each number. Use the symmetry Kij=Kji and check the diagonal.
Look for symmetry. If two rows of the table look alike (or are mirror images) with the same label, take their prices equal. Four unknowns often become one.
Use ∑iαiyi=0 to tie the remaining unknowns together.
Write the dual with numbers, block by block: same-class entries carry yiyj=+1, cross-class entries −1. Reduce to one unknown, differentiate, solve.
Check αi≥0 and note the support vectors.
Find b from a support vector: ys(∑iαiyiKis+b)=1. Confirm with a second one. Never assume b=0.
Classify a new point: f(x)=∑iαiyiK(xi,x)+b, read the sign.
Optional finish: simplify f in x1,x2 to see the curve. It doubles as a check: every support vector must score exactly ±1.
Worked through once. Four points: x1=(1,2) and x2=(−1,−2) blue; x3=(1,−2) and x4=(−1,2) orange. Kernel K=(x⋅z)2.
Step 1. Row 1 of dot products: x1⋅x1=5, x1⋅x2=−5, x1⋅x3=−3, x1⋅x4=3. Square each: 25,25,9,9. The whole table:
K=252599252599992525992525.
Steps 2–3. Rows 1–2 are identical and share a label; so are rows 3–4. Take α1=α2=a and α3=α4=c. Balance: 2a−2c=0, so c=a: all four prices equal a.
Step 4. Each row of yiyjKij is 25+25−9−9=32, so the double sum is 4⋅32a2=128a2 and
Step 5. All four prices are 321>0: every point is a support vector.
Step 6. From x1: 321(25+25−9−9)+b=1, so 1+b=1 and b=0.
Step 7. For the new point (2,1): the dot products with the four points are 4,−4,0,0; squared, 16,16,0,0. So f=321(16+16)=1: class +1, right on the edge.
Step 8. Put the kernel into f and simplify:
f(x)=321[2(x1+2x2)2−2(x1−2x2)2]=2x1x2.
The boundary x1x2=0 is the pair of axes, and f=±1 are the curves x1x2=±2, passing through all four points.
And upstairs? The lift φ(x)=(x12,2x1x2,x22) sends both blue points to the same place, (1,22,4), and both orange points to (1,−22,4). Four points became two, and a two-point SVM is the easiest there is.
Four points become twoThe four points on the floor, then lifted by φ(x) = (x₁², √2·x₁x₂, x₂²). Up there the problem is a two-point street; down here its shadow is the pair of axes.
Try: Press ▶ lift and watch each pair of same-coloured points fly to one spot. The street between the two spots is 42≈5.66 wide — exactly the distance between them.
drag the picture to orbit
Now try everything at once. Pick a data set, pick a kernel, set the fine, and a live solver draws the boundary f=0 (white) and the street edges f=±1 (violet). For the four-point set with (x⋅z)2, the recipe panel walks the eight steps with live numbers.
The kernel playgroundFive data sets, four kernels, a fine C, and a live solver. Click to add points; drag to move them.
Try: On rings, start with linear — no street exists. Switch to (x⋅z+1)2: a circle appears. Then try RBF and raise γ until the boundary starts hugging single points. Open the landscape tab to see f as hills and valleys with the boundary as the shoreline.
The kernel table is always N×N — four points give a 4×4 table whatever the degree. The degree only changes the size of the lifted space, which we never build. w still exists, w=∑αiyiφ(xi), but it lives up there; we keep the prices and the support vectors instead.
Pause & predict
In the worked example (αi=321, b=0, K=(x⋅z)2), classify the new point (−1,3).
If you want the algebra · 2 proofs, step by step
Prove it · the four-point machine is f = x₁x₂/2
Claim. For x1=(1,2)+, x2=(−1,−2)+, x3=(1,−2)−, x4=(−1,2)− with K=(x⋅z)2, αi=321 and b=0, the decision function is f(x)=x1x2/2.
1
K(x1,x)=(x1+2x2)2=K(x2,x), and K(x3,x)=(x1−2x2)2=K(x4,x). So
f(x)=321[2(x1+2x2)2−2(x1−2x2)2].
2
Use (p+q)2−(p−q)2=4pq with p=x1, q=2x2: the bracket is 2⋅4⋅2x1x2=16x1x2, so f=3216x1x2=2x1x2.
∎Checks: each training point has x1x2=±2, so f=±1 — all four sit on the street's edges. Upstairs, w=∑αiyiφ(xi)=(0,42,0) and the width is 2/∥w∥=42, the distance between the two lifted points.
Prove it · why the symmetric prices are the natural answer
Claim. In the four-point problem the prices are not unique — any α1+α2=161=α3+α4 with αi≥0 gives the same machine — and the equal split 321 each is the one of smallest size.
1
x1 and x2 have the same kernel row (the kernel sees them as the same point: φ(x1)=φ(x2)), and so do x3 and x4. In D and in f, α1 and α2 only ever appear as the sum α1+α2; likewise α3+α4.
2
So only the two sums are fixed, at 161 each. Among all splits of a fixed sum, α12+α22 is smallest when the two are equal. That is the answer "by symmetry", and the one this page's solver reports.
∎w, b and f are the same for every split — the prediction never depends on the choice.
In one sentence: Build the kernel table (dots first, kernel second), shrink the dual with symmetry and balance, find the prices, get b from a support vector, and classify by the vote — the boundary is flat upstairs and curved down here.
16
What to carry forward
One idea, built up in four acts: the widest street, prices on points, a fine for trespassers, and a similarity that measures a bigger space without going there.
The problem
min21∥w∥2s.t.yi(w⋅xi+b)≥1
The widest street is 2/∥w∥ wide once the nearest points score 1. A bowl with straight walls: one answer.
The dual
max∑αi−21∑αiαjyiyjxi⋅xj
with αi≥0, ∑αiyi=0. Its peak equals the primal minimum.
The two identities
w=i∑αiyixi,i∑αiyi=0
The street is built from the points; the two classes' pushes balance.
Three kinds of points
Outside the street: α=0, deletable. On an edge: α≥0, support vectors when α>0. Inside: impossible with a hard margin, fined with a soft one.
Soft margin's one change
0≤αi≤C,ξi=max(0,1−zi)
A fine per unit of trespass; in the dual, a ceiling on every price. Big C = strict and narrow.
The kernel swap
xi⋅xj→K(xi,xj)=φ(xi)⋅φ(xj)
Flat upstairs, curved down here, and the table stays N×N.
The recipe
Dots first, kernel second · symmetry · balance · dual with numbers · check α≥0 · b from a support vector · classify by the vote · simplify f to see the curve.
The thread to Units 16 and 18
Look at the vote once more: score every stored item by its similarity to the new one, then take a weighted sum. Hold on to that sentence. When machines start reading sentences (Unit 16) and then paying attention to words (Unit 18), the core operation will be exactly this: similarity by a dot product, then a weighted vote.
The one thing to remember
Draw the widest street, and let the few points that touch it decide. Everything else — the dual, the fine, the kernel — is how you find that street when the world is large, noisy and curved.
In one sentence: An SVM is the widest street between two groups, held up by a few support vectors, softened by a fine, and bent by a kernel — and it only ever meets the data through dot products.
17
Practice arena — sixteen problems, solved in full
Sixteen problems, easy to hard: a margin read off a given line, a two-point street from scratch, five points on a line, the kernel identity checked by hand, counting hidden features, rebuilding a model from its prices, adding a point in one dimension, verifying a claimed answer in two, the "on the edge but no price" trap, reading a soft-margin model, auditing a proposed soft-margin answer — and then five full kernel problems, including one whose boundary is a hyperbola and one where a point's price is zero. Every number here was checked by machine.
Three habits do most of the work. Write the two identities first: ∑iαiyi=0 and w=∑iαiyixi (or the kernel vote f(x)=∑iαiyiK(xi,x)+b). Dots first, kernel second: finish every dot product before you square it. And find b from a support vector, then check it with a second one — never assume b=0.
Problem 1easygeometry
A classifier has w=(3,4) and b=−10, in canonical form (the nearest points score exactly ±1). (a) Write the boundary and both street edges. (b) What is the width of the street? (c) How far is the point (1,1) from the boundary, and on which side? (d) You rescale to w=(6,8), b=−20. What changes and what does not?
What this tests. That geometry lives in ratios like ∣f∣/∥w∥, and that "width =2/∥w∥" is only true in canonical form. Plan.∥w∥ first; then the three parallel lines; then the distance formula; for (d), list what moves and what does not.
Show the full solution
Step 1 — the length of w.∥w∥=9+16=5 (the 3-4-5 triangle).
Step 2 — the three lines (a). Set f=3x1+4x2−10 to 0 and ±1:
boundary: f=+1:f=−1:3x1+4x2=10,3x1+4x2=11,3x1+4x2=9.
Step 3 — the width (b).2/∥w∥=2/5=0.4. Check: each edge is 1/∥w∥=0.2 from the boundary, and 0.2+0.2=0.4.
Step 4 — the distance of (1, 1) (c).f(1,1)=3+4−10=−3,∥w∥∣f∣=53=0.6.
It is on the negative side. Since ∣f∣=3>1, it is outside the street; as a training point it would have α=0.
Step 5 — the rescaling (d).
quantity
before
after ×2
changed?
the boundary itself
3x1+4x2=10
6x1+8x2=20
no — the same line
score f(1,1)
−3
−6
yes, doubles
∥w∥
5
10
yes, doubles
distance ∣f∣/∥w∥
0.6
0.6
no
where f=±1 sits
0.2 away
0.1 away
yes — no longer canonical
The rescaled version is not canonical: its nearest points now score 2, not 1. Reading "2/∥w∥=0.2" off it would be wrong.
answers at a glance: (a) boundary 3x1+4x2=10, edges =11 and =9. (b) width 0.4. (c) 0.6 away, negative side, outside the street. (d) the line and every distance stay; the scores and ∥w∥ double, and the form is no longer canonical.
Remember
A score is not a distance until you divide by ∥w∥, and 2/∥w∥ is the width only when the nearest points score exactly 1. Renormalise before you quote a margin.
Problem 2easyhard margin
Two training points: x1=(1,1) with y1=+1, x2=(4,5) with y2=−1. (a) Find α1,α2. (b) Find w and b. (c) Give the boundary, both edges and the width. (d) Check that the primal and dual values agree.
What this tests. The whole machinery on the smallest problem there is: balance, the edge conditions, w=∑αiyixi — then two independent checks. Plan. With two points both must be support vectors. Balance makes the prices equal; the two edge conditions give two equations in α and b.
Show the full solution
Step 1 — both points must push. If α1=0, balance α1−α2=0 forces α2=0, then w=0, which cannot give any point a score of 1. So both prices are positive and both points sit on an edge. Balance: α1=α2=α.
Step 2 — the dot products.x1⋅x1=2, x1⋅x2=4+5=9, x2⋅x2=16+25=41.
Step 3 — the two edge conditions. With f(x)=α(x1⋅x)−α(x2⋅x)+b:
(+1)[2α−9α+b]=1⇒−7α+b=1,(−1)[9α−41α+b]=1⇒32α−b=1.
Step 4 — solve (a). Add the two equations; b cancels: 25α=2, so α=252=0.08. Check with the two-point shortcut: 2/∥x1−x2∥2=2/(9+16)=0.08 ✓.
Step 5 — w and b (b).b=1+7(0.08)=1.56, and
w=0.08[(1,1)−(4,5)]=0.08(−3,−4)=(−0.24,−0.32).w points along x1−x2: the boundary is at right angles to the segment joining the two points.
Step 6 — the lines and the width (c). Multiply −0.24x1−0.32x2+1.56=0 by −25: the boundary is 6x1+8x2=39, and the edges f=±1 are 6x1+8x2=39∓25, i.e. 14 and 64. Check: (1,1) gives 14 ✓, (4,5) gives 64 ✓. ∥w∥=0.08⋅5=0.4, so the width is 2/0.4=5 — the distance between the two points, 9+16=5 ✓.
answers at a glance: α1=α2=0.08; w=(−0.24,−0.32), b=1.56; boundary 6x1+8x2=39, edges =14 and =64, width 5; primal = dual =0.08.
Remember
With exactly two points, α=2/∥x1−x2∥2, w is parallel to x1−x2, and the width is the distance between them. Use it as a five-second check.
Problem 3easyhard margin · 1-D
One-dimensional data: x=1,2,4 have y=+1; x=−1,−3 have y=−1. (a) Which points are support vectors? (b) Find w, b and the width. (c) Find every αi. (d) Which points could be deleted without changing the answer?
What this tests. Guessing the active points from a sketch, then proving the guess; and complementary slackness in its most useful form. Plan. In 1-D the street is an interval, so the classes touch at the closest opposite pair. Solve their two edge equations, then check every other point.
Show the full solution
Step 1 — the collision. The classes come closest at x=1 and x=−1. These are the candidates.
Step 2 — two edge equations.(+1)(w+b)=1 and (−1)(−w+b)=1, i.e. w+b=1 and w−b=1. Adding: w=1; subtracting: b=0. So f(x)=x, boundary x=0, width 2/∣w∣=2: the street runs from −1 to 1.
Step 3 — check every point.
x
y
score yf(x)
α
1
+1
1
21
2
+1
2
0
4
+1
4
0
−1
−1
1
21
−3
−1
3
0
All scores are at least 1, so the street is legal; exactly two are tight.
Step 4 — the prices (c). Balance makes the two live prices equal, and the two-point shortcut gives α=2/(1−(−1))2=21. Check: w=21(1)(1)+21(−1)(−1)=1 ✓. The others score more than 1, so their prices are 0.
Step 5 — what can go (d).x=2, 4 and −3 — any of them, or all three at once. Delete x=1 or x=−1 and the street widens immediately.
answers at a glance: support vectors x=1 and x=−1; w=1, b=0, boundary x=0, width 2; α=21 for x=±1, 0 for the rest; x=2,4,−3 are deletable.
Problem 4easykernel
x=(2,1), z=(1,3), K(x,z)=(x⋅z+1)2. (a) Evaluate the kernel. (b) Write the six-feature map φ, compute φ(x) and φ(z), and confirm φ(x)⋅φ(z) matches. (c) Count the arithmetic each route costs.
What this tests. That K=φ⋅φ is an identity, not an analogy — and that you can write φ when the degree is small. Plan. One line for the kernel; then the map from §14 at both points, multiplied coordinate by coordinate.
Show the full solution
Step 1 — the kernel route (a).x⋅z=2(1)+1(3)=5, so K=(5+1)2=36.
Step 2 — the map (b).φ(v)=(v12,v22,2v1v2,2v1,2v2,1).
coordinate
φ(x)
φ(z)
product
v12
4
1
4
v22
1
9
9
2v1v2
22
32
12
2v1
22
2
4
2v2
2
32
6
1
1
1
1
Total 4+9+12+4+6+1=36 ✓. Every 2 meets another 2 and becomes a plain 2.
Step 3 — the cost (c). Kernel route: two multiplications and one addition for the dot product, one addition for the +1, one squaring — five operations. Explicit route: build two six-long vectors (with square roots), then six multiplications and five additions. At degree 2 in 2-D it is close; at degree 5 in 100-D the explicit vectors have about 96.6 million coordinates, and the kernel is still a handful of operations.
answers at a glance: K=36; φ(v)=(v12,v22,2v1v2,2v1,2v2,1), φ(x)⋅φ(z)=4+9+12+4+6+1=36 ✓; five operations against a six-dimensional construction.
Problem 5easykernel theory
Input dimension n=3, polynomial degree d=4. (a) How many features does (x⋅z+1)4 secretly use? (b) And (x⋅z)4? (c) With 500 training points, how many kernel evaluations does the kernel table need, and how does that compare with building the lift?
What this tests. The two counting formulas — and that they describe two different models, not two ways of counting one. Plan. With the +1: every degree up to d, (dn+d). Without: degree exactly d, (dn+d−1). Then count the entries of a symmetric 500×500 table.
Show the full solution
Step 1 — non-homogeneous (a).(43+4)=(47)=3⋅2⋅17⋅6⋅5=35. Check degree by degree in 3 variables: 1+3+6+10+15=35 ✓.
Step 2 — homogeneous (b).(43+4−1)=(46)=2⋅16⋅5=15. This is a genuinely different model: it has only the 15 quartic products — no constant, no linear, no quadratic, no cubic terms.
Step 3 — the table (c). A symmetric 500×500 table needs 2500⋅501=125250 distinct kernel values, each a 3-term dot product, one addition and one fourth power — about six operations.
Step 4 — against the lift. The explicit lift stores 500×35=17500 numbers and takes 35-term dot products. At n=3,d=4 the trick barely pays. At n=100,d=5 the lift has (5105)=96560646 coordinates per point, and the kernel cost does not move. Past some size the kernel is not a speed-up; it is the only thing that runs at all.
answers at a glance: (a) (47)=35. (b) (46)=15. (c) 125250 evaluations at about six operations each, against 17500 stored coordinates and 35-term dot products for the lift — a gap that explodes with n and d.
Problem 6mediumhard margin
A trained hard-margin SVM reports: (2,2), y=+1, α=0.25; (4,1), y=+1, α=0; (0,0), y=−1, α=0.25. (a) Recover w and b. (b) Give the boundary and the width. (c) Verify that (4,1) deserves α=0. (d) Classify (1,0).
What this tests. Using w=∑αiyixi the way you do in practice, recovering b (which the dual never hands you), and knowing that α=0 is a claim you can check. Plan.w straight from the sum; balance as a free error check; b from one support vector, confirmed by the other.
Show the full solution
Step 1 — w (a).w=0.25(+1)(2,2)+0⋅(4,1)+0.25(−1)(0,0)=(0.5,0.5).
Balance: 0.25+0−0.25=0 ✓.
Step 2 — b. From (0,0): b=ys−w⋅xs=−1−0=−1. Confirm from (2,2): b=1−(0.5,0.5)⋅(2,2)=1−2=−1 ✓. Two support vectors must agree; if they do not, the prices are wrong.
Step 3 — boundary and width (b).0.5x1+0.5x2−1=0⟺x1+x2=2. ∥w∥=1/2, so the width is 22≈2.83.
Step 4 — does (4, 1) deserve α = 0? (c)f(4,1)=2+0.5−1=1.5, score 1.5>1: strictly outside the street, so complementary slackness forces α=0 ✓.
Step 5 — classify (1, 0) (d).f(1,0)=0.5−1=−0.5<0: class −1. But ∣f∣<1, so the point is inside the street — a correct but unsure call. Its distance to the boundary is 0.52≈0.71, less than the half-width 2≈1.41.
answers at a glance: w=(0.5,0.5), b=−1; boundary x1+x2=2, width 22; (4,1) scores 1.5>1, so α=0 is right; (1,0)→−1 with f=−0.5, inside the street.
Problem 7mediumhard margin · KKT
A hard-margin SVM, min21w2 s.t. yi(wxi+b)≥1, is trained on x1=4,y1=+1; x2=7,y2=+1; x3=1,y3=−1; x4=−3,y4=−1. (a) Write the KKT conditions, find the active points and solve for w,b and all αi. (b) Give the width and check strong duality. (c) A fifth point x5=3, y5=+1, is added. Is the old answer still optimal? If not, find the new one.
What this tests. Writing all four KKT conditions, using a sketch to spot the active points, and reasoning about a new point without starting over. Plan. Draw the number line: the closest opposite pair is 1 and 4. For (c), test the new point against the old f.
Show the full solution
Step 1 — KKT. With L=21w2−∑iαi[yi(wxi+b)−1]: stationarity w=∑αiyixi and ∑αiyi=0; primal feasibility yi(wxi+b)≥1; dual feasibility αi≥0; complementary slackness αi[yi(wxi+b)−1]=0.
Step 2 — the active pair.(+1)(4w+b)=1 and (−1)(w+b)=1. Subtract: 3w=2, so w=32 and b=−1−32=−35. Boundary: f=0 at x=2.5.
Step 3 — check the rest.f(7)=314−35=3≥1 ✓; f(−3)=−2−35=−311, score 311≥1 ✓. So α2=α4=0.
Step 4 — the prices. Balance: α1=α3. Stationarity: w=4α1−1⋅α3=3α1=32, so α1=α3=92. Shortcut check: 2/(4−1)2=92 ✓. All four KKT items hold, so (w,b)=(32,−35) is optimal, with α=(92,0,92,0).
Step 5 — width and duality (b). Width 2/∣w∣=3: the street runs from 1 to 4. Primal 21w2=92. Dual: ∑αi−21w2=94−92=92. Equal ✓.
Step 6 — the new point (c).f(3)=2−35=31, score 31<1: the new point sits inside the old street, so the old answer is no longer legal. The new closest pair is 1 and 3: 3w+b=1, w+b=−1, so w=1, b=−2. Check: f(4)=2, f(7)=5, f(−3)=−5 — all fine. Prices: α3=α5 and w=3α5−α3=2α5=1, so α3=α5=21, the rest 0. The point x=4 has been released: it now scores 2.
answers at a glance: (a) w=32, b=−35, α=(92,0,92,0). (b) width 3; primal = dual =92. (c) f(3)=31<1, so the answer changes: w=1, b=−2, α3=α5=21, others 0; width 2.
Problem 8mediumhard margin · KKT
A hard-margin SVM is trained on x1=(0,3), y=+1; x2=(−2,2), y=+1; x3=(2,1), y=−1; x4=(3,0), y=−1. The answer is claimed to be w=(−21,21), b=−21. (a) Use KKT to find all αi and so verify the claim. (b) Give the width, the support vectors, the boundary and both edges. Does removing x2 change the answer? (c) Classify (1,1). Is it inside the street?
What this tests. Verification rather than discovery: score every point, zero the prices of the ones with room, solve for the rest, then tick every KKT item. Plan.f(x)=−21x1+21x2−21; score all four; solve the two-component equation w=∑αiyixi.
Show the full solution
Step 1 — score everyone.
point
y
f
score
status
(0,3)
+1
0+23−21=1
1
on the + edge
(−2,2)
+1
1+1−21=23
23
outside ⇒ α2=0
(2,1)
−1
−1+21−21=−1
1
on the − edge
(3,0)
−1
−23−21=−2
2
outside ⇒ α4=0
Step 2 — stationarity, two components.w=α1(0,3)−α3(2,1):
first: second: −2α3=−21⇒α3=41,3α1−α3=21⇒α1=41.
Step 3 — tick the list. Balance 41+0−41−0=0 ✓; all α≥0 ✓; all scores ≥1 ✓; the two priced points are exactly the tight ones ✓. The problem is convex, so the claim is the answer: α=(41,0,41,0). Shortcut check: 2/∥(0,3)−(2,1)∥2=2/8=41 ✓.
Step 4 — geometry (b).∥w∥=21, width 22≈2.83 — the distance between the two support vectors (0,3) and (2,1). Multiply f=0 by −2: boundary x2=x1+1; edge f=+1: x2=x1+3 (through (0,3)); edge f=−1: x2=x1−1 (through (2,1)). Removing x2 changes nothing: its price is 0 and its rule has room.
Step 5 — classify (1, 1) (c).f(1,1)=−21+21−21=−21: class −1, and ∣f∣<1, so it is inside the street — 212≈0.71 from the boundary, less than the half-width 2≈1.41.
answers at a glance: (a) α=(41,0,41,0); every KKT item holds, so the claim is optimal. (b) width 22; support vectors (0,3), (2,1); boundary x2=x1+1, edges x2=x1+3 and x2=x1−1; removing x2 changes nothing. (c) (1,1)→−1, f=−21, inside the street.
Problem 9mediumhard margin · a trap
Three points: (1,1)→+1, (2,0)→+1, (0,0)→−1. (a) Find w, b and the width. (b) Find every αi. (c) Which points are support vectors? Answer carefully.
What this tests. The one definitional trap in the subject: a point can sit exactly on an edge and still have α=0. Plan. Try "all three on an edge": three linear equations for w1,w2,b. Then get the prices from w=∑αiyixi and see what is forced.
Show the full solution
Step 1 — all three tight.w1+w2+b=1, 2w1+b=1, −(0+b)=1.
Step 2 — solve back to front.b=−1; then 2w1−1=1⇒w1=1; then 1+w2−1=1⇒w2=1. So w=(1,1), b=−1, boundary x1+x2=1, width 2/2=2.
Step 3 — the prices (b).w=α1(1,1)+α2(2,0)−α3(0,0)=(α1+2α2,α1)=(1,1).
Second coordinate: α1=1. First: 1+2α2=1⇒α2=0 — forced. Balance: α1+α2−α3=0⇒α3=1.
Step 4 — check. All α≥0 ✓; all scores equal 1 ✓; complementary slackness holds since every rule is tight ✓; duality: 21∥w∥2=1 and ∑αi−21∥w∥2=2−1=1 ✓.
Step 5 — the trap (c). All three points lie exactly on an edge, but (2,0) has α=0: it touches the street without pushing on it. Delete it and nothing changes; delete either of the others and the boundary moves. So the support vectors are (1,1) and (0,0) only — the points with α>0.
answers at a glance: w=(1,1), b=−1, boundary x1+x2=1, width 2; α=(1,0,1); support vectors (1,1) and (0,0) — (2,0) is on an edge with α=0.
Remember
Say it this way: support vectors are the points with αi>0; they always lie on an edge, but not every point on an edge is one.
Problem 10mediumsoft margin
A soft-margin SVM trained with C=1 returns these prices: A: α=0; B: 0.4; C: 1.0; D: 1.0; E: 0.15. (a) Classify each as a non-support vector, a free support vector or a bounded one. (b) What do you know about each point's slack and score? (c) Which may be used to compute b? (d) Which are definitely misclassified?
What this tests. The three price regimes of §10, read from the prices to the geometry. Plan. Compare each α with 0 and with C=1; that alone fixes the regime, and the regime fixes ξ and the score.
Show the full solution
Step 1 — the three regimes (with z=yf(x)): α=0⇒z≥1; 0<α<C⇒z=1; α=C⇒z≤1.
Step 2 — apply them (a), (b), (c).
point
α
type
ξ
score z
for b?
A
0
not a support vector
0
≥1
no
B
0.4
free
0
=1
yes
C
1.0
bounded
≥0
≤1
no
D
1.0
bounded
≥0
≤1
no
E
0.15
free
0
=1
yes
Only B and E are known to score exactly 1, so only they give b=ys−∑iαiyiK(xi,xs). In practice, average over all free support vectors.
Step 3 — misclassified? (d) None, necessarily. α=C says only z≤1: at best on the edge, at worst deep on the wrong side. Misclassified needs z<0 (ξ>1), which the price alone cannot tell you.
answers at a glance: A non-support; B and E free (ξ=0, z=1); C and D bounded (ξ≥0, z≤1); only B and E give b; none is definitely misclassified.
Problem 11hardsoft margin
A colleague proposes w=(1,1), b=−3 for: (1,1)→+1, (3,3)→+1, (2,0)→−1, (0,2)→−1, (2,2)→−1. (a) For each point compute the score z and slack ξ, and say where it is. (b) Give the total objective 21∥w∥2+C∑ξi at C=1 and C=10. (c) Could this (w,b) be the soft-margin answer for any C>0?
What this tests. The hinge formula and the two halves of the objective; then running complementary slackness backwards to audit someone else's answer. Plan. Tabulate score and slack; add the halves; in (c), give each point its price regime and test the balance condition.
Show the full solution
Step 1 — scores and slacks (a).f=x1+x2−3, ξ=max(0,1−z):
point
y
f
z
ξ
where
(1,1)
+1
−1
−1
2
misclassified
(3,3)
+1
+3
3
0
outside the street
(2,0)
−1
−1
1
0
on an edge
(0,2)
−1
−1
1
0
on an edge
(2,2)
−1
+1
−1
2
misclassified
Step 2 — the objective (b).21∥w∥2=21(1+1)=1 and ∑ξi=4. At C=1: 1+4=5. At C=10: 1+40=41.
Step 3 — regimes (c).(3,3): z>1⇒α=0. (1,1) and (2,2): ξ>0⇒α=C. (2,0) and (0,2): z=1⇒α=p,q∈[0,C].
Step 4 — balance fails.i∑αiyi=C+0−p−q−C=−(p+q)=0⇒p=q=0.
Then w=∑αiyixi=C(1,1)−C(2,2)=(−C,−C). To equal (1,1) we would need C=−1, impossible. So the proposal is not optimal for any C>0.
Step 5 — for comparison. At C=1 the true answer is w=(21,21), b=−2: slacks (2,0,0,0,1), objective 21⋅21+3=3.25 — better than 5, as it must be. (The points (1,1) and (2,2) sit on each other's wrong side, so no hard-margin answer exists at all.)
answers at a glance: ξ=(2,0,0,0,2) — two misclassified, two on an edge, one outside; objective 5 at C=1, 41 at C=10; (c) no — balance forces the edge prices to 0 and then w=(−C,−C). The true C=1 answer is w=(21,21), b=−2, objective 3.25.
Problem 12mediumkernel SVM
Four points form an XNOR pattern (same signs ⇒ class +1): x1=(1,2), y1=+1; x2=(−1,−2), y2=+1; x3=(1,−2), y3=−1; x4=(−1,2), y4=−1. Use K(x,z)=(x⋅z)2. (a) Compute the 4×4 kernel table. (b) Solve the hard-margin dual and name the support vectors. (c) Find b, then classify (2,1) and (−1,3).
What this tests. A kernel table without slips, symmetry to shrink the dual to one unknown, the balance condition, b from a support vector, and classification by kernel values. Plan. Dots first, square second. Rows 1–2 and 3–4 are identical ⇒ equal prices. One-variable dual, then b from x1, then the two classifications.
Show the full solution
Step 1 — dot products. Row 1: 5,−5,−3,3. By the same arithmetic the full table of xi⋅xj is
5−5−33−553−3−335−53−3−55.
Step 2 — square every entry (a).K=252599252599992525992525.
The diagonal is ∥xi∥4=25 and the table is symmetric.
Step 3 — symmetry and balance. Rows 1–2 are identical with the same label, as are rows 3–4, so take α1=α2=a, α3=α4=c. Balance: 2a−2c=0⇒c=a.
Step 4 — the dual with numbers.∑αi=4a. The double sum, block by block: same-class blocks 2×4 entries of 25 give +200a2; cross blocks, 8 entries of 9 with yiyj=−1, give −72a2. Total 128a2:
D(a)D′(a)⇒a=4a−21⋅128a2=4a−64a2,=4−128a=0=321.
All four prices are 321>0: every point is a support vector (b).
Step 5 — b (c). From x1 (column 1 of K): 321(25+25−9−9)+b=1⇒1+b=1⇒b=0. Confirm with x3: −[321(9+9−25−25)+0]=−[−1]=1 ✓.
Step 6 — classify.(2,1): dots 4,−4,0,0, squares 16,16,0,0, f=3232=1: class +1, exactly on the edge. (−1,3): dots 5,−5,−7,7, squares 25,25,49,49, f=3250−98=−1.5: class −1.
Step 7 — the curve (optional).f(x)=321[2(x1+2x2)2−2(x1−2x2)2]=2x1x2: the boundary is the pair of axes, and f=±1 are x1x2=±2, through all four points. Upstairs, w=(0,42,0) and the width is 42.
answers at a glance: K as above; αi=321 for all four (all support vectors); b=0; (2,1)→+1 with f=1, (−1,3)→−1 with f=−1.5; f=x1x2/2.
Remember
Here x1 and x2 look identical to the kernel, so only α1+α2 is really fixed; the equal split is the natural (smallest) choice, and w, b, f are the same for any split. The slip to avoid: squaring the coordinates before finishing the dot product.
Problem 13hardkernel SVM
An inner point and two outer ones: x1=(0,0), y1=+1; x2=(2,0), y2=−1; x3=(0,−2), y3=−1. Use K(x,z)=(x⋅z+1)2. (a) Compute the 3×3 kernel table. (b) Solve the dual for the αi and find b. (c) Classify (1,1) and (1,−1).
What this tests. The "add 1, then square" habit, a dual whose classes are not balanced (one point against two), and reading a curved boundary out of f. Plan. Rows 2 and 3 are mirror images, so α2=α3=c; balance then gives α1=2c. One-variable dual; b from x1, whose column is all ones.
Show the full solution
Step 1 — dots, add 1, square (a).x1 is the origin, so every dot product with it is 0; x2⋅x2=4, x2⋅x3=0, x3⋅x3=4. Then (0+1)2=1 and (4+1)2=25:
K=11112511125.
Without the +1, the origin's row would be all zeros and it would carry no information at all.
Step 2 — balance and symmetry.α1−α2−α3=0, and α2=α3=c, so α1=2c.
Step 3 — the dual.∑αi=4c. The double sum, term by term: (1,1): 4c2; (2,2), (3,3): 25c2 each; (1,2)+(2,1): 2(2c)(c)(−1)(1)=−4c2; (1,3)+(3,1): −4c2; (2,3)+(3,2): 2c2. Total 48c2:
D(c)D′(c)⇒c=4c−24c2,=4−48c=0=121.
So α1=61, α2=α3=121 — all support vectors.
Step 4 — b (b). From x1: 61−121−121+b=1⇒b=1. Confirm with x2: −[61−1225−121+1]=−[−1]=1 ✓.
Step 5 — classify (c).(1,1): dots 0,2,−2 → kernel 1,9,1: f=61−129−121+1=31 → class +1. (1,−1): dots 0,2,2 → 1,9,9: f=61−129−129+1=−31 → class −1. Both are inside the street.
Step 6 — the circle (optional).f=67−121[(2x1+1)2+(2x2−1)2], so f=0⟺(x1+21)2+(x2−21)2=3.5: a circle centred at (−21,21), radius 3.5≈1.87.
answers at a glance: K=11112511125; α=(61,121,121), all support vectors; b=1; (1,1)→+1 (f=31), (1,−1)→−1 (f=−31); boundary: the circle (x1+21)2+(x2−21)2=3.5.
Problem 14hardkernel SVM · b ≠ 0
x1=(1,1), y1=+1; x2=(−1,−1), y2=+1; x3=(2,0), y3=−1; x4=(−2,0), y4=−1. Use K=(x⋅z)2. (a) Compute the kernel table. (b) Solve the dual and name the support vectors. (c) Find b and classify (0,2) and (3,0).
What this tests. The same skills as Problem 12 — but the bias is not zero, so anyone who "remembers b=0" loses the classifications. It also shows a kernel SVM drawing a hyperbola. Plan. Dots, square; rows 1–2 and 3–4 identical ⇒ equal prices; balance; one-variable dual; b from x1, confirmed from x3.
Step 2 — symmetry, balance, dual (b).α1=α2=a, α3=α4=c, balance c=a. Blocks: 4×4 gives 16a2, 4×16 gives 64a2, cross blocks 8×4 with a minus: −32a2. Total 48a2:
D(a)=4a−24a2⇒a=121.
All four prices are 121: all support vectors.
Step 3 — b (c). From x1: 121(4+4−4−4)+b=1⇒b=1. Confirm from x3: −[121(4+4−16−16)+1]=−[−2+1]=1 ✓. Had you assumed b=0, x1 would score 0 — on the boundary, which is absurd for a support vector.
Step 5 — the curve (optional).f=6(x1+x2)2−4x12+1. The boundary is (x1+x2)2−4x12=−6, i.e. (x2−x1)(x2+3x1)=−6 — a hyperbola. Upstairs the four points collapse to two, (1,2,1) and (4,0,0); w=61(−3,2,1), ∥w∥=31, width 23 — the distance between those two points.
answers at a glance: K as above; αi=121, all support vectors; b=1; (0,2)→+1 (f=35), (3,0)→−1 (f=−3.5); boundary a hyperbola (x2−x1)(x2+3x1)=−6.
Problem 15hardkernel SVM · given prices
x1=(0,0), y1=+1; x2=(1,1), y2=−1; x3=(1,−1), y3=−1; x4=(3,0), y4=−1. A hard-margin SVM with K=(x⋅z+1)2 reports α1=21, α2=41, α3=41, α4=0. (a) Compute the kernel table. (b) Check the balance, name the support vectors and explain α4=0. (c) Find b from one support vector and confirm it from another. (d) Classify (1,0) and (−2,1).
What this tests. The table again; what a zero price means; b when the prices are handed to you; classifying with support vectors only. Plan. Dots, add 1, square. Balance in one line. b from x1 (its column is all ones), confirm with x2, then check x4 really is outside the street.
Show the full solution
Step 1 — the table (a). Dots: everything with x1 is 0; x2⋅x2=2, x2⋅x3=0, x2⋅x4=3, x3⋅x3=2, x3⋅x4=3, x4⋅x4=9. Add 1 and square:
K=1111191161191611616100.
Step 2 — balance and support vectors (b).21−41−41−0=0 ✓. Support vectors: x1,x2,x3. α4=0 means x4's rule has room: it lies strictly outside the street and plays no part in f (checked in Step 4).
Step 3 — b (c). From x1: 21−41−41−0+b=1⇒b=1. Confirm with x2 (column 1,9,1,16): 21−49−41=−2, and y2(−2+1)=(−1)(−1)=1 ✓.
Step 4 — is x₄ really outside? Column 4 is 1,16,16,100: f(x4)=21−4−4+1=−6.5, score 6.5>1 ✓. Consistent with α4=0. (If a given price ever fails this check, the numbers are not an answer — say so.)
Step 5 — classify (d).(1,0): dots with the support vectors 0,1,1 → 1,4,4: f=21−1−1+1=−21 → −1. (−2,1): dots 0,−1,−3 → 1,0,4: f=21−0−1+1=21 → +1.
Step 6 — the circle (optional).f=23−21[(x1+1)2+x22], so f=0⟺(x1+1)2+x22=3: a circle centred at (−1,0) with radius 3≈1.73. The origin gives f=1, (1,±1) give f=−1, (3,0) gives −6.5 ✓.
answers at a glance: K as above; balance holds; support vectors x1,x2,x3, and x4 is outside the street (score 6.5); b=1; (1,0)→−1 (f=−21), (−2,1)→+1 (f=21); boundary (x1+1)2+x22=3.
Problem 16hardkernel SVM · 1-D
One-dimensional data: x1=1, y1=+1; x2=−1, y2=+1; x3=3, y3=−1; x4=−3, y4=−1. No single threshold separates them. Use K(x,z)=(xz+1)2. (a) Compute the kernel table. (b) Solve the hard-margin dual. (c) Find b, write f(x) in closed form, give the boundary on the line, and classify x=2 and x=−2.5. (d) Write the feature map φ(x) and use it to check K(1,3).
What this tests. Whether the recipe survives with scalars instead of vectors; mirror-image symmetry; turning f into a formula; the meaning of φ. Plan. Products, add 1, square. Reflecting x→−x swaps the points in pairs, so α1=α2, α3=α4; balance equates them.
Show the full solution
Step 1 — the table (a). Products xixj, add 1, square: (1+1)2=4, (−1+1)2=0, (3+1)2=16, (−3+1)2=4, (9+1)2=100, (−9+1)2=64:
K=40164044161641006441664100.K12=0: the points 1 and −1 are at right angles upstairs — kernel values may be zero.
Step 2 — symmetry and balance.α1=α2=a, α3=α4=c; balance 2a−2c=0⇒c=a.
Step 3 — the dual (b). Same-class blocks: (4+0+0+4)a2=8a2 and (100+64+64+100)a2=328a2; cross blocks: −2(16+4+4+16)a2=−80a2. Total 256a2:
D(a)=4a−128a2⇒a=641.
All four prices 641: all support vectors.
Step 4 — b and f (c). From x1=1 (column 4,0,16,4): 641(4+0−16−4)+b=1⇒b=1+41=45. Confirm from x3: −[641(16+4−100−64)+45]=−[−64144+6480]=1 ✓. Closed form, using (u+1)2+(1−u)2=2u2+2:
f(x)=641[(2x2+2)−(18x2+2)]+45=45−x2.
Step 5 — boundary and classification.f=0⟺x=±5≈±2.24: two thresholds, "class +1 if ∣x∣<5". Checks: f(±1)=1, f(±3)=−1 ✓. f(2)=45−4=41 → +1 (inside the street); f(−2.5)=45−6.25=−0.3125 → −1.
Step 6 — the feature map (d).(xz+1)2=x2z2+2xz+1=(x2)(z2)+(2x)(2z)+(1)(1), so φ(x)=(x2,2x,1). Check: φ(1)=(1,2,1), φ(3)=(9,32,1), dot product 9+6+1=16=(3+1)2 ✓. Upstairs w=(−41,0,0): the cut is x2=5, with edges x2=1 and x2=9 — a flat street 8 wide in the lifted space, two thresholds on the line.
answers at a glance: K as above; αi=641 for all four; b=45; f(x)=(5−x2)/4, boundary x=±5; x=2→+1, x=−2.5→−1; φ(x)=(x2,2x,1), K(1,3)=16.
Remember
As in Problem 12, symmetry picks the natural prices, but here other price sets give the very same machine too (for example α=(0,321,961,481)); b and f never change. And a kernel SVM in one dimension can still draw two thresholds: flat upstairs, curved down here.
Next up
Unit 14 · Thinking in Probabilities— upcoming
Every unit so far has been geometry — lines, projections, eigenvectors, margins. Everything that comes next runs on uncertainty. Unit 14 teaches the language: how likely, how surprised, how far apart two beliefs are — and it shows that the covariance ellipse of Unit 12 was a Gaussian all along, and that "minimise the squared error" was secretly "make the data most likely".