Granice Decyzyjne jako Hiperplane
Klasyfikator binarny przypisuje każdemu wejściu jedną z dwóch klas. Granica decyzyjna klasyfikatora dzieli przestrzeń wejściową na dwa obszary: jeden na klasę. Geometria tej granicy determinuje, jakie wzorce klasyfikator może nauczyć się.
Hiperplan w ℝ^n: zbiór wszystkich punktów x spełniających względem w: x + b = 0, gdzie w to wektor wag w ℝ^n i b to skalarna wartość opóźnienia. Hiperplan ma n−1 wymiarów.
W 2D: hiperplan to linia. W 3D: płaska powierzchnia. W n-D: płaska (n−1)-wymiarowa podprzestrzeń.
Perceptron klasyfikuje obliczając w·x + b i zwracając klasę 1 jeśli dodatnia, klasę 0 jeśli ujemna. Jego granica decyzyjna to hiperplan.
Liniowa Rozstrzygalność
Zbiór danych jest liniowo rozstrzygalny w ℝ^n, jeśli istnieje hiperplan, który umieszcza wszystkie punkty klasy-0 po jednej stronie i wszystkie punkty klasy-1 po drugiej. To wyłącznie geometryczna własność zbioru danych.
Testowanie Liniowej Rozstrzygalności
Zestaw danych bramki AND w 2D: punkty klasy-0 znajdują się na (0,0), (1,0), (0,1); punkt klasy-1 na (1,1). Ten zestaw danych jest liniowo rozstrzygalny.
Zestaw danych XOR w 2D: punkty klasy-0 znajdują się na (0,0) i (1,1); punkty klasy-1 na (1,0) i (0,1). Te dwa klasy leżą na przeciwległych przekątnych.
Podnoszenie do wyższych wymiarów
XOR nie jest liniowo rozdzielny w 2D. Rozwiązanie: mapuj dane do przestrzeni o wyższej liczbie wymiarów, gdzie staje się liniowo rozdzielne. To jest podstawowa idea triku kernel.
Funkcja przekształceń: funkcja φ: ℝ^n → ℝ^m (m > n), która przekształca każdy punkt wejściowy w reprezentację o wyższej liczbie wymiarów.
Dla XOR, korzystna funkcja przekształceń: φ(x₁, x₂) = (x₁, x₂, x₁x₂)
To dodaje trzeci wymiar z = x₁ × x₂. Punkty XOR przekształcają się:
- (0,0) → (0, 0, 0), klasa 0
- (1,0) → (1, 0, 0), klasa 1
- (0,1) → (0, 1, 0), klasa 1
- (1,1) → (1, 1, 1), klasa 0
W 3D: punkty klasy 0 znajdują się na (0,0,0) i (1,1,1); punkty klasy 1 na (1,0,0) i (0,1,0). Teraz znajdź płaszczyznę rozdzielającą.
Płaszczyzna rozdzielająca w 3D
Po funkcji przekształceń φ(x₁, x₂) = (x₁, x₂, x₁x₂), dane XOR istnieją w 3D. Hiperpłaszczyzna w 3D ma równanie w₁x₁ + w₂x₂ + w₃z + b = 0.
Teorema Covera: Dlaczego Wysokie Wymiary Pomagają
Teorema Covera (1965): skomplikowany problem klasyfikacji przedstawiony w przestrzeni o wysokim wymiarowości jest bardziej prawdopodobne, że będzie liniowo rozdzielony niż w przestrzeni o niskiej wymiarowości, pod warunkiem, że przestrzeń nie jest gęsto zaludniona.
Słowa kluczowe: jeśli mapujesz n punktów do przestrzeni o wymiarze d >> n, prawdopodobieństwo, że losowy oznaczenie jest liniowo rozdzielone, zbliża się do 1.
Wersja formalna: dla n punktów w ogólnie położonych w ℝ^d, liczba liniowo rozdzielonych dichotomii (klasyfikacji) wynosi dokładnie 2 × Σ_{k=0}^{d} C(n−1, k) dla d < n, a równa się 2^n (wszystkie dichotomie) dla d ≥ n − 1.
Skuteczne implikacje: funkcja mapująca φ, która podnosi XOR do 3D, jest specjalnym przypadkiem tej ogólnej zasady. Podnoszenie do wyższych wymiarów zwiększa szanse na rozdzielność. Koszt: więcej parametrów do dopasowania, większe ryzyko przeferowania.
Związek Bias-Variance jako Geometria
Niskowymiarowa granica decyzyjna (mało parametrów): wysoka bias (nie może odzwierciedlić skomplikowanych wzorców), niska variance (stabilna w odniesieniu do próbek). Wysokowymiarowa granica (wiele parametrów): niska bias, wysoka variance (może przeferować na hałas w danych treningowych).
Wymiar VC: Jak Wyrazisty Jest Klasyfikator?
Wymiar Vapnik-Chervonenkis (VC) klasy hipotez H określa, jak skomplikowana jest klasa: największa liczba punktów, które H może zniszczyć (poprawnie sklasyfikować w każdym z 2^n możliwych oznaczeń).
Perceptron w ℝ^d: wymiar VC = d + 1. d-wymiarowy hiperpłaszczyzna może zniszczyć d + 1 punktów (w ogólnym położeniu), ale nie d + 2.
Wymiar VC określa złożoność próbną: aby nauczyć się hipotezy z błędem generalizacji ε z prawdopodobieństwem 1 - δ, potrzebujesz około n ≥ (d × log(1/ε) + log(1/δ)) / ε próbek, gdzie d to wymiar VC.
Granice decyzyjne & ograniczenia zdolności maszyn
Geometria granic decyzyjnych łączy się bezpośrednio z ograniczeniami rozumowania maszyn Hamminga.
Jednowarstwowy perceptron (klasyfikator hiperplanu) nie może rozwiązać XOR. To krytyka Minsky'ego i Paperta wobec wczesnych perceptronów w 1969 roku. Argument geometryczny: XOR nie jest liniowo rozdzielny. Maszyna nie może go rozwiązać, nie dlatego że brakuje jej mocy obliczeniowej, ale dlatego, że istnieje fundamentalne niespójność geometryczna między klasą hipotez a problemem.
Rozwiązanie: wielowarstwowe sieci mogą reprezentować nieliniowe granice. Ukryte warstwy implementują mapę cech φ - podnosząc dane do wyższych wymiarów, gdzie możliwe staje się liniowe rozdzielenie. Każdy ukryty neuron oblicza jeden hiperplan; łączne wykorzystanie wielu hiperplanów przybliża krzywe.
Historia ta odzwierciedla obserwację Hamminga: pod każdym problemem istnieje struktura geometryczna ograniczająca rozumowanie maszynowe. Zadaniem nie jest dyskusja na temat tego, czy maszyny 'mogą myśleć', ale o identyfikacji ograniczeń geometrycznych i znalezieniu sposobów, aby je obejść.