Perceptronen från grunden: vad ett neuron beräknar

En perceptron tar mätvärdena, multiplicerar vart och ett med ett tal den styr, adderar dem, lägger till ett tal till och tittar på tecknet.

Skriv mätvärdena för en del som en vektor $\mathbf{x} = (x_1, x_2)$ — bredd och vikt. Perceptronen har en viktvektor $\mathbf{w} = (w_1, w_2)$ och en bias $b$. Dess poäng är

och dess svar är tecknet på den poängen: acceptera om $s(\mathbf{x}) \geq 0$, annars avvisa.

Det är hela modellen. Allt perceptronen någonsin kommer att veta om fabriken bor i tre tal.

Geometrin är värd att stanna upp vid, eftersom det är bilden som fortsätter fungera i de kommande tjugonio kapitlen även när ekvationerna slutar få plats på en rad. Mängden punkter där $s(\mathbf{x}) = 0$ — där perceptronen är exakt obeslutsam — är en rät linje i planet. På ena sidan är poängen positiv och allt accepteras; på den andra är den negativ och allt avvisas. För en perceptron betyder inlärning att flytta den linjen.

Två fakta om den linjen följer direkt av algebran, och båda spelar roll senare:

• $\mathbf{w}$ är vinkelrät mot den. Viktvektorn ligger inte längs gränsen, den pekar tvärs över den, mot den accepterade sidan.
• $b$ skjuter den utan att vrida den. Utan en bias skulle linjen tvingas gå genom origo, vilket för en fabrik som mäter millimeter och gram vore en absurd begränsning — det skulle betyda att en del med noll bredd och noll vikt sitter exakt på staketet.

Perceptronen börjar utan att veta något: $\mathbf{w} = (0, 0)$ och $b = 0$. Varje poäng är noll, så den accepterar allt.

Visa den nu ett exempel i taget. Märk de accepterade delarna $y = +1$ och de avvisade $y = -1$. För varje exempel, ställ en fråga: blev tecknet rätt? Det kompakta sättet att skriva den frågan är att kontrollera om $y \cdot s(\mathbf{x})$ är positivt — om etiketten och poängen har samma tecken är deras produkt positiv, och om de inte stämmer överens är den negativ.

Om svaret är ja, ändra inget. Om svaret är nej, knuffa:

Det är hela algoritmen, och det är värt att förstå varför det är rätt knuff i stället för att memorera den. Anta att en del borde ha accepterats ($y = +1$) och poängen blev negativ. Att lägga till $\mathbf{x}$ till $\mathbf{w}$ ändrar poängen på samma del med

vilket är ett positivt tal. Poängen på delen den just fick fel går upp, vilket är riktningen den behövde gå. Regeln är inte en heuristic någon gissade fram; den är den minsta förändringen som bevisbart förbättrar fallet framför den. Den kan förstås förstöra ett annat fall, vilket är varför du går runt igen.

Lägg märke till vad som saknas. Det finns ingen derivata någonstans. Det är ingen förbiseelse, och det är den första verkligt viktiga idén i kursen.

Det du skulle vilja derivera är felet — antalet felklassificerade delar. Men det antalet är en trappa: det ligger platt på 4 medan du knuffar linjen, och faller sedan till 3 i samma ögonblick som linjen korsar en punkt. Dess derivata är noll nästan överallt och odefinierad vid stegen. Kalkylen får inget grepp. Perceptronregeln arbetar runt det genom att inte fråga efter någon lutning alls: den frågar bara ”rätt eller fel?”, och rör sig i en riktning den kan motivera geometriskt.

Det är en verklig lösning, och det är också en återvändsgränd. I kapitel 2 kommer vi att vilja ha en loss som kommer någonstans ifrån i stället för att väljas, i kapitel 4 en modell som rapporterar hur säker den är, och i kapitel 5 något med mer än ett lager — och inget av dem går att nå från en regel som bara känner till ”fel”. Att få tillbaka en användbar lutning är det som tvingar fram de kommande två kapitlen. Men perceptronen får göra något som ingen av dess efterföljare kan: lära sig helt utan kalkyl.

Ren Python, ingen NumPy. Listor och en loop. NumPy kommer i nästa kapitel, där aritmetiken slutar få plats i en loop du skulle vilja läsa; att introducera det nu skulle gömma aritmetiken bakom ett bibliotek exakt i det ögonblick då du vill 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 fyra markerade raderna är algoritmen. Allt annat är bokföring.

Och bandet, med åtta delar uppmätta från det — fyra som levererades och fyra som kom tillbaka:

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)

De här åtta delarna är separerbara med en rät linje — varje accepterad del är under 22 mm och varje avvisad är 23 mm eller mer. Ett lodrätt staket vid 22 millimeter gör jobbet. Så perceptronen borde hitta det.

Kör den:

None [-142.1, -13.0] 54.0

Tvåhundra epoker, 454 korrigeringar, och den har inte konvergerat. Vikterna är stora och har fel tecken. Något är fel — förutom att inget är fel, och skälet är det mest användbara i det här kapitlet.

Perceptronen har en garanti, bevisad av Novikoff 1962.¹ Om datan alls kan separeras med en linje gör algoritmen högst

korrigeringar innan den slutar göra några — där $R$ är datans radie, längden på den längsta exempel-vektorn, och $\gamma$ är marginalen: avståndet från det separerande hyperplanet till den närmaste punkten i det utökade rummet där bias är en tredje koordinat. Det är därför centrering av datan ändrar det medan avståndet i millimeter inte gör det.

Garantin är ovillkorlig och nämner inte epoker, learning rates eller tur. Den nämner inte heller tid, och den utelämningen är poängen.

Sätt in våra tal. Mätt direkt från de åtta delarna, med bias invikt som en konstant feature:

Satsen bröts aldrig. Kör den råa versionen länge nog och den konvergerar — vid epok 11 976, efter 29 870 korrigeringar — bekvämt inom sin gräns på 2 633 550, och det gapet är i sig poängen: satsen begränsar värsta fallet, inte det typiska. Den behövde helt enkelt sextio gånger fler epoker än någon skulle orka sitta igenom.

Den andra raden är samma åtta delar, samma tjugo rader kod, med tre rader tillagda för att dra bort medelbredden och medelvikten från varje mätning. Det är allt. Det är hela förändringen. Den flyttar punktmolnet så att det grenslar origo i stället för att sväva ute vid (22, 57), och effekten på gränsen är en faktor femton tusen, eftersom båda termerna förbättras samtidigt: $R$ faller från 74 till 13 eftersom punkterna inte längre mäts från ett avlägset origo, och $\gamma$ stiger från 0,045 till 0,989 eftersom marginalen mäts mot en viktvektor som inte längre måste bära en enorm bias för att nå datan.

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

Konvergerade på två epoker, efter att ha korrigerat sig exakt en gång.

Det finns en verklig lärdom här och den är inte ”kom ihåg att normalisera dina inputs”, även om du bör göra det. Den är att en garanti om huruvida en algoritm avslutas säger ingenting om huruvida du kommer att vara där när den gör det, och att gapet mellan de två oftast är geometri. Det här är första gången ett mönster dyker upp som du kommer att möta igen i kapitel 6 med initialisering, i kapitel 10 med learning-rate schedules, och i kapitel 13 med kvantisering: matematiken säger att saken är möjlig, och ingenjörsarbetet avgör om den är praktisk. En kurs som bara lär dig satsen ger dig en modell som tränar i tre dagar och skyller på dig.

Nu kommer misslyckandet som avslutade den första eran av neurala nätverk, och det ryms på fyra rader.

Glöm fabriken. Ta två inputs som vardera är antingen 0 eller 1, och be svaret vara $+1$ när exakt en av dem är 1:

Det här är XOR — exklusivt eller. Innan du läser vidare, rita de fyra punkterna på papper: tre hörn av en enhetskvadrat och det fjärde. Markera de två diagonala hörnen $(0,1)$ och $(1,0)$ som accepterade, och $(0,0)$ och $(1,1)$ som avvisade. Rita nu en rät linje med de två accepterade punkterna på ena sidan och de två avvisade på den andra.

Det går inte. Det är inte att det är svårt, eller att du behöver en smartare algoritm; det är att linjen inte finns. Tre rader algebra visar varför. Om en perceptron fick alla fyra rätt, så ger de fyra raderna i ordning

Addera de två mittersta olikheterna: $w_1 + w_2 + 2b \geq 0$, alltså $w_1 + w_2 \geq -2b$. Den sista säger $w_1 + w_2 < -b$. Tillsammans: $-2b \leq w_1 + w_2 < -b$, vilket kräver $-2b < -b$, vilket kräver $b > 0$. Och den första olikheten säger $b < 0$. Det finns ingen sådan $b$, så det finns inga sådana vikter. Ingen perceptron, med några tal över huvud taget, klassificerar XOR.

Kör den ändå, för att se en algoritm misslyckas är mer värt än att få veta att den kommer att göra det:

     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 divergerar inte, och den kastar sig inte runt nära ett hyfsat svar. Den cyklar: den går en kort loop genom viktrummet och kommer tillbaka till exakt där den började, för alltid, och får två av fyra rätt — vilket är vad du skulle få genom att gissa. Hundratusen epoker och hundra går inte att skilja åt, eftersom algoritmen inte gör framsteg som en längre körning skulle kunna slutföra. Jämför det med bandet, som såg fast ut vid 200 epoker men i själva verket malde sig mot ett riktigt svar. Utifrån ser de två likadana ut de första sekunderna. Att skilja dem åt, utan satsen, är omöjligt — vilket är ännu ett argument för att känna till satsen.

1969 publicerade Marvin Minsky och Seymour Papert Perceptrons, en matematisk studie i bokformat av exakt vad den här modellen kan och inte kan representera.² XOR är dess mest citerade resultat, och citatet används oftast som en anklagelse: att boken dödade forskningen om neurala nätverk i femton år av rivalitet eller illvilja.

Matematiken i boken är korrekt, och den är mer intressant än XOR-exemplet. Minsky och Papert var inte främst intresserade av huruvida en enskild perceptron kunde göra XOR; de var intresserade av vad som händer när perceptroner får begränsade receptiva fält — där varje enhet bara ser en del av inputen — och de bevisade att vissa globala egenskaper hos en bild, till exempel om en figur hänger ihop, inte kan beräknas på det sättet oavsett hur många enheter du använder. Det är ett genuint djupt resultat om lokalitet, och det har inget med den populära berättelsen att göra.

Den populära berättelsen har också fel om historien. Minsky och Papert diskuterar uttryckligen flerlagersperceptroner och säger att frågan om deras kraft är öppen — de misstänkte att en utvidgning av teorin skulle vara ”steril”, vilket är en förutsägelse, inte ett bevis, och den var fel. Det som saknades 1969 var inte idén att stapla lager; det var ett sätt att träna en stack. Perceptronregeln kan inte göra det: den behöver veta hur fel varje enhet har, och för en enhet begravd i mitten finns ingen etikett att jämföra med. Det gapet förblev öppet tills backpropagation populariserades 1986,³ och att stänga det är vad kapitel 5 gör.

Så den ärliga sammanfattningen är denna. Boken bevisade en verklig begränsning hos en verklig modell. Finansieringskollapsen för fältet på sjuttiotalet hade många orsaker, varav en var att löftena som givits för perceptroner i början av sextiotalet hade varit extravaganta. Och det tekniska hindret gick att lösa, men ingen hade verktyget ännu.

Perceptronen är sextioåtta år gammal och du har just skrivit en. Det är värt att vara precis med vilka delar av den som fortfarande finns i maskinen du kommer att avsluta den här kursen med, eftersom svaret är: mer än du skulle gissa.

Perceptronen fastnade på två saker samtidigt, och de visar sig vara samma sak.

Den kan inte representera XOR, eftersom en linje inte räcker. Att fixa det betyder att stapla lager — ett första lager som böjer rummet, ett andra som ritar linjen i det böjda rummet. Det är kapitel 5.

Men du kan inte träna en stack med perceptronregeln, eftersom den bara känner till ”fel”, och en enhet mitt i ett nätverk har ingen egen etikett att ha fel om. För att träna en stack måste du veta hur fel, och i vilken riktning, för varje vikt — du behöver en lutning. Och perceptronens felfunktion, trappan, har ingen.

Så före stacken måste det finnas en loss function med en användbar derivata. Inte heller en som väljs för att den är bekväm att derivera: en som kommer någonstans ifrån, som säger något sant om datan, och vars gradient faller ut ur den innebörden i stället för att baklänges konstrueras för att se prydlig ut.

Det är kapitel 2, och det börjar med att ställa en fråga som perceptronen aldrig behövde besvara: inte ”är den här delen bra?”, utan ”hur sannolika är de här avläsningarna, om detta är sanningen?”

Också värt att läsa bredvid det här kapitlet: Rosenblatts ursprungliga artikel, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), som är mer läsbar än sitt rykte antyder; McCulloch och Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), artikeln som först modellerade ett neuron som en tröskel över en viktad summa; perceptronavsnittet i Hal Daumé III:s A Course in Machine Learning, som härleder samma uppdatering med en annan betoning; och kapitel 2 och 3 i Deisenroth, Faisal och Ongs Mathematics for Machine Learning för den linjära algebran, om rutan ovan gjorde att du ville ha mer än den gav.