4.2 Gradientenabstieg

Für die lineare Regression gibt es eine geschlossene Lösung (4.3). Trotzdem führen die Folien hier den Gradientenabstieg (gradient descent) ein, weil er ein sehr allgemeines Verfahren ist, das für viele ML- und praktisch alle DL-Algorithmen funktioniert 📄 04_linear_methods_ws26.pdf, Folie 9.

Stell dir vor, du stehst mit verbundenen Augen an einem Hang und willst ins Tal. Du kannst nicht sehen, wo das Tal ist, aber du spürst mit den Füßen, in welche Richtung es bergab geht und wie steil es ist. Also machst du einen Schritt in Richtung des steilsten Abstiegs, tastest erneut, machst den nächsten Schritt usw.

Übersetzt: Die Höhe ist der Verlust, die Position sind die Parameter, die gefühlte Neigung ist die Ableitung des Verlusts nach den Parametern.

Für die Abbildung auf der Folie wird $b$ festgehalten und nur $a$ variiert. Der Verlust ist dann eine Parabel in $a$ .

Die Update-Regel

📄 04_linear_methods_ws26.pdf, Folie 10

a_{t+1} = a_t - \eta\cdot\operatorname{grad}_a(\text{Loss}), \qquad \operatorname{grad}_a(\text{Loss}) = \frac{\partial\,\text{Loss}}{\partial a}

$t$ zählt die Schritte (Iterationen).
$\eta$ ist die Lernrate (learning rate), sie bestimmt die Schrittweite.
Warum das Minus? Ist die Ableitung positiv, steigt der Verlust mit wachsendem $a$ . Man muss also $a$ verkleinern, um bergab zu gehen. Ist sie negativ, muss $a$ wachsen. Das Minuszeichen sorgt in beiden Fällen für die richtige Richtung.
Automatische Schrittweitenanpassung: Die Schrittlänge ist $\eta\cdot\lvert\operatorname{grad}\rvert$ . Weit weg vom Minimum ist der Hang steil und die Schritte sind groß, nahe am Minimum wird die Ableitung klein und die Schritte werden kürzer. Im Minimum selbst ist die Ableitung 0, das Verfahren bleibt stehen.

Die richtige Lernrate

Die rote Frage der Folie: Wie wählt man die Schrittweite, wenn man blind ist? 📄 04_linear_methods_ws26.pdf, Folie 11 zeigt drei Lernraten auf derselben Parabel:

Lernrate	Verhalten
$\eta = 0{,}0001$	kleine Schritte, konvergiert stetig von einer Seite, aber langsam
$\eta = 0{,}0003$	springt über das Minimum, pendelt aber schnell ein
$\eta = 0{,}00045$	springt jedes Mal weiter auf die andere Seite: Divergenz, der Verlust wächst

Es gibt keine universell richtige Lernrate. Sie hängt von der Krümmung der Verlustfunktion ab und damit auch von der Skalierung der Daten. In der Praxis probiert man aus (typisch in Zehnerpotenzen) und beobachtet die Verlustkurve. Zum Ausprobieren verweist die Folie auf den Google Machine Learning Crash Course.

Durchgerechnetes Beispiel

Ergänzung, nicht auf den Folien: Die drei Punkte $(1,2)$ , $(2,3)$ , $(3,5)$ aus 4.1. Wie auf der Folie halten wir $b$ fest, und zwar beim optimalen Wert $b = 1/3$ . Dann ist

\text{Loss}(a) = \frac13\sum_{i=1}^3 \big(y_i - \tfrac13 - a x_i\big)^2, \qquad \frac{\partial\,\text{Loss}}{\partial a} = -\frac23\sum_i x_i\big(y_i - \tfrac13 - a x_i\big) = -\frac23(21 - 14a).

(Mit $\sum x_iy_i = 23$ , $\sum x_i = 6$ , $\sum x_i^2 = 14$ .) Das Minimum liegt bei $a^* = 1{,}5$ .

Start $a_0 = 0$ , Lernrate $\eta = 0{,}05$ :

$t$	$a_t$	Gradient	$a_{t+1} = a_t - 0{,}05\cdot\text{Gradient}$
0	0	$-\frac23\cdot 21 = -14$	$0{,}7$
1	0,7	$-\frac23(21-9{,}8) = -7{,}47$	$1{,}073$
2	1,073	$-3{,}98$	$1{,}272$
3	1,272	$-2{,}12$	$1{,}379$

Der Abstand zum Optimum schrumpft jedes Mal um den Faktor $0{,}533$ .

Warum genau dieser Faktor? Der Gradient ist linear in $a$ : $\operatorname{grad}(a) = \frac{28}{3}(a - a^*)$ , wobei $\frac{28}{3}$ die zweite Ableitung (Krümmung) ist. Einsetzen in die Update-Regel:

a_{t+1} - a^* = \Big(1 - \eta\cdot\tfrac{28}{3}\Big)(a_t - a^*).

$\eta$	Faktor $1 - \eta\cdot 28/3$	Verhalten
$0{,}01$	$0{,}91$	sehr langsam
$0{,}05$	$0{,}53$	zügig, von einer Seite
$0{,}107$	$0$	Minimum in einem Schritt
$0{,}2$	$-0{,}87$	pendelt über das Minimum, konvergiert langsam
$0{,}25$	$-1{,}33$	divergiert: $a_1 = 3{,}5$ , $a_2 = -1{,}17$ , …

Konvergenz gibt es genau dann, wenn $\lvert 1 - \eta\cdot\text{Krümmung}\rvert$ kleiner als 1 ist, also für $\eta$ kleiner als $2/\text{Krümmung} \approx 0{,}214$ . Das ist genau das Muster der drei Bilder auf Folie 11.

Gradientenabstieg in zwei (und mehr) Dimensionen

Lässt man $a$ und $b$ gleichzeitig variieren, ist der Verlust eine Fläche über der $(a,b)$ -Ebene 📄 04_linear_methods_ws26.pdf, Folie 12. Zoomt man weit genug hinein, sieht sie lokal aus wie eine schiefe Ebene (rechtes Bild der Folie). Man berechnet die Ableitung in jede Richtung und geht in beide gleichzeitig:

a_{t+1} = a_t - \eta\cdot\operatorname{grad}_a, \qquad b_{t+1} = b_t - \eta\cdot\operatorname{grad}_b

Die beiden „Kräfte“ $-\operatorname{grad}_a$ und $-\operatorname{grad}_b$ addieren sich vektoriell zur Richtung des steilsten Abstiegs. In Vektorschreibweise mit allen Gewichten $W$ :

W^{t+1} = W^t - \eta\cdot\nabla W

Komponentenweise 📄 04_linear_methods_ws26.pdf, Folie 13:

w_i^{t+1} = w_i^t - \eta\cdot\frac{\partial\,\text{loss}}{\partial w_i}, \qquad \nabla\text{loss} = \left(\frac{\partial\,\text{loss}}{\partial w_1}, \frac{\partial\,\text{loss}}{\partial w_2}\right)

Der Gradient $\nabla\text{loss}$ zeigt in Richtung des steilsten Anstiegs und steht senkrecht auf den Höhenlinien. Gradientenabstieg geht in die Gegenrichtung $-\nabla\text{loss}$ .

Warum senkrecht? Ergänzung: Entlang einer Höhenlinie ändert sich der Verlust nicht, die Richtungsableitung in Richtung der Höhenlinie ist also 0. Die Richtungsableitung in Richtung $\boldsymbol v$ ist $\nabla\text{loss}\cdot\boldsymbol v$ . Ist sie 0, stehen $\nabla\text{loss}$ und $\boldsymbol v$ senkrecht.

Zickzack bei länglichen Tälern

Auf 📄 04_linear_methods_ws26.pdf, Folie 13 sind die Höhenlinien Ellipsen. Der Gradient zeigt senkrecht zur Höhenlinie, aber nicht direkt auf das Minimum. Deshalb läuft der Weg $w^0 \to w^1 \to w^2 \to \dots$ gekrümmt. Ergänzung: Bei stark gestreckten Ellipsen (Merkmale auf sehr unterschiedlichen Skalen, z. B. Alter in Jahren und Einkommen in Euro) entsteht ein Zickzack und die Konvergenz wird langsam. Deshalb standardisiert man die Merkmale vor dem Gradientenabstieg.

Gefahren: lokale Minima

📄 04_linear_methods_ws26.pdf, Folie 14 zeigt den blinden Wanderer in einer Berglandschaft: Gradientenabstieg findet nur ein lokales Minimum. Landet man in einer Mulde, die nicht die tiefste ist, kommt man dort nicht mehr heraus.

Viele Probleme im ML sind konvex (convex): Es gibt nur ein Tal, jedes lokale Minimum ist global. Das gilt für lineare Regression, Ridge-Regression und logistische Regression.
Im Deep Learning sind die Verlustfunktionen nicht konvex. Gradientenabstieg funktioniert dort aber trotzdem erstaunlich gut („magisch“, wie die Folie sagt).

Ergänzung, nicht auf den Folien: Eine Funktion ist konvex, wenn die Verbindungsstrecke zwischen zwei Punkten ihres Graphen nie unterhalb des Graphen liegt. Für zweimal differenzierbare Funktionen heißt das: Die zweite Ableitung (bzw. die Hesse-Matrix) ist überall nichtnegativ (positiv semidefinit). Der MSE der linearen Regression hat die Hesse-Matrix $\frac2n X^TX$ , die immer positiv semidefinit ist.

Minimal-Implementierung

Ergänzung, nicht auf den Folien: Gradientenabstieg für die 1D-Regression in NumPy. Die Gradienten folgen aus $\text{MSE} = \frac1n\sum(y_i - a x_i - b)^2$ .

import numpy as np

x = np.array([1.0, 2.0, 3.0])
y = np.array([2.0, 3.0, 5.0])
a, b, eta = 0.0, 0.0, 0.05

for t in range(2000):
    r = y - (a * x + b)               # Residuen
    grad_a = -2 * np.mean(x * r)
    grad_b = -2 * np.mean(r)
    a -= eta * grad_a
    b -= eta * grad_b

print(a, b)   # -> ca. 1.5, 0.333

Das Bild: blind den Berg hinunter​

Die Update-Regel​

Die richtige Lernrate​

Durchgerechnetes Beispiel​

Gradientenabstieg in zwei (und mehr) Dimensionen​

Gefahren: lokale Minima​

Minimal-Implementierung​

Das Bild: blind den Berg hinunter