Derivació automàtica

En matemàtiques i en àlgebra computacional, la derivació automàtica, de vegades anomenada de forma alternativa derivació algorísmica, és un mètode d'avaluar numèricament la derivada d'una funció en un punt fent servir un programa d'ordinador. Els dos camins clàssics per resoldre la derivació d'una funció en un punt emprant programes d'ordinador són:

Figura 1: Relació entre la derivació automàtica i la derivació simbòlica

• amb algorismes de derivació simbòlica es troba l'expressió de la funció derivada i llavors s'avalua aquesta funció derivada en el punt en qüestió; o
• fer servir la derivació numèrica.

El principal inconvenient de la derivació simbòlica és que és lenta i també de vegades la dificultat d'obtenir una expressió matemàtica per a les funcions que venen definides per un programa d'ordinador. A més, moltes funcions esdevenen força complexes a mesura que es calculen derivades d'ordre superior.

Dos inconvenients importants de la derivació numèrica són l'error d'arrodoniment en la discretització i la cancel·lació catastròfica.

Els dos mètodes clàssics tenen problemes amb el càlcul de derivades d'ordre superior on la complexitat i els errors creixen.

La derivació automàtica soluciona tots els problemes esmentats.

La derivació automàtica explota el fet que qualsevol programa d'ordinador que implementi una funció vectorial y = F(x) (generalment) es pot descompondre en una successió d'assignacions elementals, cada una de les quals es pot derivar de forma trivial mirant la taula de derivades. Aquestes derivades de les parts elementals que componen la funció, avaluades per a un argument particular, es combinen d'acord amb la regla de la cadena per al càlcul de derivades per tal d'obtenir informació d'algun tipus de derivada de F (com ara el gradient, la tangent, la matriu jacobiana, etc.). Aquest procés dona derivades exactes (dins de l'exactitud numèrica). Com que la transformació simbòlica només es dona al nivell més bàsic, la derivació automàtica evita els problemes computacionals inherents a la complexitat del càlcul simbòlic.

La regla de la cadena, acumulació vers davant i vers darrere

La descomposició de les derivades que dona la regla de la cadena és fonamental per a la derivació automàtica. En el cas de la composició simple de funcions $f(x)=g(h(x))$ la regla de la cadena diu:

${\frac {df}{dx}}={\frac {dg}{dh}}{\frac {dh}{dx}}$

La derivació automàtica normalment es presenta de dues formes diferents, acumulació directa (o marxa directa) i acumulació inversa (o marxa inversa). Es desaconsella fer servir l'expressió marxa enrere). L'acumulació directa especifica que es ressegueixi la regla de la cadena de la dreta cap a l'esquerra, és a dir, primer es calcula $dh/dx$ i després $dg/dh$,i l'acumulació inversa de l'esquerra cap a la dreta.

Figura 2: Exemple d'acumulació directa amb un graf computacional

Acumulació directa

L'acumulació directa en derivació automàtica és la més fàcil d'entendre i d'implementar. La funció $f(x_{1},x_{2})=x_{1}x_{2}+\sin(x_{1})$ s'interpreta per l'ordinador (o el programador humà) com la successió d'operacions elementals en les variables de treball $w_{i}$, les eines de derivació automàtica amb acumulació directa afegeixen les operacions corresponents del segon component de l'aritmètica augmentada.

Expressions del codi original	Expressions afegides per a les derivades
$w_{1}=x_{1}$	$w'_{1}=1$ (llavor)
$w_{2}=x_{2}$	$w'_{2}=0$ (llavor)
$w_{3}=w_{1}w_{2}$	$w'_{3}=w'_{1}w_{2}+w_{1}w'_{2}=1x_{2}+x_{1}0=x_{2}$
$w_{4}=\sin(w_{1})$	$w'_{4}=\cos(w_{1})w'_{1}=\cos(x_{1})1$
$w_{5}=w_{3}+w_{4}$	$w'_{5}=w'_{3}+w'_{4}=x_{2}+\cos(x_{1})$

Per a calcular la derivada de $f(x_{1},x_{2})=x_{1}x_{2}+\sin(x_{1})$ cal definir una llavor de forma que es distingeixi entre derivar respecte de $x_{1}$ o $x_{2}$. La taula de més amunt esta bleix la llavor del càlcul en $w'_{1}=1$ i $w'_{2}=0$ i es pot veure que això fa que el resultat del càlcul sigui $x_{2}+\cos(x_{1})$ que és la derivada respecte de $x_{1}$. Fixeu-vos que, tot i que a la taula es presenta la derivada simbòlica, al ordinador sempre s'avalua l'expressió i el que s'emmagatzema a la memòria és sempre el seu valor numèric. La Figura 2 representa les expressions anteriors en un graf computacional.

Per tal de calcular el gradient en aquesta funció d'exemple, és a dir $\partial f/\partial x_{1}$ i $\partial f/\partial x_{2}$, calen dos passades pel graf computacional, primer amb les llavors $w'_{1}=1$ i $w'_{2}=0$, i llavors amb $w'_{1}=0$ i $w'_{2}=1$.

La complexitat computacional d'una passada d'acumulació directa és proporcional a la complexitat de l'expressió original de la funció a derivar.

L'acumulació directa és millor que l'acumulació inversa pel cas de funcions $f:\mathbb {R} \rightarrow \mathbb {R} ^{m}$ with $m\gg 1$ perquè només es necessita una passada, en comparació amb $m$ passades per a l'acumulació inversa.

Figura 3: Exemple d'acumulació inversa amb el seu graf computacional

Acumulació inversa

L'acumulació inversa ressegueix la regla de la cadena de l'esquerra cap a la dreta, o en el cas del graf computacional de la Figura 3, de dalt cap a baix. La funció de l'exemple és una funció real, i per tant només hi ha una llavor per al càlcul de la derivada, i només cal una passada per tal de calcular els dos components del gradient. Això és la meitat del treball comparat amb l'acumulació directa, però l'acumulació inversa necessita emmagatzemar algunes de les variables de treball $w_{i}$, això pot representar una qüestió significativa pel que fa a l'ús de memòria.

El graf del flux de dades d'un càlcul es pot manipular per tal de calcular el gradient del seu càlcul original. Això es fa afegint un node adjunt a cada node primari, aquest node adjunt es connecta amb branques adjuntes, paral·leles a les branques principals però que flueixen en direcció oposada. Els nodes del graf adjunt representen la multiplicació per les derivades de les funcions calculades pels nodes del graf primari. Per exemple, una suma en el graf primari causa un repartiment en l'adjunt; un repartiment en el graf primari causa una suma en l'adjunt; una funció unària $y=f(x)$ en el primari causa $x'=f'(x)y'$ en l'adjunt; etc.

L'acumulació inversa és millor que l'acumulació directa per a funcions $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ amb $n\gg 1$.

La retropropagació d'errors en perceptrons multicapa (una tècnica que es fa servir en aprenentatge artificial) és una as particular de la derivació automàtica amb acumulació inversa.

Càlcul del jacobià

La matriu jacobiana $J$ of $f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}$ és una matriu $m\times n$. Es pot calcular fent servir $n$ passades en acumulació directa, cada passada de les quals dona un vector columna de la matriu jacobiana, o amb $m$ passades d'acumulació inversa, cada una de les quals dona un vector fila de la matriu jacobiana.

Més enllà de l'acumulació directa i inversa

Les acumulacions directa i inversa són només formes (extremes) de resseguir la regla de la cadena. El problema de calcular la matriu jacobiana de $F:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}$ amb el nombre mínim d'operacions, es coneix com el problema de l'"acumulació òptima del jacobià" (AOJ). AOJ és NP-complet. Una idea centrad d'aquesta demostració és que poden existir dependències algebraiques entre les derivades parcials locals que etiqueten les arestes del graf. En particular, dues o més arestes del graf posen resultar iguals. La complexitat del problema és encara una qüestió oberta si se suposa que les etiquetes de totes les arestes són úniques i algebraicament independents.

Deducció de l'aritmètica augmentada per a la derivació automàtica amb acumulació directa fent servir nombres duals

La derivació automàtica en mode directe es realitza augmentant l'àlgebra dels nombres reals amb el que s'obté una nova aritmètica. S'afegeix un component addicional a cada nombre que representarà la derivada d'una funció en el nombre, i totes les operacions aritmètiques s'estenen a aquesta àlgebra augmentada. L'àlgebra augmentada és l'àlgebra dels nombres duals.

Se substitueix cada nombre $\,x$ pel nombre $x+x'\varepsilon$, on $x'$ és un nombre real, però $\varepsilon$ no és res més que un símbol amb la propietat $\varepsilon ^{2}=0$. Només fent servir això s'obté per a les operacions habituals d'aritmètica

$(x+x'\varepsilon )+(y+y'\varepsilon )=x+y+(x'+y')\varepsilon$

$(x+x'\varepsilon )\cdot (y+y'\varepsilon )=xy+xy'\varepsilon +yx'\varepsilon +x'y'\varepsilon ^{2}=xy+(xy'+yx')\varepsilon$

I de forma similar per a la resta i la divisió.

Ara, es poden calcular polinomis en aquesta aritmètica augmentada. Si $P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}$, llavors

$P(x+x'\varepsilon )$	$=\,$	$p_{0}+p_{1}(x+x'\varepsilon )+\cdots +p_{n}(x+x'\varepsilon )^{n}$
	$=\,$	$p_{0}+p_{1}x+\cdots +p_{n}x^{n}$
		$\,{}+p_{1}x'\varepsilon +2p_{2}xx'\varepsilon +\cdots +np_{n}x^{n-1}x'\varepsilon$
	$=\,$	$P(x)+P^{(1)}(x)x'\varepsilon$

on $P^{(1)}$ denota la derivada de $P$ respecte del seu primer argument, i $x'$, anomenada una llavor, es pot triar arbitràriament.

Els elements de la nova aritmètica són parelles ordenades que s'escriuen $\langle x,x'\rangle$, sobre els primers components s'aplica l'aritmètica ordinària, i sobre els segons l'aritmètica de les derivades de primer ordre, tal com s'ha descrit més amunt. Estenent els resultats anteriors dels polinomis a les funciona analítiques s'obté una llista de les funcions aritmètiques bàsiques i algunes funcions estàndard per a la nova aritmètica:

$\langle u,u'\rangle +\langle v,v'\rangle =\langle u+v,u'+v'\rangle$

$\langle u,u'\rangle -\langle v,v'\rangle =\langle u-v,u'-v'\rangle$

$\langle u,u'\rangle *\langle v,v'\rangle =\langle uv,u'v+uv'\rangle$

$\langle u,u'\rangle /\langle v,v'\rangle =\left\langle {\frac {u}{v}},{\frac {u'v-uv'}{v^{2}}}\right\rangle \quad (v\neq 0)$

$\sin \langle u,u'\rangle =\langle \sin(u),u'\cos(u)\rangle$

$\cos \langle u,u'\rangle =\langle \cos(u),-u'\sin(u)\rangle$

$\exp \langle u,u'\rangle =\langle \exp u,u'\exp u\rangle$

$\log \langle u,u'\rangle =\langle \log(u),u'/u\rangle \quad (u>0)$

$\langle u,u'\rangle ^{k}=\langle u^{k},ku^{k-1}u'\rangle \quad (u\neq 0)$

$\left|\langle u,u'\rangle \right|=\langle \left|u\right|,u'{\mbox{sign}}u\rangle \quad (u\neq 0)$

I en general, per a la funció primitiva $g$,

$g(\langle u,u'\rangle ,\langle v,v'\rangle )=\langle g(u,v),g^{(1)}(u,v)u'+g^{(2)}(u,v)v'\rangle$

on $g^{(1)}$ i $g^{(2)}$ són les derivades de $g$ respecte dels seus primer i segon arguments respectivament.

Quan s'aplica una operació binària bàsica a arguments barrejats — el parell $\langle u,u'\rangle$ i el nombre real $c$ — primer s'estén el nombre real a $\langle c,0\rangle$. Llavors es troba la derivada d'una funció $f:\mathbb {R} \rightarrow \mathbb {R}$ al punt $x_{0}$ calculant $f(\langle x_{0},1\rangle )$ fent servir la aritmètica anterior, això dona com a resultat $\langle f(x_{0}),f'(x_{0})\rangle$.

Arguments vectorials i funcions

Les funcions de diverses variables es poden manipular amb la mateixa eficiència i els mateixos mecanismes que les funcions d'una variable emprant un operador de derivada direccional, el qual troba la derivada direccional $y'\in \mathbb {R} ^{m}$ of $f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}$ a $x\in \mathbb {R} ^{n}$ en la direcció $x'\in \mathbb {R} ^{n}$ calculant $(\langle y_{1},y'_{1}\rangle ,\ldots ,\langle y_{m},y'_{m}\rangle )=f(\langle x_{1},x'_{1}\rangle ,\ldots ,\langle x_{n},x'_{n}\rangle )$ fent servir la mateixa aritmètica que més amunt.

Derivades d'ordre superior

L'aritmètica de més amunt es pot generalitzar de manera natural a derivades segones i a derivades d'ordre superior. Però, les regles de l'aritmètica creixen ràpid i es fan molt complicades, la complexitat serà quadràtica en els graus més alts de derivació. En comptes d'això, es fa servir aritmètica de sèries de Taylor truncades. Això és possible perquè els sumands de la sèrie de Taylor d'una funció són productes de coeficients coneguts i de les derivades de la funció. El càlcul de la matriu Hessiana fent servir derivació automàtica s'ha demostrat útil en alguns contextos d'optimització.

Implementació

La implementació del mode directe de la derivació automàtica es fa amb una interpretació no estàndard del programa en la que els nombres reals se substitueixen per nombres duals, per operar en nombres duals, les constants s'estenen a nombres duals amb un coeficient epsilon igual a zero. Aquesta interpretació no estàndard en general s'implementa fent servir una de les següents dues estratègies: transformació del codi font o sobrecàrrega d'operadors.

Transformació del codi font

Figura 4: Exemple de com podria funcionar la transformació del codi font

El codi font de cada funció se substitueix per un codi font generat automàticament que inclou instruccions per al càlcul de les derivades intercalades amb les instruccions originals.

La transformació del codi fon es pot implementar per a tots els llenguatges de programació, i també és fàcil que el compilador pugui fer optimitzacions en el moment de la compilació. Però, la implementació de l'eina mateixa de derivació automàtica és més difícil.

Exemples:

• ADIC (C/C++, mode directe)
• ADIFOR Arxivat 2008-07-02 a Wayback Machine. (Fortran77)
• OpenAD (Fortran77, Fortran95, C/C++)
• TAPENADE (Fortran77, Fortran95)

Sobrecàrrega d'operadors

Figura 5: Exemple de com podria treballar la sobrecàrrega d'operadors

La sobrecàrrega d'operadors només és possible en un codi font si està escrit en un llenguatge que el suporta. Els objectes que representen els nombres reals i les operacions matemàtiques elementals s'han de sobrecarregar perquè suportin l'aritmètica augmentada que s'ha descrit més amunt. Això fa que no calgui cap canvi en el codi font de la funció original perquè es pugui fer el càlcul de la derivada.

La sobrecàrrega d'operadors per l'acumulació directa és fàcil d'implementar i també és possible per a l'acumulació inversa. Però, els compiladors actuals es queden enrere en optimitzar el codi si es compara amb l'acumulació directa.

Exemples:

• ADC Version 4.0 Arxivat 2008-05-09 a Wayback Machine. (C/C++)
• ADF Version 4.0 Arxivat 2008-05-09 a Wayback Machine. (Fortran 77, Fortran 95)
• ADOL-C Arxivat 2009-03-12 a Wayback Machine. (C/C++)
• FADBAD++ (C/C++)
• CppAD (C/C++)
• MAD (Matlab)
• Sacado (Part of the Trilinos Arxivat 2008-05-14 a Wayback Machine. collection) (C++, forward/reverse)

Bibliografia

• Rall, Louis B. Automatic Differentiation: Techniques and Applications. 120. Springer, 1981 (Lecture Notes in Computer Science). ISBN 0-540-10861-0. 
• Griewank, Andreas. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. 19. SIAM, 2000 (Frontiers in Applied Mathematics). ISBN 0-89871-451-6. 

Enllaços externs

• www.autodiff.org, Un "lloc d'introducció a tot allò que vulgueu saber sobre la derivació automàtica"
• Compute analytic derivatives of any Fortran77 or Fortran95 through a web-based interface Derivadció automàtica de programes Fortran