Bergafwaarts: Gradient Descent, en de twee stappen die iedereen overslaat

Opnieuw geformuleerd zodat dit hoofdstuk op zichzelf staat: de acht onderdelen van de lopende band uit hoofdstuk 1, maar met een andere vraag. Niet accepteren of afwijzen — dat komt later terug — maar het gewicht van een onderdeel voorspellen op basis van de breedte.

import numpy as np

WIDTH  = np.array([18.0, 19.5, 20.2, 21.0, 24.0, 25.5, 23.0, 26.0])
WEIGHT = np.array([47.0, 52.0, 49.0, 55.0, 61.0, 66.0, 70.0, 58.0])

x = WIDTH  - WIDTH.mean()      # 22.15 mm
y = WEIGHT - WEIGHT.mean()     # 57.25 g

De metingen zijn gecentreerd, precies zoals in hoofdstuk 1 en om een reden die voor het einde van dit hoofdstuk met rente terugkomt. Het model is een lijn, $\hat{y} = a x + b$, en de loss is de mean squared error die het vorige hoofdstuk afleidde:

Twee parameters. Waarom niet gewoon heel veel waarden proberen? Laten we dat echt doen — een grid van $a = 0$ tot $5$ en $b = -5$ tot $5$, in stappen van $0.01$:

grid 501 x 1001 = 501,501 evaluations in 3.67 s
  best found: a = 2.1000, b = -0.0000, L = 24.592450

Een half miljoen evaluaties om twee getallen tot op twee decimalen vast te pinnen — en die seconde is wandkloktijd op één machine, dus een herhaling komt ergens tussen drie en zes uit; het aantal evaluaties en het minimum zijn het deel dat reproduceert. Gradient descent haalt aan het einde van dit hoofdstuk vier decimalen in acht stappen en het volledige float64-antwoord in zesendertig.

Maar snelheid is niet het argument, en dit is het punt dat de hele cursus beslist. Grid search kost $k^P$ evaluaties voor $P$ parameters met $k$ waarden per stuk. Met duizend waarden per as:

De derde rij is geen groot getal, maar een betekenisloos getal — er zijn grofweg $10^{80}$ atomen in het waarneembare universum. Zoeken wordt niet trager naarmate modellen groeien; het houdt op te bestaan. Alles wat volgt bestaat vanwege die tabel.

Zet $b = 0$ even vast, zodat er één parameter en één curve is: het beeld waarmee het vorige hoofdstuk je achterliet. Neem een punt erop, $a = 1$, en vraag: als ik $a$ een klein beetje $h$ geef, hoeveel beweegt de loss dan, per eenheid van die duw?

Die verhouding is een stijging gedeeld door run — de helling van de rechte lijn door twee punten op de curve. Naarmate $h$ krimpt, schuiven de twee punten naar elkaar toe en wordt de lijn de raaklijn. De helling daarvan is de afgeleide $L'(a)$: de snelheid waarmee de loss verandert per eenheid verandering in $a$. Geen benadering van iets, en geen oneindig kleine hoeveelheid. Een limiet van gewone verhoudingen.

Het is de moeite waard om dit uit te voeren, omdat de getallen iets zeggen wat de definitie niet zegt:

def loss1(a):
    return np.mean((a * x - y) ** 2)

for h in [1.0, 1e-2, 1e-4, 1e-6, 1e-8, 1e-10, 1e-12, 1e-14]:
    q = (loss1(1.0 + h) - loss1(1.0)) / h
    print(f"h = {h:<8.0e}   slope estimate = {q:.10f}   error = {abs(q + 16.385):.3e}")

h = 1e+00      slope estimate = -8.9400000000    error = 7.445e+00
h = 1e-02      slope estimate = -16.3105500000   error = 7.445e-02
h = 1e-04      slope estimate = -16.3842555001   error = 7.445e-04
h = 1e-06      slope estimate = -16.3849925556   error = 7.444e-06
h = 1e-08      slope estimate = -16.3850003787   error = 3.787e-07
h = 1e-10      slope estimate = -16.3850444324   error = 4.443e-05
h = 1e-12      slope estimate = -16.3851154866   error = 1.155e-04
h = 1e-14      slope estimate = -17.0530256582   error = 6.680e-01

Hier gebeuren twee dingen, en allebei dragen ze gewicht.

De fout is niet vaag evenredig met $h$ — hij is exact $7.445\,h$. Deel $h$ door honderd, en de fout deelt door honderd, elke keer tot vier significante cijfers. Die constante is geen versiering: het is de helft van de tweede afgeleide van de loss, en het is de eerste verschijning van een idee dat twee secties verder terugkomt — dat een curve dicht bij een punt eruitziet als een lijn plus een correctie evenredig met $h^2$.

En dan breekt het patroon. Onder $h = 10^{-8}$ wordt de schatting slechter, en bij $10^{-14}$ is hij al fout in het tweede cijfer. Er is niets wiskundigs gebeurd; de floating-pointdoos uit het vorige hoofdstuk deed dit. $L(a+h)$ en $L(a)$ komen overeen in hun eerste tien cijfers, het aftrekken ervan vernietigt die cijfers, en delen door een piepklein getal versterkt wat overblijft. Er is een beste $h$ — hier rond $10^{-8}$, ongeveer de wortel van de machine-epsilon — en kleiner gaan is niet zorgvuldiger, maar minder zorgvuldig. Onthoud dat; een functie aan het einde van dit hoofdstuk hangt ervan af.

De exacte helling, uit calculus in plaats van meting, is $-16.385$. Dus we kunnen stoppen met meten en beginnen met afleiden.

Dit is het idee waarop de rest van de cursus is gebouwd, één keer helder gezegd.

Twee functies componeren betekent dat je de ene in de andere voert: $(f \circ g)(x) = f(g(x))$. Niets meer.

Een deep network is niet zoals een compositie. Het is er één. Een laag is een functie; lagen stapelen is ze componeren; ‘diepte’ is het aantal functies in de keten. Wanneer hoofdstuk 5 een netwerk bouwt, bouwt het $f_4 \circ f_3 \circ f_2 \circ f_1$ en niets anders. Dat betekent dat de allerbelangrijkste regel uit de calculus, voor ons doel, de regel is die een compositie differentieert:

Snelheden vermenigvuldigen. Als $g$ drie keer zo snel verandert als $x$, en $f$ twee keer zo snel verandert als $g$, dan verandert $f$ zes keer zo snel als $x$. Dat is de hele inhoud, en het is waarom een signaal dat teruggaat door tien lagen met tien getallen wordt vermenigvuldigd — en waarom hoofdstuk 6 een sectie besteedt aan wat er gebeurt wanneer die getallen allemaal iets kleiner zijn dan één.

Gebruik dit op onze loss. Schrijf het residu als $r_i = a x_i + b - y_i$, zodat $L = \frac{1}{n}\sum r_i^2$. Elke $r_i$ hangt af van $a$ via de binnenste functie $a x_i$, waarvan de afgeleide $x_i$ is. Chain rule, term voor term:

Die gekrulde $\partial$-symbolen markeren een partiële afgeleide: differentieer ten opzichte van één variabele en behandel alle andere als constanten. Er gebeurt niets nieuws — het is dezelfde limiet als eerder, genomen langs één as. Verzamel de partiële afgeleiden in een vector en je hebt de gradient:

Op het punt $(a, b) = (1, 4)$ is die vector $(-16.385,\ 8.0)$. Twee getallen. De vraag is wat ze betekenen, en dit is de eerste stap die iedereen overslaat.

De gradient is een vector van hellingen langs de assen. Dat is alles wat we hebben bewezen. Het is niet duidelijk — en het zou ook niet duidelijk moeten zijn — dat ze samenvoegen tot een vector iets oplevert dat ergens specifiek heen wijst.

Definieer dus wat we echt willen. Kies een eenheidsvector $\mathbf{u}$, een richting. De richtingsafgeleide is de snelheid waarmee de loss verandert als je die kant op loopt:

De chain rule maakt hier iets berekenbaars van. Lopen langs $\mathbf{u}$ verandert $a$ met snelheid $u_1$ en $b$ met snelheid $u_2$, en de bijdragen tellen op:

De veranderingssnelheid in elke richting is het dot product van de gradient met die richting. En nu de punchline, één regel meetkunde. Schrijf het dot product met de hoek $\phi$ tussen de vectoren,

omdat $\mathbf{u}$ lengte 1 heeft. Het enige waar je controle over hebt is $\cos\phi$, die het grootst is bij $\phi = 0$ en het kleinst bij een halve draai, $\phi = 180$ graden. Dus:

• De steilste stijging is langs $\nabla L$ zelf, en de helling daar is exact $\lVert \nabla L \rVert$.
• De steilste daling is langs $-\nabla L$, en de helling daar is $-\lVert \nabla L \rVert$.
• Loodrecht op de gradient verandert de loss helemaal niet. Daarom kruisen de lijnen van een contourkaart de gradient onder een rechte hoek.

Dat is het minteken. Geen conventie, geen tekenomkering die iemand koos: de richting van snelste daling is de negatieve gradient omdat $\cos\phi$ minimaal is bij een halve draai, en om geen enkele andere reden.

Omdat dit een claim is over alle richtingen, testen we hem tegen alle richtingen. Sample er 3.600, één per tiende graad, en meet elke richting door een duwtje te geven:

theta = np.array([1.0, 4.0])
g = grad(theta)
print("gradient      ", g)
print("its length    ", np.linalg.norm(g))
print("its angle     ", np.degrees(np.arctan2(g[1], g[0])) % 360, "degrees")

best = max(
    ((loss(theta + 1e-6 * u) - loss(theta - 1e-6 * u)) / 2e-6, np.degrees(ang))
    for ang, u in (
        (a, np.array([np.cos(a), np.sin(a)])) for a in np.arange(3600) * 2 * np.pi / 3600
    )
)
print("steepest slope", best[0], "at", best[1], "degrees")

gradient       [-16.385   8.   ]
its length     18.23371122399386
its angle      153.97598928042032 degrees
steepest slope 18.233709624837502 at 154.0 degrees

Een zoekactie die niets weet over gradients, over 3.600 richtingen, vindt zijn steilste klim bij 154,0 graden — de eigen richting van de gradient, binnen de resolutie van 0,1 graad van de zoekactie. En de helling die hij daar vindt, 18,2337, is de lengte van de gradient tot zes cijfers. De stelling is geen verhaal over wat gradients betekenen; het is een meetbaar feit, en dit is de meting.

Nu de tweede overgeslagen stap. We weten welke kant omlaag is. Daaruit volgt niet dat die kant op lopen de loss verlaagt, want ‘omlaag’ is een uitspraak over een infinitesimale duw en een stap is niet infinitesimaal.

De brug is linearisatie. Dicht bij een punt is een gladde functie haar raaklijn plus een correctie:

Dat is de eerste-orde Taylor-expansie. De weggegooide $O(\lVert\boldsymbol{\delta}\rVert^2)$ is de kromming — dezelfde term die de schatting in de hellingstabel precies $7.445\,h$ fout maakte. Vul de stap in die we willen zetten, $\boldsymbol{\delta} = -\eta \nabla L$:

De loss daalt met $\eta \lVert \nabla L \rVert^2$. Elk deel daarvan is niet-negatief, dus de belofte is echt — voor een klein genoeg $\eta$, omdat de verwaarloosde term groeit als $\eta^2$ en hem uiteindelijk opslokt. Dat is de hele theorie. Hier zie je de belofte waargemaakt worden, en daarna breken:

eta = 0.2       promised    66.49364500   delivered   -16.01619240   ratio -0.240868
eta = 0.1       promised    33.24682250   delivered    12.61936315   ratio  0.379566
eta = 0.01      promised     3.32468225   delivered     3.11840766   ratio  0.937957
eta = 0.001     promised     0.33246822   delivered     0.33040548   ratio  0.993796
eta = 0.0001    promised     0.03324682   delivered     0.03322620   ratio  0.999380
eta = 1e-05     promised     0.00332468   delivered     0.00332448   ratio  0.999938

Lees het van onder naar boven. Naarmate $\eta$ krimpt, convergeert de geleverde daling naar de beloofde — ratio 0,99938, daarna 0,99994 — en dat is Taylors stelling die klopt. Lees het van boven naar beneden en bij $\eta = 0.2$ is de geleverde ‘daling’ negatief zestien. De stap ging bergaf en de loss ging omhoog.

Dus de update-regel is

en hij komt met een voorwaarde die niemand noemt: $\eta$ moet klein genoeg zijn. Klein genoeg vergeleken met wat, precies, is de volgende sectie.

Begin met de simpelste vallei die er is, $f(x) = x^2$, waarbij $f'(x) = 2x$. Eén stap gradient descent is

De positie wordt elke stap vermenigvuldigd met $(1 - 2\eta)$. Dat is een meetkundige rij, en meetkundige rijen hebben precies één regel: ze krimpen wanneer de vermenigvuldiger in absolute waarde kleiner is dan 1, en anders groeien ze. Dus $\lvert 1 - 2\eta \rvert < 1$, oftewel $0 < \eta < 1$.

De grens ligt exact bij $\eta = 1$. Niet ‘rond 1’, niet ‘1 is meestal te groot’. Bij $\eta = 1$ is de vermenigvuldiger $-1$ en stuitert het punt voor altijd tussen $x$ en $-x$, zonder dichterbij te komen of te ontsnappen. Eronder convergeert het; erboven divergeert het. Het interval splitst nog eens bij $\eta = 0.5$, waar de vermenigvuldiger van teken verandert: daaronder is de nadering monotoon, daarboven schiet het punt door en wisselt het van kant, en bij exact $0.5$ is de vermenigvuldiger 0 en landt één enkele stap op het minimum.

Vier regimes, uit vier regels algebra. Ga zelf over de grenzen heen:

En nu de interessante:

Nu de algemene regel, die uit hetzelfde argument valt. De vermenigvuldiger $1 - 2\eta$ was eigenlijk $1 - \eta f''$, en dicht bij een minimum heeft een loss met meerdere parameters zo’n getal per richting — de eigenwaarden van de matrix met tweede afgeleiden. Elke richting moet tegelijk stabiel zijn, dus het plafond wordt bepaald door de grootste:

Voor $f(x) = x^2$, $f'' = 2$, plafond 1, precies wat we net afleidden. Voor onze band is de matrix van tweede afgeleiden $\frac{2}{n} A^{\top} A$ met $A$ de tweekoloms matrix van inputs, en de eigenwaarden zijn 2 en 14,89, dus het plafond is $2 / 14.89 = 0.13432$. Dat is een voorspelling met vijf significante cijfers. Test hem:

lr=0.1343    -> L =      24.5924
lr=0.13431   -> L =      24.5924
lr=0.13432   -> L =       4707.8       BLEW UP
lr=0.13433   -> L =  4.00452e+16       BLEW UP
lr=0.1344    -> L = 1.18229e+107       BLEW UP

Vijf decimalen overeenstemming tussen één regel lineaire algebra en honderdduizend iteraties van een for-loop.

En hier komt hoofdstuk 1 terug. Alles hierboven gebruikte de gecentreerde metingen. Draai dezelfde code op ruwe millimeters en grammen en de eigenwaarden zijn 0,0298 en 998,1 in plaats van 2 en 14,89. Het plafond stort in van 0,134 naar 0,002004 — net zo exact, convergerend bij lr=0.002003 en ontploffend bij lr=0.002004.

Erger dan het plafond is de verhouding tussen de eigenwaarden. Het condition number meet hoe ver de vallei van rond af is: een lange smalle geul dwingt een rate af die klein genoeg is voor de steile wanden, en daarna wordt over de bodem van de geul met dezelfde kruipsnelheid gelopen. Die van ons gaat van 7,44 gecentreerd naar 33.452 ruw. Met de beste rate die elke versie kan nemen:

Dezelfde data, dezelfde code, hetzelfde antwoord aan het einde — en achtduizend keer zoveel werk, omdat niemand een gemiddelde aftrok. In hoofdstuk 1 kostte dezelfde omissie de perceptron een factor zesduizend in epochs, en de diagnose daar was geometrisch: de data zweefde ver van de oorsprong. Het is hier dezelfde geometrie in optimalisatiekostuum, en daarom is inputnormalisatie geen hygiëneadvies maar rekenkunde.¹

Niets hierboven had een library nodig. Hier is de hele optimiser.

def loss(theta):
    a, b = theta
    return np.mean((a * x + b - y) ** 2)


def grad(theta):
    a, b = theta
    residual = a * x + b - y
    return np.array([np.mean(2 * residual * x), np.mean(2 * residual)])


def descend(theta, lr, steps):
    theta = np.array(theta, dtype=float)
    for _ in range(steps):
        theta = theta - lr * grad(theta)   
    return theta


theta = descend([0.0, 0.0], lr=0.05, steps=60)
print(theta, loss(theta))

[ 2.10040296e+00 -2.76445533e-15] 24.592448791134984

Het closed-form least-squares-antwoord voor deze acht punten is $a = 2.100403$, $b = 0$, met een loss van $24.592449$. De loop vond het tot acht significante cijfers zonder te weten dat er een closed form bestaat — en dat doet ertoe, want vanaf hoofdstuk 5 zal die er niet zijn.

De trajectory, want ernaar kijken is het punt:

   0 a=0.000000 b=0.000000 L=57.437500
   1 a=1.563750 b=0.000000 L=26.736582
   2 a=1.963288 b=-0.000000 L=24.732418
   5 a=2.098116 b=-0.000000 L=24.592488
  10 a=2.100400 b=-0.000000 L=24.592449
  60 a=2.100403 b=-0.000000 L=24.592449

Het grootste deel van de afstand wordt in de eerste twee stappen afgelegd, omdat de gradient het grootst is wanneer je het verst van de bodem bent en krimpt naarmate je nadert. Gradient descent vertraagt automatisch dicht bij een minimum. Dat is een feature en het is ook, in hoofdstuk 6, een probleem.

Het argument tot nu toe heeft een gat. De stap stopt wanneer $\nabla L = \mathbf{0}$, en we hebben dat ‘het minimum’ genoemd. Een punt met nul gradient is een kritisch punt, en een minimum zijn is maar één van de manieren om dat te zijn:

• een lokaal minimum: bergop in elke richting, maar mogelijk niet het laagste van zulke punten ergens;
• een lokaal maximum: bergaf in elke richting;
• een zadelpunt: bergop in sommige richtingen en bergaf in andere. Het oppervlak $f(x,y) = x^2 - y^2$ heeft $\nabla f = (2x, -2y)$, wat nul is in de oorsprong, waar de functie tegelijk een minimum is langs de $x$-as en een maximum langs de $y$-as.

Gradient descent kan deze niet uit elkaar houden, omdat het alleen ooit naar de gradient kijkt, en de gradient is bij alle drie nul.

Onze lijn heeft één kritisch punt en dat is het antwoord — een squared-error loss over een lineair model is convex, één enkele kom, en descent daarop kan niet mislukken in het vinden van het globale minimum. Die eigenschap overleeft de aanraking met deze cursus niet. De loss van een neural network is niet convex, en vanaf hoofdstuk 5 is ‘het minimum’ niet iets dat bestaat: er zijn er veel, met verschillende dieptes, en welke je krijgt hangt af van waar je begon. Dat is één zin en blijft één zin, omdat de theorie groot is en de praktische consequentie klein.

Je kunt de hele consequentie op één curve zien. Neem $f(x) = \tfrac{x^4}{4} - \tfrac{x^2}{2} + \tfrac{x}{10}$, die twee valleien met verschillende dieptes heeft:

   x =  -1.046681   f(x) =  -0.352386   minimum
   x =   0.101031   f(x) =   0.005026   maximum
   x =   0.945649   f(x) =  -0.152639   minimum

In de ondiepe vallei landen is 56,7% slechter in loss, en het algoritme kan dat niet weten, omdat vanuit een vallei elke richting bergop is. Hier is geen reparatie voor in gradient descent en die komt er ook niet. Wat er in de praktijk wel is, is de bevinding dat dit veel minder uitmaakt dan dit plaatje suggereert — in de heel hoge dimensies van een echt netwerk blijken de meeste kritische punten zadels te zijn in plaats van vallen,² en hoofdstuk 5 meet hoe vaak een klein netwerk echt vastloopt.

Eén ding aan grad hierboven zou je moeten storen: het sommeert over de hele dataset voor elke stap. Acht onderdelen is niets. Een miljoen is een miljoen gradient-berekeningen om de parameters één keer te verplaatsen.

De ontsnapping is dat de gradient een gemiddelde is, en een gemiddelde kun je schatten uit een sample. Bereken hem op een willekeurig handjevol — een minibatch — en stap daarop. De schatting is ruisig; hij is ook unbiased, en honderden goedkope ruisige stappen verslaan één dure exacte. Op honderdduizend synthetische onderdelen, geteld in gradients per voorbeeld in plaats van stappen:

Tweehonderdnegentien keer minder rekenwerk om op dezelfde plek te komen. En het uiterste — één voorbeeld per keer, de oorspronkelijke stochastic approximation van Robbins en Monro³ — is niet de winnaar: het is vijf keer slechter dan batches van 32, omdat 32 voorbeelden bijna niets meer kosten dan één op hardware die matrices vermenigvuldigt, terwijl de ruis afneemt met de wortel van de batchgrootte. Die trade-off is waarom elk trainingsscript dat je ooit leest een batch_size bevat.

Momentum is de andere goedkope fix, en die is recht op de geul gericht. In een slecht geconditioneerde vallei zigzaggen de stappen over de smalle richting terwijl ze langs de lange richting kruipen. Momentum houdt een lopend gemiddelde van eerdere gradients bij, zodat de oscillerende componenten elkaar opheffen en de consistente component zich ophoopt:⁴

Twee extra regels. Op de ruwe ongecentreerde band — condition number 33.452, het ergste geval dat we hebben — met de beste rate die gewone descent kan nemen:

momentum beta=0.0   ->    79,513 steps to 1%
momentum beta=0.9   ->     1,609 steps to 1%
momentum beta=0.99  ->       461 steps to 1%

Een factor 172 voor twee regels code. Hoofdstuk 6 maakt hier Adam van; het mechanisme staat hier al.

Elke gradient in dit hoofdstuk is met de hand afgeleid en kan dus fout zijn. De fix is de hellingstabel van het begin: meet de afgeleide numeriek en vergelijk. Gebruik het centrale verschil, $\frac{L(\theta+h) - L(\theta-h)}{2h}$, dat de leidende foutterm opheft en voor dezelfde $h$ veel nauwkeuriger is.

def numeric_grad(f, theta, h=1e-5):
    theta = np.asarray(theta, dtype=float)
    out = np.zeros_like(theta)
    for i in range(theta.size):
        bump = np.zeros_like(theta)
        bump[i] = h
        out[i] = (f(theta + bump) - f(theta - bump)) / (2 * h)     
    return out


def gradcheck(f, df, theta, h=1e-5):
    analytic = np.asarray(df(theta), dtype=float)
    numeric = numeric_grad(f, theta, h)
    return np.max(np.abs(analytic - numeric) / np.maximum(1e-8, np.abs(analytic) + np.abs(numeric)))

De relatieve vorm van de vergelijking doet ertoe: een absoluut verschil van $10^{-4}$ is een ramp op een gradient van grootte $10^{-3}$ en irrelevant op één van grootte $10^{6}$.

relative error: 1.8929136036763527e-11
with 2 dropped: 0.33333333331650744

De eerste regel is de hierboven met de hand afgeleide gradient. De tweede is dezelfde functie waarbij de factor 2 in één component is weggelaten — een typefout van één teken — en de check vangt hem meteen. Alles onder ongeveer $10^{-7}$ is overeenstemming; alles boven $10^{-4}$ is een bug. Bewaar deze functie: hoofdstuk 5 gebruikt hem om een automatic differentiation engine te debuggen, en het is de enige reden dat een verkeerde gradient überhaupt te vinden is.

Alles in dit hoofdstuk rustte op één aanname die nooit is uitgesproken: dat je $\partial L / \partial \theta$ kunt opschrijven.

Voor een lijn met twee parameters was dat één regel algebra. Dat houdt vrijwel meteen op. Vraag een symbolic algebra system om de afgeleide van de loss van een netwerk ten opzichte van één enkel gewicht in de eerste laag, voor één enkel voorbeeld, en tel de rekenoperaties in het antwoord:

De derde rij is een netwerk met 57 parameters — zo klein dat het in hoofdstuk 6 een voetnoot zou zijn — en zijn gradient met de hand uitschrijven betekent ongeveer 97.869 operaties voor één trainingsvoorbeeld. Er is geen notatie die dit redt. Wat het redt, is de observatie dat de chain rule toegepast op een compositie enorme structuur heeft, dat dezelfde tussenliggende grootheden steeds opnieuw verschijnen, en dat ze in de juiste volgorde berekenen alle afgeleiden oplevert voor ongeveer de prijs van één forward pass. Dat is hoofdstuk 5.

Maar er is eerst een kleiner probleem, en dat wacht meteen.

We hebben nu een machine die bergaf rolt op elke differentieerbare loss. Richt hem op de oorspronkelijke vraag van de band — accepteren of afwijzen, een target dat 1 of 0 is — zet een sigmoid op de output zodat hij een kans voorspelt, en minimaliseer squared error. Hij zal draaien. Hij zal ook nauwelijks bewegen wanneer hij het meest fout zit, en de gradient zegt waarom:

Een model dat zelfverzekerd, catastrofaal fout zit — het voorspelt 0,0000454 wanneer het antwoord 1 is — produceert een squared-error gradient van $9 \times 10^{-5}$. Het heeft geen idee dat het in de problemen zit. De andere kolom, afkomstig van een loss die we nog niet hebben afgeleid, meldt 1,0: maximale urgentie, precies waar die verdiend is.

Dat roept de vraag op waarmee het volgende hoofdstuk opent. Het vorige hoofdstuk zei dat een loss een aanname is over de ruis, en squared error veronderstelt Gaussiaanse ruis. Welk ruismodel heeft een ja-of-nee-antwoord — en welke loss komt eruit wanneer je dezelfde afleiding daarop loslaat?

De methode is ouder dan al deze bronnen: Cauchy beschreef haar in 1847 in een notitie aan de Académie des Sciences, als een manier om stelsels vergelijkingen op te lossen door bergaf te lopen op de som van hun gekwadrateerde residuen. Ook de moeite waard om naast dit hoofdstuk te lezen: Sebastian Ruders An overview of gradient descent optimization algorithms (arXiv:1609.04747), dat momentum tot en met Adam behandelt in veertien leesbare pagina’s; hoofdstuk 3 van Nocedal en Wrights Numerical Optimization (2e ed., Springer, 2006), waarvan stelling 3.3 de convergentiesnelheid van steepest descent op een kwadratische functie geeft in termen van het condition number — dit is de theorie achter waarom conditionering het aantal stappen bepaalt, al behandelt het line search in plaats van het fixed-step $2/\lambda_{\max}$-plafond dat hierboven is gemeten — of §5.8 en §7.1 van Deisenroth, Faisal en Ongs Mathematics for Machine Learning voor hetzelfde terrein met minder machinerie; §6.1 van Prince’s Understanding Deep Learning en §4.3 van Goodfellow, Bengio en Courvilles Deep Learning; Dive into Deep Learning §12.1–12.3, dat de minibatch-analyse bevat met meer metingen dan hier ruimte voor is; en hoofdstuk 4 van Gérons Hands-On Machine Learning (3e ed.), de meest praktische behandeling van de learning rate als iets dat je tuned in plaats van afleidt. De MIT 6.390-notities plaatsen gradient descent vóór classificatie, zoals deze cursus doet en om dezelfde reden.