Der Kernel-Trick, Stützvektormaschinen, Kernel-Ridge und Entscheidungsbäume, mit durchgerechneten Zahlen

Der Klassifikator mit maximalem Rand

Unter allen Geraden, die zwei Klassen fehlerfrei trennen, behält die SVM diejenige, die auf jeder Seite so weit wie möglich von den nächstgelegenen Punkten entfernt bleibt.

Lassen sich zwei Klassen durch eine Gerade trennen, dann tun das unendlich viele Geraden ohne einen einzigen Trainingsfehler. Die logistische Regression wählt eine davon über die Likelihood. Die Stützvektormaschine (support vector machine, SVM) stellt stattdessen eine geometrische Frage: Welche Grenze lässt zwischen den Klassen den breitesten leeren Streifen frei? Ein neuer Kunde ähnelt einem bekannten, bis auf ein wenig Rauschen; eine Grenze, die einen Trainingspunkt streift, klassifiziert daher dessen verrauschte Nachbarn falsch.

Man kodiert die Klassen als $y_i \in \{-1, +1\}$ und schreibt $f(x) = w^{\top}x + b$. Skaliert man $w$ und $b$ gemeinsam, bleibt die Grenze unverändert, also setzt man $|f| = 1$ an den nächstgelegenen Punkten. Da ein Punkt den Abstand $|f(x)| / \lVert w \rVert$ zur Hyperebene hat, ist der Streifen $2/\lVert w \rVert$ breit, und ihn zu verbreitern heißt, $\lVert w \rVert$ zu verkleinern. Die Suche nach dem maximalen Rand (maximum margin) ergibt damit ein konvexes quadratisches Problem mit eindeutigem Minimum (Cortes und Vapnik, 1995):

Die Lösung, die auch SVC von scikit-learn mit linearem Kernel und sehr großem $C$ liefert, hat $\lVert w \rVert = 2\sqrt2/3 \approx 0.943$, der Streifen ist also $2/\lVert w \rVert = 3/\sqrt2 \approx 2.12$ breit: genau der Abstand zwischen den beiden gestrichelten Linien, gemessen entlang der Normalen $(1, 1)/\sqrt2$. Drei Kunden berühren den Streifen; sie sind die Stützvektoren (support vectors). Die anderen drei könnten sich bewegen oder verschwinden, ohne dass sich die Grenze ändert.

Zurück zum Inhalt.

Weicher Rand, Hinge-Verlust und der Preis C

Echte Daten sind nie vollständig trennbar, also lässt die SVM einige Punkte in den Streifen eindringen und verlangt für jede Einheit Übertretung einen festen Preis.

Bei Kreditdaten trennt keine Gerade die Ausfälle von den soliden Kunden. Cortes und Vapnik (1995) geben jedem Punkt eine Schlupfvariable (slack variable) $\xi_i \ge 0$, den Betrag, um den er den Rand verletzt, und fügen der Zielfunktion $C \sum_i \xi_i$ hinzu. Im Optimum ist jeder Schlupf gleich $\max(0, 1 - y_i f(x_i))$, sodass sich die Nebenbedingungen ganz entfernen lassen:

Der Summand ist der Hinge-Verlust (hinge loss): null für einen Punkt auf der richtigen Seite mit einem Vorsprung von mindestens 1, danach linear wachsend, sobald der Punkt in den Streifen eindringt oder die Grenze überquert. So gelesen ist die SVM mit weichem Rand (soft margin) eine Verlustfunktion plus eine Strafe auf $\lVert w \rVert^{2}$, dieselbe Form wie Ridge, wobei $C$ die Rolle von $1/\lambda$ spielt. Ein kleines $C$ ergibt einen breiten Rand und eine starke Regularisierung (Gefahr der Unteranpassung, Underfitting), ein großes $C$ einen schmalen Rand und die Gefahr der Überanpassung (Overfitting), wie beim C von LogisticRegression.

Zurück zum Inhalt.

Das duale Problem: Nur die Stützvektoren zählen

Schreibt man die SVM mit einem Preis pro Nebenbedingung um, zeigt sich, dass Punkte fern der Grenze den Preis null erhalten, sodass ihr Entfernen nichts ändert.

Man ordnet jeder Nebenbedingung einen Lagrange-Multiplikator $\alpha_i \ge 0$ zu und zieht die Nebenbedingungen von der Zielfunktion ab. Setzt man den Gradienten nach $w$ und dann die Ableitung nach $b$ gleich null, erhält man zwei Identitäten. Setzt man sie wieder ein, verschwinden $w$ und $b$, und es bleibt ein Problem, in dem nur noch $\alpha$ vorkommt:

Mit weichem Rand kommt nur die Obergrenze $\alpha_i \le C$ hinzu. Der komplementäre Schlupf (complementary slackness), eine der Karush-Kuhn-Tucker-Bedingungen (KKT), liefert $\alpha_i\,[\,y_i f(x_i) - 1\,] = 0$, also ist entweder der Preis null oder die Nebenbedingung aktiv. Ein korrekt klassifizierter Punkt außerhalb des Streifens hat $\alpha_i = 0$ und verschwindet aus $w$ und aus jeder Vorhersage. Diese Dünnbesetztheit (Sparsity) ist der Grund, warum SVC zum Vorhersagen nur seine support_-Punkte behält.

Durchgerechnetes Beispiel: vier Kunden auf einer Geraden

1. Daten. Solide Kunden bei $x = -3$ und $x = -1$, Ausfälle bei $x = 2$ und $x = 4$. Es sind die beiden inneren Punkte, die die Grenze einfassen.
2. Stützvektoren am Rand. Aus $y\,f(x) = 1$ bei $x = -1$ und bei $x = 2$ folgen $w - b = 1$ und $2w + b = 1$. Addiert man beide, ergibt sich $3w = 2$, also $w = 2/3$, $b = -1/3$, und die Grenze liegt bei $x = 1/2$.
3. Äußere Punkte. Bei $x = -3$ und $x = 4$ beträgt der Vorsprung $7/3 > 1$, die Nebenbedingung ist also nicht aktiv, und nach dem komplementären Schlupf ist ihr Preis null.
4. Preise. Die Bedingung $\sum_i \alpha_i y_i = 0$ erzwingt, dass die beiden verbleibenden Preise gleich sind, etwa $a$. Dann gilt $w = a(-1)(-1) + a(+1)(2) = 3a = 2/3$, also $a = 2/9$.
5. Probe. Der primale Wert $\tfrac12 w^{2} = 2/9$ ist gleich dem dualen Wert $\sum_i \alpha_i - \tfrac12 w^{2} = 4/9 - 2/9$, und der Rand $2/w = 3$ ist der Abstand von $-1$ bis $2$. Den Punkt bei $-3$ nach $-10$ zu verschieben, ändert nichts; den Punkt bei $-1$ zu verschieben, ändert alles.

Zurück zum Inhalt.

Der Kernel-Trick: polynomiale und RBF-Kernel

Das duale Problem sieht die Daten nur über Ähnlichkeiten zwischen Punktpaaren; ersetzt man das Skalarprodukt durch ein reicheres Ähnlichkeitsmaß, krümmt sich die Grenze ohne Mehraufwand.

Ein zweiter Blick auf das duale Problem: Das Training braucht nur die $n \times n$-Tabelle der Skalarprodukte $x_i^{\top}x_j$, die Gram-Matrix, und die Vorhersage nur $x_i^{\top}x$. Punkte auf einer Geraden, mit einer Klasse an beiden Enden und der anderen in der Mitte, lassen sich nicht durch einen einzigen Schwellenwert trennen, nach $x \mapsto (x, x^{2})$ aber durch eine waagerechte Gerade. Eine gekrümmte Grenze wird nach einer Transformation $\varphi$, der Merkmalsabbildung (feature map), zu einer ebenen. Der Kernel-Trick berechnet $\varphi(x)^{\top}\varphi(z)$ direkt aus $x$ und $z$, ohne $\varphi$ aufzubauen (Boser, Guyon und Vapnik, 1992).

Beim polynomialen Kernel vom Grad 2 in zwei Dimensionen multipliziert man das Quadrat aus und zerlegt den gemischten Term in $\sqrt2 \cdot \sqrt2$. So tritt die verborgene Abbildung zutage:

Probe mit $x = (1, 2)$ und $z = (3, -1)$. Die Kernel-Seite braucht zwei Produkte, eine Summe und ein Quadrat: $x^{\top}z = 1$, also $k = 1$. Die Merkmalsseite baut $\varphi(x) = (1, 2\sqrt2, 4)$ und $\varphi(z) = (9, -3\sqrt2, 1)$ auf, deren Skalarprodukt $9 - 12 + 4 = 1$ ist. Der allgemeine Kernel $(x^{\top}z + c)^{d}$ enthält jede Wechselwirkung bis zum Grad $d$, zum Preis eines Skalarprodukts und einer Potenz.

Der gaußsche oder RBF-Kernel (radiale Basisfunktion) ist 1 für identische Punkte und klingt mit dem Abstand ab; $\gamma$ legt fest, wie weit der Einfluss jedes Trainingspunkts reicht. Für zwei Punkte mit quadriertem Abstand 5 ergibt er $e^{-0.5} \approx 0.607$ bei $\gamma = 0.1$ und etwa 0,082 bei $\gamma = 0.5$. Entwickelt man die Exponentialfunktion als Potenzreihe, zeigt sich, dass seine Merkmalsabbildung unendlich viele Koordinaten hat. Mit kleinem $\gamma$ ist die Grenze fast gerade, mit großem zeichnet sie Inseln um einzelne Punkte.

Zurück zum Inhalt.

Kernel-Ridge-Regression und Kernel in der Praxis

Die Kernel-Ridge-Regression ist die Ridge-Regression, umgeschrieben mit einem Gewicht pro Trainingspunkt; so kann ein Kernel das Skalarprodukt ersetzen, und die Lösung bleibt in geschlossener Form.

Ausgangspunkt ist Ridge in geschlossener Form. Die Identität $(X^{\top}X + \lambda I_p)X^{\top} = X^{\top}(XX^{\top} + \lambda I_n)$ zeigt, dass $\hat\beta = X^{\top}\alpha$ gilt, mit einem Gewicht pro Trainingspunkt. Die Vorhersagen enthalten dann nur noch Skalarprodukte $x_i^{\top}x$, die ein Kernel ersetzt (Repräsentantensatz, Kimeldorf und Wahba, 1971):

Anders als bei der SVM gibt es keine Dünnbesetztheit: Der Verlust ist quadratisch, also ist im Allgemeinen jedes $\alpha_i$ ungleich null, und der gesamte Trainingsdatensatz wird aufbewahrt. Im Gegenzug ist die Anpassung ein einziges lineares Gleichungssystem, gelöst mit np.linalg.solve statt durch Invertieren der Matrix; mit linearem Kernel muss sie Ridge bis auf Maschinengenauigkeit reproduzieren. In scikit-learn heißt $\lambda$ bei KernelRidge alpha, und ein Achsenabschnitt wird nicht angepasst.

Die beiden Punkte mit Zielwert 0 erhalten negative Gewichte: Sie ziehen die Anpassung in ihrer Umgebung nach unten. Bei $x = 1$ ist der Zielwert 1, aber die Strafe drückt die Anpassung auf 0,576.

Ein größeres $C$ wirkt in dieselbe Richtung wie ein größeres $\gamma$, und beide werden per Kreuzvalidierung auf einem Gitter aus Zehnerpotenzen gewählt. Standardisieren Sie zuerst: Ein RBF-Kernel addiert quadrierte Abstände in den Einheiten jeder Variable, sodass ein Kreditlimit in Zehntausenden von Dollar ein Alter in Jahren erdrückt und $K$ zur Einheitsmatrix zusammenfällt. Der Scaler gehört in die Pipeline und wird auf den Trainings-Folds angepasst.

Der Preis des Tricks ist die $n \times n$-Matrix: 32 MB in doppelter Genauigkeit für 2.000 Zeilen, 2,6 GB für die 18.000 Trainingszeilen des Kreditdatensatzes und ein Lösungsaufwand von etwa $n^{3}$ Operationen. Für großes $n$ bauen zufällige Fourier-Merkmale (random Fourier features, Rahimi und Recht, 2007) $D$ zufällige Kosinus-Spalten, deren Skalarprodukte den RBF-Kernel approximieren; eine logistische Regression darauf skaliert in $O(nD)$ und liefert, anders als SVC oder KernelRidge, Wahrscheinlichkeiten.

Zurück zum Inhalt.

Entscheidungsbäume: der Split mit dem größten Reinheitsgewinn

Ein Entscheidungsbaum stellt eine Kette von Ja-Nein-Fragen, jeweils zu einer Variable, und wählt jede Frage so, dass die entstehenden Gruppen möglichst homogen sind.

Ein Entscheidungsbaum (decision tree) spielt „Wer ist es?“: War der Kunde im letzten Monat mindestens zwei Monate im Zahlungsverzug? Dann eine Frage zum Kreditlimit und so weiter, bis ein Blatt den Anteil der Ausfälle unter den Trainingskunden vorhersagt, die dort ankommen. CART (Breiman, Friedman, Olshen und Stone, 1984) lässt den Baum gierig von oben wachsen: An jedem Knoten probiert das Verfahren jede Variable und jeden Schwellenwert (die Mittelpunkte zwischen sortierten Werten), behält den Split, der die gewichtete Unreinheit der Kinder am stärksten senkt, und fährt rekursiv fort.

Die Gini-Unreinheit (Gini impurity) $G$ misst, wie gemischt ein Knoten ist: Zieht man zwei seiner Kunden zufällig mit Zurücklegen, gibt sie die Wahrscheinlichkeit an, dass ihre Klassen verschieden sind; bei zwei Klassen ist sie gleich $2p(1-p)$, null für einen reinen Knoten und höchstens $1/2$. Die Shannon-Entropie $H$, in Bit, stammt aus Quinlans ID3 (1986) und C4.5 (1993); ihre Abnahme ist der Informationsgewinn (information gain). Beide Kurven haben dieselbe Form und wählen fast immer denselben Split. scikit-learn verwendet standardmäßig Gini.

Durchgerechnetes Beispiel: der Gewinn jedes Splits

1. Elternknoten. Vier Ausfälle von zehn, also $p = 0.4$ und $G = 1 - 0.16 - 0.36 = 0.48$.
2. Kinder von A. Drei Ausfälle von vier links ergeben $G = 1 - 9/16 - 1/16 = 6/16 = 0.375$, einer von sechs rechts ergibt $G = 10/36 \approx 0.278$.
3. Gewichteter Mittelwert. Nach Anzahlen gewichtet ergibt sich $0.4 \times 0.375 + 0.6 \times 0.278 \approx 0.317$, also gewinnt Split A $0.48 - 0.317 = 0.163$. Mit der Entropie beträgt der Gewinn $0.971 - (0.4 \times 0.811 + 0.6 \times 0.650) \approx 0.256$, A gewinnt also nach beiden Kriterien.
4. Split B. Jede Seite hat zwei Ausfälle von fünf, den Anteil des Elternknotens, also haben beide Kinder dessen Unreinheit, und der Gewinn ist null. Eine Frage, die die Mischung des Elternknotens wiedergibt, sagt nichts aus, gleich welche Variable sie betrifft.
5. Probe. DecisionTreeClassifier(max_depth=1) wählt PAY_0 mit dem Schwellenwert 1,5, dem Mittelpunkt zwischen 1 und 2, und gibt dieselben drei Unreinheiten aus.

Zurück zum Inhalt.

Tiefe, Beschneiden, Instabilität und der Bias der MDI

Sich selbst überlassen, wächst ein Baum, bis er den Trainingsdatensatz auswendig kennt; er muss also gestoppt oder beschnitten werden, und seine eingebauten Wichtigkeitswerte verdienen Misstrauen.

Standardmäßig (max_depth=None) lässt scikit-learn den Baum wachsen, bis jedes Blatt rein ist. Eine maximale Tiefe, eine minimale Blattgröße (min_samples_leaf) oder ein minimaler Gewinn stoppen ihn früher; kleine Blätter liefern außerdem grobe Wahrscheinlichkeiten.

Die Simulation des Foliensatzes macht es deutlich: Eine binäre Variable setzt die Ausfallwahrscheinlichkeit auf 0,7 oder 0,3, zwei weitere sind Rauschen, 1.000 Zeilen zum Trainieren und 1.000 zum Testen, also kann kein Klassifikator 0,70 übertreffen. Ein Baum der Tiefe 1 oder 2 erreicht im Test 0,683; ein unbegrenzter Baum erzielt im Training 1,000 mit 397 Blättern und im Test 0,549, kaum besser als ein Münzwurf.

Statt früh zu stoppen, lässt CART den vollständigen Baum wachsen und beschneidet ihn dann, die Kosten-Komplexitäts-Beschneidung (cost-complexity pruning): $R(T)$ ist der Trainingsfehler, $|T|$ die Zahl der Blätter und $\alpha$ ein Preis pro Blatt, gewählt per Kreuzvalidierung (ccp_alpha in scikit-learn). Die optimalen Teilbäume sind ineinander verschachtelt, also muss man nur eine Handvoll testen.

Beim höchsten Preis bleiben zwei Blätter: ein einziger Split, auf der einzigen nützlichen Variable. Ein kurzer Baum lässt sich laut als Regel vorlesen, die ein Kunde anfechten kann, und das schätzt das regulierte Kreditgeschäft. Er ist aber auch instabil: Passt man einen Baum der Tiefe 3 neu an, nachdem zufällig 5 % der Zeilen entfernt wurden, springt die zweite Ebene zu Rauschvariablen und neuen Schwellenwerten. Breimans Bagging (1996) geht von dieser Beobachtung aus und führt zu den Random Forests und dem Boosting der nächsten Sitzung.

Das Attribut feature_importances_ von scikit-learn ist die mittlere Abnahme der Unreinheit (mean decrease in impurity, MDI): die nach Knotengröße gewichteten Gewinne der Splits auf jeder Variable, auf 1 normiert. Sie kostet nichts, ist aber doppelt verzerrt. Sie wird auf den Trainingsdaten gemessen, also zählen auch Splits, die Rauschen angepasst haben; und eine stetige Variable bietet Hunderte von Schwellenwerten, wo eine binäre nur einen bietet, daher viel mehr Zufallstreffer. Im unbegrenzten Baum der Simulation setzt die MDI das stetige Rauschen an die erste Stelle (0,754) und die nützliche Variable an die zweite (0,206); die Permutationswichtigkeit auf zurückgehaltenen Daten stellt die Reihenfolge wieder her (Strobl et al., 2007).

Zurück zum Inhalt.

Das Wichtigste in Kürze

1. Die SVM behält die Grenze mit dem breitesten Rand, $2/\lVert w \rVert$, indem sie $\tfrac12 \lVert w \rVert^{2}$ unter einer Nebenbedingung pro Punkt minimiert; der weiche Rand fügt einen Hinge-Verlust mit dem Preis $C$ hinzu.
2. Im dualen Problem gilt $w = \sum_i \alpha_i y_i x_i$, und Punkte außerhalb des Streifens haben $\alpha_i = 0$, sodass nur die Stützvektoren die Grenze formen.
3. Da das duale Problem die Daten nur über Skalarprodukte sieht, kann jeder Kernel mit positiv semidefiniten Gram-Matrizen sie ersetzen; das $\gamma$ des RBF-Kernels legt die Reichweite jedes Punkts fest.
4. Kernel-Ridge löst $\alpha = (K + \lambda I)^{-1} y$ in einem einzigen linearen Gleichungssystem, behält aber jeden Trainingspunkt; zuerst standardisieren und bei großem $n$ den Kernel approximieren.
5. Ein Baum wählt jeden Split nach der stärksten Abnahme der gewichteten Unreinheit; ein Split, der die Anteile des Elternknotens kopiert, gewinnt nichts.
6. Ein unbegrenzter Baum lernt das Rauschen, ein kurzer ist lesbar, aber instabil, und die unreinheitsbasierte Wichtigkeit bevorzugt Variablen mit vielen Schwellenwerten.

Glossar

Stützvektormaschine (support vector machine, SVM)

Ein Klassifikator, der die Grenze mit dem breitesten Rand behält, gelockert durch einen Preis für Verletzungen.

Stützvektoren (support vectors)

Die Trainingspunkte auf dem Rand oder innerhalb des Streifens; die einzigen mit einem dualen Gewicht ungleich null.

Hinge-Verlust (hinge loss)

Die Verlustfunktion $\max(0, 1 - y f(x))$, null für einen Punkt auf der richtigen Seite mit einem Vorsprung von mindestens 1.

Kernel-Trick

Jedes Skalarprodukt durch einen Kernel ersetzen, also durch ein Skalarprodukt in einem größeren Raum, berechnet, ohne diesen Raum aufzubauen.

Gram-Matrix

Die $n \times n$-Matrix der Kernelwerte für alle Paare; positiv semidefinit bei einem gültigen Kernel.

Kernel-Ridge-Regression

Ridge in dualer Form mit einem Kernel, ein Gewicht pro Trainingspunkt.

Entscheidungsbaum (decision tree)

Ein Modell aus verschachtelten Schwellenwertfragen zu jeweils einer Variable; jedes Blatt ist ein Kasten im Eingaberaum.

Gini-Unreinheit (Gini impurity)

Die Größe $1 - \sum_k p_k^{2}$, die Wahrscheinlichkeit, dass zwei aus einem Knoten gezogene Punkte verschiedenen Klassen angehören.

Kosten-Komplexitäts-Beschneidung (cost-complexity pruning)

Den vollständigen Baum wachsen lassen und dann den Teilbaum behalten, der den Trainingsfehler plus einen Preis pro Blatt minimiert.

mittlere Abnahme der Unreinheit (mean decrease in impurity, MDI)

Die eingebaute Wichtigkeit eines Baums, verzerrt zugunsten von Variablen mit vielen Schwellenwerten.

Die anderen Notizen des Kurses

Eine öffentliche Zusammenfassung pro Foliensatz, in der Reihenfolge des Kurses.

Zurück: ML-Projekt abstecken: der ProjektsteckbriefWeiter: Random Forests, Boosting, ehrlicher Vergleich

1. EinführungKI-Winter, Arbeitsmarkt und Methode
2. WerkzeugeKaggle, GitHub, Python: die Werkzeuge
3. Sitzung 1Projektrahmen und kleinste Quadrate
4. Sitzung 2Maximum Likelihood und logistische Regression
5. Sitzung 3Gradientenabstieg, Ridge und Lasso
6. Sitzung 4Entscheidungsschwelle und reproduzierbares ML
7. HausaufgabeML-Projekt abstecken: der Projektsteckbrief
8. Sitzung 5Kernel, SVM und Entscheidungsbäume
9. Sitzung 6Random Forests, Boosting, ehrlicher Vergleich
10. Sitzung 7SHAP, Fairness, PCA und Clustering
11. HausaufgabeEin einfaches Modell mit vollständiger Methode
12. Sitzung 8Neuronale Netze, Drift, konforme Vorhersage
13. HausaufgabeEin ausgeliefertes Machine-Learning-Projekt
14. Sitzung 9Ein Machine-Learning-Projekt verteidigen
15. ReferenzProjekt zum Kreditausfallscore
16. ReferenzAktienrenditen: XGBoost und Sentiment
17. ReferenzPython-Code für jedes ML-Modell
18. ReferenzDeep Learning, das Wesentliche
19. ReferenzML-Projekte mit offenen Daten nach Branche
20. ReferenzHandbuch für Daten- und KI-Fachleute
21. ReferenzData Engineering, SRE und Cloud
22. ReferenzPanorama der Machine-Learning-Modelle

Alle Notizen als Leseliste

Aufmerksamkeit und Transformer, Schritt für Schritt

Über diese Notizen

Vom Dozenten auf Grundlage der Folien verfasst, als öffentliche Zusammenfassung: die Kernideen, die Formeln und ein durchgerechnetes Beispiel. Die Übungen, ihre Lösungen, die Tests und die Bewertung bleiben im Foliensatz, für die Studierenden des Kurses.

Stand: 16. Oktober 2026.