Support Vector Machines

Source: Unit 2 §11

SVM is one of the most sophisticated yet simple-to-implement algorithms in machine learning. It is largely thought of as a linear classifier, and it is far more than that.

Myth-busting

Myth	Reality
"Only a linear classifier"	No - it handles non-linearity too, via kernels
"Only single or binary classification"	No - it can do multi-class classification
"Only a classifier"	No - it can do regression as well (SVR)
"Computationally expensive"	No - with the right C and γ it works like a charm
"Math heavy and provable"	Not a myth. It is math-heavy and fundamentally provable

≡FactsLinearly separable, formally

A data set is linearly separable if a hyperplane can separate the classes. In 2-D that hyperplane is a line, in 3-D a plane. Separable points typically form a convex hull.

The key insight: maximum margin

Many hyperplanes can separate the same data, so the question is which one is best. The SVM answer: the one that is farthest from the closest points of both classes.

All three lines classify this training set perfectly. Only one of them leaves room for the next point to arrive slightly out of place.

◎Exam cueThe definition to hold on to

SVM is a maximum-margin classifier, described in the course as "one of the most elegant ideas in computer science". The support vectors are the closest data points to the boundary, and they alone define the hyperplane.

The three hyperplanes

The street is as wide as the closest points allow. Only those points - the support vectors - touch the gutters, and only they determine where H0 sits.

Plane	Equation	Meaning
H0	w·x + b = 0	Decision boundary, the "median" of the street; separates maximally
H1	w·x + b = +1	Upper margin - the closest positive points lie on it
H2	w·x + b = −1	Lower margin - the closest negative points lie on it

≡FactsTwo geometric facts about the street

• $w$ is perpendicular to the street, exactly as it was perpendicular to the perceptron's boundary.
• The distance between H1 and H2 is $2d = (d^{+} + d^{-})$, the street width, and the whole optimisation exists to make it as large as possible.

Building the decision rule

To classify an unknown point $u$, project $u$ onto $w$ with a dot product $w \cdot u$. The farther $u$ sits on the positive side of $w$, the more likely it is a positive sample.

$$\text{classify } u \text{ as } + \text{ if } w \cdot u + b \ge 0, \text{ else } -$$

Without loss of generality the rule can be hardened, insisting that no training point sits inside the street:

$$w \cdot x_i + b \ge +1 \ \text{ for all positive samples} \qquad w \cdot x_i + b \le -1 \ \text{ for all negative samples}$$

The mathematical convenience $y_i$

Introduce a label variable for every instance: $y_i = +1$ for positive samples and $y_i = -1$ for negative ones. Multiplying each of the two constraints by its own $y_i$ flips the negative one round, and the pair collapses into a single inequality:

$$y_i (w \cdot x_i + b) \ge 1 \qquad \text{for all } i$$

Rearranged, $y_i(w \cdot x_i + b) - 1 \ge 0$. For points on the gutter - the support vectors - it is exactly zero:

$$y_i (w \cdot x_i + b) - 1 = 0 \qquad \text{(support vectors)}$$

The quantity to maximise

Take a point $x^{+}$ on the upper margin and $x^{-}$ on the lower margin. The street width is the projection of $(x^{+} - x^{-})$ onto the unit vector $w / \lVert w \rVert$:

$$\text{width} = (x^{+} - x^{-}) \cdot \frac{w}{\lVert w \rVert} = \frac{2}{\lVert w \rVert}$$

→StepsWhere the 2 comes from

1. $x^{+}$ lies on H1, so $w \cdot x^{+} + b = 1$, giving $w \cdot x^{+} = 1 - b$.
2. $x^{-}$ lies on H2, so $w \cdot x^{-} + b = -1$, giving $w \cdot x^{-} = -1 - b$.
3. Subtract: $w \cdot (x^{+} - x^{-}) = (1 - b) - (-1 - b) = 2$.
4. Divide by $\lVert w \rVert$ to turn the projection into a distance: $\text{width} = 2 / \lVert w \rVert$.

Primal form

Maximising $2/\lVert w \rVert$ is the same as minimising $\lVert w \rVert$, which is the same as minimising $\frac{1}{2}\lVert w \rVert^2$:

$$\min \ \tfrac{1}{2}\lVert w \rVert^2 \qquad \text{subject to} \qquad y_i (w \cdot x_i + b) \ge 1 \quad \forall i$$

That is the primal form. The $\frac{1}{2}\lVert w \rVert^2$ shape is a mathematical convenience for differentiation - the same trick as squaring the error in gradient descent.

Constrained optimisation and the Lagrangian

The Lagrange-multiplier detour. To maximise $f(x_1, x_2)$ subject to $g(x_1, x_2) = c$, walk along the constraint curve. The optimum is the point where $\nabla f$ and $\nabla g$ align; any further move along the constraint decreases $f$.

→StepsThe Lagrange algorithm, applied to SVM

1. Construct the Lagrangian, introducing one Lagrange multiplier $\alpha_i$ per constraint - which here means one $\alpha$ per training instance.
2. Compute $L$, set the partial derivatives to 0, and solve.

$$L = \tfrac{1}{2}\lVert w \rVert^2 - \sum_i \alpha_i \left[ y_i (w \cdot x_i + b) - 1 \right], \qquad \alpha_i \ge 0$$

The dual form

It is easier to solve the dual than the primal: instead of minimising over $w$ and $b$, we maximise over the dual variables $\alpha$.

Take the partial derivatives of $L$ with respect to $w$ and $b$ and set both to zero:

$$w = \sum_i \alpha_i y_i x_i \qquad \text{and} \qquad \sum_i \alpha_i y_i = 0$$

◎Exam cueWhat the first of those two says

The weight vector $w$ is a linear combination of the training inputs $x_i$, their labels $y_i$ and their multipliers $\alpha_i$. The model is literally built out of the training data, not merely fitted to it.

Substituting both back into $L$ eliminates $w$ and $b$ and leaves the Wolfe dual:

$$\max \ \sum_i \alpha_i - \tfrac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)$$ $$\text{subject to} \quad \alpha_i \ge 0 \quad \text{and} \quad \sum_i \alpha_i y_i = 0$$

⚠GotchaThe observation the whole next page depends on

The dual depends on the data only through the dot product $x_i \cdot x_j$. Nothing else about $x$ appears anywhere. That single fact is what makes the kernel trick possible.

KKT conditions and the support vectors

≡FactsWhy only a few points matter

• The KKT slack condition implies that for every point except the support vectors, $\alpha_i = 0$.
• Only the support vectors have $\alpha_i > 0$, so only they contribute anything to $w = \sum_i \alpha_i y_i x_i$.
• That is why an SVM is defined by a handful of points: deleting any non-support vector from the training set changes nothing at all.