Kernels

Where We Are

Support Vector Machines search for a separating hyperplane with a large margin. But XOR-like data cannot be separated by one line in its original coordinates.

We could create new features explicitly. Kernels give us a cleverer route.

1. Lift the data

Consider one-dimensional input $x$. Add a feature $x^2$:

$\phi(x)=[x,x^2].$

Points that were tangled on a line can become separable in a plane.

original x:   • ○ ○ •

lifted (x,x²):
 x² ↑       •       •
    |    ○       ○
    +--------------→ x

A nonlinear boundary in the original space can be a linear boundary in the transformed space.

2. The computational problem

What if $\phi(x)$ contains millions—or infinitely many—features? Computing every coordinate sounds impossible.

The SVM optimization often needs feature vectors only through dot products:

$\phi(x)^T\phi(z).$

A kernel computes that inner product directly:

$K(x,z)=\phi(x)^T\phi(z).$

This is the kernel trick.

3. Example: polynomial kernel

$K(x,z)=(x^Tz+c)^d.$

This behaves like a dot product in a feature space containing polynomial combinations, without explicitly constructing them all.

The RBF kernel is

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

Nearby points have similarity near 1; distant points approach 0.

4. A kernel is a similarity with geometry behind it

Do not memorize “kernel = magic nonlinear function.” The useful mental model is:

input points
   ↓ implicit feature map φ
richer space
   ↓ dot product
similarity used by a linear algorithm

5. The RBF scale matters

Large $\gamma$ makes similarity decay very quickly. Each point influences only a tiny neighbourhood and the boundary can become wiggly.

Small $\gamma$ creates broad influence and smoother boundaries.

This is another appearance of the complexity/generalization trade-off.

6. Beyond SVMs

Kernel ideas appear in Gaussian processes, kernel PCA, density methods and theoretical analyses. Modern neural networks usually learn representations rather than choose a fixed kernel, but both approaches share a central goal: create a geometry where the task becomes simpler.

What to Remember

• Nonlinear data can become linearly separable after a feature transformation.
• Kernels compute inner products in an implicit feature space.
• Polynomial and RBF kernels create different geometries.
• Hyperparameters control how flexible that geometry becomes.

Next → K-Means: so far labels told us what to predict. What can a machine discover when nobody gives it labels at all?