6.1 Fluch der Dimensionalität

Bevor die SVM eingeführt wird, motivieren die Folien, warum man in hochdimensionalen Räumen einen besonderen Lernalgorithmus braucht. Die Kurzfassung: Hohe Dimension ist zugleich Fluch (man braucht exponentiell viele Daten) und Verlockung (fast alles wird linear trennbar). Beides zusammen führt ohne zusätzliches Kriterium direkt ins Overfitting.

Der Fluch der Dimensionalität

📄 08_svm.pdf, Folie 4

Definition: Fluch der Dimensionalität (curse of dimensionality)

Die Komplexität von Funktionen mehrerer Variablen kann exponentiell mit der Dimension wachsen. Die Schätzung einer solchen Funktion erfordert dann ebenfalls exponentiell viele Daten.

Beispiel Dichteschätzung: Man schätzt eine Wahrscheinlichkeitsdichte mit einem Histogramm und teilt dazu jede Achse in 10 Intervalle. Damit jede Zelle mindestens einmal „besucht“ ist (100 % Abdeckung, coverage), braucht man mindestens so viele Datenpunkte wie Zellen:

Dimension $d$	Zellen bzw. benötigte Punkte
1	$10$
2	$100$
3	$1000$
6	$10^6$
$p$	$10^p$

Schon bei einem kleinen Graustufenbild mit $28\times 28 = 784$ Pixeln wären das $10^{784}$ Zellen, weit mehr als es Atome im Universum gibt. Mit einer realistischen Datenmenge sind fast alle Zellen leer.

Übertragung auf Klassifikation: Dasselbe gilt für die Trennfläche zwischen zwei Klassen. Ist diese beliebig kompliziert, muss man sie überall „abtasten“, um sie zu kennen. Die Anzahl der benötigten Datenpunkte skaliert ebenfalls exponentiell mit der Dimension.

Hochdimensionale Daten liegen an der Oberfläche

📄 08_svm.pdf, Folie 5 📄 08_svm.pdf, Folie 6

Ein zweiter, sehr unintuitiver Effekt: In hohen Dimensionen sitzt fast das ganze Volumen einer Kugel in einer dünnen Schale an ihrem Rand.

Annahme: Die Daten sind annähernd gleichverteilt. Dann ist die Anzahl der Beobachtungen in einem Bereich proportional zu seinem Volumen.

Frage: Welcher Volumenanteil einer $D$-dimensionalen Kugel mit Radius $R$ liegt in der Schale zwischen $r$ und $R$?

Herleitung: Das Volumen einer $D$-dimensionalen Kugel mit Radius $r$ ist

$$V(r) = k\cdot r^D,$$

wobei $k$ eine nur von $D$ abhängige Konstante ist (in 2D $k=\pi$, in 3D $k = \tfrac43\pi$). Setzt man $R = 1$ und $r = 1-\epsilon$, so ist der Anteil der Schale der Dicke $\epsilon$:

$$\frac{V(1) - V(1-\epsilon)}{V(1)} = \frac{k - k(1-\epsilon)^D}{k} = 1 - (1-\epsilon)^D.$$

Die Konstante $k$ kürzt sich heraus, das Ergebnis hängt nur von $\epsilon$ und $D$ ab.

Zahlenbeispiel für eine Schale mit $\epsilon = 0{,}1$, also die äußeren 10 % des Radius:

$D$	$(1-\epsilon)^D = 0{,}9^D$	Anteil der Schale
1	$0{,}9$	10 %
2	$0{,}81$	19 %
5	$0{,}59$	41 %
20	$0{,}12$	88 %
100	$0{,}00003$	99,997 %

Die Kurven auf Folie 6 (nach Bishop) zeigen genau diesen Zusammenhang: Für $D=20$ ist der Anteil schon bei kleinem $\epsilon$ nahe 1.

Merkbild: Die hochdimensionale Orange

Schält man eine hochdimensionale Orange, bleibt fast nichts übrig, das meiste ist Schale. Gleichverteilte hochdimensionale Daten liegen fast alle nahe am Rand des Datenbereichs, und „Nachbarschaften“ im Inneren sind nahezu leer.

Ergänzung, nicht auf den Folien: Eine verwandte Folge ist, dass in hohen Dimensionen die Abstände zwischen zufälligen Punkten alle ungefähr gleich groß werden. Deshalb funktionieren abstandsbasierte Verfahren wie $k$-Nearest-Neighbours in hohen Dimensionen oft schlecht.

Lineare Trennbarkeit in höheren Dimensionen

📄 08_svm.pdf, Folie 7

Der Fluch hat eine Kehrseite, die auf den ersten Blick wie ein Segen aussieht:

• Bei $d$-dimensionalen Daten sind weniger als $d+2$ Datenpunkte (also höchstens $d+1$) fast immer linear trennbar, egal wie die Labels verteilt sind. „Fast immer“ heißt: solange die Punkte in allgemeiner Lage sind, also z.B. nicht drei Punkte auf einer Geraden liegen.
• In 2D bedeutet das: 3 Punkte kann man (in allgemeiner Lage) mit jeder Beschriftung durch eine Gerade trennen. Bei 4 Punkten klappt das nicht mehr immer: Das XOR-Muster (gegenüberliegende Ecken eines Quadrats gleich beschriftet) ist nicht linear trennbar.

Das Problem: Selbst wenn die Trainingsdaten linear trennbar sind, folgt daraus nicht, dass der Klassifikator auf unabhängigen Testdaten gut funktioniert. Hat man nur wenige Punkte im Verhältnis zur Dimension, ist die Trennbarkeit kein Hinweis auf echte Struktur, sondern schlicht eine Folge der vielen Freiheitsgrade.

Faustregel der Folie: Man sollte ein Vielfaches von $d$ an Trainingsdaten haben, damit der Klassifikator überbestimmt ist, und sicherstellen, dass Trainings- und Testdaten ähnlich genug sind (aus derselben Verteilung stammen).

Leitfrage

Wie kann man in einem hoch- oder sogar unendlichdimensionalen Merkmalsraum klassifizieren, ohne zu viele Daten zu benötigen?

Klassifikation mit beliebigen Trennebenen

📄 08_svm.pdf, Folie 8

Die Abbildung (nach Schölkopf) zeigt drei Punkte in der Ebene und alle $2^3 = 8$ möglichen Beschriftungen. Jede davon lässt sich durch eine Gerade realisieren. Man sagt: Die Geraden können drei Punkte zerschmettern (shatter).

Ergänzung, nicht auf den Folien: Die maximale Anzahl von Punkten, die eine Klasse von Klassifikatoren zerschmettern kann, heißt VC-Dimension. Für Hyperebenen im $\mathbb R^d$ ist sie $d+1$. Das ist genau die „weniger als $d+2$“-Aussage von oben.

Konsequenz:

• In hoch- und unendlichdimensionalen Räumen kann im Allgemeinen jede beliebige Punktkonfiguration getrennt werden.
• Dass genau die gleiche Aufteilung auch bei unabhängigen Testdaten gilt, ist sehr unwahrscheinlich. Das ist Overfitting (Überanpassung).

Klassifikation in hochdimensionalen Räumen: Zwischenfazit

📄 08_svm.pdf, Folie 9

Fasst man die bisherigen Beobachtungen zusammen:

1. Die Trennflächen zwischen zwei Punktwolken können mit zunehmender Dimension immer komplexer werden.
2. Um beliebige Trennflächen zu lernen, bräuchte man eine exponentiell mit der Dimension wachsende Datenmenge. Im Allgemeinen ist Klassifikation in hoch- und unendlichdimensionalen Räumen damit unmöglich.
3. Um dennoch lernen zu können, muss die Verteilung gutartig sein. Ein funktionierender Lernalgorithmus muss solche gutartigen Strukturen erkennen und ausnutzen.
4. Reale Probleme besitzen in fast allen Fällen eine gutartige Struktur.
5. Das Perzeptron beendet das Training, sobald die Trainingsdaten getrennt sind. Es hat keinen Mechanismus, der gutartige Strukturen berücksichtigt: Es nimmt irgendeine trennende Ebene, je nach Startwert und Reihenfolge der Beispiele.

Gutartige Klassifikationsprobleme

📄 08_svm.pdf, Folie 10

Was „gutartig“ genau heißt, beantwortet die statistische Lerntheorie (statistical learning theory). Sie schätzt den Generalisierungsfehler einer Lernmaschine aus bestimmten Eigenschaften der Daten ab.

Für lineare Klassifikationsprobleme gilt:

• Linear trennbare Probleme mit hinreichend großer Trennbreite (margin) sind gutartig.
• Man kann beweisen, dass der Generalisierungsfehler mit hoher Wahrscheinlichkeit umso kleiner wird, je größer die Trennbreite ist.
• Erstaunlicherweise gilt dieses Resultat unabhängig von der Dimensionalität des Inputraums.

Die zentrale Idee des Kapitels

Sucht man statt einer beliebigen Trennebene eine mit möglichst großer Trennbreite, dann kann man in Räumen beliebiger Dimension klassifizieren. Genau das tut die Supportvektormaschine, siehe 6.2.

Warum ist das plausibel? Ergänzung, nicht auf den Folien: Eine Trennebene mit großem Abstand zu allen Punkten ist robust: Verschiebt man die Trainingspunkte ein wenig (Rauschen) oder kommen neue Testpunkte aus derselben Verteilung hinzu, landen diese mit hoher Wahrscheinlichkeit trotzdem auf der richtigen Seite. Außerdem schränkt ein großer Margin die Menge der möglichen Trennebenen stark ein: Bei Punkten in einer Kugel vom Radius $R$ können Hyperebenen mit Margin $\gamma$ höchstens etwa $R^2/\gamma^2$ Punkte zerschmettern (Vapnik). Diese „effektive Kapazität“ hängt nicht von $d$ ab, sondern nur vom Verhältnis $R/\gamma$.

Typische Fallstricke

• „Mehr Merkmale sind immer besser.“ Nein. Mehr Dimensionen machen die Trainingsdaten zwar leichter trennbar, aber ohne ein Kriterium wie die Trennbreite steigt die Gefahr von Overfitting.
• Lineare Trennbarkeit der Trainingsdaten ist kein Qualitätsmerkmal, wenn die Anzahl der Punkte in der Größenordnung von $d$ liegt.
• Die Unabhängigkeit von der Dimension bezieht sich auf die Generalisierungsschranke bei großem Margin, nicht darauf, dass die Dimension generell egal wäre. Ist der Margin klein, hilft auch die SVM nicht.