Bergab: Gradient Descent und die zwei Schritte, die alle überspringen

Noch einmal so formuliert, dass dieses Kapitel für sich steht: die acht Teile vom Förderband aus Kapitel 1, aber mit einer anderen Frage. Nicht akzeptieren oder ablehnen — das kommt später zurück —, sondern das Gewicht eines Teils aus seiner Breite vorhersagen.

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

Die Messungen sind zentriert, genau wie in Kapitel 1 und aus einem Grund, der sich noch vor Ende dieses Kapitels auszahlt. Das Modell ist eine Gerade, $\hat{y} = a x + b$, und der Loss ist der mittlere quadratische Fehler, den das vorige Kapitel hergeleitet hat:

Zwei Parameter. Warum nicht einfach viele Werte ausprobieren? Machen wir das tatsächlich — ein Gitter von $a = 0$ bis $5$ und $b = -5$ bis $5$, in Schritten von $0.01$:

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

Eine halbe Million Auswertungen, um zwei Zahlen auf zwei Dezimalstellen festzunageln — und diese Sekunde ist Wanduhrzeit auf einer Maschine, daher landet ein neuer Lauf irgendwo zwischen drei und sechs; die Anzahl der Auswertungen und das Minimum sind der reproduzierbare Teil. Gradient descent, am Ende dieses Kapitels, erreicht vier Dezimalstellen in acht Schritten und die vollständige float64-Antwort in sechsunddreißig.

Aber Geschwindigkeit ist nicht das Argument, und das ist der Punkt, der den ganzen Kurs entscheidet. Gittersuche kostet $k^P$ Auswertungen für $P$ Parameter mit jeweils $k$ Werten. Mit tausend Werten pro Achse:

Die dritte Zeile ist keine große Zahl, sie ist eine bedeutungslose — im beobachtbaren Universum gibt es ungefähr $10^{80}$ Atome. Suche wird nicht langsamer, wenn Modelle wachsen; sie hört auf zu existieren. Alles, was folgt, existiert wegen dieser Tabelle.

Fixiere $b = 0$ für einen Moment, sodass es einen Parameter und eine Kurve gibt — genau das Bild, mit dem dich das letzte Kapitel zurückgelassen hat. Nimm einen Punkt darauf, $a = 1$, und frag: Wenn ich $a$ um einen kleinen Betrag $h$ anstoße, wie stark bewegt sich der Loss pro Einheit dieses Stoßes?

Dieses Verhältnis ist Anstieg über Lauf — die Steigung der Geraden durch zwei Punkte auf der Kurve. Wenn $h$ schrumpft, rutschen die beiden Punkte zusammen und die Gerade wird zur Tangente. Ihre Steigung ist die Ableitung $L'(a)$: die Rate, mit der sich der Loss pro Änderungseinheit in $a$ ändert. Keine Näherung von irgendetwas und keine unendlich kleine Größe. Ein Grenzwert gewöhnlicher Verhältnisse.

Es lohnt sich, das laufen zu lassen, weil die Zahlen etwas sagen, was die Definition nicht sagt:

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 passieren zwei Dinge, und beide tragen Gewicht.

Der Fehler ist nicht vage proportional zu $h$ — er ist exakt $7.445\,h$. Teile $h$ durch hundert, und der Fehler teilt sich durch hundert, jedes Mal auf vier signifikante Stellen. Diese Konstante ist keine Dekoration: Sie ist die Hälfte der zweiten Ableitung des Loss und der erste Auftritt einer Idee, die in zwei Abschnitten zurückkehrt — dass eine Kurve nahe einem Punkt wie eine Gerade plus eine Korrektur proportional zu $h^2$ aussieht.

Und dann bricht das Muster. Unterhalb von $h = 10^{-8}$ wird die Schätzung schlechter, und bei $10^{-14}$ ist sie schon in der zweiten Ziffer falsch. Mathematisch ist nichts passiert; die Floating-Point-Box aus dem letzten Kapitel ist passiert. $L(a+h)$ und $L(a)$ stimmen in ihren ersten zehn Ziffern überein, ihre Subtraktion zerstört diese Ziffern, und das Teilen der Trümmer durch eine winzige Zahl verstärkt, was übrig bleibt. Es gibt ein bestes $h$ — hier etwa $10^{-8}$, ungefähr die Quadratwurzel des machine epsilon — und kleiner zu werden ist nicht sorgfältiger, sondern weniger sorgfältig. Merk dir das; eine Funktion am Ende dieses Kapitels hängt davon ab.

Die exakte Steigung aus der Analysis statt aus Messung ist $-16.385$. Also können wir aufhören zu messen und anfangen herzuleiten.

Hier ist die Idee, auf der der Rest des Kurses aufbaut, einmal klar ausgesprochen.

Zwei Funktionen zu komponieren heißt, die eine in die andere einzusetzen: $(f \circ g)(x) = f(g(x))$. Mehr nicht.

Ein tiefes Netzwerk ist nicht wie eine Komposition. Es ist eine. Eine Schicht ist eine Funktion; Schichten zu stapeln heißt, sie zu komponieren; „Tiefe“ ist die Anzahl der Funktionen in der Kette. Wenn Kapitel 5 ein Netzwerk baut, baut es $f_4 \circ f_3 \circ f_2 \circ f_1$ und sonst nichts. Das bedeutet: Die für unsere Zwecke wichtigste Regel der Analysis ist die, die eine Komposition ableitet:

Raten multiplizieren sich. Wenn $g$ sich dreimal so schnell ändert wie $x$ und $f$ sich doppelt so schnell ändert wie $g$, dann ändert sich $f$ sechsmal so schnell wie $x$. Das ist der ganze Inhalt, und es ist der Grund, warum ein Signal, das durch zehn Schichten zurückläuft, mit zehn Zahlen multipliziert wird — weshalb Kapitel 6 einen Abschnitt darauf verwendet, was passiert, wenn diese Zahlen alle etwas kleiner als eins sind.

Wende sie auf unseren Loss an. Schreibe das Residuum $r_i = a x_i + b - y_i$, sodass $L = \frac{1}{n}\sum r_i^2$. Jedes $r_i$ hängt über die innere Funktion $a x_i$ von $a$ ab, deren Ableitung $x_i$ ist. Kettenregel, Term für Term:

Diese geschweiften $\partial$-Symbole markieren eine partielle Ableitung: nach einer Variablen ableiten und jede andere als konstant behandeln. Es passiert nichts Neues — es ist derselbe Grenzwert wie zuvor, nur entlang einer Achse. Sammle die partiellen Ableitungen in einem Vektor, und du hast den Gradient:

Am Punkt $(a, b) = (1, 4)$ ist dieser Vektor $(-16.385,\ 8.0)$. Zwei Zahlen. Die Frage ist, was sie bedeuten, und das ist der erste Schritt, den alle überspringen.

Der Gradient ist ein Vektor aus Steigungen entlang der Achsen. Das ist alles, was wir bewiesen haben. Es ist nicht offensichtlich — es sollte nicht offensichtlich sein —, dass das Zusammensetzen dieser Steigungen zu einem Vektor etwas erzeugt, das in irgendeine bestimmte Richtung zeigt.

Definieren wir also das, was wir tatsächlich wollen. Wähle einen Einheitsvektor $\mathbf{u}$, eine Richtung. Die Richtungsableitung ist die Rate, mit der sich der Loss ändert, wenn du in diese Richtung gehst:

Die Kettenregel verwandelt das in etwas Berechenbares. Beim Gehen entlang $\mathbf{u}$ ändert sich $a$ mit Rate $u_1$ und $b$ mit Rate $u_2$, und die Beiträge addieren sich:

Die Änderungsrate in jeder Richtung ist das Skalarprodukt des Gradient mit dieser Richtung. Und jetzt die Pointe, eine Zeile Geometrie. Schreibe das Skalarprodukt mit dem Winkel $\phi$ zwischen den Vektoren:

da $\mathbf{u}$ die Länge 1 hat. Das Einzige, was du kontrollierst, ist $\cos\phi$, das bei $\phi = 0$ am größten und bei einer halben Drehung, $\phi = 180$ Grad, am kleinsten ist. Also:

• Der steilste Anstieg liegt entlang von $\nabla L$ selbst, und die Steigung dort ist exakt $\lVert \nabla L \rVert$.
• Der steilste Abstieg liegt entlang von $-\nabla L$, und die Steigung dort ist $-\lVert \nabla L \rVert$.
• Senkrecht zum Gradient ändert sich der Loss überhaupt nicht. Deshalb schneiden die Linien einer Höhenlinienkarte den Gradient im rechten Winkel.

Das ist das Minuszeichen. Keine Konvention, kein Vorzeichenwechsel, den jemand gewählt hat: Die Richtung des schnellsten Abfalls ist der negative Gradient, weil $\cos\phi$ bei einer halben Drehung minimiert wird, und aus keinem anderen Grund.

Da dies eine Aussage über alle Richtungen ist, teste sie gegen alle Richtungen. Stichprobe 3.600 davon, eine pro Zehntelgrad, und miss jede durch einen kleinen Stoß:

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

Eine Suche, die nichts über Gradienten weiß, findet über 3.600 Richtungen ihren steilsten Anstieg bei 154,0 Grad — der eigenen Richtung des Gradient, bis auf die 0,1-Grad-Auflösung der Suche. Und die Steigung, die sie dort findet, 18,2337, ist die Länge des Gradient auf sechs Stellen. Der Satz ist keine Geschichte darüber, was Gradienten bedeuten; er ist eine messbare Tatsache, und das ist die Messung.

Jetzt der zweite übersprungene Schritt. Wir wissen, welche Richtung nach unten führt. Daraus folgt nicht, dass ein Schritt in diese Richtung den Loss senkt, denn „nach unten“ ist eine Aussage über einen infinitesimalen Stoß, und ein Schritt ist nicht infinitesimal.

Die Brücke ist Linearisierung. In der Nähe eines Punkts ist eine glatte Funktion ihre Tangente plus eine Korrektur:

Das ist die Taylor-Entwicklung erster Ordnung. Das verworfene $O(\lVert\boldsymbol{\delta}\rVert^2)$ ist die Krümmung — derselbe Term, der die Schätzung in der Steigungstabelle um exakt $7.445\,h$ falsch gemacht hat. Setze den Schritt ein, den wir machen wollen, $\boldsymbol{\delta} = -\eta \nabla L$:

Der Loss fällt um $\eta \lVert \nabla L \rVert^2$. Jeder Teil davon ist nichtnegativ, also ist das Versprechen real — für ein ausreichend kleines $\eta$, denn der vernachlässigte Term wächst wie $\eta^2$ und frisst es irgendwann auf. Das ist die ganze Theorie. Hier wird das Versprechen gehalten und dann gebrochen:

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

Lies es von unten. Wenn $\eta$ schrumpft, konvergiert der tatsächliche Abfall gegen den versprochenen — Verhältnis 0,99938, dann 0,99994 —, was einfach Taylors Satz bei der Arbeit ist. Lies es von oben, und bei $\eta = 0.2$ ist der tatsächliche „Abfall“ minus sechzehn. Der Schritt ging bergab, und der Loss ging nach oben.

Die Update-Regel lautet also

und sie kommt mit einer Bedingung, die niemand ausspricht: $\eta$ muss klein genug sein. Klein genug im Vergleich zu was genau, ist der nächste Abschnitt.

Beginne mit dem einfachsten Tal, das es gibt: $f(x) = x^2$, wobei $f'(x) = 2x$. Ein Schritt von gradient descent ist

Die Position wird in jedem Schritt mit $(1 - 2\eta)$ multipliziert. Das ist eine geometrische Folge, und geometrische Folgen haben genau eine Regel: Sie schrumpfen, wenn der Multiplikator dem Betrag nach kleiner als 1 ist, und wachsen sonst. Also $\lvert 1 - 2\eta \rvert < 1$, also $0 < \eta < 1$.

Die Grenze liegt exakt bei $\eta = 1$. Nicht „ungefähr 1“, nicht „1 ist meistens zu groß“. Bei $\eta = 1$ ist der Multiplikator $-1$, und der Punkt springt für immer zwischen $x$ und $-x$ hin und her, ohne sich zu nähern oder zu entkommen. Darunter: Konvergenz; darüber: Divergenz. Das Intervall teilt sich bei $\eta = 0.5$ erneut, wo der Multiplikator das Vorzeichen wechselt: Darunter ist die Annäherung monoton, darüber schießt der Punkt über das Ziel hinaus und wechselt die Seiten, und bei exakt $0.5$ ist der Multiplikator 0 und ein einziger Schritt landet im Minimum.

Vier Regime aus vier Zeilen Algebra. Überschreite die Grenzen selbst:

Und jetzt der interessante Fall:

Nun die allgemeine Regel, die aus demselben Argument herausfällt. Der Multiplikator $1 - 2\eta$ war in Wahrheit $1 - \eta f''$, und nahe einem Minimum hat ein Loss mit mehreren Parametern eine solche Zahl pro Richtung — die Eigenwerte der Matrix der zweiten Ableitungen. Jede Richtung muss gleichzeitig stabil sein, also wird die Obergrenze durch den größten gesetzt:

Für $f(x) = x^2$, $f'' = 2$, Obergrenze 1, genau das, was wir gerade hergeleitet haben. Für unser Förderband ist die Matrix der zweiten Ableitungen $\frac{2}{n} A^{\top} A$ mit $A$ als zweispaltiger Eingabematrix, und ihre Eigenwerte sind 2 und 14,89, also ist die Obergrenze $2 / 14.89 = 0.13432$. Das ist eine Vorhersage mit fünf signifikanten Stellen. Teste sie:

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

Fünf Dezimalstellen Übereinstimmung zwischen einer Zeile linearer Algebra und hunderttausend Iterationen einer for-Schleife.

Und hier kommt Kapitel 1 zurück. Alles oben verwendete die zentrierten Messungen. Führe den identischen Code auf rohen Millimetern und Gramm aus, und die Eigenwerte sind 0,0298 und 998,1 statt 2 und 14,89. Die Obergrenze bricht von 0,134 auf 0,002004 ein — genauso exakt, konvergend bei lr=0.002003 und explodierend bei lr=0.002004.

Schlimmer als die Obergrenze ist das Verhältnis zwischen den Eigenwerten. Die Konditionszahl misst, wie weit das Tal von rund entfernt ist: Ein langer, dünner Graben erzwingt eine Rate, die klein genug für die steilen Wände ist, und dann wird der Boden des Grabens mit demselben Schneckentempo durchquert. Unsere geht von 7,44 zentriert auf 33.452 roh. Mit der besten Rate, die jede Version nehmen kann:

Dieselben Daten, derselbe Code, am Ende dieselbe Antwort — und achttausendmal so viel Arbeit, weil niemand einen Mittelwert subtrahiert hat. In Kapitel 1 kostete dieselbe Auslassung den Perzeptron einen Faktor von sechstausend bei den Epochen, und die Diagnose dort war geometrisch: Die Daten schwebten weit vom Ursprung entfernt. Es ist dieselbe Geometrie hier im Optimierungsgewand, und deshalb ist Eingabenormalisierung kein Hygienehinweis, sondern Arithmetik.¹

Nichts oben brauchte eine Bibliothek. Hier ist der ganze Optimierer.

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

Die geschlossene Least-Squares-Lösung für diese acht Punkte ist $a = 2.100403$, $b = 0$, mit einem Loss von $24.592449$. Die Schleife hat sie auf acht signifikante Stellen gefunden, ohne zu wissen, dass es eine geschlossene Form gibt — was wichtig ist, weil es ab Kapitel 5 keine mehr geben wird.

Die Trajektorie, denn ihr zuzusehen ist der Punkt:

   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

Der größte Teil der Strecke wird in den ersten zwei Schritten zurückgelegt, weil der Gradient am größten ist, wenn du am weitesten vom Boden entfernt bist, und schrumpft, wenn du dich näherst. Gradient descent verlangsamt sich nahe einem Minimum automatisch. Das ist ein Feature, und in Kapitel 6 ist es auch ein Problem.

Das bisherige Argument hat ein Loch. Der Schritt stoppt, wenn $\nabla L = \mathbf{0}$, und wir haben das „das Minimum“ genannt. Ein Punkt mit Gradient null ist ein kritischer Punkt, und ein Minimum zu sein ist nur eine der Möglichkeiten, einer zu sein:

• ein lokales Minimum: bergauf in jede Richtung, aber möglicherweise nicht der tiefste solche Punkt überhaupt;
• ein lokales Maximum: bergab in jede Richtung;
• ein Sattelpunkt: bergauf in manche Richtungen und bergab in andere. Die Fläche $f(x,y) = x^2 - y^2$ hat $\nabla f = (2x, -2y)$, was am Ursprung null ist, wo die Funktion entlang der $x$-Achse ein Minimum und entlang der $y$-Achse gleichzeitig ein Maximum ist.

Gradient descent kann diese nicht unterscheiden, weil es immer nur auf den Gradient schaut, und der Gradient bei allen dreien null ist.

Unsere Gerade hat einen kritischen Punkt, und er ist die Antwort — ein Squared-Error-Loss über einem linearen Modell ist konvex, eine einzelne Schüssel, und descent darauf kann das globale Minimum nicht verfehlen. Diese Eigenschaft überlebt den Kontakt mit diesem Kurs nicht. Der Loss eines neuronalen Netzwerks ist nicht konvex, und ab Kapitel 5 ist „das Minimum“ kein Ding, das existiert: Es gibt viele, in unterschiedlichen Tiefen, und welches du bekommst, hängt davon ab, wo du gestartet bist. Das ist ein Satz und bleibt ein Satz, weil die Theorie groß und die praktische Konsequenz klein ist.

Du kannst die ganze Konsequenz an einer Kurve sehen. Nimm $f(x) = \tfrac{x^4}{4} - \tfrac{x^2}{2} + \tfrac{x}{10}$, das zwei Täler unterschiedlicher Tiefe hat:

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

Im flachen Tal zu landen ist im Loss 56,7% schlechter, und der Algorithmus hat keine Möglichkeit, das zu wissen, weil aus dem Inneren eines Tals jede Richtung bergauf geht. Dafür gibt es in gradient descent keine Reparatur, und es wird keine kommen. Was es in der Praxis gibt, ist der Befund, dass es weit weniger zählt, als dieses Bild nahelegt — in den sehr hohen Dimensionen eines echten Netzwerks erweisen sich die meisten kritischen Punkte als Sättel statt als Fallen,² und Kapitel 5 misst, wie oft ein kleines Netzwerk tatsächlich stecken bleibt.

Eine Sache an grad oben sollte dich stören: Es summiert für jeden Schritt über den gesamten Datensatz. Acht Teile sind nichts. Eine Million sind eine Million Gradientenberechnungen, um die Parameter einmal zu bewegen.

Der Ausweg ist, dass der Gradient ein Durchschnitt ist, und ein Durchschnitt lässt sich aus einer Stichprobe schätzen. Berechne ihn auf einer zufälligen Handvoll — einem Minibatch — und mache darauf den Schritt. Die Schätzung ist verrauscht; sie ist aber auch unverzerrt, und Hunderte billige verrauschte Schritte schlagen einen teuren exakten. Auf hunderttausend synthetischen Teilen, gezählt in Gradienten pro Beispiel statt in Schritten:

Zweihundertneunzehnmal weniger Arithmetik, um denselben Ort zu erreichen. Und das Extrem — ein Beispiel auf einmal, die ursprüngliche stochastische Approximation von Robbins und Monro³ — ist nicht der Gewinner: Es ist fünfmal schlechter als Batches von 32, weil 32 Beispiele auf Hardware, die Matrizen multipliziert, fast nichts mehr kosten als eines, während das Rauschen mit der Quadratwurzel der Batch-Größe abfällt. Dieser Trade-off ist der Grund, warum jedes Trainingsskript, das du je lesen wirst, ein batch_size enthält.

Momentum ist die andere billige Korrektur, und sie zielt genau auf den Graben. In einem schlecht konditionierten Tal zickzacken die Schritte über die schmale Richtung, während sie in der langen langsam vorankriechen. Momentum hält einen laufenden Durchschnitt vergangener Gradienten, sodass die oszillierenden Komponenten sich aufheben und die konsistente sich ansammelt:⁴

Zwei zusätzliche Zeilen. Auf dem rohen, unzentrierten Förderband — Konditionszahl 33.452, der schlimmste Fall, den wir haben — bei der besten Rate, die plain descent nehmen kann:

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%

Ein Faktor von 172 für zwei Codezeilen. Kapitel 6 macht daraus Adam; der Mechanismus ist schon hier.

Jeder Gradient in diesem Kapitel wurde von Hand hergeleitet und könnte daher falsch sein. Die Korrektur ist die Steigungstabelle vom Anfang: Miss die Ableitung numerisch und vergleiche. Verwende die zentrale Differenz, $\frac{L(\theta+h) - L(\theta-h)}{2h}$, die den führenden Fehlerterm aufhebt und für dasselbe $h$ sehr viel genauer ist.

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)))

Die relative Form des Vergleichs ist wichtig: Eine absolute Differenz von $10^{-4}$ ist bei einem Gradient der Größe $10^{-3}$ eine Katastrophe und bei einem der Größe $10^{6}$ irrelevant.

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

Die erste Zeile ist der oben von Hand hergeleitete Gradient. Die zweite ist dieselbe Funktion, bei der in einer Komponente der Faktor 2 fehlt — ein Tippfehler eines einzelnen Zeichens —, und der Check erwischt ihn sofort. Alles unter etwa $10^{-7}$ ist Übereinstimmung; alles über $10^{-4}$ ist ein Bug. Behalte diese Funktion: Kapitel 5 benutzt sie, um eine Automatic-Differentiation-Engine zu debuggen, und sie ist der einzige Grund, warum ein falscher Gradient überhaupt auffindbar ist.

Alles in diesem Kapitel beruhte auf einer Annahme, die nie ausgesprochen wurde: dass du $\partial L / \partial \theta$ hinschreiben kannst.

Für eine Gerade mit zwei Parametern war das eine Zeile Algebra. Fast sofort ist es das nicht mehr. Bitte ein symbolisches Algebrasystem um die Ableitung des Loss eines Netzwerks nach einem einzigen Gewicht in der ersten Schicht, für ein einziges Beispiel, und zähle die Arithmetik in der Antwort:

Die dritte Zeile ist ein Netzwerk mit 57 Parametern — ein Netzwerk, das so klein ist, dass es in Kapitel 6 eine Fußnote wäre —, und seinen Gradient von Hand auszuschreiben bedeutet etwa 97.869 Operationen für ein Trainingsbeispiel. Es gibt keine Notation, die das rettet. Was es rettet, ist die Beobachtung, dass die Kettenregel, angewendet auf eine Komposition, enorme Struktur hat, dass dieselben Zwischenwerte immer wieder auftauchen und dass ihre Berechnung in der richtigen Reihenfolge alle Ableitungen ungefähr zum Preis eines forward pass liefert. Das ist Kapitel 5.

Aber zuerst gibt es ein kleineres Problem, und es wartet unmittelbar.

Wir haben jetzt eine Maschine, die auf jedem differenzierbaren Loss bergab rollen wird. Richte sie auf die ursprüngliche Frage des Förderbands — akzeptieren oder ablehnen, ein Ziel, das 1 oder 0 ist —, setze ein Sigmoid auf die Ausgabe, sodass sie eine Wahrscheinlichkeit vorhersagt, und minimiere squared error. Sie wird laufen. Sie wird sich aber auch kaum bewegen, wenn sie am falschesten liegt, und der Gradient sagt warum:

Ein Modell, das selbstbewusst, katastrophal falsch liegt — es sagt 0,0000454 voraus, wenn die Antwort 1 ist —, erzeugt einen squared-error-Gradient von $9 \times 10^{-5}$. Es hat keine Ahnung, dass es in Schwierigkeiten steckt. Die andere Spalte, aus einem Loss, den wir noch nicht hergeleitet haben, meldet 1,0: maximale Dringlichkeit, genau dort, wo sie verdient ist.

Das wirft die Frage auf, mit der das nächste Kapitel beginnt. Das letzte Kapitel sagte, ein Loss sei eine Annahme über das Rauschen, und squared error nimmt Gaußsches Rauschen an. Welches Rauschmodell hat eine Ja-oder-Nein-Antwort — und welcher Loss kommt heraus, wenn du dieselbe Herleitung darauf anwendest?

Die Methode ist älter als all diese Quellen: Cauchy beschrieb sie 1847 in einer Notiz an die Académie des Sciences, als Verfahren zum Lösen von Gleichungssystemen, indem man auf der Summe ihrer quadrierten Residuen bergab geht. Ebenfalls lesenswert neben diesem Kapitel: Sebastian Ruders An overview of gradient descent optimization algorithms (arXiv:1609.04747), das Momentum bis Adam auf vierzehn gut lesbaren Seiten behandelt; Kapitel 3 von Nocedal und Wrights Numerical Optimization (2. Aufl., Springer, 2006), dessen Satz 3.3 die Konvergenzrate von steepest descent auf einer Quadrik in Bezug auf die Konditionszahl angibt — es ist die Theorie dahinter, warum die Konditionierung die Schrittzahl entscheidet, auch wenn es line search statt der oben gemessenen fixed-step-$2/\lambda_{\max}$-Obergrenze behandelt —, oder §5.8 und §7.1 von Deisenroth, Faisal und Ongs Mathematics for Machine Learning für denselben Stoff mit weniger Maschinerie; §6.1 von Princes Understanding Deep Learning und §4.3 von Goodfellow, Bengio und Courvilles Deep Learning; Dive into Deep Learning §12.1–12.3, das die Minibatch-Analyse mit mehr Messungen enthält, als hier Platz haben; und Kapitel 4 von Géron's Hands-On Machine Learning (3. Aufl.), die praktischste Behandlung der Lernrate als etwas, das du abstimmst, statt herzuleiten. Die MIT-6.390-Notizen stellen gradient descent vor die Klassifikation, so wie dieser Kurs, und aus demselben Grund.