Derivació automàtica

De Viquipèdia
Dreceres ràpides: navegació, cerca

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

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 vénen 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 dóna 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[modifica | modifica el codi]

La descomposició de les derivades que dóna 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[modifica | modifica el codi]

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 = 1 x_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[modifica | modifica el codi]

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 sevir en aprenentatge artificial) és una as particular de la derivació automàtica amb acumulació inversa.

Càlcul del jacobià[modifica | modifica el codi]

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 dóna un vector columna de la matriu jacobiana, o amb m passades d'acumulació inversa, cada una de les quals dóna un vector fila de la matriu jacobiana.

Més enllà de l'acumulació directa i inversa[modifica | modifica el codi]

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.[1] 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[modifica | modifica el codi]

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 + (x y' + 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_2x^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_1x'\varepsilon + 2p_2xx'\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 u v, 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\ne 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 , k u^{k-1} u' \rangle \quad (u \ne 0)
\left| \langle u,u'\rangle \right| = \langle \left| u \right| , u' \mbox{sign} u \rangle \quad (u \ne 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[modifica | modifica el codi]

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[modifica | modifica el codi]

L'aritmètica de més amunt es pot generalitzar de forma 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ó[modifica | modifica el codi]

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[modifica | modifica el codi]

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:

Sobrecàrrega d'operadors[modifica | modifica el codi]

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 per què 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:

Referències[modifica | modifica el codi]

  1. Naumann, Uwe (2008), Optimal Jacobian accumulation is NP-complete, Mathematical Programming 112 (2): 427-441

Literatura[modifica | modifica el codi]

  • 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[modifica | modifica el codi]