Support Vector Machines: Margins and Kernels

Most classifiers are fitted by writing down a loss and minimising it. Support vector machines start somewhere more geometric: among all the boundaries that separate two classes, prefer the one that is furthest from every observation. Following that idea honestly leads to a classifier that ignores most of its own training data, and then to a technique for curving the boundary without paying for the space it curves in.

A. The widest slab

In $p$ dimensions a hyperplane is the set where $\beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p = 0$. It splits the space in two, so writing $f(x)$ for that left-hand side gives a classifier: predict $+1$ when $f(x) > 0$ and $-1$ otherwise. With labels coded $\pm 1$, an observation is correctly classified exactly when $y_i f(x_i) > 0$.

If the classes separate at all they usually separate in infinitely many ways, so the question is which hyperplane to take. The maximal margin classifier computes the distance from every observation to a candidate hyperplane, calls the smallest of these the margin, and picks the hyperplane with the largest one. It is the mid-line of the widest slab that fits between the classes.

Six points make it concrete. Class $+1$ at $(3,3)$, $(4,4)$, $(3,5)$ and class $-1$ at $(1,1)$, $(0,2)$, $(2,0)$. The answer is $x_1 + x_2 - 4 = 0$, with distances $|x_1 + x_2 - 4|/\sqrt{2}$:

$$\begin{array}{lll} (3,3),\ (1,1),\ (0,2),\ (2,0) & \sqrt{2} \approx 1.414 & \text{support vectors} \\ (4,4),\ (3,5) & 2\sqrt{2} \approx 2.828 & \text{irrelevant} \end{array}$$

Four observations touch the edge of the slab and hold it in place; these are the support vectors. The other two can be moved anywhere on their own side of the slab, as long as they stay outside it ($x_1 + x_2 \ge 6$), without changing the fitted classifier at all. Move one inside and the slab narrows. Note the support vectors are not split evenly between classes.

The optimisation is stated as maximising $M$ subject to $\sum_j \beta_j^2 = 1$ and $y_i(\beta_0 + \beta\cdot x_i) \ge M$ for every $i$. That normalisation looks like bookkeeping but is essential: scaling all the coefficients by any $k \neq 0$ describes the same hyperplane, so without a scale convention the parameters are undetermined. Fixing the length to one also makes the constrained quantity the true perpendicular distance.

B. Why perfection is the wrong goal

The maximal margin classifier fails in two ways. It has no solution at all when the classes are not separable, which is common. And when it does work, it is determined entirely by the points nearest the boundary, so it inherits their instability: add a single $+1$ observation at $(1.6, 1.6)$ to the six above and the best achievable margin drops from $1.414$ to $0.424$. One point, a factor of more than three. Since a narrow margin is exactly what fails to generalise, demanding perfect separation defeats itself.

The support vector classifier allows violations and charges for them. Each observation gets a slack variable $\varepsilon_i \ge 0$, the constraint becomes $y_i(\beta_0 + \beta \cdot x_i) \ge M(1 - \varepsilon_i)$, and the total is capped at $\sum_i \varepsilon_i \le C$. The slack says how badly a point behaves: zero is on the right side of the margin, up to one is inside the margin but still correctly classified, and above one is on the wrong side of the hyperplane altogether.

$C$ is a budget for violation. At $C = 0$ nothing is affordable and the problem reverts to the maximal margin classifier. As $C$ grows the margin widens and more points sit inside it. Because each misclassification costs more than one unit, $C$ also caps the number of training errors. It is not estimated by the optimiser; it is tuned by cross-validation.

The soft-margin problem has a property worth isolating: an observation strictly on the correct side of the margin has no effect on the classifier. Move it and nothing changes. Only points on the margin or violating it - the support vectors - enter the solution with non-zero coefficients. That is the precise sense in which the method is robust to distant points, and where it differs from linear discriminant analysis, which uses every observation through the class means and covariance.

$C$ is therefore the bias-variance dial in another costume. Small $C$ gives a narrow margin held up by few points: low bias, high variance. Large $C$ gives a wide margin resting on many: more bias, less variance.

C. Bending the boundary for free

Some data are not separated by anything flat - a class in a ring around another, say. The standard remedy is to enlarge the feature space: fit a linear boundary in $x_1, x_2, x_1^2, x_2^2, x_1x_2$ and it comes back down to the plane as a conic. The obstacle is cost. The monomials of degree at most 2 on $p$ predictors, constant included, number $(p+1)(p+2)/2$:

$$\begin{array}{ll} p = 2 & 6 \\ p = 10 & 66 \\ p = 100 & 5{,}151 \\ p = 1{,}000 & 501{,}501 \end{array}$$

What rescues it is that the solution can be written $f(x) = \beta_0 + \sum_i \alpha_i \langle x, x_i\rangle$, and fitting the $\alpha_i$ needs only the inner products between pairs of training observations. Neither step ever touches the coordinates. So replace every inner product with a kernel $K(x_i, x_{i'})$, a similarity function, and the algorithm still works - now implicitly in whatever space that kernel corresponds to. Since $\alpha_i$ vanishes off the support vectors, the sum is short as well.

The polynomial kernel $K(x_i,x_{i'}) = (1 + \sum_j x_{ij}x_{i'j})^d$ turns the support vector classifier into a support vector machine. It is not sleight of hand, and it is worth checking once. For $p = 2$, $d = 2$:

$$(1 + x_1z_1 + x_2z_2)^2 = \langle \varphi(x), \varphi(z)\rangle, \qquad \varphi(x) = \big(1, \sqrt{2}x_1, \sqrt{2}x_2, x_1^2, x_2^2, \sqrt{2}x_1x_2\big) .$$

The kernel returns a six-dimensional inner product from two dimensions of input. At $p = 1{,}000$ the explicit map needs half a million coordinates while the kernel still costs a thousand multiplications.

The other common choice is the radial kernel $\exp(-\gamma \sum_j (x_{ij} - x_{i'j})^2)$, which depends only on distance and decays exponentially in its square. With $\gamma = 1$, a squared distance of $2$ gives $0.135$ and a squared distance of $8$ gives $0.000335$. It is local: a prediction is governed by the training points near it, and distant ones enter with weights indistinguishable from zero. That locality is the source of its flexibility, and it corresponds to an infinite-dimensional feature space you could not write down at any price - which is the strongest argument for working through kernels rather than coordinates.

Check it for yourself below rather than on three fixed pairs. Move the second point anywhere: the kernel, computed from two coordinates, and the inner product of the two six-dimensional maps stay the same number, and the six coordinates the right-hand side had to build are printed underneath. Then switch to the radial kernel and push the points apart. Two units is already enough for a training observation to contribute nothing that matters.

Where this leaves you

A margin is a defensible reason to prefer one boundary over another, and the support vectors are the only data that matter to it. Insisting on perfect separation is fragile, so a budget for violations buys stability, and that budget is the familiar bias-variance dial. Kernels then curve the boundary by changing what "similarity" means rather than by building a larger space. The training path Support Vector Machines works each of these by hand and in code.