Support-Vector-Maschinen und Kerne

Zwei Irisarten, zwei Kronblattmessungen. Im Training trennen viele Geraden sie gleich gut. Eine Support-Vector-Maschine (SVM) wählt die, um die herum das breiteste leere Band bleibt, den Rand (englisch margin). Die Blüten am Bandrand, im Band oder auf der falschen Seite sind die Stützvektoren. Nur sie legen die Grenze fest: Alle anderen Blüten könnte man löschen, und die Grenze bliebe dieselbe. Überlappen sich die Klassen, kann das Band nicht leer sein, also zahlt die SVM eine Strafe für jede Blüte im Band oder auf der falschen Seite. Die Zahl C legt den Preis dieser Strafe fest. Ein kleines C erlaubt ein breites Band mit vielen Verletzungen; ein großes C verlangt, die Blüten auf der richtigen Seite zu halten, auch um den Preis eines schmalen Bandes.

Probier es aus

• Beginne mit den Kronblättern bei C = 100. Wie viele Blüten halten die Grenze, und wie breit ist das Band?
• Schiebe C nach unten. Bei welchem C ist die Validierung am besten, und bei welchem ist das Band bei fast gleichem Ergebnis am breitesten?
• Wechsle zu den Kelchblättern. Trennt hier irgendein C die Arten?
• Geh zu den Weinen. Vergleiche „nur x“, die Merkmale √2·x und x² und den Kern (x·z + 1)². Dann schalte auf den RBF-Kern und schiebe γ (wie schnell die Ähnlichkeit zweier Weine sinkt, wenn sie auseinanderrücken) bis 1000.

Wenn du es im Lab geprüft hast, geben wir dem, was du siehst, einen Namen.

Die Idee in einfachen Worten

Eine SVM berechnet keine Wahrscheinlichkeiten wie die logistische Regression. Sie zeichnet eine Grenze und zwei Linien parallel dazu, eine auf jeder Seite. Das Band dazwischen soll so breit wie möglich sein, und die Blüten sollen außerhalb liegen, auf ihrer eigenen Seite. Eine Blüte, die nicht passt, bekommt eine Strafe, so groß wie die Tiefe, mit der sie ins Band ragt. Das ist der Hinge-Verlust. Das Modell sucht einen Ausgleich: auf der einen Seite ein breites Band, auf der anderen C mal die Summe der Strafen.

Bei C = 0,01 kosten Strafen fast nichts. Das Band ist 3,9 cm breit, und alle 70 Trainingsblüten sind Stützvektoren: Jede verschiebt die Grenze ein wenig. Bei C = 100 ist jede Verletzung teuer. Das Band ist 0,15 cm breit, und 4 Blüten direkt an der Grenze halten es. Der Test ändert sich dabei um eine Blüte. Auf den Kronblättern liegen die Arten so weit auseinander, dass fast jede vernünftige Gerade dieselben Blüten trifft.

C wählt man wie jeden Hyperparameter: per Validierung, nicht per Test. Das Lab rechnet eine 5-fache Kreuzvalidierung innerhalb der 70 Trainingsblüten. Am besten schneidet C = 10 ab: 69 von 70. Bei C = 0,1 sind es 68 von 70, und das Band ist 1,4 cm statt 0,34 cm breit. Eine Blüte Unterschied ist in der Validierung Rauschen, und ein breiteres Band stützt die Grenze auf mehr Blüten. Das kleinste C übertreibt dafür in die andere Richtung: 64 von 70.

Die Grenze muss nicht gerade sein. Bei den Weinen fragen wir nur, ob ein Wein Rebsorte 2 ist oder eine andere, es gibt also zwei Klassen. Rebsorte 2 liegt in der Mitte der Flavanoid-Achse: Rebsorte 1 hat im Mittel 2,98, Rebsorte 2 2,08 und Rebsorte 3 0,78. Eine einzige Schwelle schneidet die Mitte nicht heraus, also zeigt die lineare SVM hier lieber nirgends auf Rebsorte 2. Validierung: 60,0 %, so viel wie die Antwort „immer eine andere Rebsorte“. Ersetzen wir x durch zwei Merkmale: √2·x und x². Die Weine landen auf einer Parabel, und eine Gerade in der Ebene (√2·x, x²) sind auf der Achse zwei Schwellen, also ein Intervall. Die Validierung steigt auf 72,0 %.

Ein Kern tut dasselbe, ohne Spalten hinzuzufügen. Die SVM braucht nur Skalarprodukte von Beispielpaaren. Das Skalarprodukt ist die Summe der Produkte zusammengehöriger Koordinaten zweier Beispiele; die SVM nutzt es als Maß ihrer Ähnlichkeit. Der Kern (x·z + 1)² liefert genau das Skalarprodukt der Vektoren (1, √2·x, x²), also ist die Grenze identisch mit der der Merkmale √2·x und x². Das ist der Kern-Trick. Der RBF-Kern (von radial basis function, radiale Basisfunktion) exp(−γ(x − z)²) misst Ähnlichkeit über den Abstand: γ sagt, wie schnell die Ähnlichkeit sinkt, wenn zwei Weine auseinanderrücken. Er entspricht unendlich vielen solchen Merkmalen. Bei γ = 3 liegt die Validierung bei 78,4 %, der besten der acht Werte von γ, und der Test ergibt danach 84,9 %. Bei γ = 0,3, 1 und 10 sind es 76,8 %, nur 2 Weine von 125 weniger. Wie bei C auf den Iris ist das praktisch ein Remis. Bei γ = 1000 steigt das Training auf 89,6 %, die Validierung fällt auf 69,6 %. Die Grenze zerfällt dann in 11 Intervalle, angepasst an einzelne Weine. Der höchste Test, 86,8 %, liegt bei γ = 100, aber nach dem Test zu wählen heißt, mit den Daten zu wählen, mit denen du bewertest.

Jak to policzono

• Iris: Iris (Fisher, 1936; UCI, Lizenz CC BY 4.0), 100 Blüten versicolor und virginica. Messungen in Zentimetern ohne Skalierung, weil beide Merkmale dieselbe Einheit haben. Geschichtete Aufteilung: 70 Blüten zum Lernen, 30 für den Test.
• Weine: Wine (Aeberhard und Forina, 1992; UCI, Lizenz CC BY 4.0), 178 Weine, nur der Flavanoid-Gehalt, C = 1. Aufteilung: 125 Weine zum Lernen, 53 für den Test. Die z-Werte kommen nur aus den Lernweinen, in der Validierung aus den Lernweinen jedes Teils.
• Validierung: geschichtete 5-fache Kreuzvalidierung innerhalb des Trainings. Modell: eine SVM mit weichem Rand; die Zahlen stimmen mit SVC aus scikit-learn überein.

Warum es funktioniert

Ein breites Band ist Regularisierung, wie die Ridge-Strafe aus Lektion 3.4. Das Band ist 2/‖w‖ breit, also bedeutet ein breites Band kleine Gewichte und eine Grenze, die weniger von einzelnen Blüten abhängt. Den Rand mit einer Strafe für Verletzungen beschrieben Cortes und Vapnik (1995). Der Kern-Trick kam schon früher zu den SVMs, durch Boser, Guyon und Vapnik (1992): Da das Modell nur Skalarprodukte nutzt, lässt sich jedes durch einen Kern ersetzen.

Dass C die Geometrie stärker ändert als das Ergebnis, ist kein Zufall einer Aufteilung. Auf 20 anderen Iris-Aufteilungen unterscheidet sich die Testgenauigkeit über die 9 Werte von C um höchstens 2 Blüten von 30, während das Band von 3,8–4,1 cm auf 0,17–0,36 cm schrumpft.

Der RBF-Kern misst Abstände, also zählen die Einheiten. Die Weine haben 13 Messungen: Prolin reicht bis 1680, der Farbton höchstens bis 1,71. Ohne Skalierung ist der Abstand fast nur Prolin. Eine RBF-SVM auf allen 13 Messungen trifft dann auf 20 Aufteilungen im Mittel 67,2 % der Validierungsweine. Mit einer Skalierung, die nur auf dem Lernteil gelernt wird: 97,9 %.

Ein häufiger Fehler

Richtig oder falsch: „Nimm immer den RBF-Kern, er ist der flexibelste.“ Falsch. Auf den Iris-Kronblättern treffen eine lineare SVM und eine RBF-SVM, jede mit per Validierung gewählten Einstellungen, auf 20 Aufteilungen im Mittel je 28,5 von 30 Testblüten. RBF ist auf 1 Aufteilung besser und auf 1 schlechter. Die Grenze ist hier fast gerade, also bringt die Flexibilität nichts und kostet etwas: zwei Hyperparameter zum Tunen statt einem und leichtere Überanpassung (γ = 1000 bei den Weinen). Im Code unten erreicht die lineare 0,950, die RBF 0,947, und RBF ist auf 2 Aufteilungen besser und auf 4 schlechter.

Die praktische Lehre: Beginne mit einem linearen Kern oder mit logistischer Regression. Greif zu RBF, wenn die Validierung zeigt, dass die Grenze nicht gerade ist, wie bei den Weinen.

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