De perceptron vanaf nul: wat een neuron berekent

Een perceptron neemt de metingen, vermenigvuldigt elke meting met een getal dat hij zelf beheert, telt ze op, telt er nog één getal bij op en kijkt naar het teken.

Schrijf de metingen van één onderdeel als een vector $\mathbf{x} = (x_1, x_2)$ — breedte en gewicht. De perceptron houdt een gewichtsvector $\mathbf{w} = (w_1, w_2)$ en een bias $b$ bij. Zijn score is

en zijn antwoord is het teken van die score: accepteren als $s(\mathbf{x}) \geq 0$, anders afwijzen.

Dat is het hele model. Alles wat de perceptron ooit over de fabriek zal weten, zit in drie getallen.

De geometrie is het waard om even bij stil te staan, omdat dit het beeld is dat de volgende negenentwintig hoofdstukken blijft werken, zelfs wanneer de vergelijkingen niet meer op één regel passen. De verzameling punten waarvoor $s(\mathbf{x}) = 0$ — waar de perceptron precies onbeslist is — is een rechte lijn in het vlak. Aan de ene kant is de score positief en wordt alles geaccepteerd; aan de andere kant is hij negatief en wordt alles afgewezen. Leren betekent voor een perceptron: die lijn verplaatsen.

Twee feiten over die lijn volgen rechtstreeks uit de algebra, en allebei doen er later toe:

• $\mathbf{w}$ staat er loodrecht op. De gewichtsvector ligt niet langs de grens, maar wijst er dwars overheen, naar de geaccepteerde kant.
• $b$ schuift hem zonder hem te draaien. Zonder bias zou de lijn gedwongen door de oorsprong gaan, wat voor een fabriek die millimeters en grammen meet een absurde beperking zou zijn — het zou betekenen dat een onderdeel met nul breedte en nul gewicht precies op de grens zit.

De perceptron begint zonder iets te weten: $\mathbf{w} = (0, 0)$ en $b = 0$. Elke score is nul, dus hij accepteert alles.

Laat hem nu één voorbeeld tegelijk zien. Label de geaccepteerde onderdelen als $y = +1$ en de afgewezen onderdelen als $y = -1$. Stel voor elk voorbeeld één vraag: kwam het teken goed uit? De compacte manier om die vraag op te schrijven is controleren of $y \cdot s(\mathbf{x})$ positief is — als het label en de score hetzelfde teken hebben, is hun product positief, en als ze van teken verschillen is het negatief.

Als het antwoord ja is, verander je niets. Als het antwoord nee is, geef je een duwtje:

Dat is het hele algoritme, en het is de moeite waard om te begrijpen waarom dit het juiste duwtje is in plaats van het uit je hoofd te leren. Stel dat een onderdeel geaccepteerd had moeten worden ($y = +1$) en de score negatief uitviel. $\mathbf{x}$ optellen bij $\mathbf{w}$ verandert de score op datzelfde onderdeel met

wat een positief getal is. De score van het onderdeel dat net fout ging, gaat omhoog, precies de richting die nodig was. De regel is geen heuristiek die iemand heeft gegokt; het is de kleinste verandering die aantoonbaar het geval vóór zich verbetert. Natuurlijk kan hij een ander geval kapotmaken, en daarom ga je nog een ronde.

Let op wat ontbreekt. Er staat nergens een afgeleide. Dat is geen vergissing, en het is het eerste echt belangrijke idee in de cursus.

Wat je zou willen differentiëren is de fout — het aantal verkeerd geclassificeerde onderdelen. Maar dat aantal is een trap: het blijft vlak op 4 terwijl je de lijn een beetje verschuift, en zakt dan naar 3 zodra de lijn een punt kruist. De afgeleide is bijna overal nul en bij de treden ongedefinieerd. Calculus krijgt er geen grip op. De perceptronregel werkt daarom om dat probleem heen door helemaal niet om een helling te vragen: hij vraagt alleen “goed of fout?”, en beweegt in een richting die hij geometrisch kan rechtvaardigen.

Dat is een echte oplossing, en ook een doodlopende weg. In hoofdstuk 2 willen we een loss die ergens vandaan komt in plaats van gekozen wordt, in hoofdstuk 4 een model dat rapporteert hoe zeker het is, en in hoofdstuk 5 iets met meer dan één laag — en geen van die dingen is bereikbaar vanuit een regel die alleen “fout” kent. Een bruikbare helling terugkrijgen is wat de volgende twee hoofdstukken afdwingt. Maar de perceptron mag iets doen wat geen van zijn opvolgers kan: leren zonder enige calculus.

Pure Python, geen NumPy. Lijsten en een loop. NumPy komt in het volgende hoofdstuk, wanneer de rekenkunde niet meer past in een loop die je zou willen lezen; het nu introduceren zou de rekenkunde achter een library verbergen, precies op het moment dat je die wilt zien.

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 vier gemarkeerde regels zijn het algoritme. Al het andere is boekhouding.

En de band, met acht onderdelen die ervan zijn gemeten — vier die zijn verzonden en vier die terugkwamen:

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)

Deze acht onderdelen zijn scheidbaar door een rechte lijn — elk geaccepteerd onderdeel is smaller dan 22 mm en elk afgewezen onderdeel is 23 mm of meer. Een verticale grens bij 22 millimeter doet het werk. Dus de perceptron zou die moeten vinden.

Voer hem uit:

None [-142.1, -13.0] 54.0

Tweehonderd epochs, 454 correcties, en hij is niet geconvergeerd. De gewichten zijn groot en hebben het verkeerde teken. Er is iets mis — behalve dat er niets mis is, en de reden is het nuttigste in dit hoofdstuk.

De perceptron heeft een garantie, bewezen door Novikoff in 1962.¹ Als de data überhaupt door een lijn gescheiden kan worden, maakt het algoritme hoogstens

correcties voordat het er geen meer maakt — waarbij $R$ de straal van de data is, de lengte van de langste voorbeeldvector, en $\gamma$ de margin is: de afstand van het scheidende hypervlak tot het dichtstbijzijnde punt in de uitgebreide ruimte waarin de bias een derde coördinaat is. Daarom verandert het centreren van de data die waarde, terwijl de afstand in millimeters dat niet doet.

De garantie is onvoorwaardelijk en noemt geen epochs, learning rates of geluk. Ze noemt ook geen tijd, en juist die weglating is het punt.

Vul onze getallen in. Rechtstreeks gemeten aan de acht onderdelen, met de bias opgenomen als een constante feature:

De stelling is nooit geschonden. Voer de ruwe versie lang genoeg uit en hij convergeert inderdaad — bij epoch 11.976, na 29.870 correcties — ruimschoots binnen zijn grens van 2.633.550, en die kloof is op zichzelf het punt: de stelling begrenst het slechtste geval, niet het typische geval. Hij had simpelweg zestig keer meer epochs nodig dan iemand zou uitzitten.

De tweede rij is dezelfde acht onderdelen, dezelfde twintig regels code, met drie regels toegevoegd om de gemiddelde breedte en het gemiddelde gewicht van elke meting af te trekken. Dat is alles. Dat is de hele verandering. Het verplaatst de puntenwolk zodat die de oorsprong kruist in plaats van rond (22, 57) te zweven, en het effect op de grens is een factor vijftienduizend, omdat beide termen tegelijk verbeteren: $R$ daalt van 74 naar 13 omdat de punten niet langer vanaf een ver weg gelegen oorsprong worden gemeten, en $\gamma$ stijgt van 0,045 naar 0,989 omdat de margin wordt gemeten tegen een gewichtsvector die geen enorme bias meer hoeft mee te dragen om de data te bereiken.

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

Geconvergeerd in twee epochs, met precies één correctie.

Hier zit een echte les in, en die is niet “vergeet niet je inputs te normaliseren”, al moet je dat wel doen. De les is dat een garantie dat een algoritme eindigt je niets vertelt over of jij erbij bent wanneer dat gebeurt, en dat de kloof tussen die twee meestal geometrie is. Dit is de eerste verschijning van een patroon dat je opnieuw tegenkomt in hoofdstuk 6 bij initialisatie, in hoofdstuk 10 bij learning-rate schedules, en in hoofdstuk 13 bij kwantisatie: de wiskunde zegt dat iets mogelijk is, en de engineering bepaalt of het praktisch is. Een cursus die je alleen de stelling leert, geeft je een model dat drie dagen traint en jou de schuld geeft.

Nu de mislukking die het eerste tijdperk van neural networks beëindigde, en hij past in vier rijen.

Vergeet de fabriek. Neem twee inputs die elk 0 of 1 zijn, en vraag dat het antwoord $+1$ is wanneer precies één ervan 1 is:

Dit is XOR — exclusive or. Teken de vier punten op papier voordat je verder leest: drie hoeken van een eenheidsvierkant en de vierde. Markeer de twee diagonale hoeken $(0,1)$ en $(1,0)$ als accepteren, en $(0,0)$ en $(1,1)$ als afwijzen. Teken nu één rechte lijn met de twee geaccepteerde punten aan de ene kant en de twee afgewezen punten aan de andere.

Dat kan niet. Niet omdat het moeilijk is, of omdat je een slimmer algoritme nodig hebt; de lijn bestaat niet. Drie regels algebra laten zien waarom. Als een perceptron alle vier goed had, dan leveren de vier rijen in volgorde op:

Tel de middelste twee ongelijkheden op: $w_1 + w_2 + 2b \geq 0$, dus $w_1 + w_2 \geq -2b$. De laatste zegt $w_1 + w_2 < -b$. Samen: $-2b \leq w_1 + w_2 < -b$, wat $-2b < -b$ vereist, wat $b > 0$ vereist. En de eerste ongelijkheid zegt $b < 0$. Zo’n $b$ bestaat niet, dus zulke gewichten bestaan niet. Geen enkele perceptron, met wat voor getallen dan ook, classificeert XOR.

Voer hem toch uit, want een algoritme zien falen is meer waard dan te horen krijgen dat het zal falen:

     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

Hij divergeert niet, en hij spartelt ook niet rond in de buurt van een redelijk antwoord. Hij cyclet: hij loopt een korte lus door de gewichtsruimte en komt precies terug waar hij begon, voor altijd, met twee van de vier goed — wat je ook zou halen door te gokken. Honderdduizend epochs en honderd zijn niet van elkaar te onderscheiden, omdat het algoritme geen vooruitgang boekt die een langere run zou kunnen afmaken. Vergelijk dat met de band, die na 200 epochs vast leek te zitten en in werkelijkheid naar een echt antwoord toe aan het malen was. Van buitenaf lijken de twee de eerste paar seconden op elkaar. Ze uit elkaar houden, zonder de stelling, is onmogelijk — nog een argument om de stelling te kennen.

In 1969 publiceerden Marvin Minsky en Seymour Papert Perceptrons, een boeklange wiskundige studie naar precies wat dit model wel en niet kan representeren.² XOR is het meest geciteerde resultaat, en het citaat wordt meestal ingezet als beschuldiging: dat het boek uit rivaliteit of rancune vijftien jaar neural network-onderzoek heeft gedood.

De wiskunde in het boek klopt, en is interessanter dan het XOR-voorbeeld. Minsky en Papert waren niet primair geïnteresseerd in de vraag of één perceptron XOR kon doen; ze waren geïnteresseerd in wat er gebeurt wanneer perceptrons beperkte receptieve velden krijgen — waarbij elke unit slechts een deel van de input ziet — en ze bewezen dat bepaalde globale eigenschappen van een afbeelding, zoals of een figuur verbonden is, op die manier niet kunnen worden berekend, ongeacht hoeveel units je gebruikt. Dat is een echt diep resultaat over localiteit, en het heeft niets te maken met het populaire verhaal.

Het populaire verhaal klopt historisch ook niet. Minsky en Papert bespreken multi-layer perceptrons expliciet en zeggen dat de vraag naar hun kracht open is — ze vermoedden dat uitbreiding van de theorie “steriel” zou zijn, wat een voorspelling is, geen bewijs, en die voorspelling was fout. Wat in 1969 ontbrak was niet het idee om lagen te stapelen; het was een manier om een stack te trainen. De perceptronregel kan dat niet: hij moet weten hoe fout elke unit is, en voor een unit die ergens in het midden begraven zit, is er geen label om mee te vergelijken. Die kloof bleef open totdat backpropagation in 1986 populair werd gemaakt,³ en hem dichten is wat hoofdstuk 5 doet.

De eerlijke samenvatting is dus dit. Het boek bewees een echte beperking van een echt model. De financieringsinstorting van het veld in de jaren zeventig had veel oorzaken, waarvan één was dat de beloften die begin jaren zestig voor perceptrons waren gedaan buitensporig waren geweest. En het technische obstakel was oplosbaar, maar niemand had de tool nog.

De perceptron is achtenzestig jaar oud en je hebt er net een geschreven. Het is de moeite waard om precies te zijn over welke delen ervan nog in de machine zitten waarmee je deze cursus zult eindigen, want het antwoord is: meer dan je zou denken.

De perceptron liep op twee dingen tegelijk vast, en die blijken hetzelfde te zijn.

Hij kan XOR niet representeren, omdat één lijn niet genoeg is. Dat oplossen betekent lagen stapelen — een eerste laag die de ruimte buigt, een tweede die de lijn in de gebogen ruimte tekent. Dat is hoofdstuk 5.

Maar je kunt een stack niet trainen met de perceptronregel, omdat die alleen “fout” kent, en een unit midden in een netwerk geen eigen label heeft om fout over te zijn. Om een stack te trainen moet je weten hoe fout, en in welke richting, voor elk gewicht — je hebt een helling nodig. En de foutfunctie van de perceptron, de trap, heeft er geen.

Dus vóór de stack moet er een loss function zijn met een bruikbare afgeleide. Ook niet eentje die gekozen is omdat hij handig te differentiëren is: eentje die ergens vandaan komt, die iets waars zegt over de data, en waarvan de gradient uit die betekenis volgt in plaats van achteraf te zijn geconstrueerd om er netjes uit te zien.

Dat is hoofdstuk 2, en het begint met een vraag die de perceptron nooit hoefde te beantwoorden: niet “is dit onderdeel goed?”, maar “hoe waarschijnlijk zijn deze metingen, als dit de waarheid is?”

Ook de moeite waard om naast dit hoofdstuk te lezen: Rosenblatts oorspronkelijke paper, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), die leesbaarder is dan zijn reputatie doet vermoeden; McCulloch en Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), de paper die voor het eerst een neuron modelleerde als een drempel op een gewogen som; de perceptronsectie van Hal Daumé III’s A Course in Machine Learning, die dezelfde update met een andere nadruk afleidt; en hoofdstukken 2 en 3 van Deisenroth, Faisal en Ongs Mathematics for Machine Learning voor de lineaire algebra, als het kader hierboven je naar meer liet verlangen dan het gaf.