Perceptron alusta alkaen: mitä neuroni laskee

Perceptron ottaa mittaukset, kertoo jokaisen hallitsemallaan luvulla, laskee ne yhteen, lisää vielä yhden luvun ja katsoo etumerkkiä.

Kirjoita yhden osan mittaukset vektorina $\mathbf{x} = (x_1, x_2)$ — leveys ja paino. Perceptronilla on painovektori $\mathbf{w} = (w_1, w_2)$ ja bias $b$. Sen pistemäärä on

ja sen vastaus on tuon pistemäärän etumerkki: hyväksy, jos $s(\mathbf{x}) \geq 0$, muuten hylkää.

Siinä on koko malli. Kaikki, mitä perceptron koskaan tietää tehtaasta, elää kolmessa luvussa.

Geometriaan kannattaa pysähtyä, koska sama kuva toimii seuraavat kaksikymmentäyhdeksän lukua silloinkin, kun yhtälöt eivät enää mahdu yhdelle riville. Pistejoukko, jossa $s(\mathbf{x}) = 0$ — jossa perceptron on täsmälleen epävarma — on tasossa suora viiva. Toisella puolella pistemäärä on positiivinen ja kaikki hyväksytään; toisella se on negatiivinen ja kaikki hylätään. Perceptronille oppiminen tarkoittaa tuon suoran siirtämistä.

Tuosta suorasta seuraa suoraan algebrasta kaksi faktaa, ja molemmilla on myöhemmin merkitystä:

• $\mathbf{w}$ on kohtisuorassa sitä vastaan. Painovektori ei kulje rajaa pitkin, vaan osoittaa sen poikki kohti hyväksyttyä puolta.
• $b$ liu'uttaa sitä kääntämättä sitä. Ilman biasia suora olisi pakotettu kulkemaan origon kautta, mikä millimetrejä ja grammoja mittaavassa tehtaassa olisi absurdi rajoite — se tarkoittaisi, että nollalevyinen ja nollapainoinen osa istuu täsmälleen aidalla.

Perceptron aloittaa tietämättä mitään: $\mathbf{w} = (0, 0)$ ja $b = 0$. Jokainen pistemäärä on nolla, joten se hyväksyy kaiken.

Näytä sille nyt yksi esimerkki kerrallaan. Merkitse hyväksytyt osat $y = +1$ ja hylätyt $y = -1$. Kysy jokaiselle esimerkille yksi kysymys: tuliko etumerkki oikein? Tiivis tapa kirjoittaa kysymys on tarkistaa, onko $y \cdot s(\mathbf{x})$ positiivinen — jos label ja pistemäärä ovat etumerkiltään samaa mieltä, niiden tulo on positiivinen, ja jos ne ovat eri mieltä, se on negatiivinen.

Jos vastaus on kyllä, älä muuta mitään. Jos vastaus on ei, tönäise:

Siinä on koko algoritmi, ja kannattaa ymmärtää miksi se on oikea tönäisy eikä vain opetella sitä ulkoa. Oletetaan, että osa olisi pitänyt hyväksyä ($y = +1$) ja pistemäärä oli negatiivinen. Kun $\mathbf{x}$ lisätään kohtaan $\mathbf{w}$, saman osan pistemäärä muuttuu näin:

mikä on positiivinen luku. Sen juuri väärin luokitteleman osan pistemäärä nousee ylös, eli siihen suuntaan kuin sen piti mennä. Sääntö ei ole jonkun arvaama heuristiikka; se on pienin muutos, joka todistettavasti parantaa edessä olevaa tapausta. Se voi tietenkin rikkoa jonkin toisen tapauksen, minkä vuoksi kierretään uudelleen.

Huomaa, mitä puuttuu. Missään ei ole derivaattaa. Tämä ei ole vahinko, ja se on kurssin ensimmäinen aidosti tärkeä idea.

Se, mitä haluaisit derivoida, on virhe — väärin luokiteltujen osien määrä. Mutta tuo määrä on porrasfunktio: se pysyy tasaisena arvossa 4, kun tönäiset suoraa, ja putoaa arvoon 3 heti kun suora ylittää pisteen. Sen derivaatta on nolla lähes kaikkialla ja määrittelemätön portaissa. Analyysilla ei ole mistä saada otetta. Perceptronin sääntö kiertää tämän niin, ettei se kysy kulmakerrointa lainkaan: se kysyy vain "oikein vai väärin?" ja liikkuu suuntaan, jonka se voi perustella geometrisesti.

Se on todellinen ratkaisu, ja samalla umpikuja. Luvussa 2 haluamme lossin, joka tulee jostakin eikä vain valita, luvussa 4 mallin, joka kertoo kuinka varma se on, ja luvussa 5 jotakin, jossa on useampi kuin yksi kerros — eikä mikään niistä ole tavoitettavissa säännöstä, joka tuntee vain sanan "väärin". Käyttökelpoisen kulmakertoimen saaminen takaisin pakottaa seuraavat kaksi lukua. Mutta perceptron saa tehdä jotakin, mihin yksikään sen seuraajista ei pysty: oppia täysin ilman analyysia.

Puhdasta Pythonia, ei NumPyä. Listoja ja silmukka. NumPy saapuu seuraavassa luvussa, jossa aritmetiikka ei enää mahdu silmukkaan, jota haluaisit lukea; sen esittely nyt piilottaisi aritmetiikan kirjaston taakse juuri sillä hetkellä, kun haluat nähdä sen.

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

Neljä korostettua riviä ovat algoritmi. Kaikki muu on kirjanpitoa.

Ja hihna, jolta on mitattu kahdeksan osaa — neljä, jotka lähetettiin, ja neljä, jotka palautettiin:

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)

Nämä kahdeksan osaa ovat erotettavissa suoralla viivalla — jokainen hyväksytty osa on alle 22 mm ja jokainen hylätty vähintään 23 mm. Pystysuora aita 22 millimetrin kohdalla hoitaa työn. Perceptronin pitäisi siis löytää se.

Aja se:

None [-142.1, -13.0] 54.0

Kaksisataa epochia, 454 korjausta, eikä se ole konvergoitunut. Painot ovat suuria ja vääränmerkkisiä. Jokin on vialla — paitsi ettei mikään ole vialla, ja syy on tämän luvun hyödyllisin asia.

Perceptronilla on takuu, jonka Novikoff todisti vuonna 1962.¹ Jos data voidaan ylipäätään erottaa suoralla, algoritmi tekee enintään

korjausta ennen kuin se lakkaa tekemästä niitä — missä $R$ on datan säde, eli pisimmän esimerkkivektorin pituus, ja $\gamma$ on margin: etäisyys erottavasta hypertasosta lähimpään pisteeseen laajennetussa avaruudessa, jossa bias on kolmas koordinaatti. Siksi datan keskittäminen muuttaa sitä, vaikka etäisyys millimetreissä ei muutu.

Takuu on ehdoton, eikä se mainitse epocheja, oppimisnopeuksia tai onnea. Se ei myöskään mainitse aikaa, ja juuri se on asian ydin.

Sijoitetaan lukumme. Suoraan kahdeksasta osasta mitattuna, bias taitettuna mukaan vakiopiirteenä:

Teoreemaa ei koskaan rikottu. Aja raakaa versiota tarpeeksi pitkään, ja se konvergoituu — epochilla 11 976, 29 870 korjauksen jälkeen — mukavasti rajansa 2 633 550 sisällä, ja tuo kuilu on itsessään asian ydin: teoreema rajoittaa pahimman tapauksen, ei tyypillistä. Se vain tarvitsi kuusikymmentä kertaa enemmän epocheja kuin kukaan jaksaisi odottaa.

Toinen rivi on samat kahdeksan osaa, samat kaksikymmentä riviä koodia, ja kolme lisäriviä, jotka vähentävät jokaisesta mittauksesta leveyden keskiarvon ja painon keskiarvon. Siinä kaikki. Se on koko muutos. Se siirtää pistepilven niin, että se asettuu origon molemmin puolin sen sijaan, että leijuisi kohdassa (22, 57), ja vaikutus rajaan on viisitoistatuhatkertainen, koska molemmat termit paranevat yhtä aikaa: $R$ putoaa 74:stä 13:een, koska pisteitä ei enää mitata kaukaisesta origosta, ja $\gamma$ nousee 0,045:stä 0,989:ään, koska margin mitataan painovektoria vasten, jonka ei enää tarvitse kantaa valtavaa biasia yltääkseen dataan.

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

Konvergoitui kahdessa epochissa ja korjasi itseään täsmälleen kerran.

Tässä on todellinen opetus, eikä se ole "muista normalisoida syötteesi", vaikka niin kannattaakin tehdä. Se on tämä: takuu siitä, päättyykö algoritmi, ei kerro mitään siitä, oletko paikalla kun se päättyy, ja näiden kahden välinen kuilu on yleensä geometriaa. Tämä on ensimmäinen esiintymä kaavasta, jonka kohtaat uudelleen luvussa 6 alustuksen kanssa, luvussa 10 oppimisnopeusaikataulujen kanssa ja luvussa 13 kvantisoinnin kanssa: matematiikka sanoo, että asia on mahdollinen, ja suunnittelu päättää, onko se käytännöllinen. Kurssi, joka opettaa sinulle vain teoreeman, ojentaa mallin, joka treenaa kolme päivää ja syyttää sinua.

Nyt epäonnistuminen, joka päätti neuroverkkojen ensimmäisen aikakauden, ja se mahtuu neljään riviin.

Unohda tehdas. Ota kaksi syötettä, joista kumpikin on joko 0 tai 1, ja pyydä vastaukseksi $+1$ silloin, kun täsmälleen toinen niistä on 1:

Tämä on XOR — poissulkeva tai. Ennen kuin luet eteenpäin, piirrä neljä pistettä paperille: yksikköneliön kolme kulmaa ja neljäs. Merkitse kaksi diagonaalista kulmaa $(0,1)$ ja $(1,0)$ hyväksytyiksi ja $(0,0)$ ja $(1,1)$ hylätyiksi. Piirrä nyt yksi suora viiva, jonka toisella puolella ovat kaksi hyväksyttyä pistettä ja toisella kaksi hylättyä.

Et pysty. Kyse ei ole siitä, että se olisi vaikeaa tai että tarvitsisit nokkelamman algoritmin; suoraa ei ole olemassa. Kolme riviä algebraa näyttää miksi. Jos perceptron saisi kaikki neljä oikein, neljän rivin lukeminen järjestyksessä antaisi

Lisää keskimmäiset kaksi epäyhtälöä: $w_1 + w_2 + 2b \geq 0$, joten $w_1 + w_2 \geq -2b$. Viimeinen sanoo $w_1 + w_2 < -b$. Yhdessä: $-2b \leq w_1 + w_2 < -b$, mikä vaatii $-2b < -b$, mikä vaatii $b > 0$. Ja ensimmäinen epäyhtälö sanoo $b < 0$. Sellaista $b$ ei ole, joten sellaisia painoja ei ole. Mikään perceptron millään luvuilla ei luokittele XORia.

Aja se silti, koska algoritmin epäonnistumisen katsominen on arvokkaampaa kuin kuulla, että se epäonnistuu:

     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

Se ei hajaannu eikä pyöri lähellä kelvollista vastausta. Se kiertää syklissä: se kulkee lyhyen lenkin painoavaruudessa ja palaa täsmälleen lähtöpaikkaansa ikuisesti, saaden kaksi neljästä oikein — saman kuin arvaamalla. Satatuhatta epochia ja sata ovat erottamattomia, koska algoritmi ei etene kohti jotakin, jonka pidempi ajo voisi viimeistellä. Vertaa tätä hihnaan, joka näytti jumittuneelta 200 epochin kohdalla ja jauhoi todellisuudessa kohti oikeaa vastausta. Ulkoa katsottuna nämä kaksi näyttävät ensimmäiset sekunnit samanlaisilta. Niiden erottaminen ilman teoreemaa on mahdotonta — mikä on yksi lisäperuste teoreeman tuntemiselle.

Vuonna 1969 Marvin Minsky ja Seymour Papert julkaisivat teoksen Perceptrons, kirjan mittaisen matemaattisen tutkimuksen täsmälleen siitä, mitä tämä malli voi ja ei voi esittää.² XOR on sen siteeratuin tulos, ja sitaattia käytetään yleensä syytöksenä: että kirja tappoi neuroverkkotutkimuksen viideksitoista vuodeksi kilpailun tai pahantahtoisuuden takia.

Kirjan matematiikka on oikein, ja se on kiinnostavampaa kuin XOR-esimerkki. Minskyä ja Papertia ei ensisijaisesti kiinnostanut, voiko yksittäinen perceptron tehdä XORin; heitä kiinnosti, mitä tapahtuu, kun perceptroneille annetaan rajoitetut vastaanottokentät — jokainen yksikkö näkee vain osan syötteestä — ja he todistivat, että tiettyjä kuvan globaaleja ominaisuuksia, kuten onko kuvio yhtenäinen, ei voi laskea sillä tavalla riippumatta siitä, kuinka monta yksikköä käytät. Se on aidosti syvä tulos paikallisuudesta, eikä sillä ole mitään tekemistä suositun tarinan kanssa.

Suosittu tarina on väärässä myös historian suhteen. Minsky ja Papert käsittelevät eksplisiittisesti monikerroksisia perceptroneja ja sanovat, että kysymys niiden voimasta on avoin — he epäilivät teorian laajentamisen olevan "steriiliä", mikä on ennuste, ei todistus, ja se oli väärä. Vuonna 1969 puuttui ei idea kerrosten pinoamisesta, vaan tapa kouluttaa pino. Perceptronin sääntö ei pysty siihen: sen täytyy tietää, kuinka väärässä kukin yksikkö on, eikä keskelle haudatulla yksiköllä ole labelia, johon verrata. Tuo aukko pysyi avoinna, kunnes backpropagation popularisoitiin vuonna 1986,³ ja sen sulkeminen on luvun 5 tehtävä.

Rehellinen yhteenveto on siis tämä. Kirja todisti todellisen mallin todellisen rajoitteen. Alan rahoituksen romahduksella 1970-luvulla oli monta syytä, joista yksi oli se, että perceptroneista 1960-luvun alussa annetut lupaukset olivat olleet ylenpalttisia. Ja tekninen este oli ratkaistavissa, mutta kenelläkään ei vielä ollut työkalua.

Perceptron on kuusikymmentäkahdeksan vuotta vanha, ja kirjoitit juuri sellaisen. Kannattaa olla täsmällinen siitä, mitkä sen osat ovat yhä koneessa, jonka tämän kurssin lopussa saat valmiiksi, koska vastaus on: enemmän kuin arvaat.

Perceptron jäi jumiin kahteen asiaan yhtä aikaa, ja ne osoittautuvat samaksi asiaksi.

Se ei voi esittää XORia, koska yksi suora ei riitä. Sen korjaaminen tarkoittaa kerrosten pinoamista — ensimmäinen kerros taivuttaa avaruutta, toinen piirtää suoran taivutettuun avaruuteen. Se on luku 5.

Mutta pinoa ei voi kouluttaa perceptronin säännöllä, koska se tuntee vain sanan "väärin", eikä verkon keskellä olevalla yksiköllä ole omaa labelia, josta se voisi olla väärässä. Pinon kouluttamiseen täytyy tietää kuinka väärin ja mihin suuntaan, jokaiselle painolle — tarvitset kulmakertoimen. Ja perceptronin virhefunktiolla, portaikolla, ei ole sellaista.

Ennen pinoa tarvitaan siis loss-funktio, jolla on käyttökelpoinen derivaatta. Eikä sellainen, joka valitaan siksi, että se on kätevä derivoida: sellainen, joka tulee jostakin, joka sanoo jotakin totta datasta ja jonka gradientti putoaa ulos tuosta merkityksestä sen sijaan, että se olisi käänteissuunniteltu näyttämään siistiltä.

Se on luku 2, ja se alkaa kysymällä kysymyksen, johon perceptronin ei koskaan tarvinnut vastata: ei "onko tämä osa hyvä?", vaan "kuinka todennäköisiä nämä lukemat ovat, jos tämä on totuus?"

Tämän luvun rinnalla kannattaa lukea myös Rosenblattin alkuperäinen artikkeli The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), joka on luettavampi kuin maineensa antaa ymmärtää; McCulloch ja Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), artikkeli, joka mallinsi ensimmäisenä neuronin kynnykseksi painotetun summan yli; Hal Daumé III:n A Course in Machine Learning -teoksen perceptron-osio, joka johtaa saman päivityksen eri painotuksella; sekä Deisenrothin, Faisalin ja Ongin Mathematics for Machine Learning -teoksen luvut 2 ja 3 lineaarialgebraa varten, jos yllä oleva laatikko jätti kaipaamaan enemmän kuin se antoi.