11 · Prawa i prawdy · 3 min czytania · aktualizacja
Kiedy perceptron gwarantuje znalezienie rozwiązania i ile popełni błędów?
W skrócie
Jeśli dane są liniowo separowalne z marginesem γ, perceptron znajdzie granicę bezbłędną po co najwyżej (R/γ)² poprawkach, niezależnie od liczby przykładów.
Co to jest
Jeżeli dane da się rozdzielić hiperpłaszczyzną z marginesem γ, a wszystkie przykłady leżą w kuli o promieniu R, to algorytm perceptronu popełni co najwyżej (R/γ)² błędów, po czym będzie klasyfikował zbiór treningowy bezbłędnie. Algorytm zaproponował Frank Rosenblatt w 1958 roku, a twierdzenie z tym ograniczeniem udowodnił Albert Novikoff w 1962 roku.
Perceptron działa banalnie: przegląda przykłady; gdy trafi na źle sklasyfikowany, dodaje go (z odpowiednim znakiem) do wektora wag. Twierdzenie mówi, że ta prosta reguła zawsze się kończy, o ile rozwiązanie istnieje — i że liczba poprawek nie zależy od liczby przykładów ani od wymiaru, tylko od geometrii: jak szeroki jest „korytarz” między klasami w stosunku do rozmiaru danych.
Druga połowa historii jest równie ważna: jeśli dane nie są liniowo separowalne, perceptron nigdy się nie zatrzyma, a wagi będą krążyć bez końca.
Mechanizm — dlaczego tak działa
Dowód Novikoffa śledzi dwie wielkości po każdej poprawce. Niech w będzie jednostkowym wektorem idealnego separatora. Iloczyn skalarny w·w rośnie przy każdej poprawce o co najmniej γ — bo dodajemy przykład, który leży po właściwej stronie w z zapasem γ. Po k poprawkach w·w ≥ kγ.
Jednocześnie długość wektora wag rośnie wolno: ‖w‖² zwiększa się o co najwyżej R² na poprawkę, bo dodajemy przykład źle sklasyfikowany (iloczyn y·w·x ≤ 0 nie dokłada nic dodatniego). Po k poprawkach ‖w‖ ≤ √k·R.
Ale w·w nie może przekroczyć ‖w‖, bo w ma długość 1. Stąd kγ ≤ √k·R, czyli k ≤ (R/γ)². Wagi rosną w dobrym kierunku liniowo, a ich długość tylko jak pierwiastek — więc po skończonej liczbie kroków muszą się „wyrównać” z rozwiązaniem.
Ograniczenia: twierdzenie gwarantuje jakąś bezbłędną granicę, nie najlepszą — perceptron zatrzymuje się na pierwszej znalezionej, często tuż przy punktach jednej z klas. Szukanie granicy o największym marginesie to zadanie SVM. A brak zbieżności przy danych nieseparowalnych (np. XOR) był jednym z argumentów książki Minsky’ego i Paperta z 1969 roku, która ostudziła zainteresowanie sieciami neuronowymi na lata.
Na przykładzie
Iris, setosa kontra versicolor (100 kwiatów, 4 cechy plus wyraz wolny). Te klasy są liniowo separowalne. Perceptron osiągnął zero błędów po 2 przejściach przez dane i zaledwie 7 poprawkach wag. Dla tego zbioru R = 9,19, a znaleziony przez nas separator ma margines γ = 0,527, co daje gwarancję co najwyżej (9,19/0,527)² ≈ 304 poprawek. Rzeczywistość była ponad 40 razy lepsza od gwarancji — typowe dla ograniczeń najgorszego przypadku.
Versicolor kontra virginica: te gatunki częściowo na siebie zachodzą. Po 1000 przejściach przez dane perceptron wciąż nie osiągnął zera błędów i wykonał łącznie 6449 poprawek — i wykonywałby je dalej bez końca.
Dane: Iris (irysy Fishera)
W praktyce
- W scikit-learn:
Perceptron(max_iter=1000, tol=1e-3); przy danych nieseparowalnych kończy się limitem iteracji, nie zbieżnością. - Skaluj cechy (
StandardScaler): R zależy od skali danych, więc wpływa na liczbę poprawek. - Uśredniony perceptron (averaged perceptron) lub regresja logistyczna dają stabilne wyniki także dla danych nieseparowalnych.
- Duży margines = szybka zbieżność i zwykle lepsza generalizacja; stąd pomysł SVM (
LinearSVC). - Zero błędów treningowych perceptronu nie mówi nic o błędzie testowym — sprawdź walidację.
Najczęstsze pytania
- Czy twierdzenie zależy od kolejności przykładów?
- Ograniczenie (R/γ)² obowiązuje dla każdej kolejności. Od kolejności zależy natomiast, którą z wielu bezbłędnych granic perceptron znajdzie.
- Co się dzieje, gdy dane są prawie separowalne?
- Perceptron nie zbiega, ale Freund i Schapire (1999) pokazali, że liczba błędów jest wtedy ograniczona przez margines i sumę „naruszeń” marginesu. Uśredniony perceptron dobrze się wtedy sprawdza.
- Czy to twierdzenie dotyczy współczesnych sieci?
- Bezpośrednio nie — sieci uczy się spadkiem gradientu na funkcji straty, a nie regułą perceptronu. Idea marginesu i geometrii danych pozostała jednak centralna w teorii generalizacji.
Źródła
- Rosenblatt F. (1958). The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review, 65(6), 386–408.
- Novikoff A. B. J. (1962). On Convergence Proofs on Perceptrons. Symposium on the Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, 12, 615–622.
- Minsky M., Papert S. (1969). Perceptrons. MIT Press.
- Freund Y., Schapire R. E. (1999). Large Margin Classification Using the Perceptron Algorithm. Machine Learning, 37(3), 277–296.