Perceptron od nuly: co počítá neuron

Perceptron vezme měření, každé vynásobí číslem, které sám ovládá, sečte je, přičte ještě jedno číslo a podívá se na znaménko.

Měření jedné součástky zapište jako vektor $\mathbf{x} = (x_1, x_2)$ — šířka a hmotnost. Perceptron drží váhový vektor $\mathbf{w} = (w_1, w_2)$ a bias $b$. Jeho skóre je

a jeho odpovědí je znaménko tohoto skóre: přijmout, pokud $s(\mathbf{x}) \geq 0$, jinak odmítnout.

To je celý model. Všechno, co se perceptron kdy o továrně dozví, žije ve třech číslech.

U geometrie stojí za to se zastavit, protože právě tenhle obrázek bude fungovat i dalších dvacet devět kapitol, i když se rovnice přestanou vejít na jeden řádek. Množina bodů, kde $s(\mathbf{x}) = 0$ — kde je perceptron přesně nerozhodnutý — je přímka v rovině. Na jedné straně je skóre kladné a vše se přijímá; na druhé je záporné a vše se odmítá. Učení pro perceptron znamená posouvat tuto přímku.

Z algebry přímo plynou dvě fakta o této přímce a obě budou později důležitá:

• $\mathbf{w}$ je na ni kolmé. Váhový vektor neleží podél hranice, míří napříč přes ni, směrem k přijímané straně.
• $b$ ji posouvá, aniž by ji otáčel. Bez bias by přímka musela procházet počátkem, což by pro továrnu měřící milimetry a gramy bylo absurdní omezení — znamenalo by to, že součástka s nulovou šířkou a nulovou hmotností sedí přesně na hraně.

Perceptron na začátku neví nic: $\mathbf{w} = (0, 0)$ a $b = 0$. Každé skóre je nula, takže přijímá všechno.

Teď mu ukazujte jeden příklad po druhém. Přijaté součástky označte $y = +1$ a odmítnuté $y = -1$. U každého příkladu položte jednu otázku: vyšlo znaménko správně? Kompaktní způsob, jak tu otázku zapsat, je zkontrolovat, zda je $y \cdot s(\mathbf{x})$ kladné — pokud se značka a skóre shodují ve znaménku, jejich součin je kladný, a pokud se neshodují, je záporný.

Pokud je odpověď ano, neměňte nic. Pokud je odpověď ne, postrčte:

To je celý algoritmus a stojí za to pochopit, proč je to správné postrčení, místo abyste si ho jen zapamatovali. Představte si, že součástka měla být přijata ($y = +1$) a skóre vyšlo záporné. Přičtení $\mathbf{x}$ k $\mathbf{w}$ změní skóre na téže součástce o

což je kladné číslo. Skóre na součástce, kterou právě spletl, jde nahoru, tedy směrem, kterým jít potřebovalo. Pravidlo není heuristika, kterou někdo odhadl; je to nejmenší změna, která prokazatelně zlepší případ před vámi. Samozřejmě může rozbít jiný případ, a proto jdete dokola znovu.

Všimněte si, co tu chybí. Nikde není žádná derivace. Není to přehlédnutí a je to první skutečně důležitá myšlenka kurzu.

To, co byste chtěli derivovat, je chyba — počet špatně klasifikovaných součástek. Jenže ten počet je schodiště: zůstává plochý na 4, když přímkou trochu posouváte, a pak spadne na 3 ve chvíli, kdy přímka překročí bod. Jeho derivace je téměř všude nulová a na schodech nedefinovaná. Kalkulus se nemá čeho chytit. Pravidlo perceptronu to obchází tím, že se na žádný sklon vůbec neptá: ptá se jen „správně, nebo špatně?“ a pohne se směrem, který umí geometricky obhájit.

To je skutečné řešení a zároveň slepá ulička. V Kapitole 2 budeme chtít ztrátu, která odněkud vychází, místo aby byla zvolena, v Kapitole 4 model, který hlásí, jak si je jistý, a v Kapitole 5 něco s více než jednou vrstvou — a ani k jednomu se z pravidla, které zná jen „špatně“, nedostaneme. Získat zpět použitelný sklon je to, co si vynutí další dvě kapitoly. Perceptron ale umí něco, co žádný z jeho nástupců neumí: učit se úplně bez kalkulu.

Čistý Python, žádný NumPy. Seznamy a smyčka. NumPy přijde v další kapitole, kde se aritmetika přestane vejít do smyčky, kterou byste chtěli číst; zavádět ho teď by schovalo aritmetiku za knihovnu právě ve chvíli, kdy ji chcete vidět.

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

Čtyři zvýrazněné řádky jsou algoritmus. Všechno ostatní je administrativa.

A pás s osmi změřenými součástkami — čtyřmi, které se expedovaly, a čtyřmi, které se vrátily:

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)

Těchto osm součástek je oddělitelných přímkou — každá přijatá součástka má méně než 22 mm a každá odmítnutá má 23 mm nebo víc. Svislý plot na 22 milimetrech to vyřeší. Perceptron by ho tedy měl najít.

Spusťte ho:

None [-142.1, -13.0] 54.0

Dvě stě epoch, 454 oprav, a nekonvergoval. Váhy jsou velké a mají špatné znaménko. Něco je špatně — až na to, že špatně není nic, a důvod je to nejužitečnější v této kapitole.

Perceptron má záruku, kterou v roce 1962 dokázal Novikoff.¹ Pokud lze data vůbec oddělit přímkou, algoritmus udělá nejvýše

oprav, než přestane dělat jakékoli další — kde $R$ je poloměr dat, délka nejdelšího příkladového vektoru, a $\gamma$ je margin: vzdálenost od oddělující hyperroviny k nejbližšímu bodu v augmentovaném prostoru, kde je bias třetí souřadnice. Proto centrování dat mění tuto hodnotu, i když vzdálenost v milimetrech ne.

Záruka je bezpodmínečná a nezmiňuje epochy, learning rate ani štěstí. Nezmiňuje ale ani čas, a právě to je podstatné.

Dosaďte naše čísla. Změřeno přímo z osmi součástek, s bias zahrnutým jako konstantní feature:

Věta nikdy porušena nebyla. Nechte surovou verzi běžet dost dlouho a opravdu zkonverguje — v epoše 11 976, po 29 870 opravách — pohodlně uvnitř své meze 2 633 550, a právě ta mezera je pointa: věta omezuje nejhorší případ, ne ten typický. Jen potřebovala šedesátkrát víc epoch, než by kdokoli vydržel sledovat.

Druhý řádek je stejných osm součástek, stejných dvacet řádků kódu, jen se přidaly tři řádky, které od každého měření odečtou průměrnou šířku a průměrnou hmotnost. To je celé. To je celá změna. Posune mračno bodů tak, aby obkročilo počátek, místo aby plulo někde u (22, 57), a dopad na mez je faktor patnáct tisíc, protože se zlepší oba členy najednou: $R$ spadne ze 74 na 13, protože body už nejsou měřeny od vzdáleného počátku, a $\gamma$ vzroste z 0,045 na 0,989, protože margin se měří vůči váhovému vektoru, který už nemusí nést obrovský bias, aby k datům dosáhl.

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

Zkonvergovalo ve dvou epochách a opravilo se přesně jednou.

Je tu skutečná lekce a není to „pamatujte na normalizaci vstupů“, i když byste měli. Je to to, že záruka, že algoritmus skončí, vám neříká nic o tom, zda u toho budete, až skončí, a že mezera mezi těmito dvěma věcmi bývá obvykle geometrie. Je to první výskyt vzorce, se kterým se znovu setkáte v Kapitole 6 u inicializace, v Kapitole 10 u rozvrhů learning rate a v Kapitole 13 u kvantizace: matematika říká, že věc je možná, a inženýrství rozhoduje, zda je praktická. Kurz, který vás naučí jen větu, vám předá model, který se trénuje tři dny, a svede to na vás.

Teď selhání, které ukončilo první éru neuronových sítí, a vejde se do čtyř řádků.

Zapomeňte na továrnu. Vezměte dva vstupy, z nichž každý je buď 0, nebo 1, a chtějte, aby odpověď byla $+1$ právě tehdy, když je přesně jeden z nich 1:

To je XOR — exclusive or. Než budete číst dál, nakreslete si čtyři body na papír: tři rohy jednotkového čtverce a ten čtvrtý. Označte dva diagonální rohy $(0,1)$ a $(1,0)$ jako přijmout a $(0,0)$ a $(1,1)$ jako odmítnout. Teď nakreslete jednu přímku, která má dva přijaté body na jedné straně a dva odmítnuté na druhé.

Nemůžete. Nejde o to, že je to těžké nebo že potřebujete chytřejší algoritmus; jde o to, že taková přímka neexistuje. Tři řádky algebry ukazují proč. Kdyby perceptron trefil všechny čtyři správně, pak čtení čtyř řádků v pořadí dává

Sečtěte prostřední dvě nerovnosti: $w_1 + w_2 + 2b \geq 0$, takže $w_1 + w_2 \geq -2b$. Poslední říká $w_1 + w_2 < -b$. Dohromady: $-2b \leq w_1 + w_2 < -b$, což vyžaduje $-2b < -b$, což vyžaduje $b > 0$. A první nerovnost říká $b < 0$. Takové $b$ neexistuje, takže neexistují ani takové váhy. Žádný perceptron, s jakýmikoli čísly, XOR neklasifikuje.

Přesto ho spusťte, protože sledovat algoritmus selhat má větší cenu než slyšet, že selže:

     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

Nediverguje a ani se nemotá poblíž slušné odpovědi. Cyklí: projde krátkou smyčku ve váhovém prostoru a vrátí se přesně tam, kde začal, navždy, se dvěma správnými ze čtyř — což je totéž, co byste dostali hádáním. Sto tisíc epoch a sto epoch jsou nerozeznatelné, protože algoritmus nedělá pokrok, který by delší běh mohl dokončit. Porovnejte to s pásem, který po 200 epochách vypadal zaseknutý, ale ve skutečnosti se pomalu dral ke skutečné odpovědi. Zvenčí vypadají první pár sekund podobně. Bez věty je od sebe nelze rozeznat — což je další argument pro to, proč větu znát.

V roce 1969 vydali Marvin Minsky a Seymour Papert Perceptrons, matematickou studii v rozsahu knihy o tom, co přesně tento model umí a neumí reprezentovat.² XOR je její nejcitovanější výsledek a citace se obvykle používá jako obvinění: že kniha na patnáct let zabila výzkum neuronových sítí kvůli rivalitě nebo zášti.

Matematika v knize je správná a je zajímavější než příklad XOR. Minsky a Papert se primárně nezajímali o to, zda jeden perceptron zvládne XOR; zajímalo je, co se stane, když perceptrony dostanou omezená receptivní pole — každá jednotka vidí jen část vstupu — a dokázali, že určité globální vlastnosti obrazu, například zda je figura spojitá, takto nelze vypočítat bez ohledu na to, kolik jednotek použijete. To je opravdu hluboký výsledek o lokalitě a s populárním příběhem nemá nic společného.

Populární příběh se plete i v historii. Minsky a Papert výslovně probírají vícevrstvé perceptrony a říkají, že otázka jejich síly je otevřená — tušili, že rozšiřování teorie bude „sterilní“, což je předpověď, ne důkaz, a byla špatně. To, co v roce 1969 chybělo, nebyla myšlenka vrstvy skládat; chyběl způsob, jak takový stack trénovat. Pravidlo perceptronu to neumí: potřebuje vědět, jak moc se každá jednotka mýlí, a pro jednotku pohřbenou uprostřed neexistuje značka, se kterou by ji bylo možné porovnat. Tato mezera zůstala otevřená, dokud nebylo v roce 1986 zpopularizováno backpropagation,³ a její uzavření je to, co dělá Kapitola 5.

Poctivé shrnutí je tedy toto. Kniha dokázala reálné omezení reálného modelu. Kolaps financování oboru v sedmdesátých letech měl mnoho příčin, z nichž jednou bylo, že sliby dávané perceptronům na začátku šedesátých let byly přehnané. A technická překážka byla řešitelná, jen na ni ještě nikdo neměl nástroj.

Perceptronu je šedesát osm let a vy jste si právě jeden napsali. Stojí za to být přesný v tom, které jeho části jsou stále ve stroji, s nímž tento kurz dokončíte, protože odpověď zní: víc, než byste hádali.

Perceptron se zasekl na dvou věcech najednou a ukáže se, že jsou to tatáž věc.

Nedokáže reprezentovat XOR, protože jedna přímka nestačí. Opravit to znamená skládat vrstvy — první vrstvu, která ohne prostor, a druhou, která v ohnutém prostoru nakreslí přímku. To je Kapitola 5.

Stack ale nelze trénovat pravidlem perceptronu, protože to zná jen „špatně“ a jednotka uprostřed sítě nemá vlastní značku, vůči níž by se mohla mýlit. K trénování stacku potřebujete pro každou váhu vědět, jak moc je špatně a kterým směrem — potřebujete sklon. A chybová funkce perceptronu, to schodiště, žádný nemá.

Před stackem tedy musí přijít ztrátová funkce s použitelnou derivací. A ne taková, která je zvolena proto, že se pohodlně derivuje: taková, která odněkud vychází, říká něco pravdivého o datech a jejíž gradient plyne z tohoto významu, místo aby byl zpětně navržen tak, aby vypadal úhledně.

To je Kapitola 2 a začíná otázkou, na kterou perceptron nikdy nemusel odpovídat: ne „je tahle součástka dobrá?“, ale „jak pravděpodobná jsou tato měření, pokud je toto pravda?“

Spolu s touto kapitolou stojí za přečtení také původní Rosenblattův článek The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), který je čtivější, než naznačuje jeho pověst; McCulloch a Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), článek, který jako první modeloval neuron jako práh nad váženým součtem; perceptronová část knihy Hala Daumého III A Course in Machine Learning, která odvozuje stejnou aktualizaci s jiným důrazem; a kapitoly 2 a 3 knihy Deisenrotha, Faisala a Onga Mathematics for Machine Learning k lineární algebře, pokud ve vás výše uvedený box nechal chuť na víc, než dal.