= Dual prediction with a kernel
{title2=$f(z)=\sum_i\beta_i k(p_i,z)+b$}
If the weight <vector> lies in the <linear span> of the training <feature map> outputs, write $w=\sum_i\beta_i\phi(p_i)$. Then
$$
f(z)=w^T\phi(z)+b=\sum_i\beta_i k(p_i,z)+b.
$$
This is a dual representation: coefficients weight training examples rather than feature coordinates. They need not be positive, and need not be unique when the <kernel matrix> is singular. Some <kernel methods> instead write $\beta_i=\alpha_i y_i$ with $\alpha_i\geq0$ under their own optimization constraints.<The kernel trick by Ryan Giordano>[Kernelizing classification with support vector machines: displayed prediction as a sum of label-weighted kernel evaluations]{ref} The formula is an algebraic conversion for a weight <vector> in this <linear span>, not a claim about every possible weight <vector>. The <representer theorem> gives a broader reason this form appears in regularized <kernel methods>.
For the <XOR separation by a product feature>, let $\Phi$ have rows $\phi(p_i)^T$. The <Gram matrix> of those rows, equivalently the <kernel matrix>, is
$$
\Phi=\begin{pmatrix}1&\sqrt2&1\\1&-\sqrt2&1\\1&-\sqrt2&1\\1&\sqrt2&1\end{pmatrix},\qquad
K=\Phi\Phi^T=\bigl((p_i^Tp_j)^2\bigr)_{ij}=\begin{pmatrix}4&0&0&4\\0&4&4&0\\0&4&4&0\\4&0&0&4\end{pmatrix}.
$$
Its <eigenvalues> are $8,8,0,0$, so it is a <positive semidefinite matrix> of <rank> two, not an invertible <matrix>. More generally, for any real coefficient <vector> $a$ and any finite set of inputs,
$$
a^TKa=\left\|\sum_i a_i\phi(p_i)\right\|_2^2\geq0.
$$
This proves the <positive-semidefinite kernel> condition for the displayed <polynomial kernel> on all of $\mathbb R^2$, rather than checking only this square.
Here $Ky=8y$, so the explicit choice $\beta=y/8$ gives $K\beta=y$ and $\Phi^T\beta=w$. Consequently
$$
f(z)=\frac{-k(p_1,z)+k(p_2,z)+k(p_3,z)-k(p_4,z)}8=-z_1z_2.
$$
For the new input $z=(1,1/2)$, the four <polynomial kernel> evaluations are $(9/4,1/4,1/4,9/4)^T$. Their weighted sum is $-1/2$, and the <sign function> predicts $-1$. No explicit <feature map> is needed for this calculation. These coefficients were constructed to reproduce the chosen separator; no fitting algorithm or <generalization> guarantee is being asserted.
\Image[/kernel-quadratic-gram-dual-evaluation.png]
{title=Quadratic kernel Gram matrix and a dual prediction for a new input}
{description=Both panels use the same ordered four square corners. The Gram matrix has eigenvalues eight, eight, zero, zero. The new-input column contains four kernel evaluations, whose signed weighted contributions sum to minus one half.}
Back to article page
