2.2 Machine learning lecture 3 course notes  (Page 10/12)

The application of kernels to support vector machines should already be clear and so we won't dwell too much longer on it here. Keep in mind however that the idea of kernels hassignificantly broader applicability than SVMs. Specifically, if you have any learning algorithm that you can write in terms of only inner products $⟨x,z⟩$ between input attribute vectors, then by replacing this with $K(x,z)$ where $K$ is a kernel, you can “magically” allow your algorithm to work efficiently in the high dimensional feature space corresponding to $K$ . For instance, this kernel trick can be applied with the perceptron to to derive a kernel perceptron algorithm. Many of the algorithms that we'll see later in thisclass will also be amenable to this method, which has come to be known as the “kernel trick.”

Regularization and the non-separable case

The derivation of the SVM as presented so far assumed that the data is linearly separable. While mapping data to a high dimensional feature space via $\Phi$ does generally increase the likelihood that the data is separable, we can't guarantee that it always will be so.Also, in some cases it is not clear that finding a separating hyperplane is exactly what we'd want to do, since that mightbe susceptible to outliers. For instance, the left figure below shows an optimal margin classifier, and when a single outlier is added in the upper-left region (right figure), it causes the decisionboundary to make a dramatic swing, and the resulting classifier has a much smaller margin.

To make the algorithm work for non-linearly separable datasets as well as be less sensitive to outliers, we reformulate our optimization (using ${\ell }_1$ regularization ) as follows:

Thus, examples are now permitted to have (functional) margin less than 1, and if an example has functional margin $1-{\xi }_i$ (with $\xi >0$ ), we would pay a cost of the objective function being increased by $C{\xi }_i$ . The parameter $C$ controls the relative weighting between the twin goals of making the ${\left|\right|w\left|\right|}^2$ small (which we saw earlier makes the margin large) and of ensuring that most examples have functional margin at least 1.

As before, we can form the Lagrangian:

Here, the ${\alpha }_i$ 's and $r_i$ 's are our Lagrange multipliers (constrained to be $\ge 0$ ). We won't go through the derivation of the dual again in detail, but after setting the derivatives with respectto $w$ and $b$ to zero as before, substituting them back in, and simplifying, we obtain the following dual form of the problem:

As before, we also have that $w$ can be expressed in terms of the ${\alpha }_i$ 's as given in  [link] , so that after solving the dual problem, we can continue to use  [link] to make our predictions. Note that, somewhat surprisingly, in adding ${\ell }_1$ regularization, the only change to the dual problem is that what was originally a constraint that $0\le {\alpha }_i$ has now become $0\le {\alpha }_i\le C$ . The calculation for $b^{*}$ also has to be modified ( [link] is no longer valid); see the comments in the next section/Platt's paper.