SVM and kernel functions

Despite the Soft Margin, some problems are intrinsically nonseparable in feature space. However, based on knowledge of the problem, it may be possible to infer that a nonlinear transformation $\phi:X \to F$ maps the input feature space $\mathcal{X}$ into the feature space $\mathcal{F}$, where the separating hyperplane provides better discrimination between the categories. The discriminant function in space $\mathcal{F}$ is

$$f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x}) + b$$ (5.43)

To enable separation, the space $\mathcal{F}$ is normally of higher dimension than the space $\mathcal{X}$. This increase in dimensionality would make it computationally expensive to calculate explicitly the coordinates of the samples in space $\mathcal{F}$. Kernel methods make it possible to work in the transformed space without explicitly calculating its coordinates.

The vector $\mathbf{w}$ is a linear combination of the training samples (the support vectors in the hard margin case):

$$\mathbf{w} = \sum_i \alpha_i \phi(\mathbf{x}_i)$$ (5.44)

The discriminant function therefore takes the form

$$\begin{array}{rl} f(\mathbf{x}) & = \sum_i \alpha_i \phi(\m... ...& = \sum_i \alpha_i k(\mathbf{x}, \mathbf{x}_i) + b \end{array}$$ (5.45)

with the kernel function evaluated at $k(\mathbf{x},\mathbf{x}')$.

When evaluating the discriminant function, it is therefore necessary to use the support vectors, at least those associated with a non-negligible parameter $\alpha_i$. In effect, an SVM with a kernel identifies some training samples as useful information for determining how close the sample being evaluated is to them.

The bias is calculated directly from equation (5.45) by averaging

$$b = \E[ y_j - \sum_i \alpha_i k(\mathbf{x}_j, \mathbf{x}_i) ]$$ (5.46)

The most widely used kernels, because they are simple to evaluate, are Gaussian kernels of the form

$$k(\mathbf{x},\mathbf{x}') = e^{-\gamma \Vert\mathbf{x}-\mathbf{x}'\Vert^2 }$$ (5.47)

with $\gamma$ as a parameter to be set, and polynomial kernels of degree $d$ of the form

$$k(\mathbf{x},\mathbf{x}') = (\mathbf{x}^\top \mathbf{x}' + 1)^d$$ (5.48)

and when $d=1$ the formulation reduces to the linear case.

The use of kernel functions, together with the possibility of precomputing all combinations $k(\mathbf{x}_i,\mathbf{x}_j)$, makes it possible to define a common interface between linear and nonlinear training while effectively maintaining the same level of performance.

It is worth noting that the prediction $f(\mathbf{x})=\mathbf{w}^{\top} \phi(\mathbf{x})$ takes the form

$$\phi(\mathbf{x}) = \left[ k_1(\mathbf{x}, \mathbf{x}_1), \ldots, k_n(\mathbf{x}, \mathbf{x}_n) \right]$$ (5.49)

where $\mathbf{x}_i$ represents a subset of the training set. Models written in this form effectively perform template matching between the sample $\mathbf {x}$ being evaluated and the prototypes $\mathbf{x}_i$.

We have therefore seen how a classifier can be constructed by directly imposing a separation geometry between the classes. The hinge-loss formulation, however, also makes it possible to frame SVMs within the more general framework of empirical risk minimization, which will be introduced in the next section.