The Kernel Trick

Imagine red and blue coins scattered on a table, with red in the centre, and blue in a ring around it. You cannot separate them with a straight ruler. Now slap the table, so that the coins jump into the air, with the middle jumping higher. For a moment, you could slide a flat sheet of paper between them. That is the kernel trick.

• Coins on a table, in a ring
• A ruler cannot split them
• Slap the table

Lifting into a new dimension

Data that cannot be separated in two dimensions can often be separated in three, or more. We could compute all these new dimensions, but that would be very expensive. The genius of the kernel trick is that the algorithm only ever needs to know how similar two points are. A kernel function gives that similarity directly, as if we had made the journey to the higher dimension, without ever going there. The most popular one is the radial basis function, or R B F.

Rings of data

Here is exactly that ring-shaped data. We try three kernels. Run it. The linear kernel can do no better than a coin flip, as expected. A straight line is hopeless. But the R B F kernel scores nearly perfectly, separating a circle from a ring. We changed a single word.

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

X, y = make_circles(n_samples=500, factor=0.4, noise=0.08, random_state=0)

for kernel in ["linear", "poly", "rbf"]:
    print(f"{kernel:<7} {cross_val_score(SVC(kernel=kernel), X, y, cv=5).mean():.3f}")

linear  0.558
poly    0.606
rbf     1.000

Gamma controls reach

R B F has its own setting, called gamma. It controls how far the influence of a single point reaches. A low gamma gives smooth, broad boundaries. A high gamma lets each point draw a tiny island around itself. We test a range. Run it. At a gamma of one thousand, the training score is nearly perfect, and the test score has collapsed. By now, you recognise this pattern immediately. Overfitting has one more disguise.

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

X, y = make_moons(n_samples=400, noise=0.3, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)

for gamma in [0.01, 1, 100, 1000]:
    m = SVC(kernel="rbf", gamma=gamma).fit(X_tr, y_tr)
    print(f"gamma {gamma:<5} train {m.score(X_tr, y_tr):.3f}"
          f"  test {m.score(X_te, y_te):.3f}")

gamma 0.01  train 0.820  test 0.870
gamma 1     train 0.910  test 0.920
gamma 100   train 0.957  test 0.900
gamma 1000  train 0.997  test 0.590

Summary