Perceptronul de la zero: ce calculează un neuron

Un perceptron ia măsurătorile, le înmulțește pe fiecare cu un număr pe care îl controlează, le adună, mai adaugă încă un număr și se uită la semn.

Scrie măsurătorile unei piese ca vector $\mathbf{x} = (x_1, x_2)$ — lățime și greutate. Perceptronul păstrează un vector de ponderi $\mathbf{w} = (w_1, w_2)$ și un bias $b$. Scorul lui este

iar răspunsul lui este semnul acelui scor: acceptă dacă $s(\mathbf{x}) \geq 0$, respinge altfel.

Acesta este întregul model. Tot ce va ști vreodată perceptronul despre fabrică încape în trei numere.

Merită să ne oprim asupra geometriei, pentru că este imaginea care continuă să funcționeze în următoarele douăzeci și nouă de capitole, chiar și când ecuațiile nu mai încap pe o singură linie. Mulțimea punctelor unde $s(\mathbf{x}) = 0$ — unde perceptronul este exact indecis — este o dreaptă în plan. Pe o parte scorul este pozitiv și totul este acceptat; pe cealaltă este negativ și totul este respins. Pentru un perceptron, învățarea înseamnă să muți acea dreaptă.

Două lucruri despre acea dreaptă urmează direct din algebră, iar ambele contează mai târziu:

• $\mathbf{w}$ este perpendicular pe ea. Vectorul de ponderi nu se află de-a lungul frontierei, ci arată de-a curmezișul ei, către partea acceptată.
• $b$ o glisează fără să o rotească. Fără un bias, dreapta ar fi obligată să treacă prin origine, ceea ce pentru o fabrică ce măsoară milimetri și grame ar fi o constrângere absurdă — ar însemna că o piesă cu lățime zero și greutate zero stă exact pe gard.

Perceptronul începe fără să știe nimic: $\mathbf{w} = (0, 0)$ și $b = 0$. Fiecare scor este zero, deci acceptă totul.

Acum arată-i câte un exemplu pe rând. Etichetează piesele acceptate cu $y = +1$ și pe cele respinse cu $y = -1$. Pentru fiecare exemplu, pune o singură întrebare: a ieșit semnul corect? Modul compact de a scrie acea întrebare este să verifici dacă $y \cdot s(\mathbf{x})$ este pozitiv — dacă eticheta și scorul au același semn, produsul lor este pozitiv, iar dacă nu sunt de acord este negativ.

Dacă răspunsul este da, nu schimba nimic. Dacă răspunsul este nu, împinge ușor:

Acesta este întregul algoritm și merită să înțelegi de ce este împingerea corectă, în loc să o memorezi. Să presupunem că o piesă ar fi trebuit acceptată ($y = +1$), iar scorul a ieșit negativ. Adăugarea lui $\mathbf{x}$ la $\mathbf{w}$ schimbă scorul pentru aceeași piesă cu

care este un număr pozitiv. Scorul piesei pe care tocmai a greșit-o merge în sus, exact în direcția în care trebuia să meargă. Regula nu este o euristică ghicită de cineva; este cea mai mică schimbare care îmbunătățește demonstrabil cazul din fața ei. Desigur, poate strica un alt caz, motiv pentru care o iei de la capăt.

Observă ce lipsește. Nu există nicio derivată nicăieri. Nu este o scăpare, ci prima idee cu adevărat importantă din curs.

Lucrul pe care ai vrea să îl derivezi este eroarea — numărul de piese clasificate greșit. Dar acel număr este o scară: stă plat la 4 cât timp împingi dreapta, apoi coboară la 3 în clipa în care dreapta trece peste un punct. Derivata lui este zero aproape peste tot și nedefinită la trepte. Calculul diferențial nu are de ce să se prindă. Regula perceptronului ocolește asta, necerând deloc o pantă: întreabă doar „corect sau greșit?” și se mișcă într-o direcție pe care o poate justifica geometric.

Aceasta este o soluție reală și este, în același timp, o fundătură. În Capitolul 2 vom vrea o pierdere care vine de undeva, nu una aleasă arbitrar, în Capitolul 4 un model care raportează cât de sigur este, iar în Capitolul 5 ceva cu mai mult de un strat — și niciuna dintre ele nu este accesibilă dintr-o regulă care știe doar „greșit”. Recuperarea unei pante utilizabile este ceea ce forțează următoarele două capitole. Dar perceptronul poate face ceva ce niciunul dintre succesorii lui nu poate: să învețe fără calcul diferențial deloc.

Python pur, fără NumPy. Liste și o buclă. NumPy apare în capitolul următor, unde aritmetica nu mai încape într-o buclă pe care ai vrea să o citești; introducerea lui acum ar ascunde aritmetica în spatele unei biblioteci exact în momentul în care vrei să o vezi.

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

Cele patru linii evidențiate sunt algoritmul. Tot restul este bookkeeping.

Și banda, cu opt piese măsurate de pe ea — patru care au plecat la livrare și patru care s-au întors:

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)

Aceste opt piese sunt separabile printr-o dreaptă — fiecare piesă acceptată este sub 22 mm și fiecare piesă respinsă are 23 mm sau mai mult. Un gard vertical la 22 de milimetri rezolvă problema. Deci perceptronul ar trebui să îl găsească.

Rulează-l:

None [-142.1, -13.0] 54.0

Două sute de epoci, 454 de corecții, și nu a convergent. Ponderile sunt mari și au semnul greșit. Ceva nu este în regulă — doar că nimic nu este în neregulă, iar motivul este cel mai util lucru din acest capitol.

Perceptronul are o garanție, demonstrată de Novikoff în 1962.¹ Dacă datele pot fi separate printr-o dreaptă, algoritmul face cel mult

corecții înainte să nu mai facă niciuna — unde $R$ este raza datelor, lungimea celui mai lung vector-exemplu, iar $\gamma$ este marginea: distanța de la hiperplanul separator la cel mai apropiat punct în spațiul augmentat unde bias-ul este o a treia coordonată. De aceea centrarea datelor o schimbă, deși distanța în milimetri nu se schimbă.

Garanția este necondiționată și nu menționează epoci, rate de învățare sau noroc. De asemenea, nu menționează timpul, iar omisiunea aceasta este ideea.

Pune numerele noastre în formulă. Măsurate direct din cele opt piese, cu bias-ul inclus ca o caracteristică constantă:

Teorema nu a fost niciodată încălcată. Rulează versiunea brută suficient de mult și converge — la epoca 11.976, după 29.870 de corecții — confortabil în interiorul limitei de 2.633.550, iar acel decalaj este el însuși ideea: teorema limitează cazul cel mai rău, nu pe cel tipic. Pur și simplu a avut nevoie de șaizeci de ori mai multe epoci decât ar sta cineva să aștepte.

Al doilea rând reprezintă aceleași opt piese, aceleași douăzeci de linii de cod, cu trei linii adăugate pentru a scădea lățimea medie și greutatea medie din fiecare măsurătoare. Asta e tot. Aceasta este întreaga schimbare. Mută norul de puncte astfel încât să străbată originea, în loc să plutească pe la (22, 57), iar efectul asupra limitei este un factor de cincisprezece mii, pentru că ambii termeni se îmbunătățesc simultan: $R$ scade de la 74 la 13, fiindcă punctele nu mai sunt măsurate dintr-o origine îndepărtată, iar $\gamma$ crește de la 0.045 la 0.989, fiindcă marginea este măsurată față de un vector de ponderi care nu mai trebuie să poarte un bias uriaș ca să ajungă la date.

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

A convergent în două epoci, corectându-se exact o dată.

Lecția reală de aici nu este „nu uita să-ți normalizezi intrările”, deși ar trebui să o faci. Este că o garanție despre dacă un algoritm se termină nu îți spune nimic despre dacă vei fi acolo când o face, iar distanța dintre cele două este de obicei geometrie. Aceasta este prima apariție a unui tipar pe care îl vei întâlni din nou în Capitolul 6 cu inițializarea, în Capitolul 10 cu programele pentru rata de învățare și în Capitolul 13 cu cuantizarea: matematica spune că lucrul este posibil, iar ingineria decide dacă este practic. Un curs care te învață doar teorema îți dă un model care se antrenează trei zile și te învinovățește pe tine.

Acum eșecul care a încheiat prima eră a rețelelor neuronale, și încape în patru rânduri.

Uită fabrica. Ia două intrări care pot fi fiecare 0 sau 1 și cere ca răspunsul să fie $+1$ atunci când exact una dintre ele este 1:

Acesta este XOR — sau exclusiv. Înainte să citești mai departe, desenează cele patru puncte pe hârtie: trei colțuri ale unui pătrat unitate și al patrulea. Marchează cele două colțuri diagonale $(0,1)$ și $(1,0)$ ca acceptate, iar $(0,0)$ și $(1,1)$ ca respinse. Acum trasează o singură dreaptă cu cele două puncte acceptate pe o parte și cele două puncte respinse pe cealaltă.

Nu poți. Nu pentru că este greu sau pentru că ai nevoie de un algoritm mai isteț; ci pentru că dreapta nu există. Trei linii de algebră arată de ce. Dacă un perceptron le-ar nimeri pe toate patru, atunci citirea celor patru rânduri în ordine dă

Adună cele două inegalități din mijloc: $w_1 + w_2 + 2b \geq 0$, deci $w_1 + w_2 \geq -2b$. Ultima spune $w_1 + w_2 < -b$. Împreună: $-2b \leq w_1 + w_2 < -b$, ceea ce cere $-2b < -b$, ceea ce cere $b > 0$. Iar prima inegalitate spune $b < 0$. Nu există un astfel de $b$, deci nu există astfel de ponderi. Niciun perceptron, cu absolut niciun număr, nu clasifică XOR.

Rulează-l oricum, pentru că să vezi un algoritm eșuând valorează mai mult decât să ți se spună că va eșua:

     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

Nu diverge și nu se zbate în apropierea unui răspuns decent. Ciclează: parcurge o buclă scurtă prin spațiul ponderilor și revine exact de unde a plecat, la nesfârșit, nimerind două din patru — ceea ce ai obține și ghicind. O sută de mii de epoci și o sută sunt indistincte, pentru că algoritmul nu face un progres pe care o rulare mai lungă l-ar putea termina. Compară asta cu banda, care părea blocată la 200 de epoci și, de fapt, măcina încet spre un răspuns real. Din exterior, cele două arată similar în primele câteva secunde. Să le deosebești fără teoremă este imposibil — încă un argument pentru a cunoaște teorema.

În 1969, Marvin Minsky și Seymour Papert au publicat Perceptrons, un studiu matematic de dimensiunea unei cărți despre exact ce poate și ce nu poate reprezenta acest model.² XOR este rezultatul cel mai citat, iar citatul este de obicei folosit ca acuzație: că această carte ar fi omorât cercetarea în rețele neuronale timp de cincisprezece ani, din rivalitate sau răutate.

Matematica din carte este corectă și este mai interesantă decât exemplul XOR. Minsky și Papert nu erau interesați în primul rând dacă un singur perceptron putea face XOR; îi interesa ce se întâmplă când perceptronii primesc câmpuri receptive limitate — fiecare unitate văzând doar o parte din intrare — și au demonstrat că anumite proprietăți globale ale unei imagini, cum ar fi dacă o figură este conectată, nu pot fi calculate astfel indiferent câte unități folosești. Acesta este un rezultat cu adevărat profund despre localitate și nu are nimic de-a face cu povestea populară.

Povestea populară greșește și istoric. Minsky și Papert discută explicit perceptroni multi-strat și spun că întrebarea despre puterea lor rămâne deschisă — bănuiau că extinderea teoriei ar fi „sterilă”, ceea ce este o predicție, nu o demonstrație, și a fost greșită. Ce lipsea în 1969 nu era ideea de a stivui straturi; era o modalitate de a antrena o stivă. Regula perceptronului nu poate face asta: trebuie să știe cât de greșită este fiecare unitate, iar pentru o unitate îngropată la mijloc nu există o etichetă cu care să o compari. Acel gol a rămas deschis până când backpropagation a fost popularizată în 1986,³ iar închiderea lui este ceea ce face Capitolul 5.

Așadar, rezumatul onest este acesta. Cartea a demonstrat o limitare reală a unui model real. Prăbușirea finanțării domeniului în anii șaptezeci a avut multe cauze, dintre care una a fost că promisiunile făcute pentru perceptroni la începutul anilor șaizeci fuseseră extravagante. Iar obstacolul tehnic era rezolvabil, doar că nimeni nu avea încă unealta.

Perceptronul are șaizeci și opt de ani și tocmai ai scris unul. Merită să fim preciși cu privire la părțile din el care încă există în mașina cu care vei încheia acest curs, pentru că răspunsul este: mai multe decât ai crede.

Perceptronul s-a blocat în două lucruri deodată, iar ele se dovedesc a fi același lucru.

Nu poate reprezenta XOR, pentru că o singură dreaptă nu este suficientă. Repararea acestui lucru înseamnă stivuirea de straturi — un prim strat care îndoaie spațiul, un al doilea care trasează dreapta în spațiul îndoit. Acesta este Capitolul 5.

Dar nu poți antrena o stivă cu regula perceptronului, pentru că ea știe doar „greșit”, iar o unitate din mijlocul unei rețele nu are o etichetă proprie față de care să fie greșită. Pentru a antrena o stivă, trebuie să știi cât de greșit este, și în ce direcție, pentru fiecare pondere — ai nevoie de o pantă. Iar funcția de eroare a perceptronului, scara, nu are una.

Așa că înainte de stivă trebuie să existe o funcție de pierdere cu o derivată utilizabilă. Și nu una aleasă fiindcă este comod de derivat: una care vine de undeva, care spune ceva adevărat despre date și al cărei gradient decurge din acel sens, în loc să fie construit invers ca să arate ordonat.

Acesta este Capitolul 2 și începe punând o întrebare la care perceptronul nu a trebuit niciodată să răspundă: nu „este această piesă bună?”, ci „cât de probabile sunt aceste măsurători, dacă acesta este adevărul?”

Merită citite alături de acest capitol și lucrarea originală a lui Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), care este mai ușor de citit decât sugerează reputația ei; McCulloch și Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), lucrarea care a modelat pentru prima dată un neuron ca prag peste o sumă ponderată; secțiunea despre perceptron din A Course in Machine Learning de Hal Daumé III, care derivă aceeași actualizare cu un accent diferit; și capitolele 2 și 3 din Mathematics for Machine Learning de Deisenroth, Faisal și Ong pentru algebra liniară, dacă caseta de mai sus te-a lăsat dorind mai mult decât ți-a oferit.