Linear, polynomial, and RBF kernels

WHY do we even need kernels?

WHAT the linear SVM does: it finds a separating hyperplane $w^\top x + b = 0$. Its decision function, after training, can be written using only dot products between the query point $x$ and the support vectors $x_i$:

$f(x) = \sum_{i} \alpha_i y_i \,(x_i^\top x) + b$

WHY this matters: the data $x$ only ever appears inside a dot product $x_i^\top x$. So if the data isn't linearly separable in its raw form, we can map it with $\phi(x)$ into a richer space and hope it becomes separable there. Then the decision function needs $\phi(x_i)^\top\phi(x)$.

HOW the trick saves us: computing $\phi(x)$ explicitly can be expensive or infinite-dimensional. But if there's a function $K$ with

$K(x,z) = \phi(x)^\top \phi(z)$

we never build $\phi$. We just replace every dot product by $K$. That replacement is the whole game.

The three workhorse kernels

Here $\gamma$ (gamma), $c$ (coef0), and $d$ (degree) are hyperparameters. Let us derive each feature map so you see why they are valid.

1. Linear kernel — the trivial map

Derivation. Take $\phi(x)=x$. Then $\phi(x)^\top\phi(z)=x^\top z=K(x,z)$. Done. It is a kernel with the identity feature map. Use it when $d$ is large and data is already ~linearly separable (text, sparse features).

2. Polynomial kernel — derive the feature map from scratch

Take the simplest case $d=2$, $c=1$, $\gamma=1$, in 2D with $x=(x_1,x_2)$, $z=(z_1,z_2)$.

$K(x,z)=(x^\top z+1)^2=(x_1z_1+x_2z_2+1)^2$

Expand it (this is why it's a kernel — we can read off $\phi$):

$= x_1^2z_1^2 + x_2^2z_2^2 + 2x_1x_2z_1z_2 + 2x_1z_1 + 2x_2z_2 + 1$

Why this step? Group each term as (something in $x$)$\times$(same something in $z$). That grouping is a dot product $\phi(x)^\top\phi(z)$ with

$\phi(x)=\big(x_1^2,\;x_2^2,\;\sqrt{2}\,x_1x_2,\;\sqrt{2}\,x_1,\;\sqrt{2}\,x_2,\;1\big)$

So a degree-2 polynomial kernel silently gives you all squares, cross-terms and linear terms — a 6-dimensional feature space from 2 inputs, computed with one dot product and one square. The $c$ controls how much weight low-order terms get; larger $c$ → more emphasis on lower-degree features.

3. RBF kernel — why it's an infinite-dimensional map

Start from $\lVert x-z\rVert^2 = x^\top x - 2x^\top z + z^\top z$:

$K(x,z)=e^{-\gamma\lVert x-z\rVert^2}=\underbrace{e^{-\gamma\lVert x\rVert^2}e^{-\gamma\lVert z\rVert^2}}_{\text{normalizers}}\; e^{\,2\gamma\, x^\top z}$

Now Taylor-expand the last factor:

$e^{2\gamma x^\top z}=\sum_{k=0}^{\infty}\frac{(2\gamma)^k}{k!}(x^\top z)^k$

Why this step? Each $(x^\top z)^k$ is itself a (homogeneous) polynomial kernel of degree $k$, i.e. a dot product in a finite space. A weighted sum of kernels is a kernel, and here the sum runs to infinity → RBF corresponds to an infinite-dimensional feature map containing polynomial features of every degree. That's why it's so expressive.

Worked examples

Common mistakes (steel-manned)

Active recall

Flashcards

Connections

• Support Vector Machines — kernels plug into the dual decision function.
• The Kernel Trick — the general principle behind all three.
• Mercer's Theorem — PSD Gram matrix condition.
• Bias-Variance Tradeoff — $\gamma$, $d$, and $C$ control it.
• Feature Scaling / Standardization — required preprocessing.
• Overfitting and Regularization — why not to crank complexity.
• Gaussian / RBF functions — same bell shape as in Naive Bayes densities.

Concept Map

Hinglish (regional understanding)