Kernels & the Kernel Trick

Source: Unit 2 §12

The problem: non-linearly separable data

Recall the observation that closed the SVM page: the dual involves only scalar quantities plus the dot product $x_i \cdot x_j$. That makes it cheap - as long as a dot product of two vectors is all we ever need.

But what if the data is not linearly separable at all?

⚠GotchaThe obvious fix is not obviously affordable

The idea is to add another dimension until the data becomes separable. Which dimension, though, and how many? More dimensions means more computation, and real data already has on the order of 1000 dimensions - separating it might need scaling by another factor of 1000.

Transforming to higher dimensions

A 1-D example. Points on a line that no threshold separates. Map each one to a 2-D feature vector $z = [x,\ x^2]$ and the picture changes completely.

The same seven points. On the line no threshold separates them; once the second coordinate x² is added, a single straight line does.

So there exists a set of dimensions - a feature map $\varphi$ - that separates the data. The catch is that computing $\varphi$ explicitly in high dimensions is expensive.

The kernel trick

Because the dual only ever needs the dot product $\varphi(x_i) \cdot \varphi(x_j)$, we can compute that dot product directly with a kernel function, without ever computing $\varphi(x)$ in the high-dimensional space at all:

$$K(x_i, x_j) = \varphi(x_i) \cdot \varphi(x_j)$$

The modified dual simply replaces $x_i \cdot x_j$ with $K(x_i, x_j)$:

$$\max \ \sum_i \alpha_i - \tfrac{1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j K(x_i, x_j)$$

◎Exam cueMercer's condition

For any kernel to be valid, it must be expressible as a dot product in some feature space. That is Mercer's condition, and it is the whole licence for substituting $K$ into the dual.

Polynomial kernel

$$K(a, b) = (a \cdot b + 1)^d$$

The worked demonstration: compute $(a \cdot b + 1)^2$ directly, then map both vectors into the higher-dimensional space and take the dot product there. Both give the same value. One dot product plus a constant, squared, replaces an expensive high-dimensional mapping.

→StepsSeeing the two routes meet, for d = 2 in 2-D

1. Take $a = (a_1, a_2)$ and $b = (b_1, b_2)$. The cheap route is $(a \cdot b + 1)^2 = (a_1 b_1 + a_2 b_2 + 1)^2$.
2. Expand it: $a_1^2 b_1^2 + a_2^2 b_2^2 + 2 a_1 a_2 b_1 b_2 + 2 a_1 b_1 + 2 a_2 b_2 + 1$.
3. The expensive route maps each vector with $\varphi(x) = (x_1^2,\ x_2^2,\ \sqrt{2}x_1x_2,\ \sqrt{2}x_1,\ \sqrt{2}x_2,\ 1)$ and takes the 6-dimensional dot product.
4. That dot product expands to exactly the same six terms. So for $d = 2$ the kernel implicitly includes all pairwise feature products - and we never build $\varphi$.

Gaussian / RBF kernel

$$K(x, x') = \exp\!\left( -\frac{\lVert x - x' \rVert^2}{2\sigma^2} \right) = \exp\!\left( -\gamma \lVert x - x' \rVert^2 \right)$$

The RBF kernel is a similarity score: identical points score 1, and the score falls away with the radial distance between them, never quite reaching 0.

≡FactsEverything the RBF kernel is

• The most popular kernel - effectively synonymous with SVM, and the default choice.
• It has the same shape as a Gaussian, but it is not a PDF: it is not normalised.
• It measures similarity between $x$ and $x'$. Identical points give $\exp(0) = 1$, the maximum; different points give a value in $[0, 1)$, and the farther apart they are, the smaller it gets.
• It depends only on the radial distance between the points, independent of their absolute position - hence Radial Basis Function.
• It effectively maps into infinite dimensions.

The hyperparameters C and γ

Parameter	Controls	High value	Low value
γ (gamma)	Reach or width of a single training point's influence (RBF)	High variance, low precision - wiggly, tight boundary, overfits	Low variance, high precision - smoother boundary
C	Trade-off between margin width and the misclassification penalty	Hard margin - punishes errors heavily, risks overfitting	Soft margin - tolerates some misclassification, generalises more

The same points, two settings. Both classify every training point correctly - that is what "large C" buys - but only the smooth one would survive a new point.

?DECISIONWhich way to move C and γ?

Training accuracy is high, validation accuracy is much lower→Lower C, lower γthe boundary has memorised the training set - smooth it out

Both training and validation accuracy are poor→Raise C, raise γthe boundary is too smooth to capture the real shape

A few noisy points sit deep inside the wrong class→Lower Ca soft margin lets the SVM write them off instead of contorting around them

Pick this when: the SVM scores far better on training data than on validation data, or far worse on both

◎Exam cueThe one sentence on tuning

Tuning C and γ is how you balance bias against variance in an SVM - underfitting against overfitting. Small C and small γ give a smoother, more general boundary that may underfit; large C and large γ give a wigglier, tighter boundary that may overfit. With the right C and γ, SVMs work like a charm.