The Kernel Trick: Feature Maps and Properties of Kernels

Every dual problem derived so far — hard-margin, soft-margin — depends on the training data only through the inner products $\langle x^{(i)},x^{(j)}\rangle$. This note cashes in that structural fact: if a feature map $\phi$ sends inputs into some richer (possibly much higher-, even infinite-dimensional) space, and if $\phi(x)^\top\phi(z)$ can be computed cheaply without ever forming $\phi(x)$ explicitly, then simply swapping $\langle x,z\rangle$ for this kernel function $K(x,z)$ upgrades the SVM (or any dot-product-only algorithm) to learn non-linear boundaries in the original input space, for free.