Backpropagation alusta asti: ensin moottori, sitten verkko

Ennen koneen rakentamista yksi kysymys on ratkaistava, koska jos vastaus olisi toisenlainen, mitään rakennettavaa ei olisi.

Perceptron epäonnistui XOR:ssa, koska yksi suora ei voi erottaa neljää pistettä. Ilmeinen korjaus on pinoaminen: aja syöte yhden lineaarisen kerroksen läpi ja sitten toisen. Auttaako se?

Ei, ja todistus on kahden rivin mittainen. Lineaarinen kerros on $\mathbf{h} = W_1\mathbf{x} + \mathbf{b}_1$. Syötä se toiseen, $\mathbf{y} = W_2\mathbf{h} + \mathbf{b}_2$, ja sijoita:

Kompositio on $W\mathbf{x} + \mathbf{b}$, missä $W = W_2W_1$ ja $\mathbf{b} = W_2\mathbf{b}_1 + \mathbf{b}_2$. Lineaaristen kerrosten pino on yksi lineaarinen kerros. Kymmenen niitä, tuhat niitä: silti yksi suora, silti kyvytön tekemään XOR:ää.

Se kannattaa katsoa tapahtuvan eikä vain uskoa:

import numpy as np
rng = np.random.default_rng(0)
W1, b1 = rng.normal(size=(3, 2)), rng.normal(size=3)
W2, b2 = rng.normal(size=(1, 3)), rng.normal(size=1)
x = rng.normal(size=2)

two_layers = W2 @ (W1 @ x + b1) + b2
one_layer  = (W2 @ W1) @ x + (W2 @ b1 + b2)
print(two_layers[0], one_layer[0], abs(two_layers[0] - one_layer[0]))

-4.612963371048  -4.612963371048  0.00e+00

Ei likimain yhtä suuri. Bitti bitiltä identtinen, koska kyse on samasta aritmetiikasta uudelleen järjestettynä.

Syvyys ei siis yksin osta mitään. Se, mikä ostaa jotain, on epälineaarisen funktion sijoittaminen kerrosten väliin — ja se on koko syy siihen, että aktivaatiofunktiot ovat olemassa. Ne eivät ole biologinen koriste tai normalisointikikka. Ilman sellaista toinen kerros on somiste.

Nyt matematiikkaan, ja kyseessä on yksi sääntö, jonka jo tunnet, sovellettuna hieman vieraampaan paikkaan.

Yhden muuttujan ketjusääntö sanoo, että jos $L$ riippuu $c$:stä ja $c$ riippuu $x$:stä, niin $\frac{dL}{dx} = \frac{dL}{dc} \cdot \frac{dc}{dx}$. Derivaatat kerrotaan ketjua pitkin.

Tässä tärkeää on se, mitä tapahtuu, kun muuttuja syöttää useampaa kuin yhtä alavirran polkua. Jos $x$ vaikuttaa $L$:een $a$:n kautta ja myös $b$:n kautta, kontribuutiot summataan:

Kerro polkua pitkin, summaa polkujen yli. Siinä on koko backpropagation, ja jokainen toteutusyksityiskohta tämän luvun loppuosassa — mukaan lukien koodin += ja zero_grad()-kutsu, johon jokainen ensimmäistä training loopiaan kirjoittava kompastuu — on suora seuraus tuosta toisesta sanasta.

Otetaan konkreettinen viiden operaation piiri, jossa $x = 0.5$ ja $y = 1.4$:

Huomaa, että $x$ esiintyy kolme kertaa: $a$:ssä, $b$:ssa ja suoraan $L$:ssa. Tee backward pass paperilla oikealta vasemmalle aloittaen kohdasta $\frac{dL}{dL} = 1$:

Pidä kiinni tuosta luvusta. Muutaman sivun päästä ohjelma tuottaa sen ilman, että sille kerrotaan mitään tästä.

Oivallus, joka tekee tästä ohjelmoitavaa: jokainen noista askelista oli paikallinen. Gradientin työntämiseen kertolaskusolmun läpi tarvitsit saapuvan gradientin ja kaksi tallennettua syötearvoa — et mitään muusta piiristä. Jokainen operaatio osaa derivoida itsensä.

Tehdään siis luku, joka muistaa, mikä sen tuotti.

class Value:
    """A number that remembers where it came from."""

    def __init__(self, data, _children=(), _op=""):
        self.data = data
        self.grad = 0.0
        self._backward = lambda: None
        self._prev = set(_children)      
        self._op = _op

Neljä kenttää. data on arvo. grad kerää arvon $\frac{\partial L}{\partial \text{self}}$. _prev on joukko niistä Value-olioista, joista tämä laskettiin — graafin reunat. Ja _backward on sulkeuma, jonka kukin operaatio asentaa: se tietää, miten tämän solmun gradientti työnnetään yksi askel taaksepäin sen syötteisiin.

Jokainen operaattori noudattaa samaa muotoa: laske ulostulo, tallenna vanhemmat, asenna paikallinen sääntö.

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data + other.data, (self, other), "+")

        def _backward():
            self.grad += out.grad       
            other.grad += out.grad      

        out._backward = _backward
        return out

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data * other.data, (self, other), "*")

        def _backward():
            self.grad += other.data * out.grad   
            other.grad += self.data * out.grad   

        out._backward = _backward
        return out

    def tanh(self):
        t = math.tanh(self.data)
        out = Value(t, (self,), "tanh")

        def _backward():
            self.grad += (1 - t * t) * out.grad

        out._backward = _backward
        return out

    def relu(self):
        out = Value(self.data if self.data > 0 else 0.0, (self,), "relu")

        def _backward():
            self.grad += (1.0 if out.data > 0 else 0.0) * out.grad

        out._backward = _backward
        return out

Lue neljä _backward-runkoa taulukkona, ja paperijohdannosta tutut virtauskuviot ovat siinä suoraan näkyvissä:

Jokainen niistä käyttää += eikä koskaan =. Se on ”summaa polkujen yli” -sääntö koodattuna. Solmua, joka syöttää kahta kuluttajaa, kutsutaan kahdesti, ja kaksi kontribuutiota summautuvat itsestään.

Sitten ajuri, joka on ainoa osa, jolla on mitään globaalia tietoa:

    def backward(self):
        order, seen = [], set()

        def build(v):
            if v in seen:
                return
            seen.add(v)
            for child in v._prev:
                build(child)
            order.append(v)

        build(self)
        self.grad = 1.0
        for v in reversed(order):       
            v._backward()               

build tuottaa graafin topologisen järjestyksen: jokainen solmu ilmestyy kaikkien syötteidensä jälkeen. Listan läpikäynti käänteisessä järjestyksessä takaa, että kun kutsut solmun _backward-funktiota, sen oma gradientti on jo valmis — jokainen sen alavirran kuluttaja on jo kontribuoinut. Jos järjestys on väärä, työnnät puolivalmiin gradientin taaksepäin, mikä tuottaa väärän vastauksen ilman virheilmoitusta.

x = Value(0.5)
y = Value(1.4)
a = x * y
b = x + y
c = a * b
d = c.tanh()
L = d + x
L.backward()
print(x.grad, y.grad)

forward:  a=0.7000  b=1.9000  c=1.3300  d=0.8692  L=1.3692
backward: dL/dd=1.0000  dL/dc=0.2444  dL/da=0.4644  dL/db=0.1711
          dL/dx=1.8212   dL/dy=0.4033

1.8212. Sama luku ohjelmasta, jolle kerrottiin sääntö kohteelle +, sääntö kohteelle *, sääntö kohteelle tanh, eikä mitään tästä piiristä.

Kaksi riippumatonta tarkistusta, koska ”se vastaa johtamaani tulosta” on heikko testi, kun sama henkilö teki molemmat.

Numeerinen derivointi. Tönäise syötettä ja mittaa. Keskitetty erotus $\frac{L(x+h) - L(x-h)}{2h}$ arvioi derivaatan ilman lainkaan analyysiä:

dL/dx:  analytic=1.821202805  numeric=1.821202805  |diff|=1.80e-10
dL/dy:  analytic=0.403269235  numeric=0.403269235  |diff|=7.64e-12

PyTorchia vasten, jossa on teollisuustason autodiff-moottori, jonka ovat kirjoittaneet ihmiset, jotka tekevät tätä työkseen:

torch dL/dx=1.821202805316   ours=1.821202805316   |diff|=2.22e-16
torch dL/dy=0.403269234753   ours=0.403269234753   |diff|=1.11e-16

Yhtäpitävyys kohdassa $2 \times 10^{-16}$, joka on 64-bittisen liukuluvun machine epsilon: kaksi moottoria suorittaa identtistä aritmetiikkaa. Pidä numeerinen tarkistus taskussa — se on työkalu uuden kerroksen backward passin debuggaamiseen, ja se on syy siihen, että väärä gradientti on ylipäätään löydettävissä.

Sama piiri, eri syötteet. Aseta $x = 2$ ja $y = -3$, mikä tekee $c = 6$:

x=0.5, y=1.4:  dL/dc = 0.244400     three paths into x:  0.6501 + 0.1711 + 1.0000 = 1.8212
x=2.0, y=-3.0: dL/dc = 0.000025     three paths into x:  0.0001 + -0.0001 + 1.0000 = 0.9999

$\tanh$-solmun ylittävä gradientti putosi kertoimella 9 945. Kaikki sen ylävirrassa — oikeassa verkossa jokainen sitä edeltävä kerros — saa käytännössä ei mitään. Piirin kaksi polkua ovat vaienneet; vain suora yhteys, joka ohittaa $\tanh$:n, kantaa yhä signaalia.

Tämä on katoavan gradientin ongelma yhdessä solmussa. Pinoa neljäkymmentä kerrosta $\tanh$:ää ja kerro neljäkymmentä tällaista tekijää keskenään, ja varhaiset kerrokset lakkaavat oppimasta kokonaan. Se on myös, sivumennen, argumentti skip connectioneille, jonka näet tässä pienoiskoossa: epälineaarisuuden ohittanut polku on ainoa, joka selvisi.

Jokainen _backward käyttää +=. Se on oikein — niin polut summataan. Mutta sillä on seuraus, johon kaikki törmäävät: gradientit kertyvät myös backward()-kutsujen yli. Moottorilla ei ole aavistustakaan, että toinen kutsusi on uusi training-askel eikä toinen polku samassa graafissa.

Siksi training loopin täytyy tyhjentää ne:

for step in range(steps):
    ys = [model(x) for x, _ in DATA]
    loss = sum((yp - yt) ** 2 for yp, (_, yt) in zip(ys, DATA))

    for p in model.parameters():   
        p.grad = 0.0

    loss.backward()
    for p in model.parameters():
        p.data -= lr * p.grad

Tämä on optimizer.zero_grad() PyTorchissa, ja tavallinen neuvo on, että sen unohtaminen rikkoo trainingin. Poistetaan siis nuo kaksi riviä ja katsotaan, kuinka rikki se on. Samat seedit, sama kaikki, 200 askelta XOR:ää:

Pienillä learning rateilla bugillinen versio voittaa jokaisella rivillä. Se konvergoi, kun oikea versio jumittuu.

Se ei ole sattuma, ja se kannattaa ymmärtää, koska se selittää, miksi tätä bugia on niin vaikea saada kiinni. Jos et koskaan tyhjennä gradienttia, niin askeleella $k$ parametri päivitetään kaikkien tähän mennessä laskettujen gradienttien summalla. Lossilla, joka osoittaa suunnilleen samaan suuntaan, tuo summa kasvaa tasaisesti, ja vaikutus on learning rate, joka kasvaa itsestään. Kohdassa $\eta = 0.05$, jossa oikea algoritmi matelee, karkaava askelkoko näyttää täsmälleen korjaukselta.

Katso sitten alimmaisia kolmea riviä. Kohdassa $\eta = 0.3$ sama mekanismi repii mallin hajalle — häviö 8.0 on tulos, jonka vakioon $\pm 1$ romahtanut malli saa — puolet siitä 16:sta, jonka neljä maksimaalisesti väärää vastausta maksaisi — — samalla kun oikea versio nyt konvergoi siististi.

Rehellinen väite ei siis ole ”kutsu aina zero_grad tai mallisi ei trainaa”. Se on: ilman sitä et enää aja gradient descentiä. Aja jotain, jonka askelkoko ajautuu ylöspäin nopeudella, jota kukaan ei valinnut, ja se näyttää toimivan, joskus paremmin kuin oikea asia, juuri siihen asti kun ei enää toimi — jolloin syytät learning ratea, alustusta tai dataa. Tämä on machine learningin pahimpien bugien muoto: ne eivät kaadu, ne muuttavat algoritmin toiseksi algoritmiksi, joka joskus saa paremman tuloksen.

Kun moottori on valmis, neuroverkko on tuskin lainkaan koodia. Neuroni on pistetulo, bias ja aktivaatio; kerros on lista neuroneja; verkko on lista kerroksia.

class Neuron:
    def __init__(self, nin):
        self.w = [Value(random.uniform(-1, 1)) for _ in range(nin)]
        self.b = Value(0.0)

    def __call__(self, x):
        act = sum((wi * xi for wi, xi in zip(self.w, x)), self.b)
        return act.tanh()

    def parameters(self):
        return self.w + [self.b]


class Layer:
    def __init__(self, nin, nout):
        self.neurons = [Neuron(nin) for _ in range(nout)]

    def __call__(self, x):
        out = [n(x) for n in self.neurons]
        return out[0] if len(out) == 1 else out

    def parameters(self):
        return [p for n in self.neurons for p in n.parameters()]


class MLP:
    def __init__(self, nin, nouts):
        sizes = [nin] + nouts
        self.layers = [Layer(sizes[i], sizes[i + 1]) for i in range(len(nouts))]

    def __call__(self, x):
        for layer in self.layers:
            x = layer(x)
        return x

    def parameters(self):
        return [p for layer in self.layers for p in layer.parameters()]

Tuossa ei ole backward passia. Ei riviäkään. Value-luokka osaa jo derivoida mitä tahansa nämä luokat sattuvat rakentamaan, mikä on koko syy siihen, että kirjoitimme sen ensin: autodiff-moottori ei tiedä, että sitä käytetään neuroverkkoon.

Nyt Chapter 1:n ongelma. Kaksi syötettä, kaksi piiloyksikköä, yksi ulostulo, yhdeksän parametria:

step   1: loss 4.156690
step  10: loss 4.005572
step  50: loss 3.996708
step 100: loss 3.510700
step 200: loss 0.038597

[0, 0] -> -0.9081  (target -1)  ok
[0, 1] -> +0.8934  (target +1)  ok
[1, 0] -> +0.8906  (target +1)  ok
[1, 1] -> -0.9207  (target -1)  ok

Neljä neljästä. Funktio, jota yksikään perceptron ei voi laskea — Chapter 1:ssä todistettu neljällä epäyhtälöllä, jotka vaativat $b$:n olevan sekä positiivinen että negatiivinen — lasketaan yhdeksällä luvulla, jotka löytyivät automaattisesti.

Tyydyttävä osa ei ole se, että se toimii. Se on se, että näet miten, koska kahdella piiloyksiköllä väliesitys on piste tasossa ja voit vain tulostaa sen.

Kun malli on trainattu häviöön 0.001241, tässä on, mihin kukin syöte päätyy piilokerroksen jälkeen ja mitä ulostuloneuroni tekee sille:

Katso ensimmäistä ja neljättä riviä. Syötteet $(0,0)$ ja $(1,1)$ ovat neliön diagonaalisesti vastakkaiset kulmat — niin kaukana toisistaan kuin kaksi pistettä tässä ongelmassa voi olla — ja piilokerros kuvaa ne pisteisiin $(0.82, -0.85)$ ja $(0.84, -0.86)$. Lähes samaan pisteeseen. Kerros on taittanut tason niin, että kaksi hylättävää kulmaa päätyy päällekkäin, ja kun ne ovat samassa paikassa, yksi suora erottaa ne kahdesta muusta.

Ja ulostuloneuroni on täsmälleen tuo suora. Sen opitut parametrit ovat $\mathbf{w} = (-3.1153,\ +3.0893)$, $b = +2.7697$, joten sen päätösraja on

joka on suora viiva — perceptron, sama objekti Chapter 1:stä, muuttumattomana. Se ei voinut ratkaista XOR:ää silloin eikä se voi sitä nytkään. Muuttunut asia on, ettei se enää katso syötettä; se katsoo avaruutta, jonka ensimmäinen kerros rakensi sille ja jossa ongelma on lineaarisesti eroteltavissa.

Tätä opittu representaatio tarkoittaa, ja siitä kannattaa olla täsmällinen, koska ilmausta käytetään löyhästi tämän kurssin loppuosassa ja koko alalla. Se ei ole kompressio, tiivistelmä tai embedding missään mystisessä mielessä. Se on koordinaattien muutos, opittu eikä suunniteltu, jonka ainoa tehtävä on tehdä seuraavan kerroksen työ helpoksi.

Tässä on teoreema, ja sitä siteerataan yleensä huonosti.

Cybenko vuonna 1989 ja Hornik vuonna 1991 todistivat, että feedforward-verkko, jossa on yksi piilokerros ja sopiva aktivaatiofunktio, voi approksimoida minkä tahansa jatkuvan funktion kompaktissa joukossa niin tarkasti kuin haluat, kunhan piiloyksiköitä on riittävästi.³⁴ Se on aito ja tärkeä tulos: se sanoo, ettei arkkitehtuuri ole rajoite.

Lue nyt, mitä se jättää pois. Se ei sano montako yksikköä — raja voi olla astronomisen suuri. Se ei sano, että painot voidaan löytää; se väittää olemassaolon, eikä gradient descent satunnaisesta alusta ole oraakkeli. Eikä se sano mitään käyttäytymisestä datalla, jota et ole nähnyt, mikä on Chapter 6:n toinen puolisko.

Ero ”on olemassa” ja ”löydettävissä” välillä ei ole akateeminen. Tässä on sama XOR-ongelma, 50 satunnaista alustusta kussakin, 1000 askelta, vain piilokerroksen koko muuttuu:

Minimikelpoisella arkkitehtuurilla joka neljäs ajo ei koskaan pääse perille — se asettuu konfiguraatioon, josta se ei voi laskeutua ulos, täsmälleen siihen paikalliseen minimiin, jonka Chapter 3 näytti yksiulotteisella pinnalla. Lisää yksi yksikkö ja epäonnistumiset lähes katoavat, ei siksi että verkosta tuli ilmaisuvoimaisempi (kaksi yksikköä riittää jo — 38 ajoa todistaa sen), vaan koska lisäulottuvuudet antavat descentille enemmän pakosuuntia.

Ja sitten kahdeksan yksikköä toimii hieman huonommin kuin neljä. Kiinteällä learning ratella ja askelbudjetilla suurempi kapasiteetti ei ole monotonisesti parempi. Jokainen, joka sanoo sinulle, että jumissa olevan verkon korjaus on aina suurempi verkko, ekstrapoloi tuon taulukon keskikohdasta.

Tämä on sama opetus kuin Chapter 1:n konvergenssiteoreemassa, ja se on sama opetus Chapter 10:ssa scaling laeista siinä muodossa, jonka tuo luku sille antaa: lossin ennuste ei ole ennuste siitä kyvykkyydestä, josta maksat, ja näiden kahden väli on se paikka, jossa engineering elää.

Sinulla on nyt verkko, joka trainaa. Se on pienempi saavutus kuin miltä se tuntuu, koska verkko trainaa neljällä esimerkillä ja sitä mitataan samoilla neljällä.

Aja sama koodi oikealla datasetillä, ja esiin tulee uusi joukko ongelmia, joista mikään ei koske gradientteja. Loss laskee hetken ja pysähtyy sitten. Tai se laskee training-datalla ja nousee kaikella muulla. Tai se ei liiku lainkaan ensimmäisestä askeleesta, ja syyksi paljastuu alkuperäisten satunnaispainojen alue. Tai yhden yksikön syöte ajautui negatiiviseksi jokaisella esimerkillä kolmannessa epochissa, ja se on ollut kuollut siitä lähtien, hiljaa, vieden palan mallin kapasiteetista mukanaan.

Nämä eivät ole eksoottisia epäonnistumisia; ne ovat juuri kirjoitetun verkon normaali tila, eikä yksikään ilmoita itsestään. Gradientti on oikein — tarkistit sen PyTorchia vasten kuudentoista desimaalin tarkkuudella — ja malli ei silti opi.

Chapter 6 käsittelee tätä: alustusta, normalisointia, overfittingiä ja regularisointia sekä diagnostista tapaa kysyä, mikä näistä on käynnissä ennen kuin mitään muutetaan. Se on ero verkon, joka pyörii, ja verkon, joka toimii, välillä.

Tämän luvun Value-luokka polveutuu suoraan Andrej Karpathyn microgradista, ja hänen videonsa The spelled-out intro to neural networks and backpropagation: building micrograd on parhaat kolme tuntia, jotka voit käyttää tähän materiaaliin, jos haluat kuulla sen selitettynä toisella tavalla jonkun muun toimesta. Hänen vuoden 2016 kirjoituksensa Yes you should understand backprop perustelee, miksi sellainen kannattaa kirjoittaa itse, ja se on pakollista luettavaa Stanfordin CS224n-kurssilla. CS231n-muistiinpanot backpropagationista (cs231n.github.io/optimization-2) ovat yllä taulukoitujen virtauskuvioiden kanoninen käsittely. Matematiikasta graafin analyysinä eikä neuroverkkofolklorena Deisenrothin, Faisalin ja Ongin Mathematics for Machine Learning -kirjan luku 5.6 on poikkeuksellisen selkeä; ja Baydinin, Pearlmutterin, Radulin ja Siskindin katsaus Automatic Differentiation in Machine Learning: a Survey (arXiv:1502.05767) on koko alan viite, mukaan lukien yllä käsitelty forward/reverse-vaihtokauppa.