ML6.5 · LESSON 5 OF 6

Kernels

Compare nearest-neighbor, naive Bayes and margin-based predictions using their actual assumptions.

THE IDEA

When no straight line works, lift the data

Look at 1D data where class 1 sits at both ends and class 0 in the middle. No single cut on the number line separates them: the best cut still gets 4 points wrong. Now give every point a second coordinate, its square, so x becomes (x, x²). The points land on a parabola, and the outer points are higher than the inner ones. A horizontal line separates them. In the original space that line is two cuts at ±√t.

line height t (on x squared) = 3Rule: class 1 when x² > t, that is when |x| > 1.7321

Mistakes with this line: 0 of 14. The best single cut on x alone makes at least 4.

Move the line in the lifted view. The two purple marks on the number line follow it.

That is the idea behind feature maps: a boundary that is linear in a higher-dimensional space can be curved in the original one.

The kernel trick: get the inner product without building the features

A margin classifier only ever needs inner products between points. A kernel K(a, b) is a function that returns the inner product of the lifted points, without constructing them. A concrete case in 2D: lift with φ(v) = (v₁², √2·v₁v₂, v₂²). For a = (1, 2) and b = (3, −1):

a · b = 1, so (a · b)² = 1
φ(a) = (1, 2.8284, 4), φ(b) = (9, -4.2426, 1)
φ(a) · φ(b) = 1

The same number, but the kernel only needed a dot product and a square. The RBF (Gaussian) kernel K(a, b) = exp(−γ‖a−b‖²) corresponds to a feature space with infinitely many coordinates, yet one evaluation costs the same as a distance. It is 1 for identical points and falls towards 0 with distance; γ sets how fast. A valid kernel must give a symmetric, positive semidefinite matrix for any set of points. An arbitrary similarity function, such as the negative distance, is not guaranteed to.

Gamma is the width dial

Below, the boundary between two classes is a wave, with 8% of the labels flipped as noise. A kernel classifier (kernel ridge regression on labels of −1 and +1) uses the RBF kernel. Small γ makes every bump huge, so the model is nearly a smooth bowl and cannot follow the wave: at γ = 0.003 training accuracy is 76.7% and validation 77%. Large γ gives each training point its own tiny bump: at γ = 30 training accuracy is 100% while validation falls to 81.3%. In between, γ = 0.3 reaches 85.3% on validation.

class 0class 1

gamma (bigger means narrower bumps) = 1

Training accuracy 96.7%, validation accuracy 80.7% (300 unseen points).
This is in between.

gamma	0.003	0.01	0.03	0.1	0.3	1	3	10	30	100
train	77	77	77	82	90	97	98	98	100	100
valid.	77	78	79	85	85	81	80	80	81	81

The classifier is kernel ridge regression on labels of -1 and +1 with lambda = 0.3: the same kernel idea as an SVM, with a simpler fit.

Slide gamma from left to right and watch the regions go from smooth, to wavy, to speckled. Compare the two accuracy rows.

Predict first. You raise gamma until training accuracy is 100%. Is the model now the best choice?

The common mistake

Chapter context

Different model families turn different notions of similarity into predictions. A geometric distance, a conditional-independence assumption and a kernel are distinct modeling decisions rather than variations of the same formula.

TRY IT YOURSELF

Part 1. Do it on the plot

Two instruments share one state: the lifted line (top) and the RBF gamma slider (below).

line height t (on x squared) = 1Rule: class 1 when x² > t, that is when |x| > 1

Mistakes with this line: 2 of 14. The best single cut on x alone makes at least 4.

class 0class 1

gamma (bigger means narrower bumps) = 1

Training accuracy 96.7%, validation accuracy 80.7% (300 unseen points).
This is in between.

gamma	0.003	0.01	0.03	0.1	0.3	1	3	10	30	100
train	77	77	77	82	90	97	98	98	100	100
valid.	77	78	79	85	85	81	80	80	81	81

The classifier is kernel ridge regression on labels of -1 and +1 with lambda = 0.3: the same kernel idea as an SVM, with a simpler fit.

To do: In the lifted view, place the horizontal line (threshold on x squared) so no point is misclassified
To do: Underfit: choose a gamma whose training accuracy is below 80%
To do: Overfit: choose a gamma with training accuracy of 98% or more but validation accuracy well below the best
To do: Choose the gamma with the best validation accuracy (within half a point)

Part 2. Do it in code

rbf_kernel(A, B, gamma) returns K with K[i, j] = exp(-gamma * ||A[i] - B[j]||^2), for every pair of rows. No loops over rows.
is_valid_kernel_matrix(K, tol=1e-8) returns True if K is square, symmetric and positive semidefinite: its smallest eigenvalue is at least -tol. Use np.linalg.eigvalsh.

import numpy as np

def rbf_kernel(A, B, gamma):
    pass

def is_valid_kernel_matrix(K, tol=1e-8):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is every arbitrary similarity function a valid positive-semidefinite kernel?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

\|x-y\|_2^2=\sum_j(x_j-y_j)^2,\quad K(x,y)=\exp(-\gamma\|x-y\|^2),\;\gamma>0.

For SVM canonical boundary planes $w^Tx+b=\pm1$ , their separation is $2/\|w\|$ . A naive-Bayes posterior is proportional to $P(c)\prod_jP(x_j\mid c)$ .

A numerically convenient naive-Bayes decision rule is

\hat c=\arg\max_c\left[\log P(c)+\sum_j\log P(x_j\mid c)\right].

This avoids multiplying many small probabilities, but it does not remove the need to handle zero likelihoods or choose an appropriate feature distribution.

Worked example

For query [1,1], squared distances to [0,0], [2,1] and [3,3] are 2, 1 and 8. The nearest point is [2,1]. Separately, a canonical SVM with w=[3,4] has norm 5 and margin width 2/5=0.4.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import sqrt, isclose
q = [1,1]
points = [[0,0],[2,1],[3,3]]
distances = [sum((a-b)**2 for a,b in zip(q,p)) for p in points]
assert distances == [2,1,8]
assert distances.index(min(distances)) == 1
assert isclose(2/sqrt(3**2+4**2), .4)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Changing feature scale can change neighbors. Kernel similarity is not automatically calibrated probability. The SVM margin formula assumes a particular normalization of the separating planes.