2.7 Kernelization

So far in this module, we have learned linear decision boundaries: the perceptron returns a separating hyperplane, and the SVM returns the one with the maximum margin. What decision boundary separates the following data?

No straight line works on the left. But an ellipse does. We can parameterize one as \[ g(x) = w_1 x_1^2 + w_2 x_2^2 + w_0 = 0, \] and, as before, use \(g\) as a scoring function: points with \(g(x) > 0\) get one label, and points with \(g(x) < 0\) get the other.

So if we transform the data by \(\phi(x_1, x_2) = (x_1^2, x_2^2)\), the two classes become linearly separable (right), and every linear method we know applies in the new space. This is why feature transformations are so important. In fact, every dataset can be made linearly separable.

Kernelization

Theorem

Given \(n\) distinct points \(S = \{x_1, \dots, x_n\}\), there exists a transformation \(\phi : S \to \mathbb{R}^m\), for some \(m\), such that \(S\) is linearly separable in the transformed space for any labeling of \(S\).

Proof. Consider the mapping into \(\mathbb{R}^n\) that sends each point to its own coordinate axis: \[ \phi(x_i) = e_i = \begin{bmatrix} 0 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{bmatrix} \leftarrow i\text{-th coordinate}. \] Let \[ w^* = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} \in \mathbb{R}^n. \] Then \(w^* \cdot \phi(x_i) = y_i\) for every \(i\), so the decision boundary given by \(w^*\) perfectly separates the transformed data \(\phi(S)\). \(\blacksquare\)

Remark. Any dataset becomes linearly separable after some feature transformation!

The catch: computation

Observations.

Examples.

Both transformations make the model class more complex. The quadratic one allows ellipses and other conic sections as decision boundaries. The infinite-dimensional one can approximate any smooth boundary.

Kernels

Definition. A function \(K : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}\) is called a kernel if there exists a feature transformation \(\phi : \mathbb{R}^d \to \mathbb{R}^m\) such that \[ K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j) \qquad \text{for all } x_i, x_j \in \mathbb{R}^d. \] (Here \(m\) may be infinite.) In words: a kernel computes a dot product in a transformed space without ever computing the transformation.

Not the same “kernel”

This is a different object from the localization kernels of kernel regression (Chapter 1.4). The shared name has historical reasons. For this chapter, set the earlier definition aside.

Examples.

Remarks.

The perceptron can be kernelized; you will do this in Homework 2.2. Here, we kernelize the SVM.

Kernelized SVM

Recall: the SVM primal. \[ \min_{w, b, \varepsilon} \tfrac12 \|w\|^2 + C \sum_{i=1}^n \varepsilon_i \quad \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1 - \varepsilon_i, \quad \varepsilon_i \geq 0, \] with classifier \(\hat f(x) = \text{sign}(w^* \cdot x + b^*)\).

Recall: the SVM dual. With slack variables, the constraints on the dual variables become \(0 \leq \alpha_i \leq C\): \[ \max_\alpha \sum_{i=1}^n \alpha_i - \frac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \quad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C. \] Substituting \(w^* = \sum_i \alpha_i^* y_i x_i\), the classifier is \[ \hat f(x) = \text{sign}\Big( \sum_{i=1}^n \alpha_i^* y_i (x_i \cdot x) + b^* \Big). \]

Key observation: the dual depends on the data in \(\mathbb{R}^d\) only through dot products! The objective uses \(x_i \cdot x_j\), and the classifier uses \(x_i \cdot x\). This is the second thing the dual buys us, besides explaining support vectors. Apply the kernel trick to both.

Setup (kernelized SVM)

To get a nonlinear boundary, you could also skip the dual entirely: explicitly transform the inputs and train an ordinary linear SVM. Kernelization lets us do the same thing without computing the transformation, which matters when the transformation is expensive, or, as for the RBF kernel, impossible to compute at all.

Demo: a linear vs. an RBF SVM

We generate 100 points on two concentric circles, which are not linearly separable, and compare a linear SVM with an RBF-kernel SVM.

from sklearn.datasets import make_circles
from sklearn.svm import SVC

X, y = make_circles(n_samples=100, factor=0.3, noise=0.05)

clf_linear = SVC(kernel="linear").fit(X, y)
clf_rbf = SVC(kernel="rbf").fit(X, y)

What we really care about is generalization: what does the learned boundary look like?

Somewhat surprisingly, despite the enormous flexibility of the RBF kernel, the learned boundary is a simple, almost circular curve, not a wildly overfit one. It has the right level of complexity for this data.

Why? The SVM does implicit regularization. Maximizing the margin means minimizing \(\|w\|^2\), the same penalty on model complexity as ridge regression in Chapter 1.3. So even though the model class is very rich, the SVM favors simple solutions within it. This is one of the reasons support vector machines were the star of machine learning before the deep learning era.