Backpropagation

Ziel¶

Verstehen können, was im TensorFlow Playground geschieht.

Genau das Mühsame soll der Gradientenabstieg übernehmen. Dafür brauchen wir den Gradienten der Loss-Funktion nach allen Gewichten aller Schichten.

Training mehrerer Schichten: Motivation¶

Beispielsetup 1¶

Eingabedaten sind eindimensional, ein einzelnes Neuron mit Aktivierungsfunktion $\sigma$ produziert eine Ausgabe, die stecken wir in ein zweites Neuron mit Aktivierungsfunktion $\operatorname{id}$. Also:

Wir planen eine Regression mit $x, y \in \mathbb{R}$, daher nehmen wir den quadratischen Fehler – hier als reine Summe, ohne den Faktor $\frac1N$ des MSE aus dem Kapitel „Gradientenabstieg“. Der Faktor verschiebt das Minimum nicht, nur die Größe des Gradienten und damit die passende Lernrate:

Die Frage ist also nur: Was ist $\frac{\partial}{\partial W} y_{\text{pred}}$, die Ableitung der Netzausgabe nach den Gewichten?

Vorbereitung¶

Nehmen wir $W = (w_{\text{erst}}, w_{\text{zweit}})$, so können wir $y_{\text{pred}}$ als Funktion von $W$ auffassen, $y_{\text{pred}}(W) = \langle w_{\text{zweit}}, \sigma(\langle w_{\text{erst}}, x \rangle) \rangle$, und die Ableitung nach $W$ wie zuvor in Komponenten berechnen. Dafür brauchen wir zwei Bausteine:

• Was ist die Ableitung von $\sigma(f(w))$ nach $w$? Kettenregel: $\frac{d}{dw} \sigma(f(w)) = \sigma'(f(w)) \, f'(w)$.

• Was ist die Ableitung von $\langle w, x \rangle$ nach $w$, und von $\langle v, f(w) \rangle$ nach $w$? Es ist $\frac{d}{dw} \langle w, x \rangle = x$ und $\frac{d}{dw} \langle v, f(w) \rangle = \langle v, f'(w) \rangle$.

Damit:

Die Update-Regeln¶

Eingesetzt in $L'$ und in die Gradientenabstiegs-Regel $W_{\text{neu}} = W_{\text{alt}} - \rho L'(W_{\text{alt}})$:

Das funktioniert, aber es ist unübersichtlich – und man sieht schon, dass Teilausdrücke mehrfach vorkommen: der Residuenterm $y_i - y_{\text{pred},i}$ und die Aktivierung $\sigma(\langle w_{\text{erst}}, x_i \rangle)$ der ersten Schicht tauchen in beiden Regeln auf.

Beispielsetups 2 und 3: mehr Dimensionen, mehr Neuronen¶

Setup 2: Eingabedaten sind zweidimensional, sonst wie oben. Jetzt neu: $w_{\text{erst}} \in \mathbb{R}^2$. An den Formeln ändert sich nichts, die Skalarprodukte sind nur länger.

Setup 3: Eingabedaten sind zweidimensional, zwei Neuronen mit Aktivierungsfunktion $\sigma$ und Gewichten $u, v \in \mathbb{R}^2$ produzieren Ausgaben, die stecken wir in ein drittes Neuron mit Aktivierungsfunktion $\operatorname{id}$ und Gewichten $w \in \mathbb{R}^2$:

Layer¶

Mehrere Neuronen, die parallel verarbeitet werden, bilden eine Schicht (Layer). Mehrmals lineare Regression ist multiple lineare Regression ist ein Linear Layer ist eine Matrix, deren Zeilen die Gewichtsvektoren sind. Schreiben wir also $u, v$ als Zeilen in eine Matrix $A \in \mathbb{R}^{2 \times 2}$ und benutzen $\sigma$ auf Vektoren komponentenweise, so ist

Die Ableitung nach einem einzelnen Gewicht $u_1 = A_{11}$ ist $\frac{\partial}{\partial u_1} = \frac{\partial}{\partial A_{11}}$, und für die ganze Matrix:

(Wobei bei $w^T \sigma'(Ax)\, x$ die Dimensionen passend zu lesen sind: $\sigma'(Ax)$ ist eine Diagonalmatrix, und das Ergebnis ist eine $2 \times 2$-Matrix, deren Eintrag $(j, k)$ gleich $w_j \sigma'((Ax)_j) x_k$ ist.)

Idee: Berechne für $y_{\text{pred}}$ gleichzeitig die Daten für den Gradienten. Nach der Kettenregel $\frac{d}{dx} f(g(x)) = f'(g(x))\, g'(x)$ mit $g(x) = \sigma(Ax)$ und $f(z) = w^T z$ berechnen wir zuerst $g$ und $g'$ vom ersten Layer, dann damit den nächsten Layer, usw. bis zum letzten. Die Zwischenergebnisse der Vorwärtsrechnung sind genau das, was die Rückwärtsrechnung braucht.

Backpropagation konkret¶

Beispiel 4: ein Netz mit drei Schichten¶

Wir betrachten

und schreiben die Vorwärtsrechnung (forward computation) schichtweise auf:

Der Faktor $\tfrac12$ ist reine Bequemlichkeit, er kürzt sich gleich gegen die 2 aus der Ableitung des Quadrats.

Rückwärts differenzieren¶

Wir verwenden die Notation der Differentiale: $dE$ ist die lineare Änderung von $E$ bei einer infinitesimalen Änderung der Parameter, und $\nabla_b E$ bezeichnet den Gradienten von $E$ nach $b$ (mit der Konvention $dE = \langle \nabla_b E, db \rangle$). Wir arbeiten uns von hinten nach vorn (backwards differentiation).

Output layer. Es ist

denn $y$ ist konstant. Weiter ist $dy_{\text{pred}} = d(b_3 + W_3 z_3) = db_3 + dW_3\, z_3 + W_3\, dz_3$. Für die Ableitung nach $b_3$ betrachten wir nur den ersten Term: $dE = r^T db_3$, also

Für die Ableitung nach $W_3$ ist das Ergebnis

Das ist ein äußeres Produkt: Der Gradient nach der Gewichtsmatrix ist Residuum mal Eingabe der Schicht, transponiert – so wie beim einzelnen Neuron der Gradient nach $w$ gleich Fehler mal $x$ war.

Nächste Schicht. Jetzt können wir $b_3$ und $W_3$ als Konstanten sehen: $dE = r^T W_3\, dz_3 + \text{irrelevante Terme}$. Mit der Kettenregel gilt $\frac{d}{dz} \tanh(f(z)) = (1 - \tanh(f(z))^2)\, f'(z)$, also

wobei $z_3^2$ und $\odot$ komponentenweise zu lesen sind. Für $b_2$: $dE = r^T W_3 \operatorname{diag}(1 - z_3^2)\, db_2$, also

Und noch eine Schicht. Nach demselben Muster:

Das Muster¶

Zusammengefasst, mit $\delta_k := \nabla_{b_k} E$ als „Fehlersignal“ der Schicht $k$:

Das Fehlersignal wird von Schicht zu Schicht rückwärts propagiert: mit der transponierten Gewichtsmatrix multipliziert und mit der Ableitung der Aktivierungsfunktion gewichtet. Man nutzt die Zwischenschritte $z_k$ aus der Vorwärtsrechnung, um den vollen Gradienten effizient zu berechnen – ein Vorwärtsdurchlauf, ein Rückwärtsdurchlauf, fertig. Der Aufwand ist etwa das Doppelte einer Inferenz, unabhängig von der Anzahl der Parameter. Das ist Backpropagation, und danach kommt Gradientenabstieg.

Genau das tut loss.backward() in PyTorch (Kapitel „Autograd und Berechnungsgraph“): Beim Vorwärtsrechnen merkt sich jeder Tensor mit requires_grad, aus welcher Operation er entstanden ist (der Berechnungsgraph), und backward läuft diesen Graphen rückwärts ab und schreibt die Gradienten in die .grad-Attribute der Parameter. optimizer.step() macht dann $W \leftarrow W - \rho \nabla_W E$.

Matrix-Differentialkalkül: Literaturtipps¶

Achtung: Das ist nicht notwendig für diese Veranstaltung, das ist weiterführend.

• Thomas P. Minka, Old and new matrix algebra useful for statistics, Notes, 2000.

• The Matrix Cookbook (Petersen & Pedersen).

• Matrix derivatives cheat sheet.

• Wikipedia: Loss functions for classification.

• Michael Nielsens Buchkapitel zu Backpropagation (sehr mathematisch): neuralnetworksanddeeplearning.com/chap2.html.

Backpropagation als Induktion¶

Noch einmal systematisch, als Wiederholung und Zusammenfassung aus der Übung – denn Backpropagation ist Klausurstoff, und die Formulierung als Induktion ist die, mit der man jede Architektur erschlägt.

Warum Backpropagation funktioniert¶

1. Im Forward Pass speichern wir für jede Rechenoperation das Zwischenergebnis und merken uns die Ableitung der einzelnen Rechenoperation und auf welche vorangehenden Ergebnisse wir zurückgreifen müssen (Konstruktion des DAG).

2. Im Backward Pass können wir für jede Rechenoperation jeweils nach den Gewichten ableiten, die für diese Operation relevant sind. Wenn wir nach Gewichten ableiten, von denen die vorangegangenen Rechenoperationen abhängen, müssen wir die Kettenregel anwenden. Dazu benötigen wir nur die Ableitung der neuen Rechenoperation (gespeichert im Forward Pass), den Wert der Rechenoperation (gespeichert im Forward Pass) und die Ableitung der vorangegangenen Rechenoperationen.

Mit vollständiger Induktion sehen wir also: Wir können alle Ableitungen berechnen mit einem Durchlauf durch den DAG. Insbesondere können wir die Loss-Funktion (das „Ende“ des DAG) nach allen Gewichten ableiten und so den vollständigen Gradienten berechnen.

Der Induktionsschritt, systematisch¶

Wir bezeichnen den Input als $x \in \mathcal{X}$. Die „bisherigen Rechenoperationen“ sind eine Abbildung $Y \colon \mathcal{X} \to \mathcal{Y}$, also $y := Y(x; w_Y)$, deren Ableitungen $\frac{dY}{dw_Y}(x; w_Y)$ wir per Induktion kennen. Die „nächste Rechenoperation“ ist eine Abbildung $Z \colon \mathcal{Y} \to \mathcal{Z}$, deren Ableitungen $\frac{dZ}{dy}$ und $\frac{dZ}{dw_Z}$ wir kennen. Die Kettenregel erlaubt uns, $Z(Y(x; w_Y); w_Z)$ nach $w_Y$ abzuleiten:

Spezialfälle: Wenn die nächste Rechenoperation der Loss ist, gibt es keine „neuen Gewichte“, dann ist nur die Ableitung nach „bisherigen Gewichten“ relevant. Der Induktionsanfang ist gegeben, indem $Y$ die Identitätsfunktion ist (Ableitung ist 1). In knapperer Notation, mit Kleinbuchstaben als Funktionsnamen:

Nicht konkret genug? Ein weiteres einfaches Beispiel¶

Wir wählen als Input $x \in \mathcal{X} \subseteq \mathbb{R}^n$. Im Beispiel soll $y := y(x; w) := w \cdot x$ sein, also ein linearer Layer. Die „nächste Rechenoperation“ ist $z \colon \mathbb{R} \to \mathbb{R}$, und zwar $z := z(y) := \operatorname{ReLU}(y) = \max(0, y)$. Die Ableitung nach $y$ ist $[y > 0]$. Aus $\frac{dz}{dw} = \frac{dz}{dy} \cdot \frac{dy}{dw}$ wird also

Übung¶

Ein Netz $x \to y = \mathrm{ReLU}(v\,x) \to z = \mathrm{ReLU}(w\,y)$ mit $v = 2$, $w = -1$, Eingabe $x = 3$ und Ziel $t = 1$; Loss $L = \tfrac12 (z-t)^2$.

1. Forward Pass: Berechnen Sie $y$, $z$ und $L$.

2. Berechnen Sie $\frac{\partial L}{\partial w}$ und $\frac{\partial L}{\partial v}$. Tipp: $\frac{\partial L}{\partial z} = z - t$, die schwache Ableitung von ReLU an der Stelle $a$ ist $[a > 0]$, und der Gradient eines Gewichts ist Eingabe des Neurons mal Ableitung des Fehlers nach seiner Ausgabe.

3. Setzen Sie $w = +1$ und rechnen Sie noch einmal. Was hat sich an $\frac{\partial L}{\partial v}$ qualitativ geändert, und warum?

Antwortprobe: In genau einem der beiden Fälle ist $\frac{\partial L}{\partial v} = 0$.

Und eine größere, wenn Sie Lust haben: Nehmen Sie das Beispiel aus dem Abschnitt „Nicht konkret genug?“ ($y = \langle a, x \rangle$, dann $z = \operatorname{ReLU}(y)$) und geben Sie der ersten Schicht ein zweites Neuron, also eine zweite Zeile $a' \in \mathbb{R}^n$. Der Loss ist dann $\|z - z_{\text{ground truth}}\|^2$ mit $z \in \mathbb{R}^2$. Leiten Sie nach beiden Zeilen ab und prüfen Sie, dass die beiden Gradienten sich nicht gegenseitig beeinflussen.