Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 2 / c / 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 $\varphi :X\to \mathcal{F}$ satisfyingEquivalently, $K$ is symmetric and every finite Gram matrix $(K(x_i,x_j){)}_{i,j}$ is positive semidefinite: ${\sum }_{i,j}{a}_i{a}_{j}K(x_i,x_j)\ge 0$ 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 solveThis is precisely the Lagrangian dual problem obtained by replacing each original input by $\varphi (x_i)$ in the primal problem. The weight vector it determines isand the intercept follows from the same Karush-Kuhn-Tucker conditions. For example, if ${\alpha }_i>0$,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 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.