SVMs & the Kernel Trick

The idea

Many hyperplanes separate two separable classes; an SVM picks the one with the widest street between them. The intuition for why that generalizes: test points are noisy copies of training points, and the boundary with maximum clearance is the one a noisy point is least likely to stumble across. Scale $w, b$ so the street edges are $w^{\top}x + b = \pm 1$; the street (margin) width is then $2/\|w\|$, and maximizing it is the hard-margin problem:

$\min_{w,b}\ \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w^{\top}x_i + b) \ge 1,\qquad y_i \in \{-1,+1\}$

Soft margin and C. Real data overlaps, so allow violations $\xi_i \ge 0$ (point $i$ may sit inside the street or on the wrong side) and charge $C$ per unit:

$\min_{w,b,\xi}\ \frac{1}{2}\|w\|^2 + C\sum_i \xi_i \quad \text{s.t.} \quad y_i(w^{\top}x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0$

Small $C$: violations are cheap → wider margin, more violations → higher bias, lower variance. Large $C$: violations are expensive → narrow margin that contorts to fit every point → lower bias, higher variance. On separable data, $C \to \infty$ approaches the hard-margin solution; on nonseparable data the hard-margin constraints are infeasible. Note the direction: $C$ works like an inverse regularization strength (sklearn agrees).

Hinge + L2 view. At the optimum $\xi_i = \max(0,\ 1 - y_i f(x_i))$ with $f(x) = w^{\top}x + b$, so the whole thing is just regularized empirical risk:

$\min_{w,b}\ C\sum_i \underbrace{\max(0,\ 1 - y_i f(x_i))}_{\text{hinge loss}} + \frac{1}{2}\|w\|^2$

Same recipe as L2-regularized logistic regression with hinge swapped for log loss. The hinge is exactly zero once $y f(x) \ge 1$ — points comfortably outside the street contribute nothing, which is where sparsity comes from. Log loss is never exactly zero, so logistic regression listens to every point.

Support vectors. Solving via Lagrange duality gives one weight $\alpha_i$ per training point:

$\max_{\alpha}\ \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle \quad \text{s.t.} \quad 0 \le \alpha_i \le C,\ \ \sum_i \alpha_i y_i = 0$

Most points get $\alpha_i = 0$. The support vectors — on the margin, inside it, or misclassified — are the only ones with $\alpha_i > 0$, and $w = \sum_i \alpha_i y_i x_i$ depends only on them. Delete any other point and retrain: identical boundary.

Why kernels work. Look at the dual and the prediction $f(x) = \sum_i \alpha_i y_i \langle x_i, x \rangle + b$: the data enters only through inner products. So replace every $\langle x, z \rangle$ with a kernel $K(x, z) = \langle \phi(x), \phi(z) \rangle$ and you have trained a linear separator in $\phi$-space without ever computing $\phi$. Concrete proof that this is real — in 2-D, the degree-2 polynomial kernel:

$(x^{\top}z)^2 = (x_1 z_1 + x_2 z_2)^2 = x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2 = \phi(x)^{\top}\phi(z)$

with $\phi(x) = (x_1^2,\ \sqrt{2}\,x_1 x_2,\ x_2^2)$ — a 3-D inner product computed with one 2-D dot product and a square. For the RBF kernel $K(x,z) = \exp(-\gamma \|x - z\|^2)$ the implicit space is infinite-dimensional; large $\gamma$ means similarity dies off over tiny distances → wiggly, memorizing boundary (overfit); small $\gamma$ → everything looks similar, boundary approaches linear (underfit). $\gamma$ and $C$ interact, so tune them jointly on a log grid.

Scaling is mandatory. Kernels are built on distances and inner products; a feature measured in thousands drowns one measured in units, so standardize before fitting — this is not optional polish, it changes the geometry.

Against logistic regression: SVM optimizes a margin, logistic a likelihood; hinge gives no native probabilities (Platt scaling fits a sigmoid to SVM scores on held-out folds); logistic uses all points, SVM only support vectors. SVMs still win on small-to-medium $n$ with complex boundaries, and linear SVMs on high-dimensional sparse data like text, where $p \gg n$ and the margin story shines. Past a few hundred thousand rows, kernel training at $O(n^2)$ to $O(n^3)$ is off the table.

Worked example

Take $w = (1, 1)$, $b = -3$, so $f(x) = x_1 + x_2 - 3$ and $\|w\| = \sqrt{2} \approx 1.414$. The street edges are $f(x) = \pm 1$ and the margin width is

$\frac{2}{\|w\|} = \frac{2}{\sqrt{2}} = \sqrt{2} \approx 1.414$

Score five points:

Check $A$: $f = 1 + 1 - 3 = -1$, and its distance to the boundary is $|f|/\|w\| = 1/\sqrt{2} \approx 0.707$ — exactly half the street width, as an on-margin point should be. $D$ is correctly classified yet still pays $\xi = 0.5$ for standing inside the street; $E$ pays $1.5$ (crossing the boundary costs more than 1). Total hinge $= 0.5 + 1.5 = 2$, and $\frac{1}{2}\|w\|^2 = 1$, so with $C = 1$ the objective is $1 + 1 \cdot 2 = 3$. If this $(w, b)$ were the trained solution for these points, deleting $F = (3,3)$ would change nothing, while deleting $B$ would let the street rotate and widen.

Now drag it yourself: rotate $w$ until the classes separate and the hinge loss hits zero, then stretch $w$ and watch the street narrow while the loss stays zero — the tension between those two moves is the SVM objective.

Cheat sheet

Primal (soft margin): $\min \frac{1}{2}\|w\|^2 + C\sum_i \xi_i$ s.t. $y_i(w^{\top}x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Margin width $2/\|w\|$.

Hinge form: $\min\ C\sum_i \max(0,\ 1 - y_i f(x_i)) + \frac{1}{2}\|w\|^2$ — hinge + L2, the analogue of penalized logistic regression.

Dual / prediction: weights $0 \le \alpha_i \le C$; $f(x) = \sum_i \alpha_i y_i K(x_i, x) + b$ — data appears only via $K$; only support vectors have $\alpha_i > 0$.

• Sweet spot: small/medium $n$ + complex boundary (RBF), or high-dim sparse features like tf-idf text (linear).
• Platt-scaled probabilities are a second model — sklearn predict and the argmax of predict_proba can disagree.
• Multiclass is bolted on: one-vs-rest or one-vs-one under the hood.