Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Automatisches Differenzieren aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Automatisches Differenzieren

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

Aufgabe: Gegeben eine Funktion
$f:\backslash mathbb\{R\}^n\; \backslash rightarrow\; \backslash mathbb\{R\}^m,\; x\; \backslash mapsto\; y$
Wie erhält man Code/Funktion für
$\{\backslash partial\; f\; \backslash over\; \backslash partial\; x\}=\backslash left[\; \backslash left(\; \{\backslash partial\; y\_i\; \backslash over\; \backslash partial\; x\_j\}\; \backslash right)\_\{i=1..m,\; j=1..n\}\; \backslash right]$
Verschiedene Ansätze hierfür sind:
# Versuche eine geschlossene, analytische Form für f zu finden und bestimmt $\{\backslash partial\; f\; \backslash over\; \backslash partial\; y\}$ durch Differentiation. Implementiere dann den Code für $\{\backslash partial\; f\; \backslash over\; \backslash 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 $\{\backslash partial\; f\; \backslash over\; \backslash 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
$\{\backslash partial\; f\_k\; \backslash over\; \backslash partial\; x\}\; =\; \backslash mbox\{Lim\}\_\{h\backslash rightarrow\; 0\}\; \{f\_k(x+h)-f\_k(x)\; \backslash over\; h\}\; \backslash approx\; \{f\_k(x+h)-f\_k(x)\; \backslash over\; h\}$. Problem: wie findet man eine optimale Schrittweite h?
# Versuche den Code durch Verwendung der Kettenregel zu transformieren, so daß man $\{\backslash partial\; f\; \backslash over\; \backslash partial\; x\}$ erhält.

Die Idee der Automatischen Differentiation (AD)

Gegeben ein Programm das eine Funktion $f(x):\backslash mathbb\{R\}^n\; \backslash rightarrow\; \backslash mathbb\{R\}^m,\; x\; \backslash mapsto\; y$ berechet. AD beschreibt eine Menge von Verfahren, deren Ziel es ist ein neues Programm zu erzeugen welches die Jacobimatrix von f $J:=\{\backslash partial\; f\; \backslash over\; \backslash partial\; x\},\; J\; \backslash in\; \backslash 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)

Vorwärtsmodus

Im Vorwärtsmodus berechnet man eine Matrix $JS,\; S\; \backslash in\; \backslash mathbb\{R\}^\{nxp\}$ mit einer beliebigen Matrix S (Seedmatrix) und einem näher zu bestimmenden Parameter p

= Beispiel

=
$p=n\; \backslash \; \backslash \; \backslash mbox\{und\}\backslash \; \backslash \; S=I\_\{nxn\}\; \backslash 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.

= Beispiel

=
Berechne eine Funktion


$[\; y\_1\; \backslash \; y\_2\; \backslash \; g\; ]\; =\; f\backslash left(x\_1,\; x\_2,\; a\backslash right)$

$b=x\_1+x\_2$

$y\_1=a\; \backslash cdot\; \backslash sin(b)$

$y\_2=b\; y\_1$


Eine Automatische Differentiation im Vorwärtsmodus hätte eine Funktion
$[g\backslash \_y\_1,\; y\_1,\; g\backslash \_y\_2,\; y\_2,\; b\; ]\; =\; g\backslash \_f\backslash left(\; g\backslash \_x\_1,\; x\_1,\; g\backslash \_x\_2,\; x\_2,\; \backslash right)$
zum Ergebnis. Der Funktionsrumpf von g_f:

$g\backslash \_b=g\backslash \_x\_1+g\backslash \_x\_2$

$b=x\_1+x\_2$

$g\backslash \_y\_1=a\backslash cdot\; cos(b)\; g\backslash \_b$

$y\_1=a\; \backslash cdot\; sin(b)$

$g\backslash \_y\_2\; =\; g\backslash \_b\; y\_1\; +\; b\; g\backslash \_y\_1$

$y\_2\; =\; b\; y\_1$

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\; \backslash in\; \backslash mathbb\{R\}^\{pxm\}$

= Beispiel 1

=

$p=m\; \backslash \; \backslash \; \backslash mbox\{und\}\backslash \; \backslash \; S=I\_\{mxm\}\; \backslash Rightarrow$ AD berechnet J

= Beispiel 2

=

$b=x\_1+x\_2$
$y\_1=a\backslash cdot\backslash sin(b)$
$y\_2=b\backslash cdot\; y\_1$
$a\backslash \_b=a\backslash \_b+y\_1+a\backslash \_y2$
$a\backslash \_y\_1=a\backslash \_y\_1+b\backslash cdot\; a\backslash \_y\_2$
$a\backslash \_b=a\backslash \_b+\backslash cos(b)\backslash cdot\; a\backslash \_y1$
$a\backslash \_x\_1=a\backslash \_x\_1+a\backslash \_b$
$a\backslash \_x\_1=a\backslash \_x\_2+a\backslash \_b$

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 gelteFür die beiden vorgestellten Modi gilt
# Vorwärtsmodus: $\{T\_\{JS\}\; \backslash over\; T\_f\}\; \backslash approx\; p,\; \{M\_\{JS\}\; \backslash over\; M\_f\}\; \backslash approx\; p$
# Rückwärtsmodus: $\{T\_\{SJ\}\; \backslash over\; T\_f\}\; \backslash approx\; p,\; \{M\_\{SJ\}\; \backslash over\; M\_f\}\; \backslash approx\; T\_f$

Die Berechnung als Kette von Berechnung

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

$a\backslash \_u=a\backslash \_u+\{\backslash partial\; g\backslash over\; \backslash partial\; u\}\; a\backslash \_s$
$a\backslash \_v=a\backslash \_v+\{\backslash partial\; g\backslash over\; \backslash partial\; v\}\; a\backslash \_s$

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\backslash left(\; x\; \backslash right)\; =\; A\_0\; +\; \backslash sum\_\{j=1\}^n\; x\_j\; A\_j,\; n=8,\; f\_1:\backslash mathbb\{R\}^8\; \backslash rightarrow\; \backslash mathbb\{R\}^\{200\}$
* Berechnung eines Gitters, das um den Tragflügel herum gelegt wird
$G\backslash left(\; A\; \backslash right):\; \backslash mathbb\{R\}^\{200\}\; \backslash leftarrow\; \backslash mathbb\{R\}^\{17428\}$
* Lösung der Navier-Stokes-Gleichungen auf dem Gitter und Berechnung der Integrals der selbigen.
$f\backslash left(\; G\; \backslash right)\; :\; \backslash mathbb\{R\}^\{17428\}\; \backslash rightarrow\; \backslash mathbb\{R\}$.

Insgesamt ergibt sich die Funktion
$f=f\backslash left(\; G\; \backslash left(\; A\; \backslash left(\; x\; \backslash right)\; \backslash right)\; \backslash right)\; \backslash rightarrow\; \{\backslash partial\; f\; \backslash over\; \backslash partial\; x\}\; =\; \{\backslash partial\; f\; \backslash over\; \backslash partial\; G\}\{\backslash partial\; G\; \backslash over\; \backslash partial\; A\; \}\{\backslash partial\; A\; \backslash over\; \backslash partial\; x\}$

Mit einem naivem Ansatz würde man drei Matrizen $\{\backslash partial\; f\; \backslash over\; \backslash partial\; G\}$,$\{\backslash partial\; G\; \backslash over\; \backslash partial\; A\}$,$\{\backslash partial\; A\; \backslash over\; \backslash partial\; x\}$ berechnen und dann zwei Matrix-Matrix Multiplikationen durchführen. Der Nachteil des Vorwärtsmodus ist allerdings:

$T\_\; \backslash approx\; 17428\; \backslash cdot\; T\_\{f\backslash left(\; G\; \backslash right)\}$

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

# Wähle $I\_\{8x8\}\; \backslash in\; \backslash 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

# $\{\backslash partial\; A\; \backslash over\; \backslash partial\; x\}\; I\_\{8x8\}\; \backslash in\; \backslash mathbb\{R\}^\{200x8\}$
# $\{\backslash partial\; G\; \backslash over\; \backslash partial\; A\}\; \{\backslash partial\; A\; \backslash over\; \backslash partial\; x\}\; \backslash in\; \backslash mathbb\{R\}^\{17428x8\}$
# $\{\backslash partial\; f\; \backslash over\; \backslash partial\; G\}\; \{\backslash partial\; G\; \backslash over\; \backslash partial\; x\}\; \backslash in\; \backslash mathbb\{R\}^\{1x8\}$

Da die Zeilenzahl jeder Matrix 8 (p=8) ist erhöht sich der Zeit- und Speicherbedarf ebenfalls um höchstens 8.

Weblinks

• Programmierwerkzeuge zum Thema
* Andreas Griewank: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, [http://www.ec-securehost.com/SIAM/FR19.html Frontiers in applied mathematics 19], ISBN 0-89871-451-6
• Autodiff

       VIDEO-NEWS UND ANGEBOTE