Support vector machines and kernels

Two iris species, two petal measurements. On the training flowers many straight lines separate them equally well. A support vector machine (SVM) picks the one with the widest empty band around it, the margin. The flowers on the edge of the band, inside it or on the wrong side are the support vectors. Only they set the boundary: you could delete every other flower and the boundary would stay the same. When the classes overlap, the band cannot be empty, so the SVM pays a penalty for every flower inside the band or on the wrong side. The number C sets the price of that penalty. A small C allows a wide band with many violations; a large C insists on keeping flowers on the right side, even at the cost of a narrow band.

Try it

• Start with the petals at C = 100. How many flowers hold the boundary, and how wide is the band?
• Move C down. At which C is validation best, and at which is the band widest for almost the same result?
• Switch to the sepals. Does any C separate the species here?
• Go to the wines. Compare „x only”, the features √2·x and x², and the kernel (x·z + 1)². Then switch to the RBF kernel and move γ (how fast the similarity of two wines falls as they move apart) all the way to 1000.

Once you have checked it in the lab, let us name what you see.

The idea in plain words

An SVM does not compute probabilities the way logistic regression does. It draws a boundary and two lines parallel to it, one on each side. The band between them should be as wide as possible, and the flowers should lie outside it, on their own side. A flower that does not fit gets a penalty equal to how deep it went into the band. This is the hinge loss. The model looks for a balance: a wide band on one side, C times the sum of penalties on the other.

At C = 0.01 penalties cost almost nothing. The band is 3.9 cm wide, and all 70 training flowers are support vectors: each one moves the boundary a little. At C = 100 every violation is expensive. The band is 0.15 cm wide, and 4 flowers right next to the boundary hold it. Meanwhile the test changes by one flower. On the petals the species lie far enough apart that almost any sensible line gets the same flowers right.

We choose C like any hyperparameter: by validation, not by the test. The lab runs 5-fold cross-validation inside the 70 training flowers. The best comes at C = 10: 69 of 70. At C = 0.1 it is 68 of 70, and the band is 1.4 cm instead of 0.34 cm. One flower of difference is noise in validation, and a wider band rests the boundary on more flowers. The smallest C goes too far the other way: 64 of 70.

The boundary does not have to be straight. On the wines we only ask whether a wine is cultivar 2 or another one, so there are two classes. Cultivar 2 sits in the middle of the flavanoid axis: cultivar 1 has 2.98 on average, cultivar 2 2.08, cultivar 3 0.78. One threshold cannot cut out the middle, so the linear SVM prefers not to point to cultivar 2 anywhere. Validation: 60.0%, as much as answering „always another cultivar”. Let us replace x with two features: √2·x and x². The wines land on a parabola, and a line in the plane (√2·x, x²) is two thresholds on the axis, an interval. Validation rises to 72.0%.

A kernel does the same without adding columns. The SVM only needs dot products of pairs of examples. A dot product is the sum of the products of matching coordinates of two examples; the SVM uses it as a measure of how similar they are. The kernel (x·z + 1)² gives exactly the dot product of the vectors (1, √2·x, x²), so the boundary comes out identical to the one with the features √2·x and x². This is the kernel trick. The RBF kernel (radial basis function) exp(−γ(x − z)²) measures similarity by distance: γ says how fast the similarity falls as two wines move apart. It corresponds to infinitely many such features. At γ = 3 validation is 78.4%, the best of the eight values of γ, and the test then gives 84.9%. At γ = 0.3, 1 and 10 validation is 76.8%, only 2 wines of 125 fewer. As with C on the irises, that is practically a draw. At γ = 1000 training rises to 89.6% and validation falls to 69.6%. The boundary then breaks into 11 intervals fitted to single wines. The highest test, 86.8%, comes at γ = 100, but choosing by the test is choosing on the data you judge with.

Jak to policzono

• Irises: Iris (Fisher, 1936; UCI, licence CC BY 4.0), 100 versicolor and virginica flowers. Measurements in centimetres without scaling, because both features share the unit. Stratified split: 70 flowers to learn from, 30 for the test.
• Wines: Wine (Aeberhard and Forina, 1992; UCI, licence CC BY 4.0), 178 wines, flavanoid content only, C = 1. Split: 125 wines to learn from, 53 for the test. Z-scores come from the learning wines only, and in validation from the learning wines of each fold.
• Validation: stratified 5-fold cross-validation inside the training part. Model: a soft-margin SVM; the numbers match scikit-learn's SVC.

Why it works

A wide band is regularisation, like the ridge penalty from lesson 3.4. The band is 2/‖w‖ wide, so a wide band means small weights and a boundary that depends less on single flowers. The margin with a penalty for violations was described by Cortes and Vapnik (1995). The kernel trick came to SVMs earlier, from Boser, Guyon and Vapnik (1992): since the model only uses dot products, every dot product can be replaced by a kernel.

That C changes the geometry more than the result is not an accident of one split. On 20 other iris splits the test accuracy over the 9 values of C differs by at most 2 flowers of 30, while the band shrinks from 3.8–4.1 cm to 0.17–0.36 cm.

The RBF kernel measures distances, so units matter. The wines have 13 measurements: proline goes up to 1680, hue at most to 1.71. Without scaling the distance is almost proline alone. An RBF SVM on all 13 measurements then gets on 20 splits 67.2% of the validation wines on average. With scaling learned on the learning part only: 97.9%.

Common mistake

True or false: „always take the RBF kernel, it is the most flexible”. False. On the iris petals a linear SVM and an RBF SVM, each with its settings chosen by validation, get 28.5 of 30 test flowers on average over 20 splits. RBF is better on 1 split and worse on 1. The boundary here is almost straight, so flexibility buys nothing and costs something: two hyperparameters to tune instead of one, and easier overfitting (γ = 1000 on the wines). In the code below linear gets 0.950, RBF 0.947, and RBF is better on 2 splits and worse on 4.

The practical lesson: start with a linear kernel or with logistic regression. Reach for RBF when validation shows that the boundary is not straight, as on the wines.

import numpy as np
from sklearn.datasets import load_iris, load_wine
from sklearn.model_selection import train_test_split, StratifiedKFold, GridSearchCV, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

iris = load_iris(as_frame=True)
keep = iris.target > 0
X, y = iris.data.loc[keep, ["petal length (cm)", "petal width (cm)"]], iris.target[keep]
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)
for C in [0.01, 1, 100]:
    m = SVC(kernel="linear", C=C).fit(X_tr, y_tr)
    print(f"C = {C:>6}: band {2 / np.linalg.norm(m.coef_):.2f} cm, {m.n_support_.sum()} support vectors of {len(y_tr)}, test {m.score(X_te, y_te):.3f}")
grids = {"linear": {"svc__kernel": ["linear"], "svc__C": [0.01, 0.1, 1, 10, 100]},
         "RBF": {"svc__kernel": ["rbf"], "svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.01, 0.1, 1, 10]}}
test = {k: [] for k in grids}
for seed in range(20):
    X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, stratify=y, random_state=seed)
    cv = StratifiedKFold(5, shuffle=True, random_state=seed)
    for k, grid in grids.items():
        search = GridSearchCV(make_pipeline(StandardScaler(), SVC()), grid, cv=cv).fit(X_tr, y_tr)
        test[k].append(search.score(X_te, y_te))
lin, rbf = np.array(test["linear"]), np.array(test["RBF"])
print(f"20 splits, settings chosen in validation: test linear {lin.mean():.3f}, RBF {rbf.mean():.3f}; RBF better {(rbf > lin).sum()}, worse {(rbf < lin).sum()}, equal {(rbf == lin).sum()}")
wine = load_wine()
cv = StratifiedKFold(5, shuffle=True, random_state=0)
for name, model in [("raw", SVC()), ("scaled inside each fold", make_pipeline(StandardScaler(), SVC()))]:
    print(f"wine, RBF SVM, {name}: validation {cross_val_score(model, wine.data, wine.target, cv=cv).mean():.3f}")

C =   0.01: band 4.21 cm, 70 support vectors of 70, test 1.000
C =      1: band 0.71 cm, 22 support vectors of 70, test 1.000
C =    100: band 0.37 cm, 12 support vectors of 70, test 1.000
20 splits, settings chosen in validation: test linear 0.950, RBF 0.947; RBF better 2, worse 4, equal 14
wine, RBF SVM, raw: validation 0.657
wine, RBF SVM, scaled inside each fold: validation 0.983