Home / MLT / Week 10

Week 10 · Support vector machines

Official syllabus line: Support Vector Machines

About 100 minEnd Term material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 9 (Lagrange multipliers, KKT, complementary slackness), MLT week 2 (kernels), MLT week 9 (linear classifiers).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine kids on a playground, boys on one side, girls on the other. You need to draw a line to separate them. Many lines could work! But which line is the very best? Think of this line as the middle of a road. We want the widest possible road that still keeps all the kids safely on their own sides. This idea is called a Support Vector Machine, aiming for the 'maximum margin'.
This special road has two clear edges. Only the few kids standing right on these edges truly matter for defining the road! These important 'edge-standers' are called 'support vectors.' If you moved any other kid, the road would not change. The best separating line is found by making this road as wide as possible, or 'maximizing the margin'.
Let's try a small example. Imagine two points on a number line: one at zero, labelled negative; another at two, labelled positive. The best separating line will be exactly in the middle, at one. The 'road' would have a width of two, with its edges at zero and two. Both original points become our support vectors, defining this perfect road.
SVMs are super important for your exams! Remember, the margin is two divided by the weight vector's length. Support vectors are the points on the road's edge. A big 'C' means a narrow road, while a small 'C' means a wide road. And with cool tricks, SVMs can even find curved roads! Keep practicing, you've got this!

The one-minute story

Think of it like this

Two groups of kids stand on a playground, boys on the left, girls on the right, and you want to draw a line between them. Many lines work. Which one is best?

Think of the line as the centre of a road. A thin road might be squeezed against some child on either side; any wobble and that child is on the wrong side. The safest line is the one at the centre of the widest possible road that still has nobody standing on it. That is the support vector machine (SVM): maximum margin.

Here is the beautiful surprise. Only the kids standing right at the edges of the road matter. If you moved any child further back, or removed them, the road would not change. Those edge-standers are the support vectors, and they alone decide where the road goes. And thanks to the kernel trick from week 2, the same machine can draw curved roads.

By the end of this week you can:

state the hard-margin SVM problem and compute the margin;
explain the dual problem and the role of support vectors (via complementary slackness);
extend to the soft margin with slack variables and the parameter $C$ ;
use the kernel trick to get non-linear boundaries and read hinge loss.

Words you need

Margin - the width of the empty road between the two classes. A wider margin is more robust.
Support vectors - the training points that lie exactly on the edge of the road (or inside it, in the soft-margin case).
Hard margin - insist that nobody is inside the road: needs separable data.
Soft margin - allow a few points inside or across, at a price.
Slack variable $\xi_i\ge0$ - how far point $i$ violates the road.
$C$ - the price of violations. Large $C$ : strict. Small $C$ : relaxed.
Hinge loss - $\max(0,\,1-y\,f(\mathbf x))$ .

Idea 1: Maximising the margin

Labels $y_i\in\{-1,+1\}$ and a linear classifier $f(\mathbf x)=\mathbf w^T\mathbf x+b$ . We scale $\mathbf w,b$ so that the closest points of each class satisfy $|f(\mathbf x)|=1$ . Then:

every training point obeys $y_i(\mathbf w^T\mathbf x_i+b)\ge1$ (correct side, outside the road);
the two road edges are $\mathbf w^T\mathbf x+b=\pm1$ , and the width of the road is

\text{margin}=\frac2{\|\mathbf w\|}

Making the road as wide as possible means making $\|\mathbf w\|$ as small as possible:

The idea

Hard-margin SVM (primal)

\min_{\mathbf w,b}\ \frac12\|\mathbf w\|^2\qquad\text{subject to}\qquad y_i(\mathbf w^T\mathbf x_i+b)\ge1\ \text{ for all }i

This is a convex problem (quadratic objective, linear constraints) with a unique solution.

Solved example: 1. A one-dimensional SVM

Question. One point $x=0$ with $y=-1$ and one point $x=2$ with $y=+1$ . Find the maximum-margin classifier and its margin.

Solution. In 1-D, $f(x)=wx+b$ . We need $-(w\cdot0+b)\ge1$ , i.e. $b\le-1$ , and $w\cdot2+b\ge1$ . To minimise $\frac12w^2$ take both constraints tight: $b=-1$ and $2w-1=1\Rightarrow w=1$ . So $f(x)=x-1$ , the boundary is at $x=1$ (the midpoint, as you'd expect), and the margin is $\frac{2}{|w|}=\mathbf2$ , the distance between the points. Both points are support vectors.

Idea 2: The dual problem and support vectors

Using Lagrange multipliers $\alpha_i\ge0$ , one for each constraint (MLF week 9), the dual of the hard-margin SVM is

\max_{\boldsymbol\alpha}\ \sum_{i}\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\mathbf x_i^T\mathbf x_j\quad\text{s.t.}\quad\alpha_i\ge0,\ \ \sum_i\alpha_iy_i=0

and the weight vector is recovered as

\mathbf w=\sum_i\alpha_iy_i\mathbf x_i

KKT complementary slackness says $\alpha_i\big[y_i(\mathbf w^T\mathbf x_i+b)-1\big]=0$ . So for any point strictly outside the road ( $y_if(\mathbf x_i)>1$ ) we get $\alpha_i=0$ : it plays no part in $\mathbf w$ . Only points on the road edges ( $y_if(\mathbf x_i)=1$ ) can have $\alpha_i>0$ . These are the support vectors.

Two consequences:

The classifier depends on only a few points. Delete any non-support vector and nothing changes.
The data enters the dual only through dot products $\mathbf x_i^T\mathbf x_j$ . Replace them by a kernel $k(\mathbf x_i,\mathbf x_j)$ and you have a kernel SVM with a curved boundary, at no extra conceptual cost. Prediction is $f(\mathbf x)=\sum_i\alpha_iy_i\,k(\mathbf x_i,\mathbf x)+b$ , a sum over support vectors only.

Solved example: 2. Solving the dual for the 1-D example

Question. For the two points in Example 1 write and solve the dual.

Solution. The points: $x_1=0$ ( $y_1=-1$ ), $x_2=2$ ( $y_2=+1$ ). The constraint $\sum\alpha_iy_i=0$ gives $-\alpha_1+\alpha_2=0$ , so $\alpha_1=\alpha_2=\alpha$ . The double sum has only one non-zero term, $i=j=2$ : $\alpha^2\cdot(+1)(+1)\cdot2\cdot2=4\alpha^2$ (every term involving $x_1=0$ vanishes). The dual objective is $2\alpha-\frac12(4\alpha^2)=2\alpha-2\alpha^2$ . Its maximum: derivative $2-4\alpha=0\Rightarrow\alpha=\mathbf{0.5}$ .

Then $w=\sum\alpha_iy_ix_i=0.5(+1)(2)+0.5(-1)(0)=1$ ✓. And $b$ from a support vector: $y_2(w\cdot2+b)=1\Rightarrow2+b=1\Rightarrow b=-1$ ✓. It matches the primal.

Idea 3: The soft margin

Real data is rarely perfectly separable, or it is separable only by a skinny, fragile road. Allow violations with slack $\xi_i\ge0$ :

The idea

Soft-margin SVM

\min_{\mathbf w,b,\boldsymbol\xi}\ \frac12\|\mathbf w\|^2+C\sum_i\xi_i\quad\text{s.t.}\quad y_i(\mathbf w^T\mathbf x_i+b)\ge1-\xi_i,\ \ \xi_i\ge0

$\xi_i=0$ : the point is correctly outside the road. $0<\xi_i<1$ : inside the road but on the right side. $\xi_i>1$ : on the wrong side (misclassified).
$C$ is the price of a violation. Large $C$ : violations are expensive, so the margin is narrow and few points violate it (low bias, risk of overfitting). Small $C$ : violations are cheap, so the margin is wide and many points may violate (more bias, underfitting risk).
In the dual the only change is the box constraint $0\le\alpha_i\le C$ . Support vectors are the points with $\alpha_i>0$ : on the edge, inside the road, or misclassified.

Hinge loss view. Eliminating $\xi_i$ gives the unconstrained problem

\min\ \frac12\|\mathbf w\|^2+C\sum_i\max\big(0,\;1-y_i(\mathbf w^T\mathbf x_i+b)\big)

The hinge loss is $0$ for points beyond the road edge and grows linearly as a point enters the road or crosses over. Compared with logistic loss (week 9), hinge loss goes exactly to zero for "safe" points, which is why those points drop out.

Idea 4: Non-linear SVMs

Use the kernel trick: the dual and the prediction only need $k(\mathbf x_i,\mathbf x_j)$ . With an RBF kernel the boundary can wrap around clusters. Choices: kernel type (linear, polynomial, RBF) and its parameters (degree, $\sigma$ ), plus $C$ , all chosen by cross-validation. A very small $\sigma$ (very local RBF) lets the SVM memorise: overfits.

Your turn

Your turn: 1. Margin from

\mathbf w

A trained SVM has $\mathbf w=(3,4)$ and $b=-2$ . What is the margin width? On which lines do the road edges lie?

Need a hint?

Margin $=2/\|\mathbf w\|$ .

Show the full solution

$\|\mathbf w\|=5$ , so the margin is $\frac25=\mathbf{0.4}$ . Edges: $3x_1+4x_2-2=+1$ and $3x_1+4x_2-2=-1$ , i.e. $3x_1+4x_2=3$ and $=1$ .

Your turn: 2. Spot the support vectors

A hard-margin SVM gives, for five points, the values $y_if(\mathbf x_i)=1,\;1.8,\;1,\;2.5,\;3.2$ . Which points can be support vectors?

Need a hint?

Support vectors lie exactly on the margin, $y_if=1$ .

Show the full solution

Points 1 and 3. The others are strictly outside the road, so their $\alpha_i=0$ .

Your turn: 3. Effect of

C

What happens to the margin width and to the number of training violations as $C$ increases?

Need a hint?

Large $C$ makes mistakes expensive.

Show the full solution

The margin gets narrower and the number of violations decreases (the model fits the training data more tightly and risks overfitting).

Your turn: 4. Hinge loss

For $f(\mathbf x)=0.4$ and $y=+1$ , compute the hinge loss. And for $f(\mathbf x)=-0.5$ , $y=+1$ ? For $f(\mathbf x)=2$ , $y=+1$ ?

Need a hint?

$\max(0,1-yf)$ .

Show the full solution

$\max(0,0.6)=\mathbf{0.6}$ (inside the road). $\max(0,1+0.5)=\mathbf{1.5}$ (wrong side). $\max(0,1-2)=\mathbf0$ (safe).

Your turn: 5. True or false

(a) Removing a non-support vector changes the SVM solution. (b) The SVM dual depends on the data only through dot products. (c) The SVM objective is convex. (d) A larger $C$ always gives better test accuracy.

Need a hint?

Use complementary slackness.

Show the full solution

(a) False. (b) True. (c) True. (d) False, it can overfit.

Exam radar

In the MLT End Term, summaries mention Soft-Margin SVM in 36 of 49 papers, Hard-Margin SVM in 25, Support Vectors in 20, Dual Problem in 15, Support Vector Machines in 13, Kernel Trick in 16. SVMs are the single most mentioned topic in the End Term.

Typical items: margin $=2/\|\mathbf w\|$ ; "which points are support vectors?"; "what does a large $C$ do?"; "the dual constraint $\sum\alpha_iy_i=0$ "; " $\mathbf w=\sum\alpha_iy_i\mathbf x_i$ "; hinge-loss values; the primal vs dual form; hard vs soft margin differences.

Watch out - real exam trap

Margin is $\frac{2}{\|\mathbf w\|}$ , not $\frac1{\|\mathbf w\|}$ (that is the distance from the boundary to one edge).
Large $C$ $\Rightarrow$ narrow margin, small $C\Rightarrow$ wide margin. Easy to flip.
Support vectors have $\alpha_i>0$ ; in the hard-margin case they lie exactly on $y_if=1$ .
Hard margin needs linearly separable data; soft margin does not.
Don't forget the dual constraint $\sum_i\alpha_iy_i=0$ .

Quick quiz

The margin of a hard-margin SVM with weight vector w is...

||w||
1 / ||w||
2 / ||w||
||w|| squared

The two edges are at w.x + b = +1 and -1, so the gap is 2 / ||w||.

A support vector is a training point...

far from the boundary
on (or inside) the margin, with a non-zero dual weight
that is misclassified only
at the origin

Complementary slackness gives non-zero alpha only for points on the margin edge (or violating it in the soft case).

In the soft-margin SVM, increasing C...

widens the margin
penalises margin violations more, narrowing the margin
removes the slack variables
has no effect

A big C makes violations expensive.

Select all TRUE statements about the SVM. (select all that apply)

The solution depends only on the support vectors.
The dual involves only dot products between data points.
It needs the data to be linearly separable in the soft-margin case.
The primal problem is non-convex.

The soft margin handles non-separable data, and the problem is convex.

Recap

Remember this

Hard margin: $\min\frac12\|\mathbf w\|^2$ s.t. $y_i(\mathbf w^T\mathbf x_i+b)\ge1$ . Margin $=2/\|\mathbf w\|$ .
Dual: $\max\sum\alpha_i-\frac12\sum\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j$ s.t. $\alpha_i\ge0$ , $\sum\alpha_iy_i=0$ ; $\mathbf w=\sum\alpha_iy_i\mathbf x_i$ . Complementary slackness $\Rightarrow$ support vectors only.
Soft margin: add $C\sum\xi_i$ ; $0\le\alpha_i\le C$ ; large $C$ = narrow margin, small $C$ = wide margin. Hinge loss $\max(0,1-yf)$ .
Kernel SVM: replace dot products with $k$ .

Formulas to keep

Primal: $\min\frac12\|\mathbf w\|^2+C\sum\xi_i$ s.t. $y_i(\mathbf w^T\mathbf x_i+b)\ge1-\xi_i$ , $\xi_i\ge0$
Margin $=\frac{2}{\|\mathbf w\|}$
Dual: $\max\sum\alpha_i-\frac12\sum_{ij}\alpha_i\alpha_jy_iy_jk(\mathbf x_i,\mathbf x_j)$ ; $0\le\alpha_i\le C$ ; $\sum\alpha_iy_i=0$
$\mathbf w=\sum\alpha_iy_i\mathbf x_i$ ; $f(\mathbf x)=\sum\alpha_iy_ik(\mathbf x_i,\mathbf x)+b$
Hinge loss: $\max(0,1-y f(\mathbf x))$

Connected weeks (learn them together)

MLF week 9 - Optimising with rules: Lagrange and KKT: The SVM dual comes straight out of Lagrange multipliers and the KKT conditions.
MLP week 8 - SVMs in sklearn: SVMs: the theory, then the code.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 33 real questions on this week All End Term papers