Support Vector Machines & the Kernel Trick

A support vector machine (SVM) classifies by the sign of a score $f(x)=w^Tx+b$. Many hyperplanes may separate training classes; the SVM chooses the one with the widest normalized gap to the nearest points. That margin encodes a robustness preference: small perturbations of non-boundary points should not change the decision.

Hard margin geometry #

For labels $y_i\in\{-1,+1\}$, scale $w,b$ so the nearest training points satisfy $y_i(w^Tx_i+b)=1$. The hard-margin problem is

$$\min_{w,b}\frac12\lVert w\rVert^2 \quad\text{subject to}\quad y_i(w^Tx_i+b)\geq1.$$

The two supporting planes $w^Tx+b=\pm1$ are separated by $2/\lVert w\rVert$. Minimizing norm maximizes this width. Only points on the margin constrain the optimum; these are the support vectors.

In one dimension, negative points at $-2,-1$ and positive points at $1,2$ yield boundary $x=0$. The support vectors are $-1$ and $1$, and the margin spans the empty interval between them. Moving $-2$ farther left changes nothing; moving $-1$ changes the solution.

Soft margin handles overlap #

Real classes overlap and labels contain errors. Introduce slack variables $\xi_i\geq0$:

$$\min_{w,b,\xi}\frac12\lVert w\rVert^2+C\sum_i\xi_i,$$

$$y_i(w^Tx_i+b)\geq1-\xi_i.$$

$C$ prices violations relative to a wide margin. Large $C$ aggressively fits training cases and permits a larger norm; small $C$ accepts more violations for a smoother boundary. Equivalent formulations may scale $C$ with sample count, so numeric values are not portable across implementations without checking the exact objective.

The unconstrained view uses hinge loss $\max(0,1-yf(x))$. Correct points outside the margin have zero loss; points inside or beyond the wrong side contribute linearly.

The kernel trick #

The dual optimization depends on feature vectors only through inner products $x_i^Tx_j$. Replacing them with a kernel

$$K(x,z)=\langle\phi(x),\phi(z)\rangle$$

fits a linear separator in an implicit feature space without explicitly constructing $\phi(x)$. The resulting score is

$$f(x)=\sum_{i\in SV}\alpha_i y_iK(x_i,x)+b.$$

The radial-basis kernel

$$K(x,z)=\exp(-\gamma\lVert x-z\rVert^2)$$

makes influence local. Large $\gamma$ creates narrow neighbourhoods and a highly flexible boundary; small $\gamma$ makes points broadly similar and the boundary smoother. $C$ and $\gamma$ interact and must be tuned together inside validation.

Not every similarity function is a valid kernel. A valid Gram matrix must satisfy the positive-semidefinite conditions needed to represent inner products and preserve convexity.

Scaling is load-bearing #

RBF distance and linear model norm depend on units. A feature with a large numeric range dominates $\lVert x-z\rVert^2$ and changes what “wide margin” means. Fit scaling on training folds only. Sparse text often uses linear SVMs with normalized count features because nonlinear kernel matrices are computationally unnecessary.

Kernel SVM training scales poorly with the number of samples because it operates on pairwise relationships; memory can approach quadratic. Prediction cost grows with the number of support vectors. Linear primal or approximate-kernel methods are more practical for very large datasets.

Scores are not probabilities #

Distance from the decision boundary is a ranking score, not a posterior probability. Probability outputs require a separate fitted calibration mapping and therefore additional held-out or cross-validated data. Calibrate under deployment prevalence; a score calibrated on balanced resampling will not remain a deployment probability automatically.

Multiclass SVMs commonly combine one-vs-rest or one-vs-one binary problems. The choice affects training cost and how scores are reconciled; there is no single native multiclass maximum-margin probability model hidden underneath.

Counterexamples and diagnostics #

• XOR is not linearly separable in its raw coordinates; an interaction feature or nonlinear kernel is required.
• A large-margin separator can still use a leaked feature and fail completely in deployment.
• One mislabeled remote point can distort a large-$C$ solution; inspect support vectors and sensitivity to $C$.
• High-dimensional RBF tuning can become meaningless when distances concentrate.
• Kernel flexibility does not provide extrapolation semantics outside observed support.
• “Only support vectors matter” describes the fitted solution, not data governance: preprocessing statistics and hyperparameter choices used other samples too.

SVMs are strongest when margin geometry matches the task, sample size is manageable, and a carefully validated kernel supplies useful structure. The kernel is an assumption about similarity, not a free nonlinear upgrade.