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.

Inhaltsverzeichnis

Berechnung von Ableitungen

Aufgabe: Gegeben sei eine Funktion

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

Wie erhält man Code/Funktion für Richtungsableitungen oder die volle Jacobi-Matrix


  \frac{\partial f}{\partial x}=\left[ \tfrac{\partial y_i}{\partial x_j} \right]_{i=1..m, j=1..n} \ ?

Verschiedene Ansätze hierfür sind:

1.) Versuche, eine geschlossene, analytische Form für f zu finden und bestimme \tfrac{\partial f}{ \partial y} durch Differentiation „auf Papier“. Implementiere dann den Code für \tfrac{\partial f}{\partial x} von Hand.
Problem: Zu schwierig, zeitaufwendig, fehleranfällig
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 \tfrac{\partial f }{ \partial x} 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
 
  \tfrac{\partial f_k}{\partial x} = \lim_{h\to 0} \frac{f_k(x+h)-f_k(x)}{h}  \approx \frac{f_k(x+h)-f_k(x)}{h}
.
Problem: wie findet man eine optimale Schrittweite h?
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 \tfrac{\partial f}{\partial x}.

Die Idee der automatischen Differentiation (AD)

Jedes Programm, das eine Funktion f(x):\R^n \to \R^m, x \mapsto y auswertet, kann als eine Abfolge von Zwischenschritten beschrieben werden, in denen Zwischenergebnisse auf elementare Weise umgewandelt werden. Man kann sich dies so vorstellen, dass es eine (potentiell unendliche) Folge von Zwischenwerten (t_1,t_2,t_3,\dots) gibt und Funktionen q_k:\R^{n+k-1}\to\R, die aber nur von ein oder zwei Variablen wirklich abhängen. Die Funktion wird ausgewertet, indem am Anfang (t_1,t_2,\dots,t_n)=(x_1,x_2,\dots,x_n) gesetzt wird und nacheinander


\begin{align}
t_{n+1}=&q_1(t_1,\dots,t_n)\\
t_{n+2}=&q_2(t_1,\dots,t_n,t_{n+1})\\
\dots&\\
t_{n+K}=&q_K(t_1,\dots,t_n,t_{n+1},\dots,t_{K-1})
\end{align}

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 (y_1,\dots,y_m)=(t_{K-m+1},\dots,t_K) zugeordnet.

AD beschreibt eine Menge von Verfahren, deren Ziel es ist, ein neues Programm zu erzeugen, das die Jacobimatrix von f, J=\tfrac{\partial f}{\partial x}\in \mathbb{R}^{m\times n} 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 (FM engl. Forward Mode)
  2. Rückwärtsmodus (BM engl. Backward Mode)

Vorwärtsmodus

Im Vorwärtsmodus berechnet man das Matrixprodukt

JS, ~S \in \mathbb{R}^{n \times p}

der Jacobi-Matrix mit einer beliebigen Matrix S (Seedmatrix), ohne vorher die Komponenten der Jacobi-Matrix zu bestimmen.

Beispiel 1

p=n \ \ \mbox{und}\ \  S=I_{n} \implies 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 Dv erzeugt, dessen i-te Komponente die Richtungsableitung entlang der i-ten unabhängigen Variablen enthält.

Beispiel 2

Berechne eine Funktion

 
\begin{align}
 & [ y_1 , y_2 , b ] = f\left(x_1, x_2, a\right) \left\{\right.\\
 & \quad b=x_1+x_2 \\
 & \quad y_1=a \cdot \sin(b) \\
 & \quad y_2=b \cdot y_1 \\
 & \left.\right\}
\end{align}
  

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

 [y_1, y_2, Dy_1, Dy_2, b ] = f_{AD}\left( x_1, x_2, Dx_1, Dx_2, a\right)

zum Ergebnis:

 \begin{align}
 & [y_1, y_2, Dy_1, Dy_2, b ] = f_{AD}\left( x_1, x_2, Dx_1, Dx_2, a\right) \left\{\right. \\
 & \quad b=x_1+x_2 \\
 & \quad Db=Dx_1+ Dx_2 \\
 & \quad y_1=a \cdot sin(b) \\
 & \quad Dy_1=a\cdot cos(b) \cdot Db \\
 & \quad y_2 = b \cdot y_1 \\
 & \quad Dy_2 = Db \cdot y_1 + b \cdot Dy_1 \\
 & \left.\right\}
\end{align}
  

Rückwärtsmodus

Der Rückwärtsmodus besteht aus zwei Phasen.

  1. Das Originalprogramm wird ausgeführt und gewisse Daten werden abgespeichert.
  2. 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 av eingeführt. Dieser Vektor enthält in der i-ten Komponente die i-te Richtungsableitung (in Richtung von v). Die Saatmatrix befindet sich in ay. Im Rückwärtsmodus erhält man als Ergebnis ein Produkt

SJ, S \in \R^{p\times m}

Beispiel 1

p=m \quad\text{und}\quad S=I_{m\times m} \implies AD berechnet J

Beispiel 2

Für jede Rechenvorschriftszeile s=g\left(u,v\right) werden die Ableitungen von u und v auf folgendem Wege von s ergänzt:

\begin{align}
a\_u & =a\_u+\frac{\partial g}{\partial u} a\_s \\
a\_v & =a\_v+\frac{\partial g}{\partial v} a\_s
\end{align}

Gesucht sind die x1- und x2-Ableitungen von y2. Diese werden jeweils als a_x1 und a_x2 bezeichnet. Der Wert a_y2 wird mit 1 initialisiert, alle anderen a\__{\ldots}-Werte werden mit 0 initialisiert.


\begin{align}
b      & =x_1+x_2 &      & (1)\\
y_1    & =a\cdot\sin(b)& & (2)\\
y_2    & =b\cdot y_1&    & (3)\\
\text{ aus (3) :}& \\
a\_b   & =a\_b+y_1\cdot a\_y_2 \\
a\_y_1 & =a\_y_1+b\cdot a\_y_2 \\
\text{ aus (2) :}&\\
a\_b   & =a\_b+a\cdot\cos(b)\cdot a\_y_1 \\
\text{ aus (1) :}& \\
a\_x_1 & =a\_x_1+1 \cdot a\_b \\
a\_x_2 & =a\_x_2+1 \cdot a\_b
\end{align}

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

Tf die Zeit f zu berechnen
Mf der Speicherbedarf dieser Rechnung
TJS die Zeit f und JS zu berechnen
MJS der Speicherbedarf dieser Rechnung
TSJ die Zeit f und SJ zu berechnen
MSJ der Speicherbedarf dieser Rechnung

Für die beiden vorgestellten Modi gilt

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

Die Berechnung als Kette von Berechnungen

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

  a\_u=a\_u+{\partial g\over \partial u} a\_s
  a\_v=a\_v+{\partial g\over \partial v} a\_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\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

  f=f\left( G \left( A \left( x \right) \right) \right) \rightarrow {\partial f \over \partial x} = {\partial f \over \partial G}{\partial G \over \partial A }{\partial A \over \partial x}

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:

  T_{{\partial f \over \partial G}\cdot S} \approx 17428 \cdot T_{f\left( G \right)}

im Rückwärtsmodus würde analog

  T_{S \cdot {\partial f \over \partial G}} \approx 17428 \cdot T_{f\left( G \right)}

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

  1. Wähle  I_{8x8} \in \mathbb{R}^{8x8} 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

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

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

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • A.D — AD steht für: Anno Domini, eine in christlichen Kalendern und früher sonst auch gebräuchliche Jahresnummerierung anstelle von n. Chr. bzw. n. u. Z. Acción Democrática, die sozialdemokratische Partei Venezuelas Action Directe, eine französische… …   Deutsch Wikipedia

  • A. D. — AD steht für: Anno Domini, eine in christlichen Kalendern und früher sonst auch gebräuchliche Jahresnummerierung anstelle von n. Chr. bzw. n. u. Z. Acción Democrática, die sozialdemokratische Partei Venezuelas Action Directe, eine französische… …   Deutsch Wikipedia

  • Ad — steht für: Anno Domini, eine in christlichen Kalendern und früher sonst auch gebräuchliche Jahresnummerierung anstelle von n. Chr. bzw. n. u. Z. Acción Democrática, die sozialdemokratische Partei Venezuelas Action Directe, eine französische… …   Deutsch Wikipedia

  • AD — steht für: Anno Domini, eine in christlichen Kalendern und früher sonst auch gebräuchliche Jahresnummerierung anstelle von n. Chr. bzw. n. u. Z. Acción Democrática, die sozialdemokratische Partei Venezuelas Action Directe, eine… …   Deutsch Wikipedia

  • Hostway — Corporation Rechtsform Corporation Gründung 1998 Sitz Chicago, USA Leitung Lucas Roh, CEO; John Lee, VP Marketing; Mitarbeiter …   Deutsch Wikipedia

  • Intervallarithmetik — bezeichnet in der Mathematik eine Methodik zur automatisierten Fehlerabschätzung auf Basis abgeschlossener Intervalle. Dabei werden nicht genau bekannte reelle Größen x betrachtet, die aber durch zwei Zahlen a und b eingegrenzt werden können.… …   Deutsch Wikipedia

  • Newton-Verfahren — Das Newton Verfahren, auch Newton Raphson Verfahren, (benannt nach Sir Isaac Newton 1669 und Joseph Raphson 1690) ist in der Mathematik ein Standardverfahren zur numerischen Lösung von nichtlinearen Gleichungen und Gleichungssystemen. Im Falle… …   Deutsch Wikipedia

  • Abkürzungen/Luftfahrt — Dies ist der erste Teil einer Liste der Abkürzungen und Akronyme, wie sie in der Luftfahrt und Militärluftfahrt verwendet werden. Liste der Abkürzungen Teil 1 A A (AA; AB; AC; AD; AE; AF; AG; AH; AI; AK; AL; AM; AN; AO; AP; AQ; AR …   Deutsch Wikipedia

  • Soziales Lernen — Der Begriff Soziales Lernen stammt aus der Lernpsychologie und wurde in etwas abgewandelter Bedeutung auch von der Sozialpädagogik und der Erziehungswissenschaft aufgegriffen. Auch die Soziale Arbeit beschäftigt sich mit dem Sozialen Lernen. Das… …   Deutsch Wikipedia

  • Denken: Wahrnehmen, Erinnern, Wollen und Handeln —   Theodor Elsenhans schrieb in dem 1912 erschienenen, damals repräsentativen »Lehrbuch der Psychologie« über das Denken: »Beim Denken beobachtet man erscheinungsmäßig immer wiederkehrende Bezüge. Man nennt den Inhalt eines Gedankens im jeweiligen …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”