= Solution
A real <positive-semidefinite kernel> on an input <set> $X$ is a <function> $K:X\times X\to\mathbb R$ for which there is an <inner product space> $\mathcal F$ and a <feature map> $\phi:X\to\mathcal F$ satisfying
$$
\boxed{K(x,z)=\langle\phi(x),\phi(z)\rangle.}
$$
Equivalently, $K$ is symmetric and every finite <Gram matrix> $(K(x_i,x_j))_{i,j}$ is <positive semidefinite>: $\sum_{i,j}a_ia_jK(x_i,x_j)\geq0$ for all real coefficients $a_i$. An infinite-dimensional <Hilbert space> is allowed.
Replace every <inner product> $x_i\cdot x_j$ in part (b) by $K(x_i,x_j)$ and solve
$$
\boxed{\max_{\alpha\geq0,\ y^T\alpha=0}
\left\{\mathbf1^T\alpha-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\frac1{4C}\|\alpha\|^2\right\}.}
$$
This is precisely the <Lagrangian dual problem> obtained by replacing each original input by $\phi(x_i)$ in the <primal problem>. The weight <vector> it determines is
$$
w_{\mathcal F}=\sum_i\alpha_i y_i\phi(x_i),
$$
and the intercept follows from the same <Karush-Kuhn-Tucker conditions>. For example, if $\alpha_i>0$,
$$
b=y_i\left(1-\frac{\alpha_i}{2C}\right)-\sum_j\alpha_j y_jK(x_j,x_i).
$$
Thus training needs only the finite <Gram matrix>, even if the <feature map> has infinitely many coordinates. This is the <kernel trick>. The result is an \b[<affine linear classifier> in the feature space]; its boundary in the original input space can be nonlinear. The squared-slack diagonal term and the equality constraint remain unchanged.
Back to article page
