Kernel Methods, machine learning lesson

The points of one class form a small ring around the origin and the points of the other class form a wider ring around it. No straight line puts one ring on each side, yet a circle separates them easily. Adding features such as squares makes that circle a flat boundary in a larger space, and kernel methods compute what such features would give without ever listing them. This lesson builds the kernel trick from inner products, checks which similarity functions are valid kernels and fits a kernel support vector machine to two rings.

Key terms

Feature space

Definition A feature map is a function $\phi$ from the input space, here $\mathbb{R}^p$ , into a real inner product space $\mathcal{F}$ , called the feature space. The space $\mathcal{F}$ may be $\mathbb{R}^D$ with the dot product, or an infinite-dimensional space of sequences or functions with an inner product $\langle \cdot, \cdot \rangle$ . A linear classifier in feature space has the score

f(\mathbf{x}) = \langle \mathbf{w}, \phi(\mathbf{x}) \rangle + b

with $\mathbf{w}$ in $\mathcal{F}$ . Its boundary is a hyperplane in $\mathcal{F}$ , and the set of inputs with $f(\mathbf{x}) = 0$ can be curved in $\mathbb{R}^p$ . Preprocessing such as standardization happens before $\phi$ and is fitted on training data only.

In plain words A model that is linear in its parameters can still draw curved boundaries when it is linear in new features rather than in the raw inputs. The representation, not the learning rule, decides which shapes are possible. This is the idea behind polynomial features, and kernels make it practical when the new features are very many.

Example Eight constructed training points form two rings. The inner points $(\pm 1, 0)$ and $(0, \pm 1)$ have label $-1$ , and the outer points $(\pm 3, 0)$ and $(0, \pm 3)$ have label $+1$ . No line separates them. For any linear score $\mathbf{w}^{\top}\mathbf{x} + b$ , opposite points cancel, so the four inner scores add up to $4b$ and the four outer scores add up to $4b$ as well, while separation would need the first sum negative and the second positive. With the single feature $\phi(\mathbf{x}) = x_1^2 + x_2^2$ the inner points have the value $1$ and the outer points $9$ , and the threshold $\phi(\mathbf{x}) = 5$ separates them. In the original plane this boundary is the circle of radius $\sqrt{5} \approx 2.236$ .

Kernel function and kernel trick

Definition A kernel function on $\mathbb{R}^p$ is a function $k$ of two inputs that equals an inner product of feature vectors,

k(\mathbf{x}, \mathbf{z}) = \langle \phi(\mathbf{x}), \phi(\mathbf{z}) \rangle ,

for some feature map $\phi$ into a real inner product space and all inputs $\mathbf{x}$ and $\mathbf{z}$ . The linear kernel $k(\mathbf{x}, \mathbf{z}) = \mathbf{x}^{\top}\mathbf{z}$ has $\phi(\mathbf{x}) = \mathbf{x}$ . The kernel trick applies to a learning algorithm that uses the feature vectors, in training and in prediction, only through their inner products. Replacing every inner product $\langle \phi(\mathbf{x}), \phi(\mathbf{z}) \rangle$ by $k(\mathbf{x}, \mathbf{z})$ then runs the algorithm in the feature space without computing $\phi$ . The dual forms of the support vector machine and of ridge regression are algorithms of this kind.

In plain words A kernel answers one question about two inputs, the inner product of their feature vectors, and many algorithms never ask anything else. Evaluating the kernel can be far cheaper than building the features. The monomials of degree at most $3$ in $100$ inputs number $\binom{103}{3} = 176{,}851$ , while the matching polynomial kernel needs one dot product of length $100$ . The cost moves elsewhere, since the algorithm now works with every pair of training points.

Example The function $k(\mathbf{x}, \mathbf{z}) = (\mathbf{x}^{\top}\mathbf{z})^2$ on $\mathbb{R}^2$ is a kernel with the three features $\phi(\mathbf{x}) = (x_1^2, \sqrt{2}\,x_1 x_2, x_2^2)$ , because expanding $(x_1 z_1 + x_2 z_2)^2$ gives exactly $x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2$ . For $\mathbf{x} = (1, 2)$ and $\mathbf{z} = (-1, 3)$ the kernel gives $5^2 = 25$ . The features $(1, 2\sqrt{2}, 4)$ and $(1, -3\sqrt{2}, 9)$ give the same value, $1 - 12 + 36 = 25$ .

Gram matrix and positive semidefinite kernel

Definition For a function $k$ and points $\mathbf{x}_1, \dots, \mathbf{x}_n$ , the Gram matrix, also called the kernel matrix, is the $n \times n$ matrix $K$ with entries $K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$ . A function $k$ is a positive semidefinite kernel if it is symmetric, $k(\mathbf{x}, \mathbf{z}) = k(\mathbf{z}, \mathbf{x})$ , and for every $n$ , every choice of points and every $\mathbf{a}$ in $\mathbb{R}^n$

\begin{aligned} \mathbf{a}^{\top} K \mathbf{a} &= \sum_{i=1}^{n}\sum_{j=1}^{n} a_i a_j K_{ij} \\[0.4em] &\ge 0 , \end{aligned}

which for a symmetric matrix means that all its eigenvalues are nonnegative. Every kernel function has this property, since

\mathbf{a}^{\top} K \mathbf{a} = \Bigl\lVert \sum_{i=1}^{n} a_i\, \phi(\mathbf{x}_i) \Bigr\rVert^2 .

Conversely, by the Moore-Aronszajn theorem, every positive semidefinite kernel equals $\langle \phi(\mathbf{x}), \phi(\mathbf{z}) \rangle$ for some feature map into a complete inner product space, a Hilbert space. So the valid kernels are exactly the positive semidefinite ones. Two consequences are $k(\mathbf{x}, \mathbf{x}) \ge 0$ and the Cauchy-Schwarz inequality $k(\mathbf{x}, \mathbf{z})^2 \le k(\mathbf{x}, \mathbf{x})\,k(\mathbf{z}, \mathbf{z})$ . One positive semidefinite Gram matrix on one data set does not make $k$ a kernel, because the condition must hold for every finite set of points.

In plain words Calling a number a similarity does not make it an inner product. A kernel must behave the way inner products do, so no weighted combination of feature vectors may have a negative squared length. This condition also makes the support vector machine dual a concave maximization with a reliable global optimum. A similarity table that fails it has no feature-space reading, and an algorithm that treats it as a kernel loses its guarantees.

Example For the points $(1, 2)$ and $(-1, 3)$ , the linear kernel gives the Gram matrix with rows $(5, 5)$ and $(5, 10)$ , whose determinant $25$ and trace $15$ are both positive, so both eigenvalues are positive. By contrast, no kernel gives any two points the Gram matrix with rows $(1, 2)$ and $(2, 1)$ . Its eigenvalues are $3$ and $-1$ , and the vector $\mathbf{a} = (1, -1)$ gives

\begin{aligned} \mathbf{a}^{\top} K \mathbf{a} &= 1 - 2 - 2 + 1 \\[0.4em] &= -2 , \end{aligned}

which would be the squared length of $\phi(\mathbf{x}_1) - \phi(\mathbf{x}_2)$ . It also breaks the Cauchy-Schwarz inequality, since $2^2 > 1 \cdot 1$ .

Polynomial kernel

Definition For a whole number $d \ge 1$ and a constant $c \ge 0$ , the polynomial kernel on $\mathbb{R}^p$ is

k(\mathbf{x}, \mathbf{z}) = \bigl(\mathbf{x}^{\top}\mathbf{z} + c\bigr)^d .

It is positive semidefinite, because sums, products and nonnegative multiples of positive semidefinite kernels are again positive semidefinite, and constants $c \ge 0$ are kernels. When $c > 0$ its features are all monomials of degree at most $d$ , each with a fixed positive weight, and when $c = 0$ they are the monomials of degree exactly $d$ . A classifier that is linear in these features has a boundary given by a polynomial equation of degree at most $d$ in the inputs. With $c < 0$ the function can fail to be a kernel, as $d = 1$ shows, since the single point $\mathbf{0}$ then has the Gram matrix $(c)$ with a negative entry. Some software writes $(\gamma\,\mathbf{x}^{\top}\mathbf{z} + r)^d$ with $\gamma > 0$ and $r \ge 0$ , which is a positive multiple of the form above with $c = r/\gamma$ .

In plain words The polynomial kernel fits a linear model on all products of up to $d$ input features without forming them. The degree sets the flexibility. Because inputs are multiplied together and raised to powers, a feature on a much larger scale than the others can dominate the kernel values, so the features are standardized first, with the scaler fitted on the training data.

Example For $d = 2$ and $c = 1$ on $\mathbb{R}^2$ , expanding $(1 + x_1 z_1 + x_2 z_2)^2$ shows that the kernel is the dot product of the six features

\begin{aligned} \phi(\mathbf{x}) = \bigl(& 1,\ \sqrt{2}\,x_1,\ \sqrt{2}\,x_2, \\[0.4em] & x_1^2,\ \sqrt{2}\,x_1 x_2,\ x_2^2 \bigr) . \end{aligned}

For $\mathbf{x} = (1, 2)$ and $\mathbf{z} = (-1, 3)$ the kernel gives $(1 + 5)^2 = 36$ . The features are $(1, \sqrt{2}, 2\sqrt{2}, 1, 2\sqrt{2}, 4)$ and $(1, -\sqrt{2}, 3\sqrt{2}, 1, -3\sqrt{2}, 9)$ , and their dot product $1 - 2 + 12 + 1 - 12 + 36$ is also $36$ . The circle $x_1^2 + x_2^2 = 5$ from the ring example is linear in these features, so this kernel can represent it.

Radial basis function kernel

Definition For a parameter $\gamma > 0$ , the radial basis function (RBF) kernel, also called the Gaussian kernel, is

k(\mathbf{x}, \mathbf{z}) = \exp\bigl(-\gamma \lVert \mathbf{x} - \mathbf{z} \rVert_2^2\bigr)

for all inputs $\mathbf{x}$ and $\mathbf{z}$ . It can also be written as $\exp\bigl(-\lVert \mathbf{x} - \mathbf{z} \rVert_2^2 / (2\sigma^2)\bigr)$ with a bandwidth $\sigma > 0$ and $\gamma = 1/(2\sigma^2)$ . It has $k(\mathbf{x}, \mathbf{x}) = 1$ , takes values in $(0, 1]$ and decreases as the distance between the inputs grows. It is positive semidefinite for every $\gamma > 0$ , its feature space is infinite-dimensional, and its Gram matrix on distinct points is positive definite. So the feature vectors of any finite set of distinct points are linearly independent, and every labeling of distinct training points is linearly separable in this feature space.

In plain words The RBF kernel calls two points similar when they are close in the input features. The parameter $\gamma$ sets the distance scale. A large $\gamma$ makes similarity fall off over short distances and allows very local boundaries that can follow noise, and a small $\gamma$ makes near and far points look alike and gives smooth boundaries that can miss real structure. These are tendencies, not guaranteed rankings of error. With distinct training inputs and a large enough $C$ , zero training mistakes are always within reach, so they say little about an RBF model. The value of $\gamma$ is chosen together with the penalty $C$ on validation data, never on the test set. Because the kernel depends on Euclidean distance, the units of the features matter, and the scaler is fitted on the training folds only.

Example With $\gamma = 0.5$ , which means $\sigma = 1$ , two points at distance $2$ have similarity $e^{-2} \approx 0.1353$ , and two points at distance $1$ have similarity $e^{-0.5} \approx 0.6065$ . For the eight ring points, $\gamma = 0.001$ gives off-diagonal Gram entries between about $0.965$ and $0.998$ , so the Gram matrix is close to the matrix of all ones and the kernel can hardly tell the points apart. With $\gamma = 50$ every off-diagonal entry is below $10^{-43}$ , so the Gram matrix is close to the identity and each point is similar only to itself.

Kernel SVM

Definition A kernel SVM is a soft-margin support vector machine fitted in the feature space of a positive semidefinite kernel $k$ . With labels $y_i \in \{-1, +1\}$ and penalty $C > 0$ , its dual problem maximizes

\begin{gathered} D(\boldsymbol{\alpha}) = \sum_{i=1}^{n} \alpha_i - \tfrac12\, \boldsymbol{\alpha}^{\top} Q\, \boldsymbol{\alpha} , \\[0.4em] Q_{ij} = y_i y_j\, k(\mathbf{x}_i, \mathbf{x}_j) , \end{gathered}

subject to $0 \le \alpha_i \le C$ and $\sum_i \alpha_i y_i = 0$ . The fitted score is

\begin{aligned} f(\mathbf{x}) &= \sum_{i=1}^{n} \alpha_i\, y_i\, k(\mathbf{x}_i, \mathbf{x}) \\[0.4em] &\quad + b , \end{aligned}

and the prediction is $+1$ when $f(\mathbf{x}) \ge 0$ and $-1$ otherwise. When some example has $0 < \alpha_i < C$ , it satisfies $y_i f(\mathbf{x}_i) = 1$ , and that equation gives the intercept. The dual follows from the primal soft-margin problem in feature space. Setting the derivatives of its Lagrangian to zero gives $\mathbf{w} = \sum_i \alpha_i y_i \phi(\mathbf{x}_i)$ , the constraint $\sum_i \alpha_i y_i = 0$ from the unpenalized intercept and the bound $\alpha_i \le C$ from the slack variables, and every inner product $\langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle$ that remains is a kernel value. Because $Q$ is positive semidefinite, $D$ is concave and the dual is a convex optimization problem. Only the support vectors, the examples with $\alpha_i > 0$ , enter the score.

In plain words A kernel SVM classifies a new point by a weighted vote of its similarities to the support vectors, positive for one class and negative for the other, plus a constant. It keeps the margin, the hinge loss and the penalty $C$ of the linear SVM and gains the shapes of the kernel. Training works with all pairs of training points, and the fitted model stores its support vectors. The kernel, its parameters and $C$ are chosen by cross-validation on the training data, with scaling fitted inside each fold, and the chosen pipeline is evaluated once on the test set.

Example Fit the eight ring points with the RBF kernel, $\gamma = 0.5$ and $C = 10$ . Turning the plane by a quarter turn maps the data set to itself, so by concavity of $D$ some optimal $\boldsymbol{\alpha}$ gives all inner points one weight and all outer points another, and the constraint $\sum_i \alpha_i y_i = 0$ makes the two weights equal. With every $\alpha_i = a$ the dual becomes

D = 8a - \tfrac12\, a^2\, \mathbf{y}^{\top} K \mathbf{y} ,

where $\mathbf{y}^{\top} K \mathbf{y} \approx 10.2922$ , so $a = 8/10.2922 \approx 0.77729$ , which lies between $0$ and $C$ . All eight points are support vectors on their margin hyperplanes, and the condition $y_i f(\mathbf{x}_i) = 1$ gives $b \approx 0.33845$ from either ring. New points at $45$ degrees score about $-1.0148$ at radius $1$ and about $0.3612$ at radius $3$ , so both receive the label of their ring. Numerically the score changes sign exactly once along each ray from the origin, at a radius from about $1.84$ on the axes to about $2.07$ on the diagonals, so the boundary is a closed curve around the origin that is close to a circle but not exactly one. Far from every training point the score approaches $b > 0$ , so such points are assigned to the outer class. A linear SVM with $C = 10$ on the same points has the optimal weight vector $\mathbf{0}$ , and every intercept from $-1$ to $1$ is optimal, so it predicts one class everywhere and gets $4$ of the $8$ training points right. These are training results on constructed data, not evidence about new data.

Check yourself

Two points are at Euclidean distance $1$ . Find their RBF similarity for $\gamma = 2$ and for $\gamma = 0.5$ , and say which setting gives the more local model. An RBF SVM with $\gamma = 2$ classifies every training point correctly but does much worse on the validation data. What should be checked and tried next?

Show the answer

For $\gamma = 2$ the similarity is $e^{-2 \cdot 1} = e^{-2} \approx 0.1353$ , and for $\gamma = 0.5$ it is $e^{-0.5} \approx 0.6065$ . The larger $\gamma$ treats the same pair as much less similar, so each training point influences a smaller neighborhood and the boundary can bend more locally.

Perfect training accuracy with poor validation accuracy suggests overfitting, and with distinct training inputs and a large enough $C$ an RBF model can always reach zero training mistakes, so the training result carries little weight. Candidate experiments are a smaller $\gamma$ or a smaller $C$ , which penalizes violations less. They should be compared by cross-validation within the training data, with the scaler fitted inside each training fold. The split itself deserves a check too, for leakage, for groups or time order that the split ignores, and for differences between the training and validation populations or label quality. The test set stays untouched until one final pipeline has been chosen.

A similarity table for three items gives each item similarity $1$ with itself, $0.9$ between the first and second and between the second and third, and $0.1$ between the first and third. The table is symmetric and every off-diagonal entry is at most $1$ in absolute value. Can it be the Gram matrix of a kernel?

Show the answer

No. Take $\mathbf{a} = (1, -1, 1)$ . The three diagonal terms contribute $3$ . Each of the three pairs appears twice, with the products $a_1 a_2 K_{12} = -0.9$ , $a_1 a_3 K_{13} = 0.1$ and $a_2 a_3 K_{23} = -0.9$ , so the pairs contribute $2(-0.9 + 0.1 - 0.9) = -3.4$ and

\mathbf{a}^{\top} K \mathbf{a} = 3 - 3.4 = -0.4 ,

which is negative. The eigenvalues are about $-0.224$ , $0.9$ and $2.324$ . A kernel Gram matrix would make this number the squared length of $\phi(\mathbf{x}_1) - \phi(\mathbf{x}_2) + \phi(\mathbf{x}_3)$ , which cannot be negative. Symmetry and the pairwise Cauchy-Schwarz checks are necessary but not sufficient. Here every self-similarity is $1$ , so the feature vectors would have length $1$ and each similarity would be the cosine of an angle. The value $0.9$ means an angle of about $25.8$ degrees, so the first and third vectors could be at most about $51.7$ degrees apart, with cosine at least $0.62$ , while the value $0.1$ needs about $84.3$ degrees.

Fit an RBF kernel SVM with $\gamma = 0.5$ and $C = 10$ to two training points, $\mathbf{x}_1 = (0, 0)$ with label $-1$ and $\mathbf{x}_2 = (2, 0)$ with label $+1$ . Find the dual weights and the intercept, classify the point $(1.5, 0)$ , and state for which values of $C$ this solution holds.

Show the answer

The constraint $\alpha_1 y_1 + \alpha_2 y_2 = 0$ gives $\alpha_1 = \alpha_2 = a$ . The kernel value between the points is $k_{12} = e^{-0.5 \cdot 4} = e^{-2}$ , and $Q_{12} = y_1 y_2 k_{12} = -e^{-2}$ , so

D(a) = 2a - a^2\,\bigl(1 - e^{-2}\bigr) .

Setting the derivative to zero gives

a = \frac{1}{1 - e^{-2}} \approx 1.1565 ,

which lies between $0$ and $C = 10$ . Both points are therefore support vectors on their margin hyperplanes. The condition $f(\mathbf{x}_2) = a\,(1 - e^{-2}) + b = 1$ gives $b = 0$ .

The point $(1.5, 0)$ has squared distances $2.25$ and $0.25$ to the two training points, so

\begin{aligned} f &= a\bigl(e^{-0.125} - e^{-1.125}\bigr) \\[0.4em] &\approx 1.1565 \cdot 0.5578 \\[0.4em] &\approx 0.6452 , \end{aligned}

and it is classified $+1$ . Every point with $x_1 = 1$ is equally far from both training points, so its score is exactly $0$ and the convention assigns it $+1$ .

The solution holds whenever $C \ge 1/(1 - e^{-2}) \approx 1.1565$ . For a smaller $C$ the weights are capped at $C$ , both points end up inside the margin, and the formula for $a$ no longer applies.

Kernel Methods

Key terms

Feature space

Kernel function and kernel trick

Gram matrix and positive semidefinite kernel

Polynomial kernel

Radial basis function kernel

Kernel SVM

Check yourself

How this lesson connects

Builds on