SVMs 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 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 practice, kernel SVM identifies some samples from the training set 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 the 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 should be noted 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 nevertheless allows SVMs to be brought within the more general framework of empirical risk minimization, which will be introduced in the following section.