Automatisches Differenzieren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

Inhaltsverzeichnis

1 Berechnung von Ableitungen
2 Die Idee der Automatischen Differentiation (AD)
3 Die Berechnung als Kette von Berechnung
4 Weblinks

[Bearbeiten] Berechnung von Ableitungen

Aufgabe: Gegeben eine Funktion

$f:\mathbb{R}^n \rightarrow \mathbb{R}^m, x \mapsto y$

Wie erhält man Code/Funktion für

${\partial f \over \partial x}=\left[ \left( {\partial y_i \over \partial x_j} \right)_{i=1..m, j=1..n} \right]$

Verschiedene Ansätze hierfür sind:

Versuche eine geschlossene, analytische Form für f zu finden und bestimmt ${\partial f \over \partial y}$ durch Differentiation. Implementiere dann den Code für ${\partial f \over \partial x}$ von Hand. Problem: Zu schwierig, zeitaufwendig, fehleranfällig
Importiere den Code für f in ein Computeralgebrasystem und wende die dort zur Verfügung stehenden Mittel an. Exportiere dann den Code für ${\partial f \over \partial x}$ in seine eigentliche Umgebung. Problem: Zeitaufwendig, skaliert nicht, zu kompliziert für größerer Programme/Funktionen
Versuche eine numerische Approximation der Ableitung zu bestimmen. Es gilt

${\partial f_k \over \partial x} = \mbox{Lim}_{h\rightarrow 0} {f_k(x+h)-f_k(x) \over h} \approx {f_k(x+h)-f_k(x) \over h}$

. Problem: wie findet man eine optimale Schrittweite h?

Versuche den Code durch Verwendung der Kettenregel zu transformieren, so daß man ${\partial f \over \partial x}$ erhält.

[Bearbeiten] Die Idee der Automatischen Differentiation (AD)

Gegeben ein Programm das eine Funktion $f(x):\mathbb{R}^n \rightarrow \mathbb{R}^m, x \mapsto y$ berechet. AD beschreibt eine Menge von Verfahren, deren Ziel es ist ein neues Programm zu erzeugen welches die Jacobimatrix von f $J:={\partial f \over \partial x}, J \in \mathbb{R}^{mxn}$ beinhaltet. Die Eingabevariablen von x heißen unabhängige Variablen, die Ausgabevariable(n) y abhängige Variablen. Bei AD unterscheidet man mindestens zwei Verschiedene Modi.

Vorwärtsmodus (FM engl Forward Mode)
Rückwärtsmodus (BM engl Backward Mode)

[Bearbeiten] Vorwärtsmodus

Im Vorwärtsmodus berechnet man eine Matrix

$JS, S \in \mathbb{R}^{nxp}$

mit einer beliebigen Matrix S (Seedmatrix) und einem näher zu bestimmenden Parameter p

[Bearbeiten] Beispiel

$p=n \ \ \mbox{und}\ \ S=I_{nxn} \Rightarrow$ AD berechnet J
Im Vorwärtsmodus werden Richtungsableitungen entlang des Kontrollflusses der Berechnung von f transportiert. Für jede skalare Variable v wird in dem AD-erzeugten Code ein Vektor g_v, dessen i-te Komponente die Richtungsableitung entlang der i-ten unabhängigen Variablen enthält.

[Bearbeiten] Beispiel

Berechne eine Funktion

  

   $b = x 1 + x 2$ 

  

   $y 2 = b y 1$

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

$[g\_y_1, y_1, g\_y_2, y_2, b ] = g\_f\left( g\_x_1, x_1, g\_x_2, x_2, \right)$

zum Ergebnis. Der Funktionsrumpf von g_f:

   $g_b = g_x 1 + g_x 2$ 

   $b = x 1 + x 2$ 

  

  

   $g_y 2 = g_b y 1 + b g_y 1$ 

   $y 2 = b y 1$

[Bearbeiten] Rückwärtsmodus

Der Rückwärtsmodus besteht aus zwei Phasen.

Das Originalprogramm wird ausgeführt und gewisse Daten werden abgespeichert
Das Originalprogramm wird Rückwärts ausgeführt. Dabei werden Richtungsableitungen transportiert und es werden die Daten aus Phase 1 verwendet.

In Phase 2 wird für jede skalare Variable v ein Vektor a_v eingeführt. Dieser Vektor enthält in der i-ten Komponente die i-te Richtungsableitung (in Richtung von v). Die Saatmatrix erscheint als Object a_y. Im Rückwärtsmodus erhält man als Ergebnis ein Produkt

$SJ, S \in \mathbb{R}^{pxm}$

[Bearbeiten] Beispiel 1

   AD berechnet J

[Bearbeiten] Beispiel 2

   $b = x 1 + x 2$ 
  
  
   $a_b = a_b + y 1 + a_y 2$ 
  
  
   $a_x 1 = a_x 1 + a_b$ 
   $a_x 1 = a_x 2 + a_b$

[Bearbeiten] Effizienzbetrachtungen

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 gelte

$T f$	die Zeit f zu berechnen
$M f$	der Speicherbedarf dieser Rechnung
$T J S$	die Zeit f und JS zu berechnen
$M J S$	der Speicherbedarf dieser Rechnung
$T S J$	die Zeit f und SJ zu berechnen
$M S J$	der Speicherbedarf dieser Rechnung

Für die beiden vorgestellten Modi gilt

Vorwärtsmodus: ${T_{JS} \over T_f} \approx p, {M_{JS} \over M_f} \approx p$
Rückwärtsmodus: ${T_{SJ} \over T_f} \approx p, {M_{SJ} \over M_f} \approx T_f$

[Bearbeiten] Die Berechnung als Kette von Berechnung

Gegeben: $s=g\left(u,v\right)$ , Frage: Wie verändert sich die Ableitug von s während der 2ten Phase, um die Ableitungen von u und v zu erhalten?

f(x) 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"

$A\left( x \right) = A_0 + \sum_{j=1}^n x_j A_j, n=8, f_1:\mathbb{R}^8 \rightarrow \mathbb{R}^{200}$

Berechnung eines Gitters, das um den Tragflügel herum gelegt wird

$G\left( A \right): \mathbb{R}^{200} \leftarrow \mathbb{R}^{17428}$

Lösung der Navier-Stokes-Gleichungen auf dem Gitter und Berechnung der Integrals der selbigen.

$f\left( G \right) : \mathbb{R}^{17428} \rightarrow \mathbb{R}$

Insgesamt ergibt sich die Funktion

Mit einem naivem Ansatz würde man drei Matrizen ${\partial f \over \partial G}$ , ${\partial G \over \partial A}$ , ${\partial A \over \partial x}$ berechnen und dann zwei Matrix-Matrix Multiplikationen 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 Saatzmatrix der folgenden einzusetzen.

Wähle $I_{8x8} \in \mathbb{R}^{8x8}$ als Saatmatrix der ersten Rechnung
Das Ergebnis der ersten Rechnung als Saatmatrix der zweiten Rechnung
Das Ergebnis der zweiten Rechnung als Saatmatrix der dritten Rechnung

also

${\partial A \over \partial x} I_{8x8} \in \mathbb{R}^{200x8}$
${\partial G \over \partial A} {\partial A \over \partial x} \in \mathbb{R}^{17428x8}$
${\partial f \over \partial G} {\partial G \over \partial x} \in \mathbb{R}^{1x8}$