Entscheidungsgrenzen als Hyperplane
Ein binärer Klassifikator zuweist jedem Eingabe einen der beiden Klassen. 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 Hyperplane in ℝ^n: die Menge aller Punkte x, die die Bedingung w·x + b = 0 erfüllen, wobei w ein Gewichtsvektor in ℝ^n und b ein skalares Bias ist. Eine Hyperplane hat n−1 Dimensionen.
In 2D: eine Hyperplane ist eine Linie. In 3D: ein flacher Plan. In n-D: ein flacher (n−1)-dimensionaler Unterraum.
Ein Perzeption klassifiziert, indem es w·x + b berechnet und die Klasse 1 zurückgibt, wenn es positiv ist, Klasse 0, wenn es negativ ist. Seine Entscheidungsgrenze ist eine Hyperplane.
Lineare Trennbarkeit
Ein Datensatz ist linear trennbar in ℝ^n, wenn es eine Hyperplane gibt, die alle class-0-Punkte auf einer Seite und alle class-1-Punkte auf der anderen Seite platziert. Dies ist eine rein geometrische Eigenschaft des Datensatzes.
Prüfung der Linearen Trennbarkeit
Der AND-Gatter-Datensatz in 2D: class-0-Punkte an (0,0), (1,0), (0,1); class-1-Punkt an (1,1). Dieser Datensatz ist linear trennbar.
Der XOR-Datensatz in 2D: class-0-Punkte an (0,0) und (1,1); class-1-Punkte an (1,0) und (0,1). Diese beiden Klassen liegen auf gegenüberliegenden Diagonalen.
Aufwärtsverschiebung in höherdimensionalen Räumen
XOR ist nicht linear separable in 2D. Die Lösung: Projektion der Daten in einen höherdimensionalen Raum, in dem sie linear separable wird. Dies ist das Kernelement des Kerneltricks.
Feature map: eine Funktion φ: ℝ^n → ℝ^m (m > n), die jeden Eingangspunkt in eine höherdimensionale Darstellung transformiert.
Für XOR, eine nützliche Feature Map: φ(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 liegen bei (0,0,0) und (1,1,1); die Klasse-1-Punkte liegen bei (1,0,0) und (0,1,0). Jetzt finden Sie eine trennende Ebene.
Trennende Ebene in 3D
Nach der Feature Map φ(x₁, x₂) = (x₁, x₂, x₁x₂) leben die XOR-Daten in 3D. Eine Hyperfläche in 3D hat die Gleichung w₁x₁ + w₂x₂ + w₃z + b = 0.
Cover's Theorem: Warum High-Dimensions helfen
Cover's Theorem (1965): Ein komplexes Klassifikationsproblem, das in einem hochdimensionalen Raum dargestellt wird, ist wahrscheinlicher linear separierbar als in einem niedrigdimensionalen Raum, vorausgesetzt, der Raum ist nicht dicht besiedelt.
Einfache Aussage: Wenn Sie n Datenpunkte in einen Raum von d Dimensionen abbilden, der viel größer als n ist, nähert sich die Wahrscheinlichkeit, dass eine zufällige Zuweisung linear separierbar ist, 1.
Formale Version: Für n Punkte in allgemeiner Position in ℝ^d ist die Anzahl linear separabler Dichotomien (Klassenzuweisungen) genau 2 × Σ_{k=0}^{d} C(n−1, k) für d < n und entspricht 2^n (alle Dichotomien) für d ≥ n − 1.
Praktische Implikation: Die Feature-Map φ, die XOR in 3D hebt, ist ein Spezialfall dieses allgemeinen Prinzips. Die Aufhebung in höheren Dimensionen erhöht die Chance der Trennbarkeit. Der Preis: mehr Parameter zum Anpassen, höheres Risiko der Überanpassung.
Der Bias-Variance-Handel als Geometrie
Niedrigdimensionale Entscheidungsgrenze (wenige Parameter): hoher Bias (kann komplexe Muster nicht erfassen), niedrige Varianz (stabil über Samples). Hochdimensionale Grenze (viele Parameter): niedriger Bias, hohe Varianz (kann auf Rauschen im Trainingsdaten überfitzen).
VC-Dimension: Wie ausdrucksstark ist ein Klassifikator?
Die Vapnik-Chervonenkis (VC)-Dimension eines Hypothesenklasses H misst, wie komplex der Klass ist: die größte Anzahl von Punkten, die H trennen kann (korrekt klassifizieren in allen 2^n möglichen Beschriftungen).
Perzepton in ℝ^d: VC-Dimension = d + 1. Ein d-dimensionaler Hyperplan kann d + 1 Punkte (in allgemeiner Position) trennen (im Allgemeinen), aber nicht d + 2.
Die VC-Dimension bestimmt die Sample-Komplexität: um ein Hypothesemodell mit Generalisierungsfehler ε mit einer Wahrscheinlichkeit von 1 - δ zu lernen, benötigt man ungefähr n ≥ (d × log(1/ε) + log(1/δ)) / ε Datensätze, wobei d die VC-Dimension ist.
Entscheidungsgrenzen & Maschinenleistungsgrenzen
Die Geometrie von Entscheidungsgrenzen verbindet direkt mit Hamming's maschinenbasierten Denklimits.
Ein Einstufiges Perzeptron (Klassifikator für Ebenen) kann XOR nicht lösen. Dies war die Kritik von Minsky & Papert an frühen Perzeptrons in 1969. Der geometrische Argument: XOR ist nicht linear separabel. Die Maschine kann es nicht lösen, nicht wegen mangelnder Rechenleistung, sondern wegen einer grundlegenden geometrischen Inkompatibilität zwischen der Hypothesenklasse und dem Problem.
Die Lösung: Mehrschichtnetze können nichtlineare Grenzen darstellen. Die versteckten Schichten implementieren die Feature-Map φ - die Daten werden in höhere Dimensionen gehoben, wo eine lineare Trennung möglich wird. Jeder versteckte Neuron berechnet eine Ebenen; die Kombination mehrerer Ebenen approximiert Kurven.
Diese Geschichte spiegelt sich in Hamming's Beobachtung wider: Jede Einschränkung der maschinellen Vernunft hat eine geometrische Struktur unterhalb von ihr. Die Aufgabe ist nicht, darüber zu argumentieren, ob Maschinen 'denken' können, sondern die geometrischen Einschränkungen zu identifizieren und Möglichkeiten zu finden, um sie zu umgehen.