Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI ๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป๐Ÿค–

Support Vector Machines: Margins and the Kernel Trick

8 minute read

Published:

TL;DR: If two classes can be separated by a straight line, infinitely many lines will do it. The SVM picks the one with the widest empty corridor around it, which turns out to depend on only a handful of points โ€” the support vectors. Solving it reveals that both the fit and the prediction touch the data only through inner products \(x_i^\top x_j\). Replace that inner product with a kernel and you are working in a much larger feature space without ever constructing it.

Which separating line?

Take two classes that a straight line can separate. There is not one such line; there is a continuum of them, and some are visibly worse than others โ€” a line that shaves past a training point will misclassify the next sample drawn from near it.

The support vector machine makes the choice precise: pick the hyperplane whose distance to the nearest point of either class is as large as possible.

Write the hyperplane as \(w^\top x + b = 0\). The signed distance from a point \(x_i\) to it is \((w^\top x_i + b)/\lVert w \rVert\). This is over-parameterised โ€” scaling \(w\) and \(b\) together changes nothing geometrically โ€” so fix the scale by demanding that the closest points satisfy \(\lvert w^\top x_i + b \rvert = 1\). With that convention the two margin boundaries are \(w^\top x + b = \pm 1\), the distance between them is \(2/\lVert w \rVert\), and the problem becomes:

\[ \min_{w,\,b} \ \tfrac{1}{2}\lVert w \rVert^2 \quad \text{subject to} \quad y_i\bigl(w^\top x_i + b\bigr) \ \ge\ 1 \quad \text{for all } i . \]

Maximising the margin and minimising \(\lVert w \rVert^2\) are the same thing. This is a convex quadratic programme, so it has a unique solution and no local minima to worry about.

A worked example you can check

Six points in the plane. Class \(+1\) at \((2,1)\), \((2,3)\), \((3,2)\); class \(-1\) at \((0,1)\), \((0,3)\), \((-1,2)\).

Maximum-margin hyperplane with four support vectorsTwo classes separated by a vertical line at x equals one. The margin band runs from x equals zero to x equals two. Four points lie exactly on the band edges and are the support vectors; two further points sit outside it and do not affect the solution. The widest empty corridor (2,1) (2,3) (3,2) (0,1) (0,3) (โˆ’1,2) margin = 2 ยท circled points are the support vectors w = (1, 0), b = โˆ’1
The maximum-margin solution is the vertical line at x = 1, giving a corridor of width 2. Four points sit exactly on its edges; the two outermost points are irrelevant to the solution.

Take \(w = (1,0)\) and \(b = -1\), so the hyperplane is \(x_1 = 1\). Evaluating \(y_i(w^\top x_i + b)\) at each point:

PointClass\(y_i(w^\top x_i + b)\)ย 
\((2,1)\)\(+1\)\(+1\)support vector
\((2,3)\)\(+1\)\(+1\)support vector
\((3,2)\)\(+1\)\(+2\)ย 
\((0,1)\)\(-1\)\(+1\)support vector
\((0,3)\)\(-1\)\(+1\)support vector
\((-1,2)\)\(-1\)\(+2\)ย 

Every constraint holds, four of them with equality, and \(\lVert w \rVert = 1\) gives a margin of \(2/1 = 2\). A brute-force search over separating directions confirms nothing beats it.

The property the name refers to. Delete \((3,2)\) and \((-1,2)\) and re-solve: you get exactly the same hyperplane and exactly the same margin. Only the points touching the margin constrain the answer. Everything else could be moved freely โ€” as long as it stays outside the corridor โ€” without changing a thing. Those touching points are the support vectors, and there are usually far fewer of them than there are training examples.

Soft margins, for data that is not separable

Real data overlaps, and then no \(w\) satisfies every constraint. Introduce a slack \(\xi_i \ge 0\) per point measuring how far it intrudes:

\[ \min_{w,\,b,\,\xi} \ \tfrac{1}{2}\lVert w \rVert^2 + C\sum_i \xi_i \quad \text{subject to} \quad y_i\bigl(w^\top x_i + b\bigr) \ \ge\ 1 - \xi_i, \quad \xi_i \ge 0 . \]

\(C\) sets the exchange rate between a wide margin and a clean fit. Large \(C\) punishes violations heavily and drives the model towards the separable solution, narrowing the margin and increasing variance. Small \(C\) tolerates intrusions and buys a wider, steadier corridor. It is a regularisation parameter in the sense the biasโ€“variance chapter describes, and it must be tuned rather than guessed.

The one fact everything else rests on

Solve the problem through its Lagrangian dual and the solution takes the form

\[ w = \sum_i \alpha_i y_i x_i , \qquad f(x) = \sum_i \alpha_i y_i \, x_i^\top x + b , \]

with \(\alpha_i \ge 0\) and โ€” this is the same observation as before, now falling out of the algebra โ€” \(\alpha_i = 0\) for every point that is not a support vector.

Look at what \(f\) actually touches. Not the coordinates of \(x\). Only the inner product between \(x\) and each support vector. The training problem has the same character: the dual objective involves the data solely through the pairwise products \(x_i^\top x_j\).

So the coordinates were never needed. If an algorithm reads the data only through inner products, you can hand it a different inner product and it will not notice. That is the whole idea. You do not need to know where the points are in some enormous feature space โ€” you only need to know the angles and lengths between them there.

The kernel trick, made concrete

Define \(k(x,z) = (x^\top z)^2\) for \(x, z \in \mathbb{R}^2\) and expand it:

\[ \begin{aligned} (x^\top z)^2 &= (x_1 z_1 + x_2 z_2)^2 \\[3pt] &= x_1^2 z_1^2 + 2 x_1 z_1 x_2 z_2 + x_2^2 z_2^2 \\[3pt] &= \bigl(x_1^2,\ \sqrt{2}\,x_1 x_2,\ x_2^2\bigr) \cdot \bigl(z_1^2,\ \sqrt{2}\,z_1 z_2,\ z_2^2\bigr). \end{aligned} \]

The right-hand side is an inner product of two explicit three-dimensional vectors. So with \(\varphi(x) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)\) we have \(k(x,z) = \varphi(x)^\top \varphi(z)\) exactly.

Check it on \(x = (1,2)\) and \(z = (3,-1)\). Directly, \(x^\top z = 3 - 2 = 1\), so \(k = 1\). Through the feature map, \(\varphi(x) = (1,\ 2\sqrt{2},\ 4)\) and \(\varphi(z) = (9,\ -3\sqrt{2},\ 1)\), giving \(9 - 12 + 4 = 1\). The same.

That is the trick in full. Computing \(k\) costs one two-dimensional dot product and a squaring. Computing \(\varphi(x)^\top\varphi(z)\) the honest way costs building two three-dimensional vectors first. Here the saving is trivial; for a degree-\(d\) polynomial kernel in \(n\) dimensions the feature space has \(\binom{n+d-1}{d}\) coordinates and the saving is the difference between possible and impossible.

The decision function becomes

\[ f(x) = \sum_{i \in \text{SV}} \alpha_i y_i \, k(x_i, x) + b . \]

Common kernels. The linear kernel \(k(x,z) = x^\top z\) recovers the plain SVM. The polynomial kernel \((x^\top z + c)^d\) gives all monomials up to degree \(d\). The RBF kernel \(k(x,z) = \exp(-\gamma \lVert x - z \rVert^2)\) corresponds to an infinite-dimensional feature space โ€” which is only usable because you never construct it. Its \(\gamma\) controls locality: large \(\gamma\) makes each support vectorโ€™s influence decay quickly, giving a wiggly boundary that can overfit; small \(\gamma\) approaches a linear fit.

Not every function is a kernel. \(k\) must be symmetric and positive semi-definite โ€” every Gram matrix \(K_{ij} = k(x_i, x_j)\) it produces must be PSD. That condition is what guarantees a feature space exists, and it is what keeps the optimisation convex. Invent a similarity function that violates it and the "kernel" SVM you get is solving a different, possibly non-convex problem.

What SVMs do not buy you

They do not scale. Training involves the \(n \times n\) Gram matrix, so cost grows roughly quadratically to cubically in the number of training points and memory quadratically. Past the order of \(10^5\) samples this is the binding constraint, and it is the main reason SVMs receded as datasets grew.

They do not give probabilities. The output \(f(x)\) is a signed distance, not a likelihood. Converting it to a probability requires a separate calibration step fitted on held-out data, and the result is a retrofit rather than something the model estimated.

Kernel choice is a real decision. With an RBF kernel you are tuning \(C\) and \(\gamma\) together over a 2-D grid, and the result is genuinely sensitive to both. There is no principled default.

They stop being interpretable once kernelised. A linear SVM has a weight vector you can read. An RBF SVM has a set of support vectors and coefficients, and no accessible statement about which features mattered.

They need scaled features. The margin is measured with a Euclidean norm, so a feature in millimetres will dominate one in metres for no good reason. Standardise first.

โœ… Key Takeaways

  • Among the infinitely many separating hyperplanes, the SVM takes the one maximising the corridor width \(2/\lVert w \rVert\) โ€” which makes it the minimiser of \(\lVert w \rVert^2\) under margin constraints.
  • Only the points touching the margin matter. Deleting the rest changes nothing, which is what "support vector" means and why the solution is sparse.
  • The soft margin adds slack variables and the parameter \(C\), trading margin width against violations โ€” a regularisation knob, not a convenience.
  • Both the training problem and the prediction touch the data only through inner products. That is the fact the kernel trick exploits.
  • \((x^\top z)^2\) in 2-D is exactly an inner product of explicit 3-D feature vectors โ€” expand it and see. RBF does the same thing into an infinite-dimensional space you never build.
  • The costs are real: quadratic-to-cubic training, no native probabilities, two coupled hyperparameters, and no interpretability once kernelised.

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test frameworkโ€™s smaller cousin, and a JSON-safe date library already installed โ€” most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually โ€” but โ€˜eventuallyโ€™ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first โ€” which is faster, shorter, and free of race conditions.