Automatisches Differenzieren

Grundidee und Bedeutung

Automatisches Differenzieren (AD), auch Differenzieren von Algorithmen, ist ein Verfahren aus Informatik und angewandter Mathematik. Es erzeugt zu einer mehrvariablen Funktion, die als Programmprozedur oder Berechnungsgraph vorliegt, eine erweiterte Prozedur. Diese wertet sowohl die Funktion als auch einen oder beliebig viele Gradienten bis hin zur vollständigen Jacobi-Matrix aus.

Für f\colon\mathbb{R}^n\to\mathbb{R}^m,\ x\mapsto y lautet die Jacobi-Matrix \frac{\partial f}{\partial x}=\left[\frac{\partial y_i}{\partial x_j}\right]_{i=1..m,j=1..n}. Solche Ableitungen werden etwa beim Newton-Verfahren zum Lösen nichtlinearer Gleichungssysteme sowie in der nichtlinearen Optimierung benötigt. AD verwendet die Kettenregel und bekannte, exakt berechenbare Ableitungen von Elementarfunktionen wie \sin, \cos, \exp und \log. Daher ist der Rechenaufwand für Ableitungen proportional, mit kleinem Faktor, zum Aufwand der Funktionsauswertung. Enthält das Ausgangsprogramm Schleifen, darf deren Durchlaufzahl nicht von den unabhängigen Variablen abhängen.

Abgrenzung zu anderen Ableitungsverfahren

Eine Ableitung kann zunächst von Hand aus einer geschlossenen analytischen Form bestimmt und anschließend programmiert werden. Das ist sehr effizient und genau, aber bei komplizierten Funktionen schwierig, zeitaufwendig und fehleranfällig.

Ein Computeralgebrasystem kann eine Berechnungsvorschrift symbolisch differenzieren und den Code exportieren. Dieser Ansatz ist ebenfalls zeitaufwendig, skaliert nicht gut und wird für größere Programme oder Funktionen zu kompliziert.

Bei der numerischen Differentiation wird für kleines h angenähert: \frac{\partial f_k}{\partial x}=\lim_{h\to0}\frac{f_k(x+h)-f_k(x)}{h}\approx\frac{f_k(x+h)-f_k(x)}{h}. Sie ist einfach, kann aber wegen der Wahl einer passenden Schrittweite h ungenau oder instabil sein.

AD stellt die Berechnung dagegen als Berechnungsbaum beziehungsweise arithmetisches Netzwerk dar. Dieser wird mit der Kettenregel so erweitert, dass Funktionswert und Ableitung berechnet werden.

Zwischenwerte und die zwei Modi

AD zerlegt f(x) in elementare Teilfunktionen. Deren Zwischenwerte werden etwa als t_1,t_2,t_3,\dots gespeichert: Zunächst gilt (t_1,\dots,t_n)=(x_1,\dots,x_n), danach werden nacheinander Teilfunktionen q_k ausgewertet. Die Ausgaben liegen schließlich in den letzten Zwischenwerten, also (y_1,\dots,y_m)=(t_{K-m+1},\dots,t_K).

Ziel ist ein Programm zur Auswertung von J=\frac{\partial f}{\partial x}\in\mathbb{R}^{m\times n}. Die Eingaben x heißen unabhängige, die Ausgaben y abhängige Variablen. Beide AD-Modi beruhen auf \frac{\partial f(g)}{\partial x}=\frac{\partial f(g)}{\partial g}\cdot\frac{\partial g}{\partial x}. Im Vorwärtsmodus wird die innere Ableitung, im Rückwärtsmodus die äußere Ableitung fortgepflanzt. Der jeweils fortgepflanzte Wert heißt Saat (seed). Anfangswerte sind \frac{\partial x}{\partial x}=1 beziehungsweise \frac{\partial f(g)}{\partial f(g)}=1.

Vorwärts- und Rückwärtsmodus

Im Vorwärtsmodus werden partielle Ableitungen entlang des Kontrollflusses von innen nach außen transportiert. Er berechnet Funktionswert und Ableitung bezüglich einer unabhängigen Variablen gleichzeitig. Für \frac{\partial y_2}{\partial x_1} setzt man beispielsweise x_1'=1 und x_2'=0; für \frac{\partial y_2}{\partial x_2} umgekehrt. Für jede unabhängige Variable ist ein eigener Durchlauf nötig.

Beim Beispiel y_0=x_1+x_2, y_1=a\sin(y_0), y_2=y_0y_1 gelten im Vorwärtsmodus: y_0'=x_1'+x_2',\qquad y_1'=a\cos(y_0)y_0',\qquad y_2'=y_0'y_1+y_0y_1'.

Der Rückwärtsmodus hat zwei Phasen: Zuerst wird das Originalprogramm ausgeführt und alle Teilfunktionswerte werden gespeichert. Danach läuft die Berechnung rückwärts; äußere partielle Ableitungen werden zur Berechnung innerer verwendet. Das heißt Backpropagation. Treten Zwischenwerte mehrfach auf, werden ihre Beiträge addiert. Im Beispiel ist \frac{\partial y_2}{\partial y_0}=y_0\,(a\cos(y_0))+y_1, weil y_0 sowohl in y_1 als auch direkt in y_2 vorkommt. In einem Rückwärtsdurchlauf entstehen die Ableitungen nach allen unabhängigen Variablen.

Aufwand und Verkettung großer Berechnungen

Mit T_f als Rechenzeit und M_f als Speicherbedarf für f gilt für den Vorwärtsmodus näherungsweise \frac{T_{JS}}{T_f}\approx p,\qquad\frac{M_{JS}}{M_f}\approx p. Für den Rückwärtsmodus gilt \frac{T_{SJ}}{T_f}\approx p,\qquad\frac{M_{SJ}}{M_f}\approx T_f. Der Vorwärtsmodus muss keine Zwischenergebnisse für einen zweiten Durchgang speichern, aber pro Komponente ausgeführt werden. Ein Compiler kann wiederverwendete partielle Ableitungen im Vorwärtsmodus optimieren.

Bei verketteten Berechnungen sollte man nicht erst alle Jacobi-Matrizen berechnen und anschließend multiplizieren. Im Tragflügel-Beispiel gilt A(x)=A_0+\sum_{j=1}^{n}x_jA_j mit n=8, A\colon\mathbb{R}^8\to\mathbb{R}^{200}, G\colon\mathbb{R}^{200}\to\mathbb{R}^{17428} und f\colon\mathbb{R}^{17428}\to\mathbb{R}. Für f(G(A(x))) wird das Ergebnis jeder Rechnung als Saatmatrix der nächsten verwendet, beginnend mit I_{8\times8}. Da jede Matrix 8 Zeilen hat, also p=8, steigen Zeit- und Speicherbedarf gegenüber der normalen Auswertung von f(x) höchstens um den Faktor 8.