Support Vector Machines

Draw two clouds of points on paper, one class each, well apart. Now draw a line that separates them. You will find you can draw infinitely many — nudge yours a little and it still works. Most classifiers pick one arbitrarily: once every point is on the right side, nothing is left to optimise. Support vector machines add the missing criterion: of all the lines that separate the classes, take the one that leaves the widest empty corridor on either side.

The intuition is a border dispute. Two villages need a boundary. Any line in the gap between them technically works, but the sensible surveyor puts it down the middle of the no-man's-land, because then a small error in anyone's map does not suddenly put a farmhouse in the wrong country. The width of that no-man's-land is the margin, and maximising it is the entire idea of an SVM.

The maths, one symbol at a time

A linear classifier scores a point $x$ with $w \cdot x + b$, where $w$ is a vector of weights (it points perpendicular to the boundary) and $b$ is an offset that slides the boundary back and forth. You predict class $+1$ when the score is positive and $-1$ when it is negative, so the boundary itself is where the score is zero.

Scores can be rescaled freely, so fix the units by demanding that the closest points on each side score exactly $\pm 1$. Every training point must then satisfy

$$y_i\,(w \cdot x_i + b) \;\ge\; 1$$

which says in plain English: every point is on its own side, and no closer to the boundary than the corridor edge. Under that convention the corridor width works out to $2/\lVert w\rVert$, so making the margin wide means making $\lVert w \rVert$ small. The SVM is therefore

$$\min_{w,\,b} \; \tfrac{1}{2}\lVert w \rVert^2 \quad \text{subject to} \quad y_i\,(w \cdot x_i + b) \ge 1 \;\; \text{for all } i$$

— shrink the weights as far as the "everyone stays outside the corridor" rules allow. It is a convex problem, so there is one answer and no local minima to worry about.

Worked example 1: two points

Put a negative point at $x^- = (1,1)$ and a positive point at $x^+ = (3,3)$. By symmetry $w$ must point along $(1,1)$, so write $w = (a, a)$. The two constraints hold with equality at the support vectors:

$$3a + 3a + b = 1, \qquad -\,(a + a + b) = 1$$

The second rearranges to $2a + b = -1$. Subtracting it from the first gives $4a = 2$, so $a = 0.5$ and $b = -1 - 2(0.5) = -2$. The boundary is $0.5x_1 + 0.5x_2 - 2 = 0$, the perpendicular bisector of the two points. Its margin is

$$\frac{2}{\lVert w \rVert} = \frac{2}{\sqrt{0.5^2 + 0.5^2}} = \frac{2}{0.7071} = 2.83$$

which is exactly the distance between the two points — the corridor fills the whole gap, as it should.

Worked example 2: what C buys you

Real data overlaps, so the hard constraint is relaxed. Each point gets a slack $\xi_i \ge 0$ measuring how far inside the corridor it strays, and the objective becomes $\tfrac{1}{2}\lVert w\rVert^2 + C\sum_i \xi_i$. The knob $C$ is the fine per unit of trespass.

Add a third point, $(2,2)$, labelled positive — it sits dead on the old boundary, scoring $1 + 1 - 2 = 0$. Its slack is $\xi = 1 - 0 = 1$. Two options:

• Keep the wide corridor and pay the fine. Cost $= \tfrac{1}{2}(0.5) + C(1) = 0.25 + C$.
• Tighten the corridor so nobody trespasses. Making $(2,2)$ a support vector gives $w = (1,1)$, $b = -3$, no slack, and a cost of $\tfrac{1}{2}(2) + 0 = 1$. The margin shrinks to $\sqrt{2} = 1.41$.

With $C = 0.1$ the first costs $0.35$ against $1$, so the SVM shrugs and keeps the wide street. With $C = 10$ it costs $10.25$, so the SVM contorts to accommodate one point. Small $C$ means a smooth boundary that tolerates noise; large $C$ means a boundary that chases outliers. Slide the flexibility control below and watch that trade-off happen.

What this means in practice

The constraint form of the objective is equivalent to minimising hinge loss, $\max(0,\, 1 - y_i(w\cdot x_i + b))$, plus a size penalty — so an SVM is plain Empirical Risk Minimization with a particular loss. Rewriting the problem in its dual form makes the data appear only through inner products, which is the door to the The Kernel Trick and Kernel Methods and to curved boundaries at linear cost. On desks, SVMs earn their keep where features outnumber observations — text and sentiment classification, small labelled event studies — because the margin criterion degrades gracefully in high dimensions.