A perceptron nulláról: mit számol egy neuron

A perceptron veszi a méréseket, mindegyiket megszorozza egy általa szabályozott számmal, összeadja őket, hozzáad még egy számot, majd megnézi az előjelet.

Egy alkatrész méréseit írjuk vektorként: $\mathbf{x} = (x_1, x_2)$ — szélesség és tömeg. A perceptron tartalmaz egy súlyvektort $\mathbf{w} = (w_1, w_2)$ és egy bias értéket $b$. A pontszáma:

és a válasza ennek a pontszámnak az előjele: elfogadás, ha $s(\mathbf{x}) \geq 0$, különben elutasítás.

Ez a teljes modell. Mindaz, amit a perceptron valaha tudni fog a gyárról, három számban él.

Érdemes megállni a geometriánál, mert ez az a kép, amely a következő huszonkilenc fejezetben is működni fog, még akkor is, amikor az egyenletek már nem férnek ki egy sorba. Azoknak a pontoknak a halmaza, ahol $s(\mathbf{x}) = 0$ — ahol a perceptron pontosan bizonytalan — egy egyenes a síkon. Az egyik oldalán a pontszám pozitív, és minden elfogadott; a másikon negatív, és minden elutasított. A tanulás egy perceptron számára azt jelenti: mozgatni ezt az egyenest.

Két tény közvetlenül következik az algebrából erről az egyenesről, és később mindkettő számítani fog:

• $\mathbf{w}$ merőleges rá. A súlyvektor nem a határ mentén fekszik, hanem átszúrja azt, az elfogadott oldal felé mutatva.
• $b$ eltolja anélkül, hogy elforgatná. Bias nélkül az egyenes kénytelen lenne átmenni az origón, ami egy millimétereket és grammokat mérő gyárban abszurd megkötés lenne — azt jelentené, hogy egy nulla szélességű és nulla tömegű alkatrész pontosan a kerítésen ül.

A perceptron semmit sem tudva indul: $\mathbf{w} = (0, 0)$ és $b = 0$. Minden pontszám nulla, ezért mindent elfogad.

Most mutass neki egyszerre egy példát. Az elfogadott alkatrészek címkéje legyen $y = +1$, az elutasítottaké pedig $y = -1$. Minden példánál tegyél fel egy kérdést: helyes lett az előjel? Ennek tömör leírása az, hogy megnézzük, $y \cdot s(\mathbf{x})$ pozitív-e — ha a címke és a pontszám előjele egyezik, a szorzatuk pozitív, ha eltér, negatív.

Ha a válasz igen, semmit sem változtatsz. Ha a válasz nem, mozdítasz rajta:

Ez a teljes algoritmus, és érdemes megérteni, miért ez a megfelelő mozdítás, nem pedig bemagolni. Tegyük fel, hogy egy alkatrészt el kellett volna fogadni ($y = +1$), de a pontszám negatív lett. Ha $\mathbf{x}$-t hozzáadod $\mathbf{w}$-höz, akkor ugyanennek az alkatrésznek a pontszáma ennyivel változik:

ami pozitív szám. Annak az alkatrésznek a pontszáma, amelyet épp rosszul kezelt, felfelé megy, vagyis abba az irányba, amerre mennie kellett. A szabály nem valaki által kitalált heurisztika; ez a legkisebb változtatás, amely bizonyíthatóan javítja az előtte álló esetet. Természetesen elronthat egy másik esetet, ezért mész körbe újra.

Figyeld meg, mi hiányzik. Sehol nincs derivált. Ez nem figyelmetlenség, és ez a kurzus első igazán fontos gondolata.

Amit deriválni szeretnél, az a hiba — a rosszul osztályozott alkatrészek száma. De ez a szám egy lépcső: laposan áll 4-en, miközben mozdítod az egyenest, majd abban a pillanatban leesik 3-ra, amikor az egyenes áthalad egy ponton. A deriváltja szinte mindenhol nulla, a lépcsőknél pedig nincs definiálva. A kalkulusnak nincs mibe kapaszkodnia. A perceptron szabály ezt megkerüli: egyáltalán nem kér meredekséget, csak azt kérdezi: „helyes vagy rossz?”, és olyan irányba mozdul, amelyet geometriailag meg tud indokolni.

Ez valódi megoldás, és egyben zsákutca is. A 2. fejezetben olyan veszteségfüggvényt akarunk majd, amely valahonnan származik, nem pusztán választottuk; a 4. fejezetben olyan modellt, amely megmondja, mennyire biztos; az 5. fejezetben pedig valamit több mint egy réteggel — és egyik sem érhető el olyan szabályból, amely csak annyit tud: „rossz”. A használható meredekség visszaszerzése kényszeríti ki a következő két fejezetet. De a perceptron olyat tehet, amit egyik utódja sem: teljesen kalkulus nélkül tanulhat.

Tiszta Python, NumPy nélkül. Listák és egy ciklus. A NumPy a következő fejezetben érkezik, amikor az aritmetika már nem fér bele olyan ciklusba, amelyet szívesen olvasnál; most bevezetni pontosan akkor rejtené el az aritmetikát egy library mögé, amikor látni akarod.

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

A négy kiemelt sor maga az algoritmus. Minden más könyvelés.

És a futószalag, nyolc róla lemért alkatrésszel — négy, amely kiment, és négy, amely visszajött:

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)

Ez a nyolc alkatrész elválasztható egy egyenessel — minden elfogadott alkatrész 22 mm alatt van, és minden elutasított 23 mm vagy több. Egy függőleges kerítés 22 milliméternél megoldja. Tehát a perceptronnak meg kellene találnia.

Futtasd:

None [-142.1, -13.0] 54.0

Kétszáz epoch, 454 korrekció, és még nem konvergált. A súlyok nagyok, és rossz előjelűek. Valami nincs rendben — kivéve, hogy minden rendben van, és ennek oka a fejezet leghasznosabb tanulsága.

A perceptronnak van garanciája, amelyet Novikoff bizonyított 1962-ben.¹ Ha az adatok egyáltalán elválaszthatók egy egyenessel, az algoritmus legfeljebb ennyi

korrekciót végez, mielőtt már egyet sem kellene — ahol $R$ az adatok sugara, a leghosszabb példavektor hossza, $\gamma$ pedig a margin: a távolság az elválasztó hipersíktól a legközelebbi pontig abban a kibővített térben, ahol a bias egy harmadik koordináta. Ezért változtatja meg az adatok központosítása, miközben a milliméterben mért távolság nem változik.

A garancia feltétel nélküli, és nem említ epochokat, tanulási rátákat vagy szerencsét. De időt sem említ, és éppen ez a lényeg.

Tegyük be a számainkat. Közvetlenül a nyolc alkatrészből mérve, a biast konstans feature-ként behajtva:

A tétel soha nem sérült. Futtasd a nyers verziót elég sokáig, és valóban konvergál — a 11 976. epochban, 29 870 korrekció után — kényelmesen a 2 633 550-es korlátján belül, és ez a rés önmagában is a lényeg: a tétel a legrosszabb esetet korlátozza, nem a tipikust. Egyszerűen hatvanszor több epochra volt szüksége, mint amennyit bárki végigülne.

A második sor ugyanaz a nyolc alkatrész, ugyanaz a húsz sor kód, három hozzáadott sorral, amely minden mérésből kivonja az átlagos szélességet és az átlagos tömeget. Ennyi. Ez a teljes változtatás. Úgy mozgatja el a pontfelhőt, hogy az az origót átszelje, ne pedig valahol (22, 57) körül lebegjen, és a korlátra gyakorolt hatás tizenötezres szorzó, mert mindkét tag egyszerre javul: $R$ 74-ről 13-ra esik, mert a pontokat már nem egy távoli origótól mérjük, $\gamma$ pedig 0,045-ről 0,989-re nő, mert a margint olyan súlyvektorhoz mérjük, amelynek már nem kell hatalmas biast cipelnie ahhoz, hogy elérje az adatokat.

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

Két epoch alatt konvergált, pontosan egyszer javítva magán.

Van itt egy valódi tanulság, és ez nem az, hogy „ne felejtsd el normalizálni a bemeneteket”, bár ezt érdemes megtenned. Hanem az, hogy egy garancia arról, hogy egy algoritmus befejeződik-e, semmit sem mond arról, ott leszel-e még, amikor befejeződik, és hogy a kettő közötti rés általában geometria. Ez az első megjelenése egy mintának, amellyel újra találkozol majd a 6. fejezetben az inicializálásnál, a 10. fejezetben a tanulási ráta ütemezéseknél, és a 13. fejezetben a kvantálásnál: a matematika azt mondja, hogy a dolog lehetséges, az engineering pedig eldönti, hogy praktikus-e. Egy kurzus, amely csak a tételt tanítja meg, olyan modellt ad a kezedbe, amely három napig tanul, aztán téged hibáztat.

Most jön a kudarc, amely lezárta a neurális hálózatok első korszakát, és elfér négy sorban.

Felejtsd el a gyárat. Vegyél két bemenetet, amelyek mindegyike vagy 0, vagy 1, és kérd, hogy a válasz akkor legyen $+1$, amikor pontosan az egyikük 1:

Ez az XOR — kizáró vagy. Mielőtt tovább olvasol, rajzold fel a négy pontot papírra: egy egységnégyzet három sarkát és a negyediket. Jelöld a két átlós sarkot, $(0,1)$-et és $(1,0)$-t elfogadottnak, $(0,0)$-t és $(1,1)$-et elutasítottnak. Most húzz egy egyenest úgy, hogy a két elfogadott pont az egyik oldalán legyen, a két elutasított pedig a másikon.

Nem tudsz. Nem arról van szó, hogy nehéz, vagy hogy okosabb algoritmus kellene; hanem arról, hogy az egyenes nem létezik. Három sor algebra megmutatja, miért. Ha egy perceptron mind a négyet helyesen kezelné, akkor a négy sort sorban olvasva ezt kapnánk:

Add össze a középső két egyenlőtlenséget: $w_1 + w_2 + 2b \geq 0$, tehát $w_1 + w_2 \geq -2b$. Az utolsó azt mondja: $w_1 + w_2 < -b$. Együtt: $-2b \leq w_1 + w_2 < -b$, amihez $-2b < -b$ kell, amihez $b > 0$ kell. Az első egyenlőtlenség pedig azt mondja: $b < 0$. Ilyen $b$ nincs, tehát ilyen súlyok sincsenek. Semmilyen perceptron, bármilyen számokkal, nem osztályozza az XOR-t.

Futtasd azért, mert többet ér látni egy algoritmust elbukni, mint csak hallani, hogy el fog:

     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

Nem divergál, és nem is vergődik egy valamirevaló válasz közelében. Ciklizál: rövid hurkot jár be a súlytérben, majd pontosan oda tér vissza, ahonnan indult, örökké, négyből kettőt eltalálva — amit találgatással is elérnél. Százezer epoch és száz megkülönböztethetetlen, mert az algoritmus nem tesz olyan előrehaladást, amelyet egy hosszabb futás befejezhetne. Hasonlítsd ezt össze a futószalaggal, amely 200 epochnál beragadtnak tűnt, valójában viszont egy valódi válasz felé őrlődött. Kívülről az első néhány másodpercben a kettő hasonlónak látszik. Megkülönböztetni őket a tétel nélkül lehetetlen — ami még egy érv amellett, hogy ismerd a tételt.

1969-ben Marvin Minsky és Seymour Papert kiadták a Perceptrons című, könyvnyi terjedelmű matematikai vizsgálatot arról, pontosan mit tud és mit nem tud reprezentálni ez a modell.² Az XOR a legtöbbet idézett eredménye, és az idézetet általában vádként használják: hogy a könyv rivalizálásból vagy rosszindulatból tizenöt évre megölte a neurális hálózatok kutatását.

A könyv matematikája helyes, és érdekesebb is, mint az XOR-példa. Minskyt és Papertet nem elsősorban az érdekelte, hogy egyetlen perceptron képes-e XOR-t számolni; az érdekelte őket, mi történik, amikor a perceptronok korlátozott receptive fieldeket kapnak — minden egység csak a bemenet egy részét látja —, és bebizonyították, hogy egy kép bizonyos globális tulajdonságai, például hogy egy alakzat összefüggő-e, így nem számíthatók ki, függetlenül attól, hány egységet használsz. Ez valóban mély eredmény a lokalitásról, és semmi köze a népszerű történethez.

A népszerű történet történelmileg is téves. Minsky és Papert kifejezetten tárgyalják a többrétegű perceptronokat, és azt mondják, hogy az erejük kérdése nyitott — sejtették, hogy az elmélet kiterjesztése „steril” lenne, ami jóslat, nem bizonyítás, és téves volt. Ami 1969-ben hiányzott, az nem a rétegek egymásra pakolásának ötlete volt; hanem egy mód arra, hogy betanítsunk egy ilyen stacket. A perceptron szabály erre nem képes: tudnia kellene, mennyire téved az egyes egység, egy középen eltemetett egységnek pedig nincs címkéje, amelyhez hasonlíthatná magát. Ez a rés egészen addig nyitva maradt, amíg a backpropagation 1986-ban népszerűvé nem vált,³ és ennek lezárása az 5. fejezet feladata.

A tisztességes összegzés tehát ez. A könyv egy valódi modell valódi korlátját bizonyította. A terület finanszírozási összeomlásának a hetvenes években sok oka volt, ezek egyike az, hogy a perceptronokkal kapcsolatban a korai hatvanas években tett ígéretek túlzóak voltak. A technikai akadály pedig megoldható volt, csak még senkinél nem volt meg az eszköz.

A perceptron hatvannyolc éves, és most írtál egyet. Érdemes pontosan megfogalmazni, mely részei vannak még mindig abban a gépben, amellyel a kurzus végére elkészülsz, mert a válasz: több, mint gondolnád.

A perceptron egyszerre két dolgon akadt el, és ezekről kiderül, hogy ugyanazok.

Nem tudja reprezentálni az XOR-t, mert egy egyenes nem elég. Ennek javítása rétegek egymásra rakását jelenti — egy első réteget, amely meghajlítja a teret, és egy másodikat, amely egyenest húz a meghajlított térben. Ez az 5. fejezet.

De a perceptron szabállyal nem tudsz stacket tanítani, mert az csak annyit tud: „rossz”, és egy hálózat közepén lévő egységnek nincs saját címkéje, amelyhez képest rossz lehetne. Egy stack tanításához minden súlynál tudnod kell, mennyire rossz, és melyik irányba — meredekségre van szükséged. A perceptron hibafüggvényének, a lépcsőnek pedig nincs ilyenje.

Ezért a stack előtt szükség van egy használható deriválttal rendelkező veszteségfüggvényre. Nem olyanra, amelyet csak azért választunk, mert kényelmes deriválni: olyanra, amely valahonnan származik, igazat mond az adatokról, és amelynek gradientje a jelentéséből következik, nem pedig visszafelé terveztük meg, hogy szépnek tűnjön.

Ez a 2. fejezet, és egy olyan kérdéssel indul, amelyre a perceptronnak soha nem kellett válaszolnia: nem azzal, hogy „jó ez az alkatrész?”, hanem azzal, hogy „mennyire valószínűek ezek a leolvasások, ha ez az igazság?”

A fejezet mellé érdemes olvasni Rosenblatt eredeti cikkét is, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), amely olvashatóbb, mint a híre alapján gondolnád; McCulloch és Pitts cikkét, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), amely először modellezett egy neuront súlyozott összeg feletti küszöbként; Hal Daumé III A Course in Machine Learning című munkájának perceptronról szóló szakaszát, amely ugyanazt a frissítést más hangsúllyal vezeti le; valamint Deisenroth, Faisal és Ong Mathematics for Machine Learning című könyvének 2. és 3. fejezetét a lineáris algebrához, ha a fenti doboz kevesebbet adott, mint amennyit szerettél volna.