Entscheidungsgrenzen als Hyperebenen
Ein binärer Klassifikator ordnet jede Eingabe einer von zwei Klassen zu. Die Entscheidungsgrenze des Klassifikators teilt den Eingaberaum in zwei Regionen: eine pro Klasse. Die Geometrie dieser Grenze bestimmt, welche Muster der Klassifikator lernen kann.
Eine Hyperebene in ℝ^n: die Menge aller Punkte x, die w·x + b = 0 erfüllen, wobei w ein Gewichtsvektor in ℝ^n und b ein Skalar-Bias ist. Eine Hyperebene hat n−1 Dimensionen.
In 2D: eine Hyperebene ist eine Linie. In 3D: eine ebene Fläche. In n-D: ein flacher (n−1)-dimensionaler Unterraum.
Ein Perceptron klassifiziert durch Berechnung von w·x + b und gibt Klasse 1 zurück, wenn positiv, Klasse 0 wenn negativ. Seine Entscheidungsgrenze ist eine Hyperebene.
Lineare Trennbarkeit
Ein Datensatz ist linear trennbar in ℝ^n, wenn eine Hyperebene existiert, die alle Punkte von Klasse 0 auf einer Seite und alle Punkte von Klasse 1 auf der anderen Seite platziert. Dies ist eine rein geometrische Eigenschaft des Datensatzes.
Testen linearer Trennbarkeit
Der AND-Gate-Datensatz in 2D: Klasse-0-Punkte bei (0,0), (1,0), (0,1); Klasse-1-Punkt bei (1,1). Dieser Datensatz ist linear trennbar.
Der XOR-Datensatz in 2D: Klasse-0-Punkte bei (0,0) und (1,1); Klasse-1-Punkte bei (1,0) und (0,1). Diese beiden Klassen liegen auf sich gegenüberliegenden Diagonalen.
Anheben in höhere Dimensionen
XOR ist in 2D nicht linear trennbar. Die Lösung: die Daten in einen höherdimensionalen Raum abbilden, in dem sie linear trennbar werden. Dies ist die Kernidee des Kernel-Tricks.
Merkmalabbildung: eine Funktion φ: ℝ^n → ℝ^m (m > n), die jeden Eingabepunkt in eine höherdimensionale Darstellung transformiert.
Für XOR ist eine nützliche Merkmalabbildung: φ(x₁, x₂) = (x₁, x₂, x₁x₂)
Dies fügt eine dritte Dimension z = x₁ × x₂ hinzu. Die XOR-Punkte transformieren sich zu:
- (0,0) → (0, 0, 0), Klasse 0
- (1,0) → (1, 0, 0), Klasse 1
- (0,1) → (0, 1, 0), Klasse 1
- (1,1) → (1, 1, 1), Klasse 0
In 3D: die Klasse-0-Punkte befinden sich bei (0,0,0) und (1,1,1); die Klasse-1-Punkte befinden sich bei (1,0,0) und (0,1,0). Finde jetzt eine trennende Ebene.
Trennebene in 3D
Nach der Merkmalabbildung φ(x₁, x₂) = (x₁, x₂, x₁x₂) leben die XOR-Daten in 3D. Eine Hyperebene in 3D hat die Gleichung w₁x₁ + w₂x₂ + w₃z + b = 0.
Cover's Theorem: Warum höhere Dimensionen helfen
Cover's Theorem (1965): ein komplexes Klassifikationsproblem, das in einem hochdimensionalen Raum dargestellt wird, ist wahrscheinlicher linear trennbar als in einem niedrigdimensionalen Raum, vorausgesetzt, der Raum ist nicht dicht bevölkert.
Informelle Aussage: wenn du n Datenpunkte in einen Raum der Dimension d >> n abbildest, nähert sich die Wahrscheinlichkeit, dass eine zufällige Kennzeichnung linear trennbar ist, 1 an.
Formale Version: für n Punkte in allgemeiner Position in ℝ^d ist die Anzahl der linear trennbaren Dichotomien (Klassenzuweisungen) genau 2 × Σ_{k=0}^{d} C(n−1, k) für d < n, und gleich 2^n (alle Dichotomien) für d ≥ n − 1.
Praktische Implikation: die Merkmalabbildung φ, die XOR zu 3D hebt, ist ein Spezialfall dieses allgemeinen Prinzips. Das Anheben in höhere Dimensionen erhöht die Chance auf Trennbarkeit. Die Kosten: mehr Parameter zum Anpassen, höheres Risiko des Overfitting.
Der Bias-Varianz-Tradeoff als Geometrie
Niedrigdimensionale Entscheidungsgrenze (wenige Parameter): hoher Bias (kann komplexe Muster nicht erfassen), niedrige Varianz (stabil über Stichproben). Hochdimensionale Grenze (viele Parameter): niedriger Bias, hohe Varianz (kann an Rauschen in Trainingsdaten überanpassen).
VC-Dimension: Wie ausdrucksstark ist ein Klassifikator?
Die Vapnik-Chervonenkis (VC) -Dimension einer Hypothesenklasse H misst, wie komplex die Klasse ist: die größte Anzahl von Punkten, die H zerschmettern kann (korrekt klassifizieren in allen 2^n möglichen Kennzeichnungen).
Perceptron in ℝ^d: VC-Dimension = d + 1. Eine d-dimensionale Hyperebene kann d + 1 Punkte (in allgemeiner Position) zerschmettern, aber nicht d + 2.
Die VC-Dimension bestimmt die Stichprobenkomplexität: um eine Hypothese mit Verallgemeinerungsfehler ε mit Wahrscheinlichkeit 1 − δ zu lernen, benötigst du ungefähr n ≥ (d × log(1/ε) + log(1/δ)) / ε Stichproben, wobei d die VC-Dimension ist.
Entscheidungsgrenzen & die Grenzen der Maschinenleistung
Die Geometrie von Entscheidungsgrenzen verbindet sich direkt mit Hammings Grenzen des maschinellen Denkens.
Ein Single-Layer-Perceptron (Hyperebenen-Klassifikator) kann XOR nicht lösen. Dies war Minskys & Paperts Kritik an frühen Perceptrons im Jahr 1969. Das geometrische Argument: XOR ist nicht linear trennbar. Die Maschine kann es nicht lösen, nicht wegen mangelnder Rechenkraft, sondern wegen einer fundamentalen geometrischen Inkompatibilität zwischen der Hypothesenklasse und dem Problem.
Die Lösung: mehrschichtige Netzwerke können nichtlineare Grenzen darstellen. Die verborgenen Schichten implementieren die Merkmalabbildung φ — das Anheben der Daten in höhere Dimensionen, wo lineare Trennung möglich wird. Jedes verborgene Neuron berechnet eine Hyperebene; die Kombination mehrerer Hyperebenen approximiert Kurven.
Diese Geschichte passt zu Hammings Beobachtung: jede Limitation des maschinellen Denkens hat eine geometrische Struktur darunter. Die Aufgabe ist nicht, über 'können Maschinen denken' zu argumentieren, sondern die geometrischen Einschränkungen zu identifizieren und Wege zu finden, um sie zu umgehen.