Automatisches Differenzieren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das automatische Differenzieren bzw. Differenzieren von Algorithmen ist ein Verfahren der Informatik und angewandten Mathematik. Zu einer Funktion in mehreren Variablen, die als Prozedur in einer Programmiersprache oder als Berechnungsgraph gegeben ist, wird eine erweiterte Prozedur erzeugt, die sowohl die Funktion als auch einen oder beliebig viele Gradienten bis hin zur vollen Jacobi-Matrix auswertet. Wenn das Ausgangsprogramm Schleifen enthält, darf die Anzahl der Schleifendurchläufe nicht von den unabhängigen Variablen abhängig sein.

Diese Ableitungen werden z. B. für das Lösen von nichtlinearen Gleichungssystemen mittels Newton-Verfahren und für Methoden der nichtlinearen Optimierung benötigt.

Das wichtigste Hilfsmittel dabei ist die Kettenregel sowie die Tatsache, dass zu den im Computer verfügbaren Elementarfunktionen wie sin, cos, exp, log die Ableitungen bekannt und genauso exakt berechenbar sind. Damit wird der Aufwand zur Berechnung der Ableitungen proportional (mit kleinem Faktor) zum Aufwand der Auswertung der Ausgangsfunktion.

Berechnung von Ableitungen

[Bearbeiten | Quelltext bearbeiten]

Aufgabe: Gegeben sei eine Funktion

Gesucht ist der Code/die Funktion für Richtungsableitungen oder die volle Jacobi-Matrix

Verschiedene Ansätze hierfür sind:

  1. Versuche, eine geschlossene, analytische Form für f zu finden und bestimme durch Differentiation „auf Papier“. Implementiere dann den Code für von Hand.
    Problem: Zu schwierig, zeitaufwendig, fehleranfällig
    Vorteile: sehr effizient, hohe Genauigkeit
  2. Erzeuge die Berechnungsvorschrift für f in einem Computeralgebrasystem und wende die dort zur Verfügung stehenden Mittel zum symbolischen Differenzieren an. Exportiere dann den Code für in seine eigentliche Umgebung.
    Problem: Zeitaufwendig, skaliert nicht, zu kompliziert für größere Programme/Funktionen
  3. Bestimme eine numerische Approximation der Ableitung. Es gilt für kleines h
    .
    Problem: Wahl der optimalen Schrittweite h, ungenau, eventuell Instabilität
    Vorteil: einfache Berechnung
  4. Stelle die Berechnungsvorschrift als Berechnungsbaum, d. h. als arithmetisches Netzwerk, dar und erweitere diesen unter Verwendung der Kettenregel zu einem Berechnungsbaum für Funktionswert und Ableitung .

Die Idee der automatischen Differentiation (AD)

[Bearbeiten | Quelltext bearbeiten]

Eine Funktion kann als eine Verkettung elementarer Teil-Funktionen beschrieben werden. Automatische Differentiation (AD) berechnet die Ableitung als Verkettung partieller Ableitungen. AD benötigt daher den Wert und die Ableitung jeder Teil-Funktion als Zwischenergebnis. Dem Zwischenwert jeder Teil-Funktion wird nachfolgend eine Variable zugewiesen. Man kann sich dies so vorstellen, dass es eine (potentiell unendliche) Folge von Zwischenwerten gibt und Funktionen , die aber nur von ein oder zwei Variablen wirklich abhängen. Die Funktion wird ausgewertet, indem am Anfang gesetzt wird und nacheinander

bestimmt wird. Dies kann so eingerichtet werden, dass die Funktionswerte von f sich in den zuletzt ausgewerteten Zwischenergebnissen befinden, d. h. am Ende wird noch zugeordnet.

AD beschreibt eine Menge von Verfahren, deren Ziel es ist, ein neues Programm zu erzeugen, das die Jacobimatrix von f, auswertet. Die Eingabevariablen x heißen unabhängige Variablen, die Ausgabevariable(n) y abhängige Variablen. Bei AD unterscheidet man mindestens zwei verschiedene Modi.

  1. Vorwärtsmodus (engl. Forward Mode)
  2. Rückwärtsmodus (engl. Reverse Mode)

Beide Modi basieren auf der Kettenregel, wonach die Ableitung einer Funktion sich als Verkettung partieller Ableitungen darstellen lässt: . Der Vorwärtsmodus beginnt mit der inneren Ableitung , der Rückwärtsmodus mit der äußeren . Der Wert der partiellen Ableitung, genannt Saat (engl. seed), wird jeweils vor- bzw. zurückpropagiert und ist initial bzw. . Der Vorwärtsmodus wertet im selben Schritt die Funktion aus und berechnet die Ableitung bzgl. einer unabhängigen Variablen. Für jede unabhängige Variable ist daher ein eigener Schritt nötig, in dem die Ableitung bzgl. einer unabhängigen Variable auf eins () und aller anderen auf null () gesetzt wird. Im Gegensatz dazu benötigt der Rückwärtsmodus für die partiellen Ableitungen die ausgewerteten Teil-Funktionen. Der Rückwärtsmodus wertet daher die Funktion zuerst aus und berechnet die Ableitungen bzgl. aller unabhängiger Variablen in einem zusätzlichen Rückwärtsschritt.

Automatisches Differenzieren im Vorwärtsmodus

Im Vorwärtsmodus werden die partiellen Ableitungen entlang des Kontrollflusses der Berechnung von f transportiert, also von der innersten zur äußersten partiellen Ableitung.

Berechne eine Funktion

 

Eine automatische Differentiation im Vorwärtsmodus hätte eine Funktion

 

zum Ergebnis, die den Wert der inneren Ableitung von () erwartet und die Ableitung von () zurückgibt:

 

Um die Ableitung zu berechnen, muss und gesetzt werden und entsprechend für dann und .

Deutlich intuitiver ist, die Funktion rekursiv anhand ihrer Teilfunktionen zu berechnen. Dabei gibt der modifizierte Funktionsaufruf ein Zweier-Tupel aus dem Wert der Funktion und der partiellen Ableitung zurück und erwartet als Argument den Wert aller Variablen und der partiellen Ableitung aller unabhängigen Variablen:

 

Der Vorwärtsmodus berechnet die Funktion und die Ableitung (aber jeweils nur für eine unabhängige Variable) in einem Schritt. Der zugehörige Methodenaufruf erwartet den abzuleitenden Ausdruck Z und die Variable V, nach der abgeleitet wird. Die Methode gibt ein Wertepaar aus der ausgewerteten Funktion und der zugehörigen Ableitung zurück. Die Methode arbeitet den Ausdrucksbaum rekursiv ab, bis eine Variable erreicht wird. Ist das die Variable, nach der abgeleitet wird, so ist deren Ableitung 1, 0 anderenfalls. Anschließend werden die partielle Funktion sowie die partielle Ableitung ausgewertet.[1]

tuple<float,float> auswerten(Ausdruck Z, Ausdruck V) {
   if istVariable(Z)
      if (Z=V) return {wertVon(Z),1};
      else return {wertVon(Z),0};
   else if (Z = X + Y)
      {x,x'} = auswerten(X,V);
      {y,y'} = auswerten(Y,V);
      return {x+y, x'+y'};
   else if (Z = X - Y)
      {x,x'} = auswerten(X,V);
      {y,y'} = auswerten(Y,V);
      return {x-y, x'-y'};
   else if (Z = X * Y)
      {x,x'} = auswerten(X,V);
      {y,y'} = auswerten(Y,V);
      return {x*y, x'*y+x*y'};
}

Rückwärtsmodus

[Bearbeiten | Quelltext bearbeiten]
Automatisches Differenzieren im Rückwärtsmodus
Beispiel für automatisches Differenzieren im Rückwärtsmodus

Der Rückwärtsmodus besteht aus zwei Phasen.

  1. Das Originalprogramm wird ausgeführt und die Werte der ausgewerteten Teil-Funktionen zwischengespeichert.
  2. Das Originalprogramm wird rückwärts ausgeführt. Dabei werden die äußeren partiellen Ableitungen zur Berechnung der inneren verwendet. Dabei werden die Werte aus Phase 1 verwendet.

Zuerst werden die Teil-Funktionen der Funktion ausgewertet:

Anschließend wird die äußerste partielle Ableitung gebildet, um daraus die inneren Ableitungen zu berechnen. Für die Ableitung muss man berücksichtigen, dass in und vorkommt: aus stammt der Teil , aus der Teil , die beide addiert werden.

Aufgrund der Distributivität könnte man in , und aufteilen mit .

Der Rückwärtsmodus berechnet alle Komponente der Jacobi-Matrix in zwei Schritten: Im Vorwärtsschritt wird zuerst die Funktion ausgewertet und die partiellen Ergebnisse zwischengespeichert. Im Rückwärtsschritt werden die partiellen Ableitungen berechnet und der zuvor abgeleitete Wert zurückpropagiert (backpropagation). Der zugehörige Methodenaufruf erwartet den abzuleitenden Ausdruck Z und seed mit dem abgeleiteten Wert des Elternausdrucks. Für den obersten Ausdruck, Z nach Z abgeleitet, ist dieser 1. Die Methode arbeitet den Ausdrucksbaum rekursiv ab, bis eine Variable erreicht wird, und addiert den aktuellen seed-Wert zu dem Ausdruck für die Ableitung der Komponente.[2][3]

void ableiten(Ausdruck Z, float seed) {
   if (Z = X + Y)
      ableiten(X,seed);
      ableiten(Y,seed);
   else if (Z = X - Y)
      ableiten(X,seed);
      ableiten(Y,-seed);
   else if (Z = X * Y)
      ableiten(X,wertVon(X)*seed);
      ableiten(Y,seed*wertVon(Y));
   else if istVariable(Z)
      partielleAbleitungVon(Z) += seed;
}

Effizienzbetrachtungen

[Bearbeiten | Quelltext bearbeiten]

Die Effizienz von AD-Algorithmen hängt vom Modus und dem Parameter p ab. Die Wahl des Modus und des Parameters p hängt davon ab, wofür die Jacobimatrix berechnet wird. Es bezeichne

die Zeit f zu berechnen
der Speicherbedarf dieser Rechnung
die Zeit f und JS zu berechnen
der Speicherbedarf dieser Rechnung
die Zeit f und SJ zu berechnen
der Speicherbedarf dieser Rechnung

Für die beiden vorgestellten Modi gilt

  1. Vorwärtsmodus:
  2. Rückwärtsmodus:

Der Vorwärtsmodus hat den Vorteil, dass keine Zwischenergebnisse für einen zweiten Durchgang gespeichert werden müssen, und den Nachteil, dass er pro Komponente einmal ausgeführt werden muss. Dennoch basieren beide AD-Algorithmen auf der Berechnung partieller Ableitungen. Ein Compiler ist daher in der Lage den Code des Vorwärtsmodus zu optimieren, sodass partielle Ableitungen, die für mehr als eine Komponente benötigt werden, auch nur einmal – wie im Rückwärtsmodus – berechnet werden.[1]

Die Berechnung als Kette von Berechnungen

[Bearbeiten | Quelltext bearbeiten]

Gegeben: , Frage: Wie verändert sich die Ableitung von s während der zweiten Phase, um die Ableitungen von u und v zu erhalten?

wird als Sequenz von Programmen interpretiert. Im Beispiel „Optimierung eines Tragflügels“ umfasst die Berechnung die folgenden Schritte.

  • Überlagerung des Tragflügels mit sogenannten „Mode-Funktionen“
  • Berechnung eines Gitters, das um den Tragflügel herum gelegt wird
.

Insgesamt ergibt sich die Funktion

  

Mit einem naiven Ansatz würde man drei Matrizen , , berechnen und dann zwei Matrizenmultiplikationen durchführen. Der Nachteil des Vorwärtsmodus ist allerdings:

  

im Rückwärtsmodus würde analog

  

gelten. Ein besserer Ansatz ist, das Ergebnis einer Berechnung jeweils als Saatmatrix der folgenden einzusetzen.

  1. Wähle als Saatmatrix der ersten Rechnung
  2. Das Ergebnis der ersten Rechnung als Saatmatrix der zweiten Rechnung
  3. Das Ergebnis der zweiten Rechnung als Saatmatrix der dritten Rechnung

also

Da die Zeilenzahl jeder Matrix 8 (p=8) ist, erhöht sich der Zeit- und Speicherbedarf gegenüber der regulären Auswertung von um höchstens 8.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b Maximilian E. Schüle, Maximilian Springer, Alfons Kemper, Thomas Neumann,: LLVM Code Optimisation for Automatic Differentiation. In: DEEM '22: Proceedings of the Sixth Workshop on Data Management for End-To-End Machine Learning. 2022, doi:10.1145/3533028.3533302 (englisch).
  2. Maximilian E. Schüle, Harald Lang, Maximilian Springer, Alfons Kemper, Thomas Neumann, Stephan Günnemann: In-Database Machine Learning with SQL on GPUs. In: 33rd International Conference on Scientific and Statistical Database Management. 2021, doi:10.1145/3468791.3468840 (englisch).
  3. Maximilian E. Schüle, Harald Lang, Maximilian Springer, Alfons Kemper, Thomas Neumann, Stephan Günnemann: Recursive SQL and GPU-support for in-database machine learning. In: Distributed and Parallel Databases. 2022, doi:10.1007/s10619-022-07417-7 (englisch).