Backpropagation zur effizienten Berechnung des Gradienten

Bisher haben wir Verfahren betrachtet, die hauptsächlich den Gradienten verwendet haben, um das Optimierungsproblem

zu lösen. In diesem Abschnitt soll betrachtet werden, wie man den Gradienten effizient mit Dynamic Programming bestimmen kann: Das hierbei entwickelte numerische Verfahren heißt Backpropagation.

Ohne Backpropagation wäre das Training tiefer neuronaler Netze praktisch kaum möglich. Das Verfahren liefert nicht direkt die neuen Parameter, sondern die Gradienten, die anschließend von einem Optimierungsverfahren verwendet werden. Die bereits betrachteten Optimierungen durch Teilauswertung auf Batches verlieren dabei nicht ihre Gültigkeit. Für das hier betrachtete Verfahren gehen wir einfach von einer festen Batch-Größe aus, zu Beginn von einem einfachen Trainingsdatenpunkt .

Einstiegsbeispiel

Gegeben sei das folgende FNN:

Die Bias-Werte seien auf 0 gesetzt. Die Funktionsgleichung des FNNs lautet daher:

Für einen Trainingsdatenpunkt bezeichnen wir die Ausgabe des Netzes mit

Als Kostenfunktion verwenden wir in diesem Einstiegsbeispiel das halbe Quadrat der Abweichung:

Die übliche MSE-Summe fällt weg, wenn nur ein Trainingsdatenpunkt verwendet wird. Der Faktor vereinfacht lediglich die Ableitung. Er ändert nicht, für welche Parameterwerte die Kosten minimal werden.

Ausgangspunkt: Der Optimierer benötigt den Gradienten

Aus den vorangegangenen Abschnitten ist bereits bekannt, dass ein Standard-SGD-Schritt die Parameter mit Hilfe des Gradienten aktualisiert:

Backpropagation ist nicht der Optimierer und führt diesen Schritt nicht selbst aus. Das Verfahren beantwortet vielmehr die noch offene Frage:

Wie kann der Gradient eines tiefen neuronalen Netzes effizient berechnet werden?

Wir berechnen dazu zunächst den Gradienten direkt mit der Kettenregel. Die Parameter unseres einfachen Netzes sind

Gesucht ist daher der Spaltenvektor

Den Gradienten mit der Kettenregel ausschreiben

Zur besseren Lesbarkeit verwenden wir zunächst die üblichen Bezeichner für die Netzeingaben und Aktivierungen:

Für das Gewicht der letzten Schicht ist die Verkettung am kürzesten:

Bei der Ableitung nach werden der Trainingsdatenpunkt sowie die Gewichte und festgehalten. Damit kann die Kostenfunktion ausdrücklich als Funktion von geschrieben werden. Mit dem bereits berechneten Wert gilt zunächst

Dabei bezeichnen

die Multiplikation mit der festgehaltenen Aktivierung beziehungsweise die Kostenfunktion zum festgehaltenen Zielwert . Sie sind also bei Ableitung nach konstant.

Setzt man auch vollständig ein, erhält man

Diese vollständig eingesetzte Darstellung beschreibt dieselbe Verkettung wie die Pfeilkette. Sie macht jedoch unmittelbar sichtbar, an welchen Stellen in der Kostenfunktion vorkommt.

Die Kettenregel liefert

Beim ersten Faktor ist ein Zwischenschritt wichtig. Zunächst betrachten wir nur die äußere Kostenfunktion

Ihre Ableitung als Funktion der formalen Variablen lautet

Für die Kettenregel wird diese Ableitung anschließend an der aktuellen Ausgabe des Netzes ausgewertet. Da gilt, folgt

Die Schreibweise bedeutet also nicht, dass die inneren Funktionen verschwunden sind. Der Bezeichner fasst lediglich den Wert der vollständig verketteten Netzfunktion zusammen:

An dieser Stelle ist zunächst nur eine abkürzende Bezeichnung für diesen Funktionswert. Später wird sich aus der Effizienzbetrachtung ergeben, dass das Netz diesen Wert tatsächlich in einem Vorwärtslauf berechnet und für den Rückwärtslauf speichert (Caching, siehe unten).

Für die beiden übrigen lokalen Ableitungen gilt

Damit folgt

Für muss die Kettenregel einen Schritt weiter zurückverfolgt werden:

Für das erste Gewicht ergibt sich schließlich

Übereinander geschrieben lautet der vollständige Gradient somit

Diese Form ist mathematisch korrekt, aber noch nicht effizient ausgewertet. Gerade weil die drei Komponenten untereinander stehen, fallen gemeinsame Teilprodukte auf. Der blaue Faktor kommt in allen drei Komponenten vor. Der rote Faktor erweitert ihn in der ersten und zweiten Komponente. Der grüne Faktor kommt in diesem Netz nur in der ersten Komponente vor. Bei einer tieferen Verkettung würde aber auch er in weiteren, davorliegenden Komponenten wiederkehren. Die verbleibenden schwarzen Faktoren unterscheiden die einzelnen Komponenten voneinander.

Wiederkehrende Teilprodukte

In jeder Komponente kommt der Ausdruck

vor. In den ersten beiden Komponenten tritt zusätzlich das längere Teilprodukt

auf. Würde man jede Komponente des Gradienten unabhängig berechnen, würden diese Teilprodukte immer wieder neu ausgewertet. Bei einem großen Netz mit vielen Schichten und Verzweigungen wäre diese Mehrfachberechnung sehr aufwendig.

Die naheliegende Lösung besteht darin, jedes wiederkehrende Teilproblem nur einmal zu lösen, sein Ergebnis zu speichern und es anschließend wiederzuverwenden. Genau diese Grundidee wird beim Dynamic Programming genutzt.

Die -Terme als gespeicherte Teilergebnisse

Für jede Schicht definieren wir

Dies sind also genau die wiederkehrenden Terme, die wir jeweils nur einmal auswerten und speichern wollen, um sie wieder zu verwenden:

Der grüne Term wird in dem hier betrachteten Netz noch nicht wiederverwendet. Bei einer zusätzlichen davorliegenden Schicht wäre er jedoch ebenfalls Teil des nächsten Fehlersignals.

Interpretation der -Werte

Ein ist mathematisch die Sensitivität der Kosten bezüglich der Netzeingabe . Es beschreibt näherungsweise, wie sich die Kosten verändern, wenn geringfügig verändert wird:

Algorithmisch wird dieser Wert von hinten nach vorne durch das Netz weitergegeben. Deshalb nennen wir im Folgenden Fehlersignal; die Bezeichnung Fehlerterm ist ebenfalls gebräuchlich. Das Fehlersignal ist jedoch nicht mit der bloßen Abweichung gleichzusetzen. Es ist eine partielle Ableitung.

Für die Ausgabeschicht gilt

Dieser bereits berechnete Wert wird für die vorherige Schicht wiederverwendet:

Entsprechend folgt

Darstellung als Rekursion (als Grundlage für Dynamic Programming)

Die Fehlersignale werden also rekursiv berechnet:

Für ein Netz mit einer beliebigen Anzahl von Schichten beginnt die Rekursion in der Ausgabeschicht ("Rekursionsverankerung"):

Die letzte Gleichheit gilt für die hier verwendete quadratische Kostenfunktion. Von diesem Rekursionsanfang aus wird das Fehlersignal Schicht für Schicht nach hinten weitergegeben:

Mit diesen gespeicherten Teilergebnissen vereinfacht sich der Gradient zu

Einheitlich mit lässt sich jede Komponente schreiben als

Die Rekursion der -Terme vermeidet wiederholte Teilprodukte. Sie setzt aber Werte voraus, die in den Formeln bereits auftreten:

Diese Werte können vor der Berechnung des Gradienten in einem Vorwärtspass bestimmt und dabei gespeichert werden. Der Vorwärtspass ist die Berechnung von und entspricht damit einer üblichen Inferenz.

Warum werden diese Werte gebraucht?

• Für die lokale Ableitung einer Aktivierungsfunktion wird ihr aktuelles Argument benötigt, also .
• Für den Gradienten eines Gewichts wird die Aktivierung der vorherigen Schicht benötigt, also .
• Für die Ableitung der Kostenfunktion wird die Netzausgabe benötigt.

In der bisher verwendeten Leibniz-Schreibweise bei der Anwendung der Kettenregel

ist nicht unmittelbar zu sehen, an welcher Stelle die Ableitung der äußeren Funktion ausgewertet wird. Für die Verkettung von nur zwei Funktionen ,

lautet die Kettenregel in Funktionsschreibweise

Damit wird die Auswertungsstelle sichtbar: Zuerst muss der innere Funktionswert berechnet werden; anschließend wird die Ableitung genau an diesem Wert ausgewertet. Im neuronalen Netz übernehmen die gespeicherten Größen und die Rolle solcher inneren Funktionswerte. Sie werden im Vorwärtsdurchlauf berechnet und stehen dadurch für die lokalen Ableitungen im Rückwärtsdurchlauf zur Verfügung.

Setzt man in der Kettenregel alle inneren Funktionen vollständig ein, treten dieselben verschachtelten Funktionswerte immer wieder auf. Beispielsweise ist

Bestandteil von , , und schließlich . Statt diese inneren Funktionen während der Ableitung erneut auszuwerten, werden ihre Werte beim Durchlaufen des Netzes gespeichert:

Dieser Ablauf ist der Forward-Pass. Das Speichern seiner Funktionswerte ist Memoizing beziehungsweise Caching: Bereits berechnete Werte werden aufbewahrt, damit die Kettenregel im Rückwärtslauf an den richtigen Stellen ausgewertet werden kann.

Damit sind zwei unterschiedliche Arten des Speicherns zu unterscheiden:

1. Memoizing im Forward-Pass: Die Funktionswerte und werden gespeichert.
2. Dynamic Programming im Backward-Pass: Die rekursiven Teilableitungen werden gespeichert und wiederverwendet.

Der Forward-Pass erscheint hier also als notwendige Konsequenz aus der Kettenregel: Um die lokalen Ableitungen effizient auswerten zu können, müssen die zuvor berechneten Argumente und Funktionswerte noch verfügbar sein.

Verallgemeinerung auf Schichten mit mehreren Neuronen

Um das Verfahren auf Schichten mit mehreren Neuronen zu verallgemeinern, betrachten wir zunächst ein weiteres Beispiel:

Das Netz im Vorwärtslauf

Das Netz besitzt einen Eingang, drei Neuronen in der ersten versteckten Schicht, zwei Neuronen in der zweiten versteckten Schicht und ein Ausgabeneuron. Wie in der Abbildung betrachten wir zunächst ein Netz ohne Bias-Werte. Bei bezeichnet der erste Index das Quellneuron in Schicht und der zweite Index das Zielneuron in Schicht .

In der ersten Schicht gilt für

Die beiden Netzeingaben der zweiten Schicht sind

und damit

Für das Ausgabeneuron folgt

und für den halben quadratischen Fehler

Alle - und -Werte werden bei diesem Vorwärtspass berechnet und für den anschließenden Rückwärtslauf gespeichert.

Die Fehlersignale im Rückwärtslauf

Für die gespeicherten -Bezeichner führen wir die drei bereits verwendeten Farben schichtweise fort: Blau kennzeichnet das Fehlersignal der Ausgabeschicht, Rot die beiden Fehlersignale der zweiten Schicht und Grün die drei Fehlersignale der ersten Schicht. Die Farbe bezeichnet jeweils einen vollständig berechneten und gespeicherten -Wert.

Der Rekursionsanfang liegt beim Ausgabeneuron:

Dieser Wert wird für beide Neuronen der zweiten Schicht wiederverwendet:

In der ersten Schicht treffen an jedem Neuron zwei rückwärts laufende Pfade zusammen. Deshalb werden die beiden Beiträge zunächst addiert und anschließend mit der lokalen Aktivierungsableitung multipliziert:

Die -Werte als DP-Tabelle

Die gespeicherten Teilergebnisse lassen sich wie eine Dynamic-Programming-Tabelle lesen. Jede Zeile zeigt den Zustand des Speichers nach einem weiteren Rückwärtsschritt:

Die Einträge werden nicht bei jeder Verwendung neu berechnet. Beispielsweise wird einmal bestimmt und danach sowohl für als auch für benutzt. Entsprechend gehen die beiden roten Werte jeweils in alle drei grünen Werte ein.

Zusammensetzen des Gradienten

Mit den gespeicherten Fehlersignalen entstehen die Ableitungen der beiden Ausgangsgewichte unmittelbar:

Für die sechs Gewichte zwischen den beiden versteckten Schichten gilt

Schließlich erhält man für die drei Gewichte der ersten Schicht

Damit wird die Wiederverwendung unmittelbar sichtbar: Ein gespeichertes Fehlersignal wird sowohl für sämtliche Gewichtsgradienten seiner Schicht als auch für die Berechnung der Fehlersignale in der davorliegenden Schicht benutzt.

Backpropagation für Schichten mit mehreren Neuronen

Für die kompakte Matrixschreibweise verwenden wir im Folgenden Spaltenvektoren. Die Zielneuronen stehen daher in den Zeilen und die Quellneuronen in den Spalten der Gewichtsmatrix. Bezogen auf die Kantenbezeichnungen der Abbildung gilt somit .

Wir fassen die Aktivierungen, Netzeingaben und Bias-Werte als Vektoren und die Gewichte als Matrix auf:

Die Aktivierungsfunktion wird dabei komponentenweise ausgewertet. Für eine allgemeine differenzierbare Kostenfunktion lautet das Fehlersignal der Ausgabeschicht

wobei die komponentenweise Multiplikation bezeichnet. Beim hier verwendeten halben quadratischen Fehler ist

Für eine verborgene Schicht ergibt sich die Rückwärtsrekursion

Die Transposition ist notwendig, weil die Fehlersignale der nachfolgenden Schicht über die verbindenden Gewichte zu den Neuronen der aktuellen Schicht zurückgeführt werden. Besitzt eine Schicht mehrere Neuronen, ist daher ein Vektor mit einem Fehlersignal für jedes Neuron.

Die Gradienten bezüglich der Gewichte und Bias-Werte lauten

und

Der Bias benötigt also keine eigene Rückwärtsrekursion. Da

gilt, ist sein Gradient unmittelbar das Fehlersignal der betreffenden Schicht.

Der vollständige Ablauf

Aus der Herleitung ergibt sich nun der Backpropagation-Ablauf:

1. Vorwärts rechnen und Funktionswerte speichern: Für jede Schicht werden und berechnet.
2. Kosten bestimmen: Aus und dem Zielwert werden die Kosten berechnet.
3. Fehlersignal der Ausgabeschicht bestimmen: wird aus der Ableitung der Kosten und der lokalen Aktivierungsableitung gebildet.
4. Fehlersignale rückwärts berechnen: Mit der Rekursion werden bestimmt.
5. Gradienten zusammensetzen: Für jede Schicht werden und berechnet.
6. Gradienten an den Optimierer übergeben: Erst der Optimierer entscheidet, wie die Parameter mit diesen Gradienten verändert werden.

Für einen Mini-Batch wird dieser Ablauf für die Beispiele des Batches durchgeführt. Die einzelnen Gradienten werden anschließend entsprechend der gewählten Kostenfunktion summiert oder gemittelt.

Die folgende App stellt Forward-Werte, Fehlersignale und Gradienten schrittweise dar. In den Formelansichten kann zwischen numerischen Werten, rekursiven Termen und weiter eingesetzten Ausdrücken gewechselt werden.