Backpropagation oder auch Backpropagation of Error bzw. FehlerrückführungWerner Kinnebrock: Neuronale Netze: Grundlagen, Anwendungen, Beispiele. R. Oldenbourg Verlag, München 1994, ISBN 3-486-22947-8. bzw. Rückpropagierung ist ein verbreitetes Verfahren zum Einlernen künstlicher neuronaler Netze. Es gehört in der einfachen Form zur Gruppe der überwachten Lernverfahren und wird als Verallgemeinerung der Delta-Regel auf mehrschichtige Netze angewandt. 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 erhält Eingabedaten und bildet diese auf einen Ausgabewert ab. Die numerischen Eingabedaten werden in jeder Schicht des Netzes mit einer Matrix von Gewichten multipliziert, welche die Parameter des Netzes sind.
Beim Training des neuronalen Netzes wird die Abweichung zwischen dem Ausgabewert des Netzes und dem Zielwert des externen Lehrers (im einfachen Fall) berechnet und dieser Fehler rückwärts durch alle Schichten des Netzes propagiert (Backpropagation). Durch Backpropagation lässt sich ermitteln, welche Pfade den größten Einfluss auf den Fehler haben; sie ermöglicht es, Gewichte von Verbindungen zu stärken oder zu schwächen, um den Fehler zu verringern und eine gewünschte Vorhersage zu erreichen.Brent Scarff, Towards Data Science: Understanding Backpropagation
Im weiterentwickelten Fall (etwa bei der Architektur von AlphaGo) kann auch der menschliche externe Lehrer fehlen und der Zielwert aus anderen Teilen der Architektur geliefert werden.
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).
Fehlerminimierung Beim Lernproblem wird für beliebige Netze eine möglichst zuverlässige Abbildung von gegebenen Eingabe- auf gegebene Ausgabevektoren angestrebt. Dazu wird die Qualität der Abbildung durch eine Fehlerfunktion beschrieben, die hier durch den quadratischen Fehler definiert wird:
.
Dabei ist der Fehler die Anzahl der Ausgabe-Neuronen, die gewünschte Soll-Ausgabe oder Zielwert (target) die errechnete Ist-Ausgabe (output).
Der Faktor wird dabei lediglich zur Vereinfachung der Ableitung hinzugenommen.
Das Ziel ist nun die Minimierung der Fehlerfunktion, wobei 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ängt.
Geschichte Nach verschiedenen QuellenStuart Dreyfus: Artificial Neural Networks, Back Propagation and the Kelley-Bryson Gradient Procedure. In: J. Guidance, Control and Dynamics. 1990.Eiji Mizutani, Stuart Dreyfus, Kenichi Nishio: On derivation of MLP backpropagation from the Kelley-Bryson optimal-control gradient formula and its application. In: Proceedings of the IEEE International Joint Conference on Neural Networks (IJCNN 2000). Como Italy, July 2000.Jürgen Schmidhuber: Deep learning in neural networks: An overview. In: Neural Networks. 61, 2015, S. 85–117. ArXivJürgen Schmidhuber: Deep Learning. In: Scholarpedia. 10(11), 2015, S. 328–332. Section on Backpropagation wurden die Grundlagen des Verfahrens im Kontext der Steuerungstheorie hergeleitet durch Prinzipien dynamischer Programmierung, und zwar durch Henry J. Kelley im Jahre 1960Henry J. Kelley: Gradient theory of optimal flight paths. In: Ars Journal. 30(10), 1960, S. 947–954. (online) und Arthur E. Bryson im Jahre 1961.Arthur E. Bryson: A gradient method for optimizing multi-stage allocation processes. In: Proceedings of the Harvard Univ. Symposium on digital computers and their applications. April 1961. 1962 publizierte Stuart Dreyfus eine einfachere Herleitung durch die Kettenregel.Stuart Dreyfus: The numerical solution of variational problems. In: Journal of Mathematical Analysis and Applications. 5(1), 1962, S. 30–45. (online) Vladimir Vapnik zitiert einen Artikel aus dem Jahre 1963A. E. Bryson, W. F. Denham, S. E. Dreyfus: Optimal programming problems with inequality constraints. I: Necessary conditions for extremal solutions. In: AIAA J. 1, 11, 1963, S. 2544–2550. 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.Seppo Linnainmaa: The representation of the cumulative rounding error of an algorithm as a Taylor expansion of the local rounding errors. Master’s Thesis (in Finnish), Univ. Helsinki, 1970, S. 6–7.Seppo Linnainmaa: Taylor expansion of the accumulated rounding error. In: BIT Numerical Mathematics. 16(2), 1976, S. 146–160. Dies ist die moderne Variante des Backpropagation-Verfahrens, welche auch bei dünner Vernetzung effizient ist.Andreas Griewank: Who Invented the Reverse Mode of Differentiation? Optimization Stories. In: Documenta Matematica. Extra Volume ISMP, 2012, S. 389–400.Andreas Griewank, Andrea Walther: Principles and Techniques of Algorithmic Differentiation. 2. Auflage. SIAM, 2008.
1973 verwendete Stuart Dreyfus Backpropagation, um Parameter von Steuersystemen proportional zu ihren Fehlergradienten zu adjustieren.Stuart Dreyfus: The computational solution of optimal control problems with time lag. In: IEEE Transactions on Automatic Control. 18(4), 1973, S. 383–385. Paul Werbos erwähnte 1974 die Möglichkeit, dieses Prinzip auf künstliche neuronale Netze anzuwenden,Paul Werbos: Beyond regression: New tools for prediction and analysis in the behavioral sciences. PhD thesis. Harvard University 1974. und im Jahre 1982 tat er dies auf die heute weit verbreitete Art und Weise.Paul Werbos: Applications of advances in nonlinear sensitivity analysis. In: System modeling and optimization. Springer, Berlin/Heidelberg 1982, S. 762–770. (online) 1986 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.David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams: Learning representations by back-propagating errors. In: Nature. Band 323, 1986, S. 533–536. Eric A. Wan war 1993 der erste, der einen internationalen Mustererkennungswettbewerb durch Backpropagation gewann.Eric A. Wan: Time series prediction by using a connectionist network with internal delay lines. In: Santa Fe Institute Studies in the Sciences of Complexity-Proceedings. Vol. 15, Addison-Wesley Publishing Co., 1993, S. 195–195.
Herleitung Die Formel des Backpropagation-Verfahrens wird durch Differenziation hergeleitet: Für die Ausgabe eines Neurons mit zwei Eingaben und erhält man eine zweidimensionale Hyperebene, wobei der Fehler des Neurons abhängig von den Gewichtungen der Eingaben 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 mini|420px|Künstliches Neuron mit Index j Für die Herleitung des Backpropagation-Verfahrens sei die Neuronenausgabe eines künstlichen Neurons kurz dargestellt. Die Ausgabe eines künstlichen Neurons lässt sich definieren durch
und die Netzeingabe durch
Dabei ist eine differenzierbare Aktivierungsfunktion deren Ableitung nicht überall gleich null ist, die Anzahl der Eingaben, die Eingabe und die Gewichtung zwischen Eingabe und Neuron .
Auf einen Schwellwert 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 ergibt sich durch Verwendung der Kettenregel:
lang=de|mini|300px|Einfaches Netz mit verdeckter Schicht und Ausgabeschicht mit jeweils drei bzw. zwei Neuronen. Mit Matrizen und Vektoren lautet die Kettenregel:
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:
mit
Dabei ist die Änderung des Gewichts der Verbindung von Neuron zu Neuron , eine feste Lernrate, mit der die Stärke der Gewichtsänderungen bestimmt werden kann, das Fehlersignal des Neurons , entsprechend zu , die Soll-Ausgabe des Ausgabeneurons , die Ausgabe des Neurons , die Ist-Ausgabe des Ausgabeneurons und der Index der Neuronen des nachfolgenden Layers von Neuron .
Bei einem einschichtigen Netzwerk ist . Die Ausgabe entspricht dann also den Eingängen des Netzwerks.
Modifizierung der Gewichte
Die Variable 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:
.
Dabei ist der neue Wert des Gewichts, der alte Wert des Gewichts und die oben berechnete Änderung des Gewichts (basierend auf )
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.
Kettenregel Die Vorhersagen sind eine lineare Funktion, gefolgt von einer Sigmoidfunktion. Das Modell und die Verlustfunktion lauten wie folgt:
Partielle Ableitungen können auf dieselbe Weise berechnet werden, wie univariate Ableitungen berechnet würden. Man kann die Kostenfunktion in Bezug auf und erweitern und dann die Ableitungen mithilfe wiederholter Anwendungen der univariaten Kettenregel berechnen:
Die multivariable Kettenregel ist eine Verallgemeinerung der univariaten Kettenregel:Roger Grosse, University of Toronto: Lecture 6: BackpropagationRoger Grosse, University of Toronto: Backpropagation & Automatic Differentiation
Kostenfunktionen für das maschinelle Lernen basieren normalerweise auf Matrixberechnungen. Eine Theorie besagt, dass es immer einen Algorithmus zum Berechnen von Ableitungen einer Kostenfunktion gibt, der höchstens ein paar Mal so viele Operationen verwendet wie die Kostenfunktion selbst.