06 · Sieci · 4 min czytania · aktualizacja
Dlaczego pojedynczy perceptron nie potrafi nauczyć się funkcji XOR?
W skrócie
XOR to najprostsze zadanie, którego nie rozwiąże żaden model liniowy. Pokazuje, po co sieciom warstwa ukryta i nieliniowa funkcja aktywacji.
Co to jest
Problem XOR to klasyczny przykład zadania klasyfikacji, którego nie da się rozwiązać pojedynczym perceptronem ani żadnym innym modelem liniowym. Funkcja XOR (alternatywa wykluczająca) zwraca 1, gdy dokładnie jedno z dwóch wejść jest równe 1: XOR(0, 0) = 0, XOR(0, 1) = 1, XOR(1, 0) = 1, XOR(1, 1) = 0. Rozwiązuje go dopiero sieć z co najmniej jedną warstwą ukrytą i nieliniową aktywacją.
Narysuj cztery punkty w rogach kwadratu. Jedynki leżą na jednej przekątnej, zera na drugiej. Spróbuj poprowadzić jedną prostą tak, by po jednej stronie były same jedynki, a po drugiej same zera. Nie da się: każda prosta, która oddzieli jedną jedynkę od zer, zostawi drugą jedynkę po złej stronie.
XOR ma też znaczenie historyczne. W 1969 roku Marvin Minsky i Seymour Papert w książce „Perceptrons” formalnie pokazali ograniczenia jednowarstwowych perceptronów, a XOR stał się ich symbolem. Wiedziano, że sieci wielowarstwowe nie mają tego ograniczenia, ale brakowało skutecznej metody ich trenowania. Upowszechnienie propagacji wstecznej w 1986 roku rozwiązało ten problem.
Mechanizm — dlaczego tak działa
Model liniowy podejmuje decyzję według znaku w₁x₁ + w₂x₂ + b, czyli dzieli płaszczyznę jedną prostą. Dowód niemożności jest krótki. Żeby (0, 1) i (1, 0) dały wynik dodatni, potrzeba w₂ + b > 0 oraz w₁ + b > 0. Żeby (0, 0) dało wynik ujemny, potrzeba b < 0. Dodając dwie pierwsze nierówności, dostajemy w₁ + w₂ + 2b > 0, a więc w₁ + w₂ + b > −b > 0, czyli punkt (1, 1) też wypadłby dodatnio. Sprzeczność.
Warstwa ukryta zmienia reprezentację danych. Weźmy dwa neurony ReLU: h₁ = max(0, x₁ + x₂) oraz h₂ = max(0, x₁ + x₂ − 1), i wyjście y = h₁ − 2·h₂. Dla (0, 0): h = (0, 0), y = 0. Dla (0, 1) i (1, 0): h = (1, 0), y = 1. Dla (1, 1): h = (2, 1), y = 2 − 2 = 0. Sieć oblicza XOR dokładnie.
Co się stało geometrycznie? W nowej przestrzeni (h₁, h₂) dwa punkty klasy 1 zlały się w jeden, (1, 0), a punkty klasy 0 trafiły do (0, 0) i (2, 1). Teraz klasy da się rozdzielić prostą. To ogólna zasada sieci neuronowych: warstwy ukryte przekształcają dane tak, aby ostatnia, liniowa warstwa miała łatwe zadanie.
Nieliniowość jest konieczna. Gdyby zamiast ReLU użyć funkcji tożsamościowej, h₁ i h₂ byłyby liniowe względem wejść, cała sieć sprowadziłaby się do jednego modelu liniowego i XOR znów byłby nierozwiązywalny.
Istnienie rozwiązania nie oznacza, że trening je znajdzie. Sieć z dwoma neuronami ukrytymi ma niewielki zapas: jeśli jeden neuron „zgaśnie” albo oba nauczą się tego samego, gradient utknie. Dlatego w praktyce XOR, mimo że wymaga tylko dwóch neuronów, trenuje się pewniej w nieco szerszej sieci.
Na przykładzie
Regresja logistyczna dopasowana do czterech punktów XOR (scikit-learn, domyślna regularizacja) ustawia obie wagi na 0 i przypisuje każdemu punktowi prawdopodobieństwo 0,5. Trafność wynosi 50%, czyli tyle, co rzut monetą. Przeszukanie siatki wag dowolnego klasyfikatora liniowego daje co najwyżej 75%: trzy punkty dobrze, czwarty zawsze źle.
Następnie wytrenowano MLPClassifier z aktywacją tanh i solverem L-BFGS ze 100 różnych losowych inicjalizacji (random_state od 0 do 99). Z 2 neuronami ukrytymi wszystkie cztery punkty poprawnie sklasyfikowało 50 sieci na 100. Z 3 neuronami: 86 na 100, z 4: 99 na 100, z 8: wszystkie 100. Minimalna architektura wystarcza w teorii, ale w praktyce co druga próba kończy się w złym minimum lokalnym. Nadmiarowe neurony dają optymalizacji więcej dróg do rozwiązania.
W praktyce
- XOR to standardowy test poprawności własnej implementacji sieci: jeśli kod nie uczy się XOR z 4–8 neuronami ukrytymi, ma błąd w propagacji wstecznej lub inicjalizacji.
- scikit-learn:
MLPClassifier(hidden_layer_sizes=(4,), activation='tanh', solver='lbfgs')uczy się XOR w ułamku sekundy;solver='adam'przy czterech punktach potrzebuje dużo więcej iteracji. - Wagi nie mogą startować od zera: wszystkie neurony ukryte liczyłyby to samo i dostawały identyczny gradient, więc sieć nigdy nie wyszłaby z symetrii.
- W danych rzeczywistych „efekt XOR” to interakcja cech: każda cecha z osobna nic nie mówi, liczy się ich kombinacja. Model liniowy jej nie zobaczy, chyba że dodasz cechę x₁·x₂ ręcznie.
- Drzewo decyzyjne rozwiązuje XOR dwoma podziałami, ale zachłanny pierwszy podział ma zerowy zysk informacyjny, więc z zatrzymywaniem wzrostu drzewo może się nawet nie zacząć budować.
Najczęstsze pytania
- Czy XOR naprawdę zatrzymał badania nad sieciami neuronowymi?
- Książka Minsky’ego i Paperta jest często wskazywana jako jedna z przyczyn spadku zainteresowania sieciami w latach 70. Historycy podkreślają jednak, że złożyło się na to więcej czynników, m.in. brak metody trenowania sieci wielowarstwowych i słabe komputery.
- Czy dodanie cechy x₁·x₂ rozwiązuje XOR bez sieci?
- Tak. W przestrzeni (x₁, x₂, x₁·x₂) klasy są liniowo rozdzielne, np. x₁ + x₂ − 2·x₁x₂ daje dokładnie XOR. Sieć robi to samo automatycznie: sama wymyśla potrzebne cechy w warstwie ukrytej.
- Ile neuronów ukrytych minimalnie potrzeba?
- Wystarczą dwa neurony ukryte i jeden wyjściowy. Przy połączeniach bezpośrednich z wejścia do wyjścia da się nawet z jednym neuronem ukrytym. Minimalna sieć trenuje się jednak zawodnie, co pokazuje przykład powyżej.
Źródła
- Minsky M., Papert S., „Perceptrons: An Introduction to Computational Geometry”, MIT Press, 1969.
- Rumelhart D. E., Hinton G. E., Williams R. J., „Learning representations by back-propagating errors”, Nature 323, 1986, s. 533–536.
- Goodfellow I., Bengio Y., Courville A., „Deep Learning”, MIT Press, 2016, podrozdz. 6.1 „Example: Learning XOR”.
- Bishop C. M., „Pattern Recognition and Machine Learning”, Springer, 2006, rozdz. 5 „Neural Networks”.