Perceptron od zera: co oblicza neuron

Perceptron bierze pomiary, mnoży każdy przez kontrolowaną przez siebie liczbę, dodaje je do siebie, dodaje jeszcze jedną liczbę i sprawdza znak.

Zapisz pomiary jednej części jako wektor $\mathbf{x} = (x_1, x_2)$ — szerokość i masę. Perceptron przechowuje wektor wag $\mathbf{w} = (w_1, w_2)$ oraz bias $b$. Jego wynik to

a jego odpowiedzią jest znak tego wyniku: zaakceptuj, jeśli $s(\mathbf{x}) \geq 0$, w przeciwnym razie odrzuć.

To cały model. Wszystko, co perceptron kiedykolwiek będzie wiedział o fabryce, mieści się w trzech liczbach.

Warto zatrzymać się przy geometrii, bo to obraz, który będzie działał przez kolejne dwadzieścia dziewięć rozdziałów nawet wtedy, gdy równania przestaną mieścić się w jednej linijce. Zbiór punktów, dla których $s(\mathbf{x}) = 0$ — gdzie perceptron jest dokładnie niezdecydowany — jest prostą na płaszczyźnie. Po jednej stronie wynik jest dodatni i wszystko zostaje zaakceptowane; po drugiej jest ujemny i wszystko zostaje odrzucone. Uczenie, dla perceptronu, oznacza przesuwanie tej prostej.

Z algebry wynikają bezpośrednio dwa fakty o tej prostej i oba będą później ważne:

• $\mathbf{w}$ jest do niej prostopadły. Wektor wag nie leży wzdłuż granicy, tylko wskazuje w poprzek niej, w stronę akceptowaną.
• $b$ przesuwa ją bez obracania. Bez bias prosta musiałaby przechodzić przez początek układu, co w fabryce mierzącej milimetry i gramy byłoby absurdalnym ograniczeniem — oznaczałoby, że część o zerowej szerokości i zerowej masie siedzi dokładnie na granicy.

Perceptron zaczyna, nie wiedząc nic: $\mathbf{w} = (0, 0)$ i $b = 0$. Każdy wynik jest zerowy, więc akceptuje wszystko.

Teraz pokazuj mu po jednym przykładzie. Oznacz zaakceptowane części jako $y = +1$, a odrzucone jako $y = -1$. Dla każdego przykładu zadaj jedno pytanie: czy znak wyszedł poprawnie? Zwięzły zapis tego pytania polega na sprawdzeniu, czy $y \cdot s(\mathbf{x})$ jest dodatnie — jeśli etykieta i wynik mają zgodny znak, ich iloczyn jest dodatni, a jeśli się nie zgadzają, jest ujemny.

Jeśli odpowiedź brzmi tak, niczego nie zmieniaj. Jeśli brzmi nie, popchnij:

To cały algorytm i warto zrozumieć, dlaczego to właściwe popchnięcie, zamiast je zapamiętywać. Załóżmy, że część powinna zostać zaakceptowana ($y = +1$), a wynik wyszedł ujemny. Dodanie $\mathbf{x}$ do $\mathbf{w}$ zmienia wynik dla tej samej części o

czyli o liczbę dodatnią. Wynik dla części, na której perceptron właśnie się pomylił, idzie w górę, czyli w kierunku, w którym miał pójść. Ta reguła nie jest heurystyką, którą ktoś zgadł; to najmniejsza zmiana, która w możliwy do udowodnienia sposób poprawia przypadek stojący przed nią. Oczywiście może zepsuć inny przypadek, dlatego przechodzisz przez dane ponownie.

Zwróć uwagę, czego tu nie ma. Nigdzie nie ma pochodnej. To nie przeoczenie, tylko pierwsza naprawdę ważna idea w kursie.

Rzeczą, którą chciałoby się różniczkować, jest błąd — liczba błędnie sklasyfikowanych części. Ale ta liczba jest schodami: pozostaje płaska na poziomie 4, gdy lekko przesuwasz prostą, a potem spada do 3 dokładnie w chwili, gdy prosta przetnie punkt. Jej pochodna jest zerowa prawie wszędzie i niezdefiniowana na stopniach. Rachunek różniczkowy nie ma się czego chwycić. Reguła perceptronu obchodzi to, w ogóle nie pytając o nachylenie: pyta tylko „dobrze czy źle?” i rusza w kierunku, który potrafi uzasadnić geometrycznie.

To prawdziwe rozwiązanie, ale także ślepa uliczka. W rozdziale 2 będziemy chcieli funkcji straty, która skądś wynika, zamiast być wybraną arbitralnie, w rozdziale 4 modelu, który mówi, jak bardzo jest pewny, a w rozdziale 5 czegoś z więcej niż jedną warstwą — i żadna z tych rzeczy nie jest osiągalna z reguły, która zna tylko „źle”. Odzyskanie użytecznego nachylenia wymusza kolejne dwa rozdziały. Ale perceptron może zrobić coś, czego nie potrafi żaden z jego następców: uczyć się zupełnie bez rachunku różniczkowego.

Czysty Python, bez NumPy. Listy i pętla. NumPy pojawi się w następnym rozdziale, gdy arytmetyka przestanie mieścić się w pętli, którą chciałbyś czytać; wprowadzenie go teraz ukryłoby arytmetykę za biblioteką dokładnie w momencie, w którym chcesz ją zobaczyć.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Cztery wyróżnione linie to algorytm. Cała reszta to obsługa techniczna.

A oto taśma z ośmioma zmierzonymi częściami — czterema, które wysłano, i czterema, które wróciły:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Te osiem części da się rozdzielić prostą — każda zaakceptowana część ma mniej niż 22 mm, a każda odrzucona ma 23 mm lub więcej. Pionowy płot na 22 milimetrach załatwia sprawę. Perceptron powinien więc go znaleźć.

Uruchom go:

None [-142.1, -13.0] 54.0

Dwieście epok, 454 poprawki, a zbieżności brak. Wagi są duże i mają zły znak. Coś jest nie tak — poza tym, że nic nie jest nie tak, a powód jest najbardziej użyteczną rzeczą w tym rozdziale.

Perceptron ma gwarancję, udowodnioną przez Novikoffa w 1962 roku.¹ Jeśli dane w ogóle da się rozdzielić prostą, algorytm wykona najwyżej

poprawek, zanim przestanie je wykonywać — gdzie $R$ to promień danych, długość najdłuższego wektora przykładu, a $\gamma$ to margines: odległość od rozdzielającej hiperpłaszczyzny do najbliższego punktu w przestrzeni rozszerzonej, w której bias jest trzecią współrzędną. Właśnie dlatego centrowanie danych zmienia tę wartość, choć odległość w milimetrach się nie zmienia.

Gwarancja jest bezwarunkowa i nie wspomina o epokach, learning rates ani szczęściu. Nie wspomina też o czasie — i o to chodzi.

Podstawmy nasze liczby. Zmierzone bezpośrednio z ośmiu części, z bias włączonym jako stała cecha:

Twierdzenie nigdy nie zostało naruszone. Uruchom surową wersję na wystarczająco długo, a zbiegnie — w epoce 11 976, po 29 870 poprawkach — spokojnie w granicy 2 633 550, a sama ta różnica jest częścią lekcji: twierdzenie ogranicza najgorszy przypadek, nie typowy. Potrzebowało po prostu sześćdziesiąt razy więcej epok, niż ktokolwiek chciałby przeczekać.

Drugi wiersz to te same osiem części, te same dwadzieścia linijek kodu, z trzema liniami dodanymi po to, by od każdego pomiaru odjąć średnią szerokość i średnią masę. To wszystko. To cała zmiana. Przesuwa chmurę punktów tak, że obejmuje początek układu, zamiast unosić się w okolicy (22, 57), a wpływ na ograniczenie to czynnik piętnastu tysięcy, bo oba składniki poprawiają się naraz: $R$ spada z 74 do 13, ponieważ punkty nie są już mierzone od odległego początku układu, a $\gamma$ rośnie z 0.045 do 0.989, ponieważ margines jest mierzony względem wektora wag, który nie musi już nieść ogromnego bias, żeby dosięgnąć danych.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Zbieżność w dwóch epokach, po dokładnie jednej poprawce.

Jest tu prawdziwa lekcja i nie brzmi ona „pamiętaj o normalizacji wejść”, choć powinieneś. Brzmi: gwarancja, że algorytm skończy, nie mówi ci nic o tym, czy będziesz przy tym, gdy skończy, a różnica między jednym a drugim zwykle jest geometrią. To pierwszy raz, gdy pojawia się wzorzec, który zobaczysz ponownie w rozdziale 6 przy inicjalizacji, w rozdziale 10 przy harmonogramach learning rate i w rozdziale 13 przy kwantyzacji: matematyka mówi, że coś jest możliwe, a inżynieria decyduje, czy jest praktyczne. Kurs, który uczy cię tylko twierdzenia, wręcza ci model trenujący się trzy dni i obwinia ciebie.

Teraz porażka, która zakończyła pierwszą erę sieci neuronowych, a mieści się w czterech wierszach.

Zapomnij o fabryce. Weź dwa wejścia, z których każde ma wartość 0 albo 1, i poproś, aby odpowiedzią było $+1$ wtedy, gdy dokładnie jedno z nich jest równe 1:

To XOR — alternatywa wykluczająca. Zanim czytasz dalej, narysuj cztery punkty na kartce: trzy rogi kwadratu jednostkowego i czwarty. Oznacz dwa przekątne rogi $(0,1)$ i $(1,0)$ jako zaakceptowane, a $(0,0)$ i $(1,1)$ jako odrzucone. Teraz narysuj jedną prostą, która ma dwa zaakceptowane punkty po jednej stronie i dwa odrzucone po drugiej.

Nie możesz. Nie dlatego, że to trudne albo że potrzebujesz sprytniejszego algorytmu; taka prosta po prostu nie istnieje. Trzy linijki algebry pokazują dlaczego. Gdyby perceptron poprawnie sklasyfikował wszystkie cztery, to czytając cztery wiersze po kolei, dostalibyśmy

Dodaj dwie środkowe nierówności: $w_1 + w_2 + 2b \geq 0$, więc $w_1 + w_2 \geq -2b$. Ostatnia mówi $w_1 + w_2 < -b$. Razem: $-2b \leq w_1 + w_2 < -b$, co wymaga $-2b < -b$, co wymaga $b > 0$. A pierwsza nierówność mówi $b < 0$. Nie istnieje takie $b$, więc nie istnieją takie wagi. Żaden perceptron, z żadnymi liczbami, nie klasyfikuje XOR.

Mimo to uruchom go, bo oglądanie porażki algorytmu jest warte więcej niż informacja, że poniesie porażkę:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Nie rozbiega się i nie miota w okolicy niezłej odpowiedzi. On cykli się: przechodzi krótką pętlę przez przestrzeń wag i wraca dokładnie tam, skąd zaczął, w nieskończoność, trafiając dwa z czterech przypadków — tyle, ile dałoby zgadywanie. Sto tysięcy epok i sto są nieodróżnialne, bo algorytm nie robi postępów, które dłuższe uruchomienie mogłoby dokończyć. Porównaj to z taśmą, która wyglądała na zablokowaną po 200 epokach, a w rzeczywistości mozolnie szła ku prawdziwej odpowiedzi. Z zewnątrz przez pierwsze kilka sekund oba przypadki wyglądają podobnie. Odróżnienie ich bez twierdzenia jest niemożliwe — i to kolejny argument za tym, żeby znać twierdzenie.

W 1969 roku Marvin Minsky i Seymour Papert opublikowali Perceptrons, książkowe studium matematyczne dokładnie tego, co ten model może reprezentować, a czego nie.² XOR jest najczęściej cytowanym wynikiem, a cytat zwykle służy jako oskarżenie: że książka zabiła badania nad sieciami neuronowymi na piętnaście lat z powodu rywalizacji albo złośliwości.

Matematyka w tej książce jest poprawna i ciekawsza niż przykład XOR. Minsky i Papert nie byli przede wszystkim zainteresowani tym, czy pojedynczy perceptron potrafi wykonać XOR; interesowało ich, co dzieje się, gdy perceptrony dostają ograniczone pola recepcyjne — każda jednostka widzi tylko część wejścia — i udowodnili, że pewnych globalnych własności obrazu, takich jak to, czy figura jest spójna, nie da się w ten sposób obliczyć niezależnie od liczby użytych jednostek. To naprawdę głęboki wynik o lokalności i nie ma nic wspólnego z popularną opowieścią.

Popularna opowieść myli się też historycznie. Minsky i Papert wprost omawiają perceptrony wielowarstwowe i mówią, że pytanie o ich moc pozostaje otwarte — podejrzewali, że rozszerzenie teorii będzie „jałowe”, co jest przewidywaniem, nie dowodem, i było błędne. Tym, czego brakowało w 1969 roku, nie była idea układania warstw; brakowało sposobu, by taki stos trenować. Reguła perceptronu tego nie potrafi: musi wiedzieć, jak bardzo myli się każda jednostka, a dla jednostki ukrytej w środku nie ma etykiety, z którą można ją porównać. Ta luka pozostała otwarta aż do spopularyzowania backpropagation w 1986 roku,³ a jej zamknięcie jest zadaniem rozdziału 5.

Uczciwe podsumowanie brzmi więc tak. Książka udowodniła rzeczywiste ograniczenie rzeczywistego modelu. Załamanie finansowania tej dziedziny w latach siedemdziesiątych miało wiele przyczyn, z których jedną były przesadne obietnice składane perceptronom na początku lat sześćdziesiątych. A techniczna przeszkoda była rozwiązywalna, tylko nikt nie miał jeszcze narzędzia.

Perceptron ma sześćdziesiąt osiem lat, a ty właśnie napisałeś jeden. Warto precyzyjnie wskazać, które jego części nadal znajdują się w maszynie, z którą skończysz ten kurs, bo odpowiedź brzmi: więcej, niż sądzisz.

Perceptron utknął na dwóch rzeczach naraz, które okazują się tą samą rzeczą.

Nie potrafi reprezentować XOR, bo jedna prosta nie wystarcza. Naprawa oznacza układanie warstw — pierwszą warstwę, która zgina przestrzeń, i drugą, która rysuje prostą w zgiętej przestrzeni. To rozdział 5.

Ale nie da się trenować stosu regułą perceptronu, bo zna ona tylko „źle”, a jednostka w środku sieci nie ma własnej etykiety, co do której mogłaby się mylić. Żeby trenować stos, musisz wiedzieć, jak bardzo jest źle i w którym kierunku, dla każdej wagi — potrzebujesz nachylenia. A funkcja błędu perceptronu, schody, go nie ma.

Dlatego przed stosem musi pojawić się funkcja straty z użyteczną pochodną. I nie taka wybrana dlatego, że wygodnie się ją różniczkuje: taka, która skądś wynika, mówi coś prawdziwego o danych, a jej gradient wypływa z tego znaczenia, zamiast być konstruowany od końca, by wyglądał schludnie.

To rozdział 2, a zaczyna się od pytania, na które perceptron nigdy nie musiał odpowiadać: nie „czy ta część jest dobra?”, ale „jak prawdopodobne są te odczyty, jeśli to jest prawda?”

Warto też czytać równolegle z tym rozdziałem: oryginalny artykuł Rosenblatta, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), bardziej przystępny, niż sugeruje jego reputacja; McCulloch i Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), artykuł, który jako pierwszy modelował neuron jako próg nad ważoną sumą; sekcję o perceptronie w A Course in Machine Learning Hala Daumé III, która wyprowadza tę samą aktualizację z innym akcentem; oraz rozdziały 2 i 3 książki Deisenrotha, Faisala i Onga Mathematics for Machine Learning dla algebry liniowej, jeśli powyższe pudełko zostawiło cię z apetytem na więcej.