Perceptronen fra bunden: Hvad en neuron beregner

En perceptron tager målingerne, ganger hver af dem med et tal, den kontrollerer, lægger dem sammen, lægger ét tal mere til og ser på fortegnet.

Skriv målingerne af én del som en vektor $\mathbf{x} = (x_1, x_2)$ — bredde og vægt. Perceptronen har en vægtvektor $\mathbf{w} = (w_1, w_2)$ og en bias $b$. Dens score er

og dens svar er fortegnet på den score: accepter hvis $s(\mathbf{x}) \geq 0$, afvis ellers.

Det er hele modellen. Alt, hvad perceptronen nogensinde kommer til at vide om fabrikken, ligger i tre tal.

Geometrien er værd at dvæle ved, fordi det er det billede, der bliver ved med at virke gennem de næste niogtyve kapitler, selv når ligningerne ikke længere kan være på én linje. Mængden af punkter hvor $s(\mathbf{x}) = 0$ — hvor perceptronen er helt i tvivl — er en ret linje i planet. På den ene side er scoren positiv, og alt accepteres; på den anden er den negativ, og alt afvises. For en perceptron betyder læring at flytte den linje.

To fakta om den linje følger direkte af algebraen, og begge får betydning senere:

• $\mathbf{w}$ står vinkelret på den. Vægtvektoren ligger ikke langs grænsen, den peger på tværs af den, mod den accepterede side.
• $b$ flytter den uden at dreje den. Uden en bias ville linjen være tvunget gennem origo, hvilket for en fabrik, der måler millimeter og gram, ville være en absurd begrænsning — det ville betyde, at en del med nul bredde og nul vægt står præcis på hegnet.

Perceptronen starter med at vide ingenting: $\mathbf{w} = (0, 0)$ og $b = 0$. Hver score er nul, så den accepterer alt.

Vis den nu ét eksempel ad gangen. Mærk de accepterede dele $y = +1$ og de afviste $y = -1$. For hvert eksempel stiller du ét spørgsmål: kom fortegnet rigtigt ud? Den kompakte måde at skrive det spørgsmål på er at tjekke, om $y \cdot s(\mathbf{x})$ er positiv — hvis label og score er enige i fortegn, er deres produkt positivt, og hvis de er uenige, er det negativt.

Hvis svaret er ja, ændrer du ingenting. Hvis svaret er nej, skubber du:

Det er hele algoritmen, og det er værd at forstå hvorfor det er det rigtige skub i stedet for at lære det udenad. Antag, at en del burde være blevet accepteret ($y = +1$), og scoren blev negativ. At lægge $\mathbf{x}$ til $\mathbf{w}$ ændrer scoren på den samme del med

hvilket er et positivt tal. Scoren på den del, den lige tog fejl af, går op, hvilket er den retning, den skulle bevæge sig i. Reglen er ikke en heuristik, nogen har gættet på; den er den mindste ændring, der beviseligt forbedrer den sag, der ligger foran den. Den kan selvfølgelig ødelægge en anden sag, og derfor går du rundt igen.

Læg mærke til, hvad der mangler. Der er ingen afledt nogen steder. Det er ikke en forglemmelse, og det er den første virkelig vigtige idé i kurset.

Det, du ville have lyst til at differentiere, er fejlen — antallet af forkert klassificerede dele. Men det antal er en trappe: det ligger fladt på 4, mens du skubber linjen, og falder så til 3 i samme øjeblik linjen krydser et punkt. Dets afledte er nul næsten overalt og udefineret ved trinene. Calculus har intet at gribe fat i. Perceptron-reglen arbejder uden om det ved slet ikke at spørge efter en hældning: den spørger kun »rigtigt eller forkert?« og bevæger sig i en retning, den kan begrunde geometrisk.

Det er en reel løsning, og det er også en blindgyde. I Kapitel 2 vil vi have en loss, der kommer et sted fra i stedet for bare at være valgt, i Kapitel 4 en model, der rapporterer hvor sikker den er, og i Kapitel 5 noget med mere end ét lag — og ingen af delene kan nås fra en regel, der kun kender »forkert«. At få en brugbar hældning tilbage er det, der tvinger de næste to kapitler frem. Men perceptronen får lov til noget, ingen af dens efterfølgere kan: at lære helt uden calculus.

Ren Python, ingen NumPy. Lister og en løkke. NumPy kommer i næste kapitel, hvor aritmetikken holder op med at passe ind i en løkke, du faktisk ville gide læse; at introducere det nu ville skjule aritmetikken bag et bibliotek præcis i det øjeblik, hvor du vil se den.

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

De fire fremhævede linjer er algoritmen. Alt andet er bogføring.

Og transportbåndet, med otte dele målt fra det — fire der blev sendt videre, og fire der kom retur:

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)

Disse otte dele kan separeres af en ret linje — hver accepteret del er under 22 mm, og hver afvist del er 23 mm eller mere. Et lodret hegn ved 22 millimeter klarer opgaven. Så perceptronen burde finde det.

Kør den:

None [-142.1, -13.0] 54.0

To hundrede epochs, 454 rettelser, og den er ikke konvergeret. Vægtene er store og har forkert fortegn. Noget er galt — bortset fra at intet er galt, og årsagen er det mest nyttige i dette kapitel.

Perceptronen har en garanti, bevist af Novikoff i 1962.¹ Hvis data overhovedet kan separeres af en linje, laver algoritmen højst

rettelser, før den holder op med at lave nogen — hvor $R$ er dataenes radius, længden af den længste eksempel-vektor, og $\gamma$ er margin: afstanden fra det separerende hyperplan til det nærmeste punkt i det udvidede rum, hvor bias er en tredje koordinat. Det er derfor centrering af data ændrer den, mens afstanden i millimeter ikke gør.

Garantien er ubetinget, og den nævner hverken epochs, learning rates eller held. Den nævner heller ikke tid, og den udeladelse er pointen.

Sæt vores tal ind. Målt direkte fra de otte dele, med bias foldet ind som en konstant feature:

Sætningen blev aldrig brudt. Kør den rå version længe nok, og den konvergerer — ved epoch 11.976, efter 29.870 rettelser — komfortabelt inden for sin grænse på 2.633.550, og det mellemrum er i sig selv pointen: sætningen begrænser værste fald, ikke det typiske. Den havde bare brug for tres gange flere epochs, end nogen ville sidde igennem.

Den anden række er de samme otte dele, de samme tyve linjer kode, med tre linjer tilføjet for at trække den gennemsnitlige bredde og den gennemsnitlige vægt fra hver måling. Det er det. Det er hele ændringen. Den flytter punktskyen, så den spænder over origo i stedet for at svæve ude ved (22, 57), og effekten på grænsen er en faktor femten tusind, fordi begge led forbedres på én gang: $R$ falder fra 74 til 13, fordi punkterne ikke længere måles fra et fjernt origo, og $\gamma$ stiger fra 0,045 til 0,989, fordi margin måles mod en vægtvektor, der ikke længere skal bære en enorm bias for at nå dataene.

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

Konvergeret på to epochs efter at have rettet sig selv præcis én gang.

Der er en reel lektie her, og den er ikke »husk at normalisere dine inputs«, selvom du bør gøre det. Den er, at en garanti for om en algoritme bliver færdig, fortæller dig intet om, hvorvidt du er der, når den gør, og at afstanden mellem de to normalt er geometri. Det er første gang, du møder et mønster, du vil møde igen i Kapitel 6 med initialisering, i Kapitel 10 med learning-rate-planer og i Kapitel 13 med kvantisering: matematikken siger, at tingen er mulig, og engineering afgør, om den er praktisk. Et kursus, der kun lærer dig sætningen, giver dig en model, der træner i tre dage og giver dig skylden.

Nu kommer fejlen, der afsluttede den første æra af neurale netværk, og den passer på fire rækker.

Glem fabrikken. Tag to inputs, der hver især enten er 0 eller 1, og bed svaret være $+1$, når præcis én af dem er 1:

Det er XOR — eksklusiv eller. Før du læser videre, så tegn de fire punkter på papir: tre hjørner af et enhedskvadrat og det fjerde. Markér de to diagonale hjørner $(0,1)$ og $(1,0)$ som accepter, og $(0,0)$ og $(1,1)$ som afvis. Tegn nu én ret linje med de to accepterede punkter på den ene side og de to afviste punkter på den anden.

Det kan du ikke. Det er ikke, fordi det er svært, eller fordi du har brug for en smartere algoritme; det er, fordi linjen ikke findes. Tre linjers algebra viser hvorfor. Hvis en perceptron fik alle fire rigtige, så giver de fire rækker i rækkefølge

Læg de to midterste uligheder sammen: $w_1 + w_2 + 2b \geq 0$, så $w_1 + w_2 \geq -2b$. Den sidste siger $w_1 + w_2 < -b$. Sammen: $-2b \leq w_1 + w_2 < -b$, hvilket kræver $-2b < -b$, hvilket kræver $b > 0$. Og den første ulighed siger $b < 0$. Der findes ingen sådan $b$, så der findes ingen sådanne vægte. Ingen perceptron, med nogen tal overhovedet, klassificerer XOR.

Kør den alligevel, fordi det er mere værd at se en algoritme fejle end at få at vide, at den vil:

     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

Den divergerer ikke, og den tumler ikke rundt tæt på et anstændigt svar. Den cykler: den går en kort løkke gennem vægtrummet og kommer tilbage til præcis dér, hvor den startede, for evigt, mens den får to ud af fire rigtige — det samme som du ville få ved at gætte. Hundrede tusind epochs og hundrede er ikke til at skelne, fordi algoritmen ikke gør fremskridt, som en længere kørsel kunne afslutte. Sammenlign det med transportbåndet, der så fastlåst ud efter 200 epochs, men i virkeligheden sled sig mod et rigtigt svar. Udefra ser de to ens ud de første par sekunder. At skelne dem fra hinanden uden sætningen er umuligt — hvilket er endnu et argument for at kende sætningen.

I 1969 udgav Marvin Minsky og Seymour Papert Perceptrons, en boglang matematisk undersøgelse af præcis hvad denne model kan og ikke kan repræsentere.² XOR er dens mest citerede resultat, og citatet bruges normalt som en anklage: at bogen slog forskningen i neurale netværk ihjel i femten år af rivalisering eller ond vilje.

Matematikken i bogen er korrekt, og den er mere interessant end XOR-eksemplet. Minsky og Papert var ikke primært interesserede i, om en enkelt perceptron kunne lave XOR; de var interesserede i, hvad der sker, når perceptroner får begrænsede receptive fields — hvor hver enhed kun ser en del af inputtet — og de beviste, at visse globale egenskaber ved et billede, såsom om en figur hænger sammen, ikke kan beregnes på den måde, uanset hvor mange enheder du bruger. Det er et virkelig dybt resultat om lokalitet, og det har intet at gøre med den populære fortælling.

Den populære fortælling tager også fejl af historien. Minsky og Papert diskuterer eksplicit flerlags-perceptroner og siger, at spørgsmålet om deres styrke er åbent — de mistænkte, at en udvidelse af teorien ville være »steril«, hvilket er en forudsigelse, ikke et bevis, og den var forkert. Det, der manglede i 1969, var ikke idéen om at stable lag; det var en måde at træne en stak på. Perceptron-reglen kan ikke gøre det: den skal vide, hvor forkert hver enhed er, og for en enhed begravet i midten findes der intet label at sammenligne med. Det hul forblev åbent, indtil backpropagation blev populariseret i 1986,³ og at lukke det er, hvad Kapitel 5 gør.

Så den ærlige opsummering er denne. Bogen beviste en reel begrænsning ved en reel model. Feltets finansieringskollaps i halvfjerdserne havde mange årsager, hvoraf én var, at løfterne om perceptroner i de tidlige tressere havde været overdrevne. Og den tekniske forhindring kunne løses, men ingen havde værktøjet endnu.

Perceptronen er otteogtres år gammel, og du har lige skrevet en. Det er værd at være præcis om, hvilke dele af den der stadig findes i maskinen, du ender dette kursus med, for svaret er: mere end du tror.

Perceptronen sad fast på to ting på én gang, og de viser sig at være det samme.

Den kan ikke repræsentere XOR, fordi én linje ikke er nok. At løse det betyder at stable lag — et første lag, der bøjer rummet, et andet, der tegner linjen i det bøjede rum. Det er Kapitel 5.

Men du kan ikke træne en stak med perceptron-reglen, fordi den kun kender »forkert«, og en enhed i midten af et netværk har intet label for sig selv at tage fejl i forhold til. For at træne en stak skal du vide hvor forkert, og i hvilken retning, for hver vægt — du har brug for en hældning. Og perceptronens fejlfunktion, trappen, har ikke en.

Så før stakken må der være en loss-funktion med en brugbar afledt. Heller ikke én valgt, fordi den er nem at differentiere: én der kommer et sted fra, som siger noget sandt om dataene, og hvis gradient falder ud af den betydning i stedet for at være reverse-engineered til at se pæn ud.

Det er Kapitel 2, og det starter med at stille et spørgsmål, perceptronen aldrig behøvede at svare på: ikke »er denne del god?«, men »hvor sandsynlige er disse målinger, hvis dette er sandheden?«

Også værd at læse sammen med dette kapitel: Rosenblatts oprindelige artikel, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), som er mere læsbar, end dens rygte antyder; McCulloch og Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), artiklen der først modellerede en neuron som en tærskel over en vægtet sum; perceptron-afsnittet i Hal Daumé III’s A Course in Machine Learning, som udleder den samme update med en anden vægtning; og kapitel 2 og 3 i Deisenroth, Faisal og Ongs Mathematics for Machine Learning for den lineære algebra, hvis boksen ovenfor gav dig lyst til mere, end den gav.