Gradientenabstieg

Im letzten Kapitel blieb die Frage offen, in welche Richtung man von der bisher besten Schätzung $w$ aus gehen soll, damit die Loss-Funktion kleiner wird. Die Antwort ist der Gradient, und um ihn für verkettete Funktionen auszurechnen, brauchen wir zuerst die Kettenregel.

Kurze Erinnerung an die Kettenregel¶

Für das Training werden wir Ableitungen von verketteten Funktionen brauchen, deshalb die Kettenregel in der Form, die wir benötigen: für Funktionen zwischen Vektorräumen.

Für eine Funktion $g \colon \mathbb{R}^n \to \mathbb{R}^m$ an einem Punkt $x_0$ ist die Ableitung $(Dg)(x_0)$ – eine $m \times n$-Matrix, die Jacobi-Matrix – die beste lineare Approximation, also für $x_1$ nah bei $x_0$:

Gegeben eine weitere Funktion $f \colon \mathbb{R}^m \to \mathbb{R}^k$, ebenso

Im Spezialfall $y_0 = g(x_0)$, $y_1 = g(x_1)$ setzen wir ein:

Damit ist $(Df)(g(x_0)) \cdot (Dg)(x_0)$ die beste lineare Approximation von $f \circ g$ bei $x_0$. In anderer Notation der gleiche Sachverhalt:

Die Ableitung einer Verkettung ist das Matrixprodukt der Ableitungen, ausgewertet an den richtigen Stellen. Das ist bereits die halbe Backpropagation.

Summe über alle Pfade. Die Matrixform versteckt einen Fall, der beim Rechnen von Hand oft schiefgeht: Wenn eine Variable auf mehreren Wegen in das Ergebnis eingeht, addieren sich die Beiträge. Für $L = u \cdot v$ mit $u = g(w)$ und $v = h(w)$ ist

Kleinstes Beispiel: $u = w$ und $v = w$, also $L = w^2$. Wer nur einem Pfad folgt, erhält $w$; richtig ist $w + w = 2w$. In einem Netz geht jedes Gewicht der ersten Schicht über alle Neuronen der zweiten Schicht in den Loss ein. Backpropagation ist im Kern die Buchhaltung dieser Summe, und die Matrixmultiplikation $(Df)\,(Dg)$ erledigt sie automatisch: Ein Matrixprodukt ist eine Summe über Zwischenindizes.

Numerische Probe. Ableitungen kann man nachprüfen, ohne sie zu kennen: Für kleines $h$ ist

Beispiel: $L(w) = (1 - 2w)^2$, also $L'(w) = -4\,(1 - 2w)$ und $L'(1) = 4$. Nachrechnen: $L(1) = 1$, $L(1{,}01) = (1 - 2{,}02)^2 = 1{,}0404$, Differenzenquotient $0{,}0404 / 0{,}01 = 4{,}04$. Diese Probe (gradient check) ist der wichtigste Handgriff, wenn eine von Hand hergeleitete Ableitung oder ein selbst geschriebenes backward nicht stimmen will. PyTorch hat sie eingebaut: torch.autograd.gradcheck.

Gradienten¶

Wir stellen uns für den Moment vor, dass $w \in \mathbb{R}^2$ ist (also die Daten zwei Features haben). Wir stellen uns die $w$-Ebene vor und darauf ein $L(w)$-Gebirge. An jedem Punkt die Frage: Wohin sollen wir gehen, wenn wir runter wollen? Antwort: In die Richtung, wo $L(w)$ am schnellsten kleiner wird, also „nach unten“ – das heißt entlang des negativen Gradienten $\operatorname{grad}(L)(w) = L'(w) \in \mathbb{R}^2$.

Gradienten konkret¶

Betrachten wir den MSE für eine lineare Regression, mit der Notation $x^{(i)}_j$ für Feature $j$ von Datenpunkt $i$ aus dem Kapitel „Was ist Deep Learning?“:

Halte zunächst die Komponente $w_2$ fest und variiere $w_1$. Das gibt eine Funktion in einer Variablen, $w_1 \mapsto L(w_1, w_2)$, und ihre Ableitung gibt die Änderung von $L$ abhängig von $w_1$ an, also die Änderung in Richtung der ersten Koordinate der $w$-Ebene: „Wenn ich einen (infinitesimalen) Schritt nach Osten gehe, wie stark ändert sich $L$ dann?“ Danach $w_1$ festhalten und $w_2$ variieren: ein Schritt nach Norden.

Diese beiden Ableitungen heißen besser partielle Ableitungen $\frac{\partial}{\partial w_1} L(w)$ und $\frac{\partial}{\partial w_2} L(w)$, und der Gradient ist der Vektor aus beiden:

Nicht verwechseln: die Ableitung $L'$ (eine Funktion, die jedem $w$ einen Vektor zuordnet) und $L'(w)$, der Gradientenvektor an einem Punkt $w$.

Richtungsableitung. Die Änderung in Richtung $e_1$ ist $\langle L'(w), e_1 \rangle = \frac{\partial L}{\partial w_1}(w)$. Die Änderung in Richtung eines beliebigen Einheitsvektors $v$ ist

In welche Richtung $v$ ist die Änderung maximal? Das Skalarprodukt $\langle L'(w), v \rangle$ ist $\|L'(w)\| \cos \alpha$ mit dem Winkel $\alpha$ zwischen $v$ und dem Gradienten, und der Kosinus ist maximal 1, wenn $v$ in Richtung $L'(w)$ zeigt, und minimal -1 in der Gegenrichtung. Der Gradient zeigt bergauf, der negative Gradient bergab.

Endlich ausrechnen. Mit der Kettenregel:

Der Algorithmus¶

Damit haben wir die sehr clevere Variante der approximativen Minimierung:

1. Sehr clever ein $w$ auswählen, in der Nähe der bisher besten Schätzung:

   $$w_{\text{neu}} := w_{\text{alt}} - \rho\, L'(w_{\text{alt}}).$$

   (12)

2. $L(w)$ ausrechnen, vergleichen mit dem bisher niedrigsten Wert,

3. Größer? Pech gehabt, weitermachen (ggf. mit kleinerem $\rho$). Kleiner? Besseres $w$ gefunden!

4. Jetzt ggf. aufhören, wenn $w$ gut genug ist.

Das ist der Gradientenabstieg, und $\rho$ ist die Lernrate – dieselbe, die wir beim Perzeptron schon hatten. Zu klein, und man braucht ewig; zu groß, und man springt über das Tal hinweg.

Wie groß „zu groß“ ist, hängt von den Daten ab, und zwar von jedem Feature einzeln. Für den MSE ist $\frac{\partial L}{\partial w_j} = \frac1N \sum_i 2\,(y_i - \langle w, x^{(i)} \rangle)\,(-x^{(i)}_j)$, also proportional zu den Werten von Feature $j$. Hat Feature 1 Werte um 1 und Feature 2 Werte um 1000 (Körpergröße in Metern, Einkommen in Euro), so ist die zweite Gradientenkomponente etwa tausendmal größer als die erste, und die Krümmung des Loss-Gebirges in $w_2$-Richtung ist eine Million mal größer: Das Tal ist eine lange, schmale Schlucht. Eine Lernrate, die in $w_1$-Richtung vernünftig vorankommt, springt in $w_2$-Richtung über die Schlucht hinaus; eine, die dort stabil ist, kriecht in $w_1$-Richtung.

Der einfachste Ausweg ist, alle Features vorher auf Mittelwert 0 und Standardabweichung 1 zu bringen (Standardisierung, sklearn.preprocessing.StandardScaler, und beim Testset mit den Werten aus dem Trainingsset skalieren). Dass dieselbe Idee auch innerhalb eines Netzes hilft (Batch Normalization, Layer Normalization) und dass Optimierer wie Adam die Lernrate pro Parameter anpassen, sehen wir in späteren Kapiteln; der Grund ist immer dieser.

Wie so ein Loss-Gebirge für ein echtes neuronales Netz aussieht, zeigen z.B. Li, Xu, Taylor, Studer und Goldstein, Visualizing the loss landscape of neural nets (arXiv:1712.09913, 2017). Die Landschaften sind nicht konvex, es gibt viele lokale Minima, Sattelpunkte und Plateaus – und trotzdem funktioniert Gradientenabstieg erstaunlich gut.

Zurück zum Perzeptron¶

Die neue Perspektive erklärt auch die Perzeptronregel. Der „harte“ Perceptron Loss $\sum_i \max(0, -y_i \operatorname{sign}\langle w, x_i \rangle)$ hat ein Problem: Ableitung?!? Die Funktion ist stückweise konstant, der Gradient ist fast überall 0. Besser ist der „weiche“ Perceptron Loss ohne das $\operatorname{sign}$:

Ein Summand ist 0, wenn $x_i$ korrekt klassifiziert ist ($y_i \langle w, x_i \rangle > 0$), und sonst $-y_i \langle w, x_i \rangle > 0$, also proportional dazu, wie weit auf der falschen Seite $x_i$ liegt. Die (schwache) Ableitung ist

die Summe über die falsch klassifizierten Samples. Die allgemeine Update-Regel $w_{\text{neu}} = w_{\text{alt}} - \rho\, L'(w)$ liefert für ein einzelnes $(x, y_{\text{true}})$, also $N = 1$:

Das ist exakt die Perzeptronregel. Rosenblatt hat also, ohne es so zu nennen, stochastischen Gradientenabstieg auf dem Perceptron Loss gemacht.

Und zurück zur logistischen Regression¶

Für die BCE lohnt sich dieselbe Rechnung, denn sie hat eine Pointe. Für ein einzelnes Sample $(x, y)$ mit Logit $z = \langle w, x \rangle$ und $p = \sigma(z)$ ist

Mit $\sigma' = \sigma(1 - \sigma)$ und der Kettenregel:

Alle Logarithmen und Sigmoide heben sich gegenseitig weg; übrig bleibt der Vorhersagefehler. Mit $\frac{\partial z}{\partial w} = x$ ist der Gradient $(p - y)\,x$, und die Update-Regel lautet

Das ist buchstäblich die Perzeptronregel aus dem Kapitel „Das Perzeptron trainieren“, nur mit $f(x) = \sigma(\langle w, x \rangle)$ statt $[\langle w, x \rangle > 0]$: Statt „falsch oder richtig“ zählt jetzt „um wie viel daneben“. Die Formel $p - y$ werden wir bei Backpropagation als Startwert der Rückwärtsrechnung wiedersehen; sie gilt genauso für Softmax mit Kreuzentropie.

Loss-Funktionen, die wir bisher gesehen haben¶

Für ein einzelnes Sample mit $y = 1$, aufgetragen gegen den Wert der Entscheidungsfunktion $f(x) = \langle w, x \rangle$:

• Perceptron Loss $\max(0, -f(x))$: null, sobald $f(x) > 0$, davor linear.

• Hinge Loss $\max(0, 1 - f(x))$: null erst ab $f(x) \ge 1$, verlangt also einen Sicherheitsabstand (Margin) – das ist der Loss der Support Vector Machine.

• BCE Loss $-\log \sigma(f(x))$: glatt, wird nie exakt null, bestraft auch richtig klassifizierte Samples noch ein bisschen, wenn sie nahe an der Grenze liegen.

Take-Home Message¶

Ein einzelnes Neuron besteht aus einer Aktivierungsfunktion $\tau$ und einem Gewichtsvektor $w$ (den Parametern). Inferenz:

Training, mit Hyperparameter $\rho$, hängt von der Loss-Funktion $L(w)$ ab:

Für binäre Klassifikation nimmt man $\tau = \sigma$ und $L = L_{\text{BCE}}$. Das ist logistische Regression. In echt kennt man die Landschaft nicht und muss die Lernrate ausprobieren.

Nicht-stochastischer Gradientenabstieg??¶

Gradientenabstieg ist der Oberbegriff und gleichzeitig die spezifische Bezeichnung für: den ganzen Datensatz einlesen, dabei die Loss-Funktion auswerten und den Gradienten bestimmen, damit die Gewichte anpassen, und erneut den ganzen Datensatz einlesen usw. (auch Batch Gradient Descent).

Stochastischer Gradientenabstieg (SGD) ist das Anpassen der Gewichte mit einer Schätzung des Gradienten aus einem Teildatensatz – meist ist ein einzelnes Sample gemeint. Das ist zufällig gewählt (die Anordnung der Daten wird als zufällig angenommen), daher stochastisch. Der geschätzte Gradient ist verrauscht, aber im Mittel korrekt, und man kommt viel häufiger zu einem Update.

Was „im Mittel korrekt“ genau heißt: Der Loss $L(w) = \frac1N \sum_{i=1}^N \ell(x_i, y_i; w)$ ist ein Stichprobenmittel, also eine Schätzung des Erwartungswerts $\mathbb{E}\bigl[\ell(X, Y; w)\bigr]$ über die erzeugende Verteilung aus dem Kapitel „Was ist Deep Learning?“. Das ist die Größe, die wir eigentlich klein haben wollen, denn sie misst den Fehler auf neuen Daten. Der Gradient eines Mini-Batches ist ebenfalls ein Stichprobenmittel; weil der Erwartungswert linear ist, ist sein Erwartungswert der Gradient des vollen Loss. Nach dem Gesetz der großen Zahlen (DS-Skript) liegt das Mittel über viele Batches nahe daran, auch wenn jeder einzelne Batch danebenliegt.

Wo steckt in diesem Verfahren überall Zufall? Im Startvektor, in den Daten, die wir als Stichprobe einer Verteilung modellieren, und in der Reihenfolge, in der die Samples verarbeitet werden. Deshalb liefern zwei Trainingsläufe mit denselben Daten verschiedene Gewichte, und ein Schritt lässt sich nicht sinnvoll rückgängig machen; man kann nur neu starten.

Der Kompromiss ist Mini-Batch SGD: Eine kleine, handhabbare Menge von Samples (die Batch Size, z.B. 32 oder 64) wird gemeinsam verarbeitet und damit der Gradient approximiert. Das ist, was in der Praxis fast immer gemeint ist, wenn jemand „SGD“ sagt – auch torch.optim.SGD aus dem Kapitel „Logistische Regression“ weiß nichts davon, wie viele Samples im Batch waren. Ein Durchlauf durch den gesamten Datensatz heißt Epoche.

Übung¶

Sei $x = (2, -1)$ fest und $L(w) := (1 - w \cdot x)^2$.

1. Bestimmen Sie $\frac{\partial L}{\partial w_1}$ und $\frac{\partial L}{\partial w_2}$ mit der Kettenregel. Tipp: Äußere Funktion $u \mapsto u^2$, innere $w \mapsto 1 - w\cdot x$. Die Ableitung von $w \cdot x$ nach $w_j$ ist $x_j$ – mehr steckt nicht dahinter.

2. Werten Sie den Gradienten bei $w = (0,0)$ aus und führen Sie einen Schritt mit Lernrate $\rho = 0{,}1$ aus.

3. Berechnen Sie $L$ vor und nach dem Schritt.

Antwortprobe: $L$ ist nach dem Schritt exakt 0 – bei $\rho = 0{,}1$ und $\|x\|^2 = 5$ landet man genau im Minimum. Kommt etwas anderes heraus, fehlt meist der Faktor 2 aus der Kettenregel.