Automatische Differenzierung in 30 Zeilen Python verstehen

 (vmartin.fr)
3 Punkte von GN⁺ 2023-08-27 | 1 Kommentare | Auf WhatsApp teilen
  • Der Artikel zeigt, wie man die für das Training neuronaler Netze zentrale automatische Differenzierung mit einer skalaren Tensor-Klasse selbst implementiert – und wie Wertberechnung und Ableitungsberechnung auf demselben Berechnungsgraphen zusammenhängen
  • Bei normalen Python-Variablen bleibt bei z = x + y nur der Ergebniswert erhalten und die Beziehung geht verloren; daher muss Tensor sowohl den Wert als auch die Operationshistorie speichern
  • Mit Children(a, b, op) und rekursiven forward()-Aufrufen entsteht ein binärer Berechnungsbaum; durch Überladen von Addition und Multiplikation lässt sich der Ausdruck auch dann neu berechnen, wenn Werte erst später eingesetzt werden
  • grad(deriv_to) setzt die Ableitung nach sich selbst auf 1 und nach anderen Skalaren auf 0 und wendet die Ableitungsregeln der Grundoperationen rekursiv an, um einen neuen Berechnungsgraphen zu erzeugen
  • Die Implementierung verarbeitet nur Skalare und kann langsam sein; als Verbesserungen bleiben Array-Operationen, Pruning von Multiplikationszweigen mit 0, Behandlung von Konstantenknoten und ein Cache zur Reduktion wiederholter Berechnungen

Bei normalen Python-Variablen geht die Beziehung verloren

  • Wenn man wie x = 3, y = 5, z = x + y rechnet, bleibt in z nur der Ergebniswert 8 erhalten
  • Selbst wenn sich später der Wert von x oder y ändert, kann z nicht mehr nachverfolgen, aus welchen Variablen es erzeugt wurde
  • Da die Beziehungen zwischen Variablen nicht erhalten bleiben, ist es schwierig, Ableitungen nach einer bestimmten Variablen automatisch zu berechnen

Operationshistorie mit Tensor erhalten

  • Der neue Typ Tensor speichert einen Wert (value) und überlädt Operatoren, sodass Berechnungen zwischen Tensor-Objekten einen neuen Tensor zurückgeben
  • Die erste Implementierung überlädt nur __add__, sodass Tensor(3) + Tensor(5) ein T:8 erzeugen kann
  • In diesem Schritt wird die Operationshistorie, dass z das Ergebnis von x + y ist, aber noch nicht erhalten

Berechnungsgraph und forward()

  • Um die Operationshistorie zu bewahren, wird Children = namedtuple('Children', ['a', 'b', 'op']) eingeführt
    • a: linker Eingabe-Tensor
    • b: rechter Eingabe-Tensor
    • op: die eigentliche Operation, etwa np.add oder np.multiply
  • Jeder Tensor kann nicht nur einen Zahlenwert, sondern auch children haben; darüber wird ein Berechnungsgraph in Form eines binären Baums aufgebaut
  • forward() besucht rekursiv die Kindknoten und berechnet den tatsächlichen Wert
    • Aus x = Tensor(3), y = Tensor(5) sowie z1 = x + y, z2 = z1 * y wird T:40
    • Auch wenn man den Graphen zuerst mit x = Tensor(None), y = Tensor(None) erstellt, später x.value = 3, y.value = 5 setzt und z2.forward() aufruft, wird T:40 berechnet

Automatische Differenzierung als Berechnungsgraph erstellen

  • Automatische Differenzierung wird implementiert, indem für jede von Tensor unterstützte Grundoperation eine Ableitungsregel ergänzt wird
  • grad(self, deriv_to) durchläuft den Berechnungsgraphen rekursiv und zerlegt eine komplexe Funktion in eine Kombination einfacher Funktionen
  • Die Grundregeln lauten:
    • Leitet man einen Tensor nach sich selbst ab, ergibt das Tensor(1)
    • Leitet man einen Skalar ohne Kinder nach einem anderen Tensor ab, ergibt das Tensor(0)
    • Addition: (a + b)' = a' + b'
    • Multiplikation: (ab)' = a'b + ab'
  • Leitet man z2 = (x + y) * y nach y ab, ist das Ergebnis g kein einfacher Wert, sondern ein neuer Berechnungsgraph für die partielle Ableitung
    • Als Ausdruck: g = ∂z2/∂y = x + 2*y
    • Für x = 3, y = 5 hat g den Wert 13

Erweiterung um Subtraktion, Division und Exponentialfunktion

  • Um komplexere Ausdrücke zu verarbeiten, werden Tensor Subtraktion, Division, Exponentialfunktion und Negation hinzugefügt
  • grad() enthält die zugehörigen Ableitungsregeln für jede Operation
    • Subtraktion: (a - b)' = a' - b'
    • Division: (a/b)' = (a'b - ab') / b²
    • Exponentialfunktion: exp(a)' = a' * exp(a)
  • Auch forward() wird angepasst, um Operationen zu behandeln, die nur einen Operanden benötigen
    • Beispiel: exp(a) benötigt keinen zweiten Operanden b
    • -x wird als 0 - x verarbeitet

Beispielausdruck und Verifikation mit Sympy

  • Der folgende Ausdruck wird mit Tensor geschrieben, und die partiellen Ableitungen nach x und y werden berechnet
z = (12 - (x * e^y)) / (45 + x * y * e^-x)
  • Im Code wird das so ausgedrückt:
x = Tensor(3)
y = Tensor(5)
z = (Tensor(12) - (x * y.exp())) / (Tensor(45) + x * y * (-x).exp())
  • Die berechneten Werte der partiellen Ableitungen lauten:
    • z.grad(x) → T:-3.34729777301069
    • z.grad(y) → T:-9.70176956641438
  • Das Ergebnis derselben Formel, berechnet mit diff() und evalf() von Sympy, ist identisch
    • Für xs = 3, ys = 5 beträgt der Ableitungswert nach x -3.34729777301069
    • Der Ableitungswert nach y beträgt -9.70176956641438

Einschränkungen der einfachen Implementierung und Optimierungspunkte

  • Diese Implementierung kommt einem sehr einfachen System für automatische Differenzierung nahe und kann zugleich sehr langsam sein
  • Die aktuelle Klasse verarbeitet nur Skalare
    • Damit daraus eine nützlichere Library wird, müssten Array-Operationen beliebiger Größe ergänzt werden
  • Am Berechnungsgraphen erkennt man mehrere mögliche Optimierungen
    • Wenn bei einem Multiplikationsknoten eines der Kinder 0 ist, muss man nicht tiefer weiter suchen
    • Wenn ein Knoten und seine Kinder nicht vom Tensor x abhängen, nach dem abgeleitet wird, kann man diesen Knoten als Konstante betrachten und den Durchlauf stoppen
    • Bei wiederholten gleichen Operationen kann ein Cache verhindern, dass dieselbe Berechnung mehrfach ausgeführt wird

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-08-27
Hacker-News-Meinungen

  • Ich mag solche kleinen, eleganten Code-Demos. Sie helfen dabei, Konzepte zu verstehen, indem man sich selbst die Hände schmutzig macht.
    Sasha Rushs GPU-Puzzles und Tensor-Puzzles sind ähnliche Beispiele.
    https://github.com/srush/GPU-Puzzles
    https://github.com/srush/Tensor-Puzzles

  • Wer glaubt, damit automatische Differentiation vollständig verstanden zu haben, macht sich etwas vor.
    Wenn der Graph ein Baum ist, ist alles so einfach wie in diesem Artikel. Wenn der Graph aber ein allgemeinerer gerichteter azyklischer Graph ist, zum Beispiel x = 5; y = 2x; z = xy, dann bleibt die Implementierung zwar sehr simpel, aber zu verstehen, warum diese Implementierung korrekt ist, ist nicht trivial. Wer denkt, das sei „einfach die normale Kettenregel“, macht sich ebenfalls etwas vor.
    Eine der frühen Erklärungen stammt von Paul Werbos; er nannte die benötigte Regel die Kettenregel geordneter Ableitungen und bewies sie per Induktion aus der normalen Kettenregel. Trotzdem folgt sie nicht unmittelbar und offensichtlich aus der normalen Kettenregel. Falls jemand vom Gegenteil überzeugt ist, würde ich mich freuen, wenn er mir beweist, dass ich falschliege.

    • Wo sollte man dann mehr dazu lesen? Die Leute, die Frameworks wie autograd, PyTorch oder mxnet entwickelt haben, müssen das irgendwo ausführlich gelernt haben; ich würde gern wissen, welche Quellen das waren. Soweit ich weiß, stammt mxnet aus der Wissenschaft, vermutlich von der CMU.
    • Ehrlich gesagt bin ich mir in solchen Diskussionen nicht sicher, was die Leute eigentlich wollen; vielleicht liegt es daran, dass die implizierte Abstraktion der geordneten Ableitungen nicht ideal ist.
      Wenn man die normale Kettenregel entlang der Kanten eines Berechnungsgraphen, also eines gerichteten azyklischen Graphen, anwendet, erhält man in jedem Schritt die richtigen Werte. Die zusätzliche Regel, die man braucht, lautet im Wesentlichen: „Wenn eine Variable in einer Berechnung mehrfach verwendet wird, also mehrere Kanten von demselben Knoten ausgehen oder in Rückwärtsrichtung mehrere Kanten hineingehen, muss man die jeweils berechneten Gradienten addieren.“ Das halte ich ebenfalls für ziemlich grundlegend und intuitiv.
      Wenn man zum Beispiel in f(x, y) sowohl für x als auch für y z einsetzt, gilt d/dz f(z, z) = f_x(z, z) + f_y(z, z), wobei die tiefgestellten Indizes partielle Ableitungen bezeichnen. Für mich ist dieser Ansatz mathematisch einfacher, als beides zu vermischen und es so wirken zu lassen, als gehe es „über die Kettenregel hinaus“. Außerdem scheint er näher an der tatsächlichen Implementierung zu sein, insbesondere an dem, was PyTorch, womit ich am vertrautesten bin, macht.
    • Die Kettenregel ist für partielle Ableitungen definiert; technisch gesehen kann man es also weiterhin einfach als Kettenregel betrachten.

  • Automatische Differentiation fühlt sich wie Magie an.
    Viele Informatiker waren davon fasziniert und haben Artikel geschrieben, die die Technik aus einer breiteren Perspektive vorstellen. Mein eigener Text gehört auch dazu und enthält außerdem eine „Arme-Leute-Variante“, die komplexe Zahlen ohne Operator-Overloading verwendet.
    https://pizzaseminar.speicherleck.de/automatic-differentiati...

    • Als ich 1994–1995 Machine Learning gemacht habe, kannte ich automatische Differentiation nicht, und selbst der Professor, der die Zielfunktion erstellt hatte, leitete die analytischen Ableitungen von Hand her. Erst vor ein paar Jahren habe ich davon erfahren; rückblickend auf die Zeit, die ich Ende der 90er damit verbrachte, Mathematica gut genug zu lernen, um analytische Ableitungen selbst zu erzeugen, fand ich das erstaunlich.
    • Das scheint auf die Complex-Step Derivative Approximation von J. Martins, P. Sturdza und J. Alonso aus dem Jahr 2003 zurückzugehen. Der Artikel ist lesenswert.
      [0]: https://doi.org/10.1145/838250.838251
    • Es fühlt sich wirklich wie Magie an. Falls es eine Einführung in Backpropagation gibt, die auf ähnliche Weise geschrieben ist, würde ich sie gern kennen.

  • Ich habe eine 26-Zeilen-Implementierung automatischer Differentiation in Python geschrieben: https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b0...

    • Kurz ist schön, aber mein Kopf funktioniert offenbar viel besser mit etwas angemessenem Whitespace. Solche anderen Stile sollte ich wohl auch etwas üben.

  • Das ist den Techniken sehr ähnlich, die in wissensbasierten Engineering-Systemen verwendet werden; dort nennt man es Dependency Tracking. In Kombination mit Caching von Knoten oder Tensoren kann es den Rechenaufwand reduzieren, was besonders bei großen parametrischen 3D-Modellen nützlich ist.
    Beim Abrufen eines Werts ruft man rekursiv den binären/Dependency-Baum auf, prüft, welche Variablen sich geändert haben, und berechnet nur das Nötige neu. Mit eigenen Python-Objekten und Attributen, die __set__- und __get__-Methoden haben, kann man es wie eine eingebaute Funktion eines objektorientierten Modells wirken lassen.
    x = Tensor(3)
    y = Tensor(5)
    z = x + y
    print(x, y) # 3, 5
    print(z) # 8
    x.value = 4 # Beim Setzen des Werts wird nichts neu berechnet
    print(z) # 9, weil die geänderte Abhängigkeit in dem Moment neu berechnet wird, in dem der Wert abgerufen wird

  • Andrej Karpathy hat ein interessantes Video, in dem er eine Autograd-Engine baut; es ist ziemlich aufschlussreich.
    https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7
    Repository:
    https://github.com/karpathy/micrograd

  • Die Variante von automatischer Differenzierung, die ich kenne, baut keinen Rechengraphen auf. Stattdessen wird der jeweilige Wert on the fly berechnet.

    • Vermutlich ist Forward-Mode Automatic Differentiation gemeint. Sie ist nützlicher, wenn die Ausgabedimension einer Funktion vergleichsweise groß ist, und unterscheidet sich von Reverse-Mode Automatic Differentiation, die nützlicher ist, wenn die Ausgabedimension vergleichsweise klein ist.
      Beide funktionieren, aber je nach Situation ist die eine effizienter. Bei Dingen wie „Training neuronaler Netze“ optimiert man häufig eine einzelne Verlustausgabe über viele Ziele hinweg, daher verwendet man normalerweise den Reverse Mode.

  • Ich wünschte, automatische Differenzierung würde einfach numerische Kettenregel genannt oder zumindest so erklärt. Wörtlich genommen ist das alles, mit ein paar Tricks, um bei bestimmten Operationen die Jacobi-Matrix nicht explizit berechnen zu müssen; das wäre viel klarer.

    • Das hier erklärte und in Backpropagation-Implementierungen am häufigsten verwendete „autodiff“ ist Reverse-Mode Automatic Differentiation, aber es gibt auch den Forward Mode und Strategien zwischen diesen beiden Extremen. Am Ende läuft alles auf die Kettenregel hinaus, aber auf Algorithmusebene ist die Wahl der Methode keineswegs trivial.
      Wenn man tatsächlich aufgefordert wird, die Kettenregel zu verwenden, um Gradienten durch einen Rechengraphen zu propagieren, würden die meisten wohl intuitiv den Forward Mode als Standard annehmen. Ich auch.
      https://en.wikipedia.org/wiki/Automatic_differentiation#Beyo...
      Unter diesem Gesichtspunkt scheint es nützlich, den Begriff für eine bestimmte Methode zu verwenden, mit der man die durch die Kettenregel gelieferten Ausdrücke durchläuft und dabei Gradienten akkumuliert.
    • Technisch gesehen ist das falsch. Numerische Kettenregel verwendet die Finite-Differenzen-Methode, und dabei akkumulieren sich im Laufe der Berechnung Fehler.
      Siehe den Abschnitt „Unterschiede zu anderen Methoden“: https://en.m.wikipedia.org/wiki/Automatic_differentiation
      Wie in den Kommentaren in der Nähe gesagt: Der Kernpunkt ist, dass die Implementierung wirklich wichtig und ein Studium wert ist. Automatische Differenzierung als Bündel von Methoden zur Implementierung der Kettenregel zu bezeichnen, ist in Ordnung; sie „einfach“ numerische Kettenregel zu nennen, ist aber falsch.
    • Es mag genauer sein, aber klarer würde ich es nicht nennen.

  • Automatische Differenzierung ist doch in der Kategorie glatter Funktionen nur die kartesische Linse der Jacobi-Matrix und des totalen Differentials – wo ist das Problem? https://www.youtube.com/watch?v=ne99laPUxN4

  • Ich frage mich, warum der Klassenname Tensor ist. Gibt es eine Möglichkeit, Ausdrücke oder deren Ableitungen als Tensoren zu betrachten? Oder liegt es daran, dass auch Skalare Tensoren sind und man das so erweitern kann, dass auch andere Tensor-Typen unterstützt werden?

    • Ich kann mich irren, aber mathematisch würde man zweidimensionale Objekte wohl Matrizen und Objekte ab drei Dimensionen Tensoren nennen.
      Da der beschriebene Algorithmus der automatischen Differenzierung für beliebige höherdimensionale Objekte funktioniert, scheint es sinnvoll, solche Objekte Tensoren zu nennen.