Backpropagation
# Backpropagation

Backpropagation oder auch Backpropagation of Error bzw. auch Fehlerrückführung (auch Rückpropagierung) ist ein verbreitetes Verfahren zum Einlernen künstlicher neuronaler Netze. Es gehört zur Gruppe der überwachten Lernverfahren und wird als Verallgemeinerung der Delta-Regel auf mehrschichtige Netze angewandt. Dazu muss ein externer Lehrer existieren, der zu jedem Zeitpunkt der Eingabe die gewünschte Ausgabe, den Zielwert, kennt. Die Rückwärtspropagierung ist ein Spezialfall eines allgemeinen Gradientenverfahrens in der Optimierung, basierend auf dem mittleren quadratischen Fehler.

## Funktionsweise

Ein künstliches neuronales Netz nimmt im einfachsten Fall Eingabedaten und ordnet sie auf einen Ausgangswert ab. Das gesamte Netz liest Zahlen ein und findet Muster in diesen Zahlen. Die Eingabedaten werden durch eine Matrix von Gewichten gefiltert, die die Parameter des Netzes sind. Die Methode zur Feinabstimmung dieser Gewichte nimmt einen Ausgangsfehler neuronaler Netze auf und verbreitet diesen Fehler durch das Netz rückwärts und ermittelt, welche Pfade den größten Einfluss auf die Ausgabe haben. Dieses Prinzip nennt man Backpropagation. Die Backpropagation ermittelt, welche Wege einen größeren Einfluss auf die endgültige Antwort haben, und ermöglicht es, Verbindungen zu stärken oder zu schwächen, um eine gewünschte Vorhersage zu erreichen.

## Geschichte

Nach verschiedenen Quellen wurden die Grundlagen des Verfahrens im Kontext der Steuerungstheorie hergeleitet durch Prinzipien dynamischer Programmierung, und zwar durch Henry J. Kelley im Jahre 1960 und Arthur E. Bryson im Jahre 1961. 1962 publizierte Stuart Dreyfus eine einfachere Herleitung durch die Kettenregel. Vladimir Vapnik zitiert einen Artikel aus dem Jahre 1963 in seinem Buch über Support Vector Machines. 1969 beschrieben Bryson und Yu-Chi Ho das Verfahren als mehrstufige Optimierung dynamischer Systeme.

Seppo Linnainmaa publizierte im Jahre 1970 schließlich die allgemeine Methode für automatisches Differenzieren (AD) diskreter Netzwerke verschachtelter differenzierbarer Funktionen. Dies ist die moderne Variante des Backpropagation-Verfahrens, welche auch bei dünner Vernetzung effizient ist.

1973 verwendete Stuart Dreyfus Backpropagation, um Parameter von Steuersystemen proportional zu ihren Fehlergradienten zu adjustieren. Paul Werbos erwähnte 1974 die Möglichkeit, dieses Prinzip auf künstliche neuronale Netze anzuwenden, und im Jahre 1982 tat er dies auf die heute weit verbreitete Art und Weise. Vier Jahre später zeigten David E. Rumelhart, Geoffrey E. Hinton und Ronald J. Williams durch Experimente, dass diese Methode zu nützlichen internen Repräsentationen von Eingabedaten in tieferen Schichten neuronaler Netze führen kann, was die Grundlage von Deep Learning ist. Eric A. Wan war 1993 der erste, der einen internationalen Mustererkennungswettbewerb durch Backpropagation gewann.

## Fehlerminimierung

Beim Lernproblem wird für beliebige Netze eine möglichst zuverlässige Abbildung von gegebenen Eingabevektoren auf gegebene Ausgabevektoren angestrebt. Dazu wird die Qualität der Abbildung durch eine Fehlerfunktion beschrieben, die hier durch den quadratischen Fehler definiert wird:

    $E={\frac {1}{2}}\sum \limits _{i=1}^{n}(t_{i}-o_{i})^{2}$.

Dabei ist

    $E$ der Fehler,
    $n$ die Anzahl der Ausgabe Neuronen,
    $t_{i}$ die gewünschte Soll-Ausgabe oder Zielwert (target) und
    $o_{i}$ die errechnete Ist-Ausgabe (output).

Der Faktor ${\tfrac {1}{2}}$ wird dabei lediglich zur Vereinfachung bei der Ableitung hinzugenommen.

Das Ziel ist nun die Minimierung der Fehlerfunktion, wobei aber im Allgemeinen lediglich ein lokales Minimum gefunden wird. Das Einlernen eines künstlichen neuronalen Netzes erfolgt bei dem Backpropagation-Verfahren durch die Änderung der Gewichte, da die Ausgabe des Netzes – außer von der Aktivierungsfunktion – direkt von ihnen abhängig ist.

## Algorithmus

Der Backpropagation-Algorithmus läuft in folgenden Phasen:

* Ein Eingabemuster wird angelegt und vorwärts durch das Netz propagiert.
* Die Ausgabe des Netzes wird mit der gewünschten Ausgabe verglichen. Die Differenz der beiden Werte wird als Fehler des Netzes erachtet.
* Der Fehler wird nun wieder über die Ausgabe- zur Eingabeschicht zurück propagiert. Dabei werden die Gewichtungen der Neuronenverbindungen abhängig von ihrem Einfluss auf den Fehler geändert. Dies garantiert bei einem erneuten Anlegen der Eingabe eine Annäherung an die gewünschte Ausgabe.

Der Name des Algorithmus ergibt sich aus dem Zurückpropagieren des Fehlers (engl. error back-propagation).

## Herleitung

Die Formel des Backpropagation-Verfahrens wird durch Differenziation hergeleitet: Für die Ausgabe eines Neurons mit zwei Eingaben $x_{1}$ und $x_{2}$ erhält man eine zweidimensionale Hyperebene, wobei der Fehler des Neurons abhängig von den Gewichtungen $w_{1},w_{2}$ der Eingaben $x_{1},x_{2}$ ist. Diese Fehleroberfläche enthält Minima, die es zu finden gilt. Dies kann nun durch das Gradientenverfahren erreicht werden, indem von einem Punkt auf der Oberfläche aus in Richtung des stärksten Abfallens der Fehlerfunktion abgestiegen wird.

### Neuronenausgabe

Für die Herleitung des Backpropagation-Verfahrens sei die Neuronenausgabe eines künstlichen Neurons kurz dargestellt. Die Ausgabe $o_{j}$ eines künstlichen Neurons $j$ lässt sich definieren durch

    $o_{j}=\varphi ({\mbox{net}}_{j})$

und die Netzeingabe ${\mbox{net}}_{j}$ durch

    ${\mbox{net}}_{j}=\sum \limits _{i=1}^{n}x_{i}w_{ij}.$

Dabei ist

    $\varphi$ eine differenzierbare Aktivierungsfunktion deren Ableitung nicht überall gleich null ist,
    $n$ die Anzahl der Eingaben,
    $x_{i}$ die Eingabe $i$ und
    $w_{ij}$ die Gewichtung zwischen Eingabe $i$ und Neuron $j$.

Auf einen Schwellwert $\theta _{j}$ wird hier verzichtet. Dieser wird meist durch ein immer „feuerndes“ on-Neuron realisiert und dessen Ausgabe mit dem konstanten Wert 1 belegt. Auf diese Weise entfällt eine Unbekannte.

### Ableitung der Fehlerfunktion

Die partielle Ableitung der Fehlerfunktion $E$ ergibt sich durch Verwendung der Kettenregel:

    ${\dfrac {\partial E}{\partial w_{ij}}}={\frac {\partial E}{\partial o_{j}}}{\frac {\partial o_{j}}{\partial {\mbox{net}}_{j}}}{\frac {\partial {\mbox{net}}_{j}}{\partial w_{ij}}}$

Mit Matrizen und Vektoren lautet die Kettenregel:

    ${\dfrac {\partial E}{\partial W}}={\frac {\partial E}{\partial O}}{\frac {\partial O}{\partial Net}}{\frac {\partial Net}{\partial W}}$

Aus den einzelnen Termen kann nun die folgende Formel berechnet werden. Dabei ist die Herleitung im Gegensatz zur einfachen Delta-Regel abhängig von zwei Fällen:

* Liegt das Neuron in der Ausgabeschicht, so ist es direkt an der Ausgabe beteiligt,
* liegt es dagegen in einer verdeckten Schicht, so kann die Anpassung nur indirekt berechnet werden.

Konkret:

    $\Delta w_{ij}=-\eta {\dfrac {\partial E}{\partial w_{ij}}}=-\eta \delta _{j}o_{i}$
    mit
    $\delta _{j}={\begin{cases}\varphi '({\mbox{net}}_{j})(o_{j}-t_{j})&{\mbox{falls }}j{\mbox{ Ausgabeneuron ist,}}\\\varphi '({\mbox{net}}_{j})\sum _{k}\delta _{k}w_{jk}&{\mbox{falls }}j{\mbox{ verdecktes Neuron ist.}}\end{cases}}$

Dabei ist

    $\Delta w_{ij}$ die Änderung des Gewichts $w_{ij}$ der Verbindung von Neuron $i$ zu Neuron $j$,
    $\eta$ eine feste Lernrate, mit der die Stärke der Gewichtsänderungen bestimmt werden kann,
    $\delta _{j}$ das Fehlersignal des Neurons $j$, entsprechend zu ${\frac {\partial E}{\partial {\mbox{net}}_{j}}}$,
    $t_{j}$ die Soll-Ausgabe des Ausgabeneurons $j$,
    $o_{i}$ die Ausgabe des Neurons $i$,
    $o_{j}$ die Ist-Ausgabe des Ausgabeneurons $j$ und
    $k$ der Index der Neuronen des nachfolgenden Layers von Neuron $j$.

Bei einem einschichtigen Netzwerk ist $o_{i}=x_{i}$. Die Ausgabe $o_{i}$ entspricht dann also den Eingängen des Netzwerks.

### Modifizierung der Gewichte

Die Variable $\delta _{j}$ geht dabei auf die Unterscheidung der Neuronen ein: Liegt das Neuron in einer verdeckten Schicht, so wird seine Gewichtung abhängig von dem Fehler geändert, den die nachfolgenden Neuronen erzeugen, welche wiederum ihre Eingaben aus dem betrachteten Neuron beziehen.

Die Änderung der Gewichte kann nun wie folgt vorgenommen werden:

    $w_{ij}^{\mbox{neu}}=w_{ij}^{\mbox{alt}}+\Delta w_{ij}$.

Dabei ist

    $w_{ij}^{\mbox{neu}}$ der neue Wert des Gewichts,
    $w_{ij}^{\mbox{alt}}$ der alte Wert des Gewichts und
    $\Delta w_{ij}$ die oben berechnete Änderung des Gewichts (basierend auf $w_{ij}^{\mbox{alt}}$)

Das Ziel der Backpropagation ist es, die Ableitung des Fehlers in Bezug auf die Gewichte im Netz zu finden. Wenn nach der Änderung eines Wertes in Bezug auf einen anderen Wert gesucht ist, ist dies eine Ableitung. Für die Berechnung repräsentiert jedes Neuron eine Funktion und jede Kante führt einen Vorgang auf dem angehängten Neuron aus. Man beginnt mit dem Fehlerneuron und bewegt sich jeweils ein Neuron zurück und nimmt die partielle Ableitung des aktuellen Neurons in Bezug auf den Neurons in der vorhergehenden Schicht. Jeder Ausdruck wird an den vorhergehenden Ausdruck gekettet, um den Gesamtwert zu berechnen. Dies ist die Kettenregel.

### Aktivierungsfunktion

Der Backpropagation-Algorithmus sucht nach dem Minimum der Fehlerfunktion unter Verwendung des Gradientenverfahrens. Die Kombination von Gewichten, die die Fehlerfunktion minimiert, wird als Lösung des Lernproblems angesehen. Weil dieses Verfahren die Berechnung des Gradienten der Fehlerfunktion bei jedem Iterationsschritt erfordert, muss die Fehlerfunktion stetig und differenzierbar sein.

Eine der beliebtesten Aktivierungsfunktionen für Backpropagation-Netze ist die Sigmoidfunktion $s_{c}(x)={\frac {1}{1+e^{-cx}}}$. Die Konstante $c$ ist beliebig wählbar und ihr Kehrwert ${\frac {1}{c}}$ wird Temperaturparameter in stochastischen neuronalen Netzen genannt. Die Form des Sigmoids ändert sich entsprechend dem Wert von $c$. Höhere Werte von $c$ bringen die Form des Sigmoids näher an die der Heaviside-Funktion, und im Grenzwert $c\rightarrow \infty$ konvergiert das Sigmoid zu einer Heaviside-Funktion.

Die Ableitung der Sigmoidfunktion nach $x$ ist ${\frac {\partial }{\partial x}}s_{c}(x)={\frac {c\cdot e^{-cx}}{(1+e^{-cx})^{2}}}=c\cdot s_{c}(x)\cdot (1-s_{c}(x))$

Eine Alternative zum Sigmoid ist das symmetrische Sigmoid, definiert als $S(x)=2\cdot s(x)-1={\frac {1-e^{-x}}{1+e^{-x}}}$. Dies ist der Tangens hyperbolicus für das Argument ${\frac {x}{2}}$, also $\tanh \left({\frac {x}{2}}\right)$.

Viele andere Arten von Aktivierungsfunktionen wurden vorgeschlagen und der Backpropagation-Algorithmus ist auf alle anwendbar. Eine differenzierbare Aktivierungsfunktion macht die von einem neuronalen Netz berechnete Funktion differenzierbar unter der Annahme, dass die Integralfunktion an jedem Knoten nur die Summe der Eingaben ist, weil das Netz selbst nur zusammengesetzte Funktionen berechnet.

## Erweiterung

Die Wahl der Lernrate $\eta$ ist wichtig für das Verfahren, da ein zu hoher Wert eine starke Veränderung bewirkt, wobei das Minimum verfehlt werden kann, während eine zu kleine Lernrate das Einlernen unnötig verlangsamt.

Verschiedene Optimierungen von Rückwärtspropagierung, z. B. Quickprop, zielen vor allem auf die Beschleunigung der Fehlerminimierung; andere Verbesserungen versuchen vor allem die Zuverlässigkeit zu erhöhen.

### Backpropagation mit variabler Lernrate

Um eine Oszillation des Netzes, d. h. alternierende Verbindungsgewichte zu vermeiden, existieren Verfeinerungen des Verfahrens, bei dem mit einer variablen Lernrate $\eta$ gearbeitet wird.

### Backpropagation mit Trägheitsterm

Durch die Verwendung eines variablen Trägheitsterms (Momentum) $\alpha$ kann der Gradient und die letzte Änderung gewichtet werden, so dass die Gewichtsanpassung zusätzlich von der vorausgegangenen Änderung abhängt. Ist das Momentum $\alpha$ gleich 0, so hängt die Änderung allein vom Gradienten ab, bei einem Wert von 1 lediglich von der letzten Änderung.

Ähnlich einer Kugel, die einen Berg hinunter rollt und deren aktuelle Geschwindigkeit nicht nur durch die aktuelle Steigung des Berges, sondern auch durch ihre eigene Trägheit bestimmt wird, lässt sich der Backpropagation ein Trägheitsterm hinzufügen:

    $\Delta w_{ij}(t+1)=(1-\alpha )\eta \delta _{j}x_{i}+\alpha \Delta w_{ij}(t)$

Dabei ist

    $\Delta w_{ij}(t+1)$ die Änderung des Gewichts $w_{ij}(t+1)$ der Verbindung von Neuron $i$ zu Neuron $j$ zum Zeitpunkt $(t+1)$,
    $\eta$ eine Lernrate,
    $\delta _{j}$ das Fehlersignal des Neurons $j$ und
    $x_{i}$ die Eingabe des Neurons $i$,
    $\alpha$ der Einfluss des Trägheitsterms $\Delta w_{ij}(t)$. Dieser entspricht der Gewichtsänderung zum vorherigen Zeitpunkt.

Damit hängt die aktuelle Gewichtsänderung $(t+1)$ sowohl vom aktuellen Gradienten der Fehlerfunktion (Steigung des Berges, 1. Summand), als auch von der Gewichtsänderung des vorherigen Zeitpunktes ab (eigene Trägheit, 2. Summand).

Durch den Trägheitsterm werden unter anderem Probleme der Backpropagation-Regel in steilen Schluchten und flachen Plateaus vermieden. Da zum Beispiel in flachen Plateaus der Gradient der Fehlerfunktion sehr klein wird, käme es ohne Trägheitsterm unmittelbar zu einem „Abbremsen“ des Gradientenabstiegs, dieses „Abbremsen“ wird durch die Addition des Trägheitsterms verzögert, so dass ein flaches Plateau schneller überwunden werden kann.

Sobald der Fehler des Netzes minimal wird, kann das Einlernen abgeschlossen werden und das mehrschichtige Netz ist nun bereit, die erlernten Muster zu klassifizieren.

### Gleichungen der Backpropagation

Die Gleichungen der Backpropagation lassen sie wie folgt zusammenfassen:

    ${\begin{aligned}\delta _{j}^{L}&={\frac {\partial E}{\partial o_{j}^{L}}}\varphi '({\mbox{net}}_{j}^{L})\\\delta _{j}^{l}&=((w^{l+1})^{T}\delta ^{j+1})\circ \varphi '({\mbox{net}}_{j}^{l})\\{\frac {\partial E}{\partial t_{j}^{L}}}&=\delta _{j}^{l}\\{\frac {\partial E}{\partial w_{ij}^{L}}}&=o_{j}^{l-1}\delta _{i}^{l}\end{aligned}}$

Diese Gleichungen bieten eine Möglichkeit, den Gradienten der Kostenfunktion zu berechnen. Daraus ergibt sich folgender Algorithmus:

* Setze die Aktivierung $o^{1}$ für die Eingabeschicht
* Berechne $z^{l}=w^{l}o^{l-1}+t^{l}$ und $o^{l}=\varphi ({\mbox{net}}_{j}^{l})$ für $l=2,3,\ldots ,L$
* Berechne den Vektor ${\frac {\partial E}{\partial o_{j}^{L}}}\varphi '({\mbox{net}}_{j}^{L})$
* Berechne den Vektor $\delta _{j}^{l}=((w^{l+1})^{T}\delta ^{j+1})\circ \varphi '({\mbox{net}}_{j}^{l})$ für $l=L-1,L-2,\ldots ,2$
* Der Gradient der Kostenfunktion ist ${\frac {\partial E}{\partial w_{ij}^{L}}}=o_{j}^{l-1}\delta _{i}^{l}$ und ${\frac {\partial E}{\partial t_{j}^{L}}}=\delta _{j}^{l}$

## Biologischer Kontext

Als Verfahren des maschinellen Lernens ist Backpropagation ein mathematisch fundierter Lernmechanismus künstlicher neuronaler Netze und versucht nicht, tatsächliche neuronale Lernmechanismen biologistisch zu modellieren. Es ist kein Resultat neurophysiologischer Experimente und wird deshalb häufig von Neurowissenschaftlern kritisiert. Es gibt keine neurophysiologische Evidenz, die nahelegt, dass Backpropagation oder ein ähnliches Verfahren von biologischen Neuronen benutzt wird (Dies gilt nicht für Gradientenverfahren im Allgemeinen). Im Folgenden werden einige Gründe für die biologische Inplausibilität von Backpropagation dargelegt: (entnommen aus Y. Bengio et al.)

* Es ist unklar, wie Information über die Zielwerte $t_{i}$ in den synaptischen Spalt der letzten Neuronenschicht gelangen kann.
* Biologische Neuronen kommunizieren über binäre Zustandsänderungen (spikes), nicht über kontinuierliche Werte.
* Biologische Neuronen sind zeitsensibel, d. h. ihre Aktivität variiert nicht nur abhängig von der Intensität der Eingangs-Informationen, sondern von dessen Zeitverhalten („timing“) (Spike Time Dependent Plasticity, STDP).
* Backpropagation setzt zeitlich perfekt synchronisierte, diskrete Schritte voraus.
* Ein potenzieller Feedbackmechanismus müsste über die exakten, nicht-linearen Ableitungen der, im Gehirn in Struktur und Selektivität immens variierenden, Neuronen im Vorwärtsteil verfügen.
* Der Feedbackmechanismus müsste über exakt symmetrische Gewichte verfügen (weight transport problem).
