Support Vector Machines

1. Hyperebenen und Abstände

Folien 2-4

Eine Hyperebene wird über eine Konstante und einen Normalenvektor beschrieben. Der Normalenvektor steht orthogonal auf der Hyperebene. Jeder Punkt x auf der Hyperebene erfüllt:

Dabei ist n₀ der Achsenabschnitt beziehungsweise Bias-Term, n der Normalenvektor, x ein Featurevektor und d die Anzahl der Features.

Abstand eines Punktes zur Hyperebene

Für einen Punkt p und die Hyperebene E: n^Tx + n₀ = 0 lautet der geometrische Abstand:

Ohne Betrag liefert p^Tn + n₀ einen vorzeichenbehafteten Abstand, wenn n normiert ist. Das Vorzeichen sagt, auf welcher Seite der Hyperebene der Punkt liegt.

2. Lineare binäre Klassifikation

Folien 6-10

Die Folien betrachten zunächst binäre Klassifikation mit genau zwei Klassen. Ziel ist eine Regel, die die beiden Klassen durch eine Hyperebene trennt. Die Entscheidungsfunktion lautet:

Trennende Hyperebene prüfen

Man kodiert die Klassen als y_i = +1 und y_i = −1. Ein Datenpunkt (x_i, y_i) ist korrekt klassifiziert, wenn das Vorzeichen von f(x_i) zur Kodierung passt.

Falls die Klassenkodierung andersherum gewählt wird, kann die Bedingung äquivalent mit negativem Vorzeichen auftreten. Wichtig ist nicht das absolute Vorzeichen der Hyperebene, sondern die konsistente Zuordnung zwischen Klasse und Seite.

3. Hard Margin Classifier

Folien 11-15

Wenn viele Hyperebenen die Daten korrekt trennen, ist nicht jede gleich gut. Eine große Margin bedeutet, dass die Entscheidungsgrenze möglichst weit von den nächsten Trainingspunkten entfernt liegt. Diese nächsten Punkte heißen Supportvektoren.

Warum Supportvektoren die Lösung bestimmen

Nur die Punkte auf den Margin-Grenzen stützen die Lage der optimalen Hyperebene. Kleine Änderungen an Nicht-Supportvektoren verändern die Hyperebene nicht, solange diese Punkte außerhalb der Margin bleiben. Änderungen an Supportvektoren können die Lage der Grenze direkt verschieben.

Margin-Bedingung

Für eine normierte Hyperebene ohne Margin-Verletzung gilt:

M ist die geforderte Margin, m die Anzahl der Beobachtungen. Diese Bedingung setzt voraus, dass n normiert ist; sonst steht links kein geometrischer Abstand.

Optimierungsproblem

Die Folien formulieren die Hard-Margin-Idee als Maximierung der Margin unter Nebenbedingungen:

Hier steht p für die Anzahl der Features. Die Nebenbedingung Σ n_j² = 1 normiert den Normalenvektor. In der Praxis wird das Problem oft in ein quadratisches Optimierungsproblem umformuliert.

4. Soft Margin / Support Vector Classifier

Folien 16-18

Der Soft Margin Classifier lockert die harte Forderung nach perfekter Trennung. Die Grundidee: Die meisten Punkte sollen gut getrennt werden, aber einzelne Punkte dürfen innerhalb der Margin oder sogar auf der falschen Seite der Hyperebene liegen.

Slack-Variablen

Für jeden Trainingspunkt gibt es eine Slack-Variable ε_i. Sie misst, wie stark der Punkt die Margin-Bedingung verletzt. Ein Budget C begrenzt in der Foliennotation die Summe dieser Verletzungen.

5. Kernel und Feature-Räume

Folien 19-35

Warum lineare Grenzen nicht immer reichen

Manche Daten lassen sich im ursprünglichen Feature-Raum nicht sinnvoll linear trennen. Das liegt nicht nur an einem schlecht gewählten Soft-Margin-Parameter: Eine lineare Entscheidungsgrenze kann strukturell ungeeignet sein.

Feature-Raum erweitern

Eine Lösung ist, zusätzliche Features zu erzeugen, zum Beispiel Potenzen und Produkte der ursprünglichen Variablen. Ein linearer Klassifikator im erweiterten Raum kann im ursprünglichen Raum eine nichtlineare Grenze erzeugen.

Das Problem: Polynome höherer Ordnung werden numerisch schnell schwierig. Außerdem ist vorab unklar, welcher Polynomgrad oder welche Feature-Kombination ausreicht.

Distanzfeatures als Motivation für Kernel

Die Folien zeigen eine 1D-Situation: Im ursprünglichen Raum sind die Klassen nicht durch einen Punkt trennbar. Wenn man aber als zweites Feature den Abstand zu einem geeigneten Referenzpunkt verwendet, entsteht eine lineare Trennmöglichkeit im erweiterten Raum.

Der entscheidende Schritt: Statt einen einzelnen Referenzpunkt manuell zu wählen, kann man alle Trainingspunkte als Referenzen betrachten. Ein Kernel fasst diese Idee über eine parametrisierte Ähnlichkeits- oder innere-Produkt-Funktion zusammen.

Radial-Kernel

K ist die Kernelfunktion, γ steuert die Reichweite des Kernels, p ist die Featurezahl, und x_j beziehungsweise x′_j sind die j-ten Komponenten der beiden Vektoren. Große Werte von γ machen den Kernel lokaler und können zu sehr flexiblen Grenzen führen; kleine Werte glätten stärker.

Kernel-Trick

Der Kernel-Trick vermeidet, die hochdimensionale Transformation explizit auszurechnen. Statt direkt mit ϕ(x) zu arbeiten, berechnet man nur innere Produkte im transformierten Raum:

Der Raum ℋ kann sehr hochdimensional oder beim Radial-Kernel sogar unendlich-dimensional sein. Man muss ϕ aber nicht explizit bilden; es reicht, K auszuwerten.

Vorhersage mit Kernel-SVM

Die Hyperebene im hochdimensionalen Raum kann durch Trainingspunkte und Gewichte beschrieben werden:

Die Gewichte α_i werden im Training bestimmt. Punkte mit α_i = 0 werden für die Vorhersage nicht benötigt; Punkte mit α_i ≠ 0 sind Supportvektoren. Die Folien verwenden in der Kernel-Summe n als Anzahl der Trainingspunkte; an anderer Stelle steht dafür m.

6. Mehrklassen-SVM und Modellwahl

Folien 36-39

SVMs mit mehr als zwei Klassen

Die bisherige SVM-Formulierung ist binär. Für K Klassen nutzt man typischerweise Reduktionsstrategien:

Modellwahl

Wenn Klassen fast exakt trennbar sind, können Soft-Margin-Klassifikatoren besser passen als logistische Regression oder LDA, weil die Margin-Idee die Grenze an den kritischsten Punkten ausrichtet. Wenn die Trennung nicht klar ist, können logistische Regression und Soft-Margin-SVM ähnlich wirken.

Wenn Wahrscheinlichkeiten benötigt werden, sind logistische Regression oder LDA naheliegender. Es gibt SVM-Varianten mit Wahrscheinlichkeiten, aber die Standard-SVM liefert primär Scores und Klassenentscheidungen. Für nichtlineare Daten sind Kernel-SVMs besonders relevant; Kernelideen können prinzipiell auch bei anderen Verfahren verwendet werden.

7. Lab und Implementierung

Folien 41-48

Der Lab-Teil nutzt R, die Pakete e1071 und ggplot2, einen künstlichen nichtlinearen Datensatz und eine SVM mit radialem Kernel.

Grundworkflow in R

library(e1071)
library(ggplot2)
set.seed(123)

x1 <- runif(100, -2, 2)
x2 <- runif(100, -2, 2)
y <- ifelse(x1^2 + x2^2 < 1.5, "Class_A", "Class_B")
dat <- data.frame(x1 = x1, x2 = x2, y = factor(y))

svm_model <- svm(
  y ~ .,
  data = dat,
  kernel = "radial",
  cost = 10,
  gamma = 1
)

Für die Visualisierung wird ein Gitter über den Feature-Raum gelegt. Das Modell sagt für jeden Gitterpunkt eine Klasse voraus. Daraus entstehen farbige Entscheidungsregionen und eine Konturlinie als Entscheidungsgrenze.

Moons-Datensatz

Die Moons-Aufgabe prüft, ob man die Modellidee übertragen kann: Ein linearer Kernel wird die halbmondförmigen Klassen typischerweise schlecht trennen, ein radialer Kernel kann die gekrümmte Struktur erfassen.

8. Klausurteil

Typische Aufgaben und Rechenwege

1. Abstand berechnen: Setze den Punkt in f(x) ein, bilde ∥n∥, teile den Betrag des Scores durch die Norm.
2. Trennung prüfen: Berechne y_i · f(x_i) für alle Punkte. Positiv bedeutet korrekt unter der gewählten Kodierung.
3. Margin prüfen: Stelle zuerst sicher, dass der Normalenvektor normiert ist. Dann prüfe y_i · f(x_i) ≥ M.
4. Supportvektoren identifizieren: Hard Margin: Punkte auf den Margin-Grenzen. Soft Margin: Punkte auf der Grenze, innerhalb der Margin oder falsch klassifiziert.
5. Slack-Budget prüfen: Summiere die ε_i. Die Bedingung der Folien ist erfüllt, wenn Σ ε_i ≤ C.
6. RBF-Kernel berechnen: Quadrierte Distanz komponentenweise aufsummieren, mit −γ multiplizieren, Exponentialfunktion anwenden.
7. OVA/OVO zählen: One-vs-All benötigt K Klassifikatoren, One-vs-One benötigt K(K−1)/2.

Häufige Fehler

Kompakte Lerncheckliste

Mögliche Klausurfragen

1. Definieren Sie eine Hyperebene in ℝ^d und erklären Sie die Rolle des Normalenvektors.
2. Berechnen Sie den Abstand eines gegebenen Punktes zu einer angegebenen Hyperebene.
3. Prüfen Sie anhand von y_i · f(x_i), ob eine Hyperebene alle Trainingspunkte korrekt trennt.
4. Erklären Sie den Unterschied zwischen trennender Hyperebene und Hard-Margin-Hyperebene.
5. Identifizieren Sie in einer Grafik die Supportvektoren und begründen Sie Ihre Wahl.
6. Formulieren und interpretieren Sie die Nebenbedingungen des Hard-Margin-Problems.
7. Erklären Sie, warum Soft Margin bei nicht exakt trennbaren Daten eingesetzt wird.
8. Interpretieren Sie vorgegebene Slack-Werte ε_i und prüfen Sie das Budget C.
9. Zeigen Sie anhand eines Beispiels, wie eine Feature-Erweiterung eine nichtlineare Grenze im Originalraum erzeugt.
10. Berechnen Sie einen Radial-Kernelwert für zwei Featurevektoren.
11. Erklären Sie den Kernel-Trick ohne explizite Berechnung von ϕ.
12. Vergleichen Sie OVA und OVO für ein Klassifikationsproblem mit K Klassen.
13. Welche Modellwahl ist sinnvoll, wenn Wahrscheinlichkeiten benötigt werden?
14. Warum kann kernel = "radial" beim Moons-Datensatz funktionieren, während ein linearer Kernel scheitert?

9. Abdeckungstabelle