= Kernel trick
{wiki}
The kernel trick evaluates <inner products> of <feature map> outputs through $k(x,z)=\langle\phi(x),\phi(z)\rangle$ without explicitly constructing those <vectors>. An algorithm expressed entirely through these <inner products> can therefore operate on nonlinear derived coordinates using only evaluations of a <positive-semidefinite kernel> on the original inputs. A <classifier> linear in the derived coordinates can have a nonlinear boundary in the original coordinates.
The <polynomial kernel> gives a finite, fully visible example: $k(x,z)=(x^Tz)^2$ corresponds to $\phi(x)=(x_1^2,\sqrt2 x_1x_2,x_2^2)^T$. The <XOR separation by a product feature> below makes the interaction coordinate $x_1x_2$ useful, while <dual prediction with a kernel> shows how to predict without calculating it explicitly.
An arbitrary score called a similarity need not be a <positive-semidefinite kernel>. Symmetry alone, even with nonnegative entries, is insufficient: the symmetric <matrix>
$$
S=\begin{pmatrix}1&2\\2&1\end{pmatrix}
$$
has $a^TSa=-2$ for $a=(1,-1)^T$, so it cannot be a <Gram matrix> of real <inner products>. A <positive-semidefinite kernel> requires a <positive semidefinite matrix> for every finite choice of inputs, not just the observed <training data>.<Gaussian Processes for Machine Learning by Carl Edward Rasmussen and Christopher K. I. Williams>[Section 4.1, p. 80: Gram matrices, quadratic-form definition of positive semidefiniteness, and nonnegative eigenvalues]{ref} The existing <Moore-Aronszajn theorem> connects this requirement to a <Reproducing kernel Hilbert space>; this example needs only finite <linear algebra>.
Back to article page
