Diferenciación automática

En matemáticas y álgebra computacional , la diferenciación automática ( autodiferenciación , autodiff o AD ), también llamada diferenciación algorítmica , diferenciación computacional , ^[1]^[2] es un conjunto de técnicas para evaluar la derivada parcial de una función especificada por un programa de computadora.

La diferenciación automática aprovecha el hecho de que cada cálculo informático, por complicado que sea, ejecuta una secuencia de operaciones aritméticas elementales (suma, resta, multiplicación, división, etc.) y funciones elementales ( exp , log , sen , cos , etc.). Al aplicar la regla de la cadena repetidamente a estas operaciones, se pueden calcular derivadas parciales de orden arbitrario de forma automática, con precisión de trabajo y utilizando como máximo un pequeño factor constante de más operaciones aritméticas que el programa original.

Diferencia con otros métodos de diferenciación

Figura 1: Cómo se relaciona la diferenciación automática con la diferenciación simbólica

La diferenciación automática es distinta de la diferenciación simbólica y la diferenciación numérica . La diferenciación simbólica enfrenta la dificultad de convertir un programa de computadora en una sola expresión matemática y puede conducir a un código ineficiente. La diferenciación numérica (el método de diferencias finitas) puede introducir errores de redondeo en el proceso de discretización y cancelación. Ambos métodos clásicos tienen problemas con el cálculo de derivadas superiores, donde la complejidad y los errores aumentan. Finalmente, ambos métodos clásicos son lentos al calcular derivadas parciales de una función con respecto a muchas entradas, como es necesario para los algoritmos de optimización basados en gradientes . La diferenciación automática resuelve todos estos problemas.

Aplicaciones

La diferenciación automática es particularmente importante en el campo del aprendizaje automático . Por ejemplo, permite implementar la retropropagación en una red neuronal sin una derivada calculada manualmente.

Acumulación hacia adelante y hacia atrás

Regla de la cadena de derivadas parciales de funciones compuestas

Fundamental para la diferenciación automática es la descomposición de las diferenciales proporcionada por la regla de la cadena de derivadas parciales de funciones compuestas . Para la composición simple, la regla de la cadena da ${\begin{aligned}y&=f(g(h(x)))=f(g(h(w_{0})))=f(g(w_{1}))=f(w_{2})=w_{3}\\w_{0}&=x\\w_{1}&=h(w_{0})\\w_{2}&=g(w_{1})\\w_{3}&=f(w_{2})=y\end{aligned}}$ ${\frac {\parcial y}{\parcial x}}={\frac {\parcial y}{\parcial w_{2}}}{\frac {\parcial w_{2}}{\parcial w_{1}}}{\frac {\parcial w_{1}}{\parcial x}}={\frac {\parcial f(w_{2})}{\parcial w_{2}}}{\frac {\parcial g(w_{1})}{\parcial w_{1}}}{\frac {\parcial h(w_{0})}{\parcial x}}$

Dos tipos de diferenciación automática

Generalmente se presentan dos modos distintos de diferenciación automática.

acumulación hacia adelante (también llamada de abajo hacia arriba , modo hacia adelante o modo tangente )
acumulación inversa (también llamada de arriba hacia abajo , modo inverso o modo adjunto )

La acumulación hacia adelante especifica que uno recorre la regla de la cadena desde adentro hacia afuera (es decir, primero computar y luego y por último ), mientras que la acumulación inversa tiene el recorrido desde afuera hacia adentro (primero computar y luego y por último ). Más sucintamente, $\parcial w_{1}/\parcial x$ $\partial w_{2}/\partial w_{1}$ $\parcial y/\parcial w_{2}$ $\parcial y/\parcial w_{2}$ $\partial w_{2}/\partial w_{1}$ $\parcial w_{1}/\parcial x$

La acumulación hacia adelante calcula la relación recursiva: con , y, ${\frac {\parcial w_{i}}{\parcial x}}={\frac {\parcial w_{i}}{\parcial w_{i-1}}}{\frac {\parcial w_{i-1}}{\parcial x}}$ $w_{3}=y$
La acumulación inversa calcula la relación recursiva: con . ${\frac {\parcial y}{\parcial w_{i}}}={\frac {\parcial y}{\parcial w_{i+1}}}{\frac {\parcial w_{i+1}}{\parcial w_{i}}}$ $estilo de visualización w_{0}=x$

El valor de la derivada parcial, llamada semilla , se propaga hacia adelante o hacia atrás y es inicialmente o . La acumulación hacia adelante evalúa la función y calcula la derivada con respecto a una variable independiente en una pasada. Por lo tanto, para cada variable independiente es necesario un paso separado en el que la derivada con respecto a esa variable independiente se establece en uno ( ) y la de todas las demás en cero ( ). Por el contrario, la acumulación inversa requiere las funciones parciales evaluadas para las derivadas parciales. Por lo tanto, la acumulación inversa evalúa primero la función y calcula las derivadas con respecto a todas las variables independientes en un paso adicional. ${\frac {\parcial x}{\parcial x}}=1$ ${\frac {\y parcial}{\y parcial}}=1$ $x_{1},x_{2},\puntos ,x_{n}$ ${\frac {\parcial x_{1}}{\parcial x_{1}}}=1$ ${\frac {\partial x_{2}}{\partial x_{1}}}=\dots ={\frac {\partial x_{n}}{\partial x_{1}}}=0$

Cuál de estos dos tipos se debe utilizar depende del número de barridos. La complejidad computacional de un barrido es proporcional a la complejidad del código original.

La acumulación hacia adelante es más eficiente que la acumulación inversa para funciones $f : R n \to R m$ con $n ≪ m$ ya que solo son necesarios $n barridos, en comparación con$ $m$ barridos para la acumulación inversa.
La acumulación inversa es más eficiente que la acumulación directa para funciones $f : R n \to R m$ con $n ≫ m$ ya que solo son necesarios $m barridos, en comparación con$ $n$ barridos para la acumulación directa.

La retropropagación de errores en perceptrones multicapa, una técnica utilizada en el aprendizaje automático , es un caso especial de acumulación inversa. ^[2]

La acumulación hacia adelante fue introducida por RE Wengert en 1964. ^[3] Según Andreas Griewank, la acumulación inversa se ha sugerido desde finales de la década de 1960, pero se desconoce quién la inventó. ^[4] Seppo Linnainmaa publicó la acumulación inversa en 1976. ^[5]

Acumulación hacia adelante

En la AD de acumulación hacia adelante, primero se fija la variable independiente con respecto a la cual se realiza la diferenciación y se calcula la derivada de cada subexpresión de manera recursiva. En un cálculo con lápiz y papel, esto implica sustituir repetidamente la derivada de las funciones internas en la regla de la cadena: Esto se puede generalizar a múltiples variables como un producto matricial de jacobianos . ${\begin{aligned}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{n-1}}}{\frac {\partial w_{n-1}}{\partial x}}\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}{\frac {\partial w_{n-2}}{\partial x}}\right)\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}\left({\frac {\partial w_{n-2}}{\partial w_{n-3}}}{\frac {\partial w_{n-3}}{\partial x}}\right)\right)\\[6pt]&=\cdots \end{aligned}}$

En comparación con la acumulación inversa, la acumulación hacia adelante es natural y fácil de implementar, ya que el flujo de información de las derivadas coincide con el orden de evaluación. Cada variable se complementa con su derivada (almacenada como un valor numérico, no como una expresión simbólica), como se indica con el punto. Las derivadas se calculan luego en sincronía con los pasos de evaluación y se combinan con otras derivadas mediante la regla de la cadena. $w_{i}$ ${\dot {w}}_{i}$ ${\dot {w}}_{i}={\frac {\partial w_{i}}{\partial x}}$

Usando la regla de la cadena, si tiene predecesores en el gráfico computacional: $w_{i}$

{\dot {w}}_{i}=\sum _{j\in \{{\text{predecessors of i}}\}}{\frac {\partial w_{i}}{\partial w_{j}}}{\dot {w}}_{j}

Figura 2: Ejemplo de acumulación hacia adelante con gráfico computacional

A modo de ejemplo, considere la función: Para mayor claridad, las subexpresiones individuales se han etiquetado con las variables . ${\begin{aligned}y&=f(x_{1},x_{2})\\&=x_{1}x_{2}+\sin x_{1}\\&=w_{1}w_{2}+\sin w_{1}\\&=w_{3}+w_{4}\\&=w_{5}\end{aligned}}$ $w_{i}$

La elección de la variable independiente a la que se realiza la diferenciación afecta los valores semilla $ẇ 1$ y $ẇ 2$ . Dado el interés en la derivada de esta función con respecto a $x 1$ , los valores semilla deben establecerse en: ${\begin{aligned}{\dot {w}}_{1}={\frac {\partial w_{1}}{\partial x_{1}}}={\frac {\partial x_{1}}{\partial x_{1}}}=1\\{\dot {w}}_{2}={\frac {\partial w_{2}}{\partial x_{1}}}={\frac {\partial x_{2}}{\partial x_{1}}}=0\end{aligned}}$

Una vez establecidos los valores iniciales, los valores se propagan utilizando la regla de la cadena, como se muestra. La figura 2 muestra una representación gráfica de este proceso como un gráfico computacional.

Para calcular el gradiente de esta función de ejemplo, que requiere no solo sino también , se realiza un barrido adicional sobre el gráfico computacional utilizando los valores semilla . ${\tfrac {\partial y}{\partial x_{1}}}$ ${\tfrac {\partial y}{\partial x_{2}}}$ ${\dot {w}}_{1}=0;{\dot {w}}_{2}=1$

Implementación

Pseudocódigo

La acumulación hacia adelante calcula la función y la derivada (pero solo para una variable independiente cada una) en una sola pasada. La llamada al método asociado espera que la expresión Z se derive con respecto a una variable V. El método devuelve un par de la función evaluada y su derivada. El método recorre el árbol de expresiones recursivamente hasta que se alcanza una variable. Si se solicita la derivada con respecto a esta variable, su derivada es 1, 0 en caso contrario. Luego se evalúan la función parcial así como la derivada parcial. ^[6]

tupla < float , float > evaluarYDerivar ( Expresión Z , Variable V ) { if isVariable ( Z ) if ( Z = V ) return { valueOf ( Z ), 1 }; else return { valueOf ( Z ), 0 }; else if ( Z = A + B ) { a , a ' } = evaluarYDerivar ( A , V ); { b , b ' } = evaluarYDerivar ( B , V ); return { a + b , a ' + b ' }; else if ( Z = A - B ) { a , a ' } = evaluarYDerivar ( A , V ); { b , b ' } = evaluarYDerivar ( B , V ); return { a - b , a ' - b ' }; else if ( Z = A * B ) { a , a ' } = evaluarYDerivar ( A , V ); { b , b ' } = evaluarYDeriva ( B , V ); devolver { a * b , b * a ' + a * b ' }; }

C++

#include <iostream> struct ValueAndPartial { float valor , parcial ; }; struct Variable ; struct Expresión { virtual ValueAndPartial evaluarAndDerive ( Variable * variable ) = 0 ; }; struct Variable : pública Expresión { float valor ; Variable ( float valor ) : valor ( valor ) {} ValueAndPartial evaluarAndDerive ( Variable * variable ) { float parcial = ( this == variable ) ? 1.0f : 0.0f ; return { valor , parcial }; } }; struct Plus : pública Expresión { Expresión * a , * b ; Plus ( Expresión * a , Expresión * b ) : a ( a ), b ( b ) {} ValueAndPartial evaluarAndDerive ( Variable * variable ) { auto [ valorA , parcialA ] = a -> evaluarAndDerive ( variable ); auto [ valorB , parcialB ] = b -> evaluarYDeriva ( variable ); return { valorA + valorB , parcialA + parcialB }; } }; struct Multiplicar : public Expresión { Expresión * a , * b ; Multiplicar ( Expresión * a ,                                                                                          Expresión * b ) : a ( a ), b ( b ) {} ValorYPartial evaluarYDeriva ( Variable * variable ) { auto [ valorA , parcialA ] = a -> evaluarYDeriva ( variable ); auto [ valorB , parcialB ] = b -> evaluarYDeriva ( variable ); return { valorA * valorB , valorB * parcialA + valorA * parcialB }; } }; int main () { // Ejemplo: Encontrar los parciales de z = x * (x + y) + y * y en (x, y) = (2, 3) Variable x ( 2 ), y ( 3 ); Más p1 ( & x , & y ) ; Multiplica m1 ( & x , & p1 ); Multiplica m2 ( & y , & y ) ; Más z ( & m1 , & m2 ); float xPartial = z .evaluarYDeriva ( & x ) .parcial ; float yPartial = z .evaluarAndDerive ( & y ) .parcial ; std :: cout << "∂z/∂x = " << xPartial << ", " << "∂z/∂y = " << yPartial << std:: endl ; // Salida : ∂z / ∂x = 7 , ∂z / ∂y = 8 return 0 ; }

Acumulación inversa

En la AD de acumulación inversa, la variable dependiente que se va a diferenciar es fija y la derivada se calcula con respecto a cada subexpresión de forma recursiva. En un cálculo con lápiz y papel, la derivada de las funciones externas se sustituye repetidamente en la regla de la cadena: ${\begin{aligned}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x}}\\&=\left({\frac {\partial y}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac {\partial w_{1}}{\partial x}}\\&=\left(\left({\frac {\partial y}{\partial w_{3}}}{\frac {\partial w_{3}}{\partial w_{2}}}\right){\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac {\partial w_{1}}{\partial x}}\\&=\cdots \end{aligned}}$

En la acumulación inversa, la cantidad de interés es el adjunto , denotado con una barra ; es una derivada de una variable dependiente elegida con respecto a una subexpresión : ${\bar {w}}_{i}$ $w_{i}$ ${\bar {w}}_{i}={\frac {\partial y}{\partial w_{i}}}$

Usando la regla de la cadena, si tiene sucesores en el gráfico computacional: $w_{i}$

{\bar {w}}_{i}=\sum _{j\in \{{\text{successors of i}}\}}{\bar {w}}_{j}{\frac {\partial w_{j}}{\partial w_{i}}}

La acumulación inversa recorre la regla de la cadena desde el exterior hacia el interior o, en el caso del gráfico computacional de la Figura 3, desde arriba hacia abajo. La función de ejemplo tiene un valor escalar y, por lo tanto, solo hay una semilla para el cálculo de la derivada y solo se necesita un barrido del gráfico computacional para calcular el gradiente (de dos componentes). Esto es solo la mitad del trabajo en comparación con la acumulación hacia adelante, pero la acumulación inversa requiere el almacenamiento de las variables intermedias $w i,$ así como las instrucciones que las produjeron en una estructura de datos conocida como "cinta" o lista de Wengert ^[7] (sin embargo, Wengert publicó la acumulación hacia adelante, no la acumulación inversa ^[3] ), que puede consumir una memoria significativa si el gráfico computacional es grande. Esto se puede mitigar hasta cierto punto almacenando solo un subconjunto de las variables intermedias y luego reconstruyendo las variables de trabajo necesarias repitiendo las evaluaciones, una técnica conocida como rematerialización . Los puntos de control también se utilizan para guardar estados intermedios.

Figura 3: Ejemplo de acumulación inversa con gráfico computacional

Las operaciones para calcular la derivada mediante acumulación inversa se muestran en la siguiente tabla (observe el orden inverso):

Operaciones para calcular la derivada: ${\bar {w}}_{5}=1{\text{ (seed)}}$; ${\bar {w}}_{4}={\bar {w}}_{5}\cdot 1$; ${\bar {w}}_{3}={\bar {w}}_{5}\cdot 1$; ${\bar {w}}_{2}={\bar {w}}_{3}\cdot w_{1}$; ${\bar {w}}_{1}={\bar {w}}_{3}\cdot w_{2}+{\bar {w}}_{4}\cdot \cos w_{1}$

El gráfico de flujo de datos de un cálculo se puede manipular para calcular el gradiente de su cálculo original. Esto se hace añadiendo un nodo adjunto para cada nodo primario, conectado por aristas adjuntas que son paralelas a las aristas primarias pero fluyen en la dirección opuesta. Los nodos en el gráfico adjunto representan la multiplicación por las derivadas de las funciones calculadas por los nodos en el primario. Por ejemplo, la adición en el primario causa un abanico de salida en el adjunto; el abanico de salida en el primario causa una adición en el adjunto; ^[a] una función unaria $y = f (x)$ en el primario causa $x̄ = ȳ f'(x)$ en el adjunto; etc.

Implementación

Pseudocódigo

La acumulación inversa requiere dos pasadas: en la pasada hacia adelante, primero se evalúa la función y se almacenan en caché los resultados parciales. En la pasada inversa, se calculan las derivadas parciales y se retropropaga el valor derivado previamente. La llamada al método correspondiente espera que se derive la expresión Z y se genere como semilla el valor derivado de la expresión principal. Para la expresión superior, Z derivada con respecto a Z, este es 1. El método recorre el árbol de expresiones de forma recursiva hasta que se alcanza una variable y agrega el valor semilla actual a la expresión derivada. ^[8]^[9]

void derive ( Expresión Z , float semilla ) { if isVariable ( Z ) derivadaPartialDe ( Z ) += semilla ; else if ( Z = A + B ) derive ( A , semilla ); derive ( B , semilla ); else if ( Z = A - B ) derive ( A , semilla ); derive ( B , - semilla ); else if ( Z = A * B ) derive ( A , valorDe ( B ) * semilla ); derive ( B , valorDe ( A ) * semilla ); }

C++

#include <iostream> struct Expresión { float valor ; virtual void evaluar () = 0 ; virtual void derivar ( float semilla ) = 0 ; }; struct Variable : pública Expresión { float parcial ; Variable ( float valor ) { this -> valor = valor ; parcial = 0.0f ; } void evaluar () {} void derivar ( float semilla ) { parcial += semilla ; } }; struct Más : pública Expresión { Expresión * a , * b ; Más ( Expresión * a , Expresión * b ) : a ( a ), b ( b ) {} void evaluar () { a -> evaluar (); b -> evaluar (); valor = a -> valor + b -> valor ; } void derivar ( float semilla ) { a -> derivar ( semilla ); b -> derivar ( semilla ); } }; struct Multiplicar : pública Expresión { Expresión * a , * b ; Multiplicar ( Expresión * a , Expresión * b ) : a ( a ), b ( b ) {} void evaluar () { a ->                                                                                             evaluar (); b -> evaluar (); valor = a -> valor * b -> valor ; } void derive ( float seed ) { a -> derive ( b -> valor * semilla ); b -> derive ( a -> valor * semilla ); } }; int main () { // Ejemplo: Encontrar los parciales de z = x * (x + y) + y * y en (x, y) = (2, 3) Variable x ( 2 ), y ( 3 ); Más p1 ( & x , & y ); Multiplica m1 ( & x , & p1 ); Multiplica m2 ( & y , & y ); Más z ( & m1 , & m2 ); z . evaluar (); std :: cout << "z = " << z . valor << std :: endl ; // Salida: z = 19 z . derivar ( 1 ); std :: cout << "∂z/∂x = " << x . parcial << ", " << "∂z/∂y = " << y . parcial << std :: endl ; // Salida: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }

Más allá de la acumulación hacia adelante y hacia atrás

La acumulación hacia adelante y hacia atrás son sólo dos formas (extremas) de recorrer la regla de la cadena. El problema de calcular un jacobiano completo de $f : R n \to R m$ con un número mínimo de operaciones aritméticas se conoce como el problema de acumulación jacobiana óptima (OJA), que es NP-completo . ^[10] Central para esta prueba es la idea de que pueden existir dependencias algebraicas entre los parciales locales que etiquetan los bordes del grafo. En particular, dos o más etiquetas de borde pueden reconocerse como iguales. La complejidad del problema aún está abierta si se supone que todas las etiquetas de borde son únicas y algebraicamente independientes.

Diferenciación automática utilizando números duales

La diferenciación automática en modo directo se logra aumentando el álgebra de números reales y obteniendo una nueva aritmética . Se agrega un componente adicional a cada número para representar la derivada de una función en el número, y todos los operadores aritméticos se extienden para el álgebra aumentada. El álgebra aumentada es el álgebra de números duales .

Reemplace cada número con el número , donde es un número real, pero es un número abstracto con la propiedad (un infinitesimal ; consulte Análisis infinitesimal suavizado ). Usando solo esto, la aritmética regular da como resultado . $\,x$ $x+x'\varepsilon$ $x'$ $\varepsilon$ $\varepsilon ^{2}=0$ ${\begin{aligned}(x+x'\varepsilon )+(y+y'\varepsilon )&=x+y+(x'+y')\varepsilon \\(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 \\(x+x'\varepsilon )/(y+y'\varepsilon )&=(x/y+x'\varepsilon /y)/(1+y'\varepsilon /y)=(x/y+x'\varepsilon /y)\cdot (1-y'\varepsilon /y)=x/y+(x'/y-xy'/y^{2})\varepsilon \end{aligned}}$ $(1+y'\varepsilon /y)\cdot (1-y'\varepsilon /y)=1$

Ahora, los polinomios se pueden calcular en esta aritmética aumentada. Si , entonces donde denota la derivada de con respecto a su primer argumento, y , llamada semilla , se puede elegir arbitrariamente. $P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}$ ${\begin{aligned}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 \end{aligned}}$ $P^{(1)}$ $P$ $x'$

La nueva aritmética consta de pares ordenados , elementos escritos , con aritmética ordinaria en el primer componente y aritmética de diferenciación de primer orden en el segundo componente, como se describió anteriormente. Extender los resultados anteriores sobre polinomios a funciones analíticas da una lista de la aritmética básica y algunas funciones estándar para la nueva aritmética: y en general para la función primitiva , donde y son las derivadas de con respecto a sus primer y segundo argumentos, respectivamente. $\langle x,x'\rangle$ ${\begin{aligned}\left\langle u,u'\right\rangle +\left\langle v,v'\right\rangle &=\left\langle u+v,u'+v'\right\rangle \\\left\langle u,u'\right\rangle -\left\langle v,v'\right\rangle &=\left\langle u-v,u'-v'\right\rangle \\\left\langle u,u'\right\rangle *\left\langle v,v'\right\rangle &=\left\langle uv,u'v+uv'\right\rangle \\\left\langle u,u'\right\rangle /\left\langle v,v'\right\rangle &=\left\langle {\frac {u}{v}},{\frac {u'v-uv'}{v^{2}}}\right\rangle \quad (v\neq 0)\\\sin \left\langle u,u'\right\rangle &=\left\langle \sin(u),u'\cos(u)\right\rangle \\\cos \left\langle u,u'\right\rangle &=\left\langle \cos(u),-u'\sin(u)\right\rangle \\\exp \left\langle u,u'\right\rangle &=\left\langle \exp u,u'\exp u\right\rangle \\\log \left\langle u,u'\right\rangle &=\left\langle \log(u),u'/u\right\rangle \quad (u>0)\\\left\langle u,u'\right\rangle ^{k}&=\left\langle u^{k},u'ku^{k-1}\right\rangle \quad (u\neq 0)\\\left|\left\langle u,u'\right\rangle \right|&=\left\langle \left|u\right|,u'\operatorname {sign} u\right\rangle \quad (u\neq 0)\end{aligned}}$ $g$ $g(\langle u,u'\rangle ,\langle v,v'\rangle )=\langle g(u,v),g_{u}(u,v)u'+g_{v}(u,v)v'\rangle$ $g_{u}$ $g_{v}$ $g$

Cuando se aplica una operación aritmética básica binaria a argumentos mixtos (el par y el número real ), el número real se eleva primero a . La derivada de una función en el punto se encuentra ahora calculando con la aritmética anterior, que da como resultado . $\langle u,u'\rangle$ $c$ $\langle c,0\rangle$ $f:\mathbb {R} \to \mathbb {R}$ $x_{0}$ $f(\langle x_{0},1\rangle )$ $\langle f(x_{0}),f'(x_{0})\rangle$

Implementación

A continuación se muestra un ejemplo de implementación basado en el enfoque de número dual.

Pseudocódigo

Doble más (Dual A, Dual B) { devolver { parterealDe(A) + parterealDe(B), parteinfinitaDe(A) + parteinfinitaDe(B) };}Doble menos (Dual A, Dual B) { devolver { parterealDe(A) - parterealDe(B), infinitesimalPartOf(A) - infinitesimalPartOf(B) };}Doble multiplicación (Dual A, Dual B) { devolver { parterealDe(A) * parterealDe(B), ParterealDe(B) * ParteinfinitsimalDe(A) + ParterealDe(A) * ParteinfinitsimalDe(B) };}X = {x, 0};Y = {y, 0};Épsilon = {0, 1};xPartial = infinitesimalPartOf(f(X + Epsilon, Y));yPartial = infinitesimalPartOf(f(X, Y + Epsilon));

C++

#include <iostream> struct Dual { float partereal , parteinfinitesimal ; Dual ( float partereal , float parteinfinitesimal = 0 ) : partereal ( partereal ), parteinfinitesimal ( parteinfinitesimal ) {} Operador dual + ( dual otro ) { return dual ( partereal + otro . partereal , parteinfinitesimal + otro . parteinfinitesimal ); } Operador dual * ( dual otro ) { return dual ( partereal * otro . partereal , otro . partereal * parteinfinitesimal + partereal * otro . parteinfinitesimal ); } }; // Ejemplo: Encontrar los parciales de z = x * (x + y) + y * y en (x, y) = (2, 3) Dual f ( dual x , dual y ) { return x * ( x + y ) + y * y ; } int main () { dual x = dual ( 2 ); dual y = dual ( 3 ); Epsilon dual = Dual ( 0 , 1 ); a dual = f ( x + epsilon , y ); b dual = f ( x , y + epsilon ); std :: cout << "∂z/∂x = " << a . infinitesimalPart << ", " << "∂z/∂y = " << b . infinitesimalPart <<                                                                                                        std :: endl ; // Salida: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }

Argumentos y funciones vectoriales

Las funciones multivariadas se pueden manejar con la misma eficiencia y mecanismos que las funciones univariadas adoptando un operador de derivada direccional. Es decir, si es suficiente calcular , la derivada direccional de en la dirección se puede calcular como utilizando la misma aritmética que antes. Si se desean todos los elementos de , entonces se requieren evaluaciones de funciones. Nótese que en muchas aplicaciones de optimización, la derivada direccional es de hecho suficiente. $y'=\nabla f(x)\cdot x'$ $y'\in \mathbb {R} ^{m}$ $f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}$ $x\in \mathbb {R} ^{n}$ $x'\in \mathbb {R} ^{n}$ $(\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 )$ $\nabla f$ $n$

Alto orden y muchas variables

La aritmética anterior se puede generalizar para calcular derivadas de segundo orden y superiores de funciones multivariadas. Sin embargo, las reglas aritméticas se complican rápidamente: la complejidad es cuadrática en el grado de derivada más alto. En su lugar, se puede utilizar el álgebra polinómica de Taylor truncada . La aritmética resultante, definida en números duales generalizados, permite un cálculo eficiente utilizando funciones como si fueran un tipo de datos. Una vez que se conoce el polinomio de Taylor de una función, las derivadas se extraen fácilmente.

Implementación

El AD en modo directo se implementa mediante una interpretación no estándar del programa en la que los números reales se reemplazan por números duales, las constantes se elevan a números duales con un coeficiente épsilon cero y las primitivas numéricas se elevan para operar en números duales. Esta interpretación no estándar generalmente se implementa utilizando una de dos estrategias: transformación del código fuente o sobrecarga de operadores .

Transformación de código fuente (SCT)

Figura 4: Ejemplo de cómo podría funcionar la transformación del código fuente

El código fuente de una función se reemplaza por un código fuente generado automáticamente que incluye declaraciones para calcular las derivadas intercaladas con las instrucciones originales.

La transformación del código fuente se puede implementar para todos los lenguajes de programación y también es más fácil para el compilador realizar optimizaciones en tiempo de compilación. Sin embargo, la implementación de la herramienta AD en sí es más difícil y el sistema de compilación es más complejo.

Sobrecarga de operadores (OO)

Figura 5: Ejemplo de cómo podría funcionar la sobrecarga del operador

La sobrecarga de operadores es una posibilidad para el código fuente escrito en un lenguaje que la admita. Los objetos para números reales y operaciones matemáticas elementales deben sobrecargarse para satisfacer la aritmética aumentada que se muestra arriba. Esto no requiere ningún cambio en la forma o secuencia de operaciones en el código fuente original para que la función se diferencie, pero a menudo requiere cambios en los tipos de datos básicos para números y vectores para admitir la sobrecarga y, a menudo, también implica la inserción de operaciones de señalización especiales. Debido a la sobrecarga inherente de la sobrecarga de operadores en cada bucle, este enfoque generalmente demuestra un rendimiento de velocidad más débil.

Sobrecarga de operadores y transformación del código fuente

Los operadores sobrecargados se pueden utilizar para extraer el gráfico de valoración, seguido de la generación automática de la versión AD de la función primaria en tiempo de ejecución. A diferencia de la AAD OO clásica, dicha función AD no cambia de una iteración a la siguiente. Por lo tanto, no hay sobrecarga en tiempo de ejecución de interpretación OO o de cinta por cada muestra Xi.

Al generar la función AD en tiempo de ejecución, se puede optimizar para tener en cuenta el estado actual del programa y calcular previamente ciertos valores. Además, se puede generar de manera que utilice de manera consistente la vectorización de CPU nativa para procesar fragmentos de datos de usuario de 4(8) veces el doble (AVX2\AVX512 acelera x4-x8). Si se tiene en cuenta el subprocesamiento múltiple, este enfoque puede generar una aceleración final del orden de 8 × #Cores en comparación con las herramientas AAD tradicionales. Hay una implementación de referencia disponible en GitHub. ^[11]

Véase también

Programación diferenciable

Notas

^ En términos de matrices de peso, el adjunto es la transpuesta . La suma es el covector , ya que y el abanico de salida es el vector ya que $[1\cdots 1]$ $[1\cdots 1]\left[{\begin{smallmatrix}x_{1}\\\vdots \\x_{n}\end{smallmatrix}}\right]=x_{1}+\cdots +x_{n},$ $\left[{\begin{smallmatrix}1\\\vdots \\1\end{smallmatrix}}\right],$ $\left[{\begin{smallmatrix}1\\\vdots \\1\end{smallmatrix}}\right][x]=\left[{\begin{smallmatrix}x\\\vdots \\x\end{smallmatrix}}\right].$

Referencias

^ Neidinger, Richard D. (2010). "Introducción a la diferenciación automática y a la programación orientada a objetos en MATLAB" (PDF) . SIAM Review . 52 (3): 545–563. CiteSeerX 10.1.1.362.6580 . doi :10.1137/080743627. S2CID 17134969.
^ ab Baydin, Atilim Gunes; Pearlmutter, Barak; Radul, Alexey Andreyevich; Siskind, Jeffrey (2018). "Diferenciación automática en el aprendizaje automático: una encuesta". Revista de investigación en aprendizaje automático . 18 : 1–43.
^ ab RE Wengert (1964). "Un programa simple de evaluación automática de derivadas". Comm. ACM . 7 (8): 463–464. doi : 10.1145/355586.364791 . S2CID 24039274.
^ Griewank, Andreas (2012). "¿Quién inventó el modo inverso de diferenciación?" (PDF) . Historias de optimización, Documenta Matematica . Serie Documenta Mathematica. Volumen adicional ISMP: 389–400. doi :10.4171/dms/6/38. ISBN 978-3-936609-58-5.
^ Linnainmaa, Seppo (1976). "Expansión de Taylor del error de redondeo acumulado". BIT Numerical Mathematics . 16 (2): 146–160. doi :10.1007/BF01931367. S2CID 122357351.
^ Maximilian E. Schüle, Maximilian Springer, Alfons Kemper , Thomas Neumann (2022). "Optimización del código LLVM para la diferenciación automática". Actas del sexto taller sobre gestión de datos para el aprendizaje automático de extremo a extremo . págs. 1–4. doi :10.1145/3533028.3533302. ISBN 9781450393751. Número de identificación del sujeto 248853034.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Bartholomew-Biggs, Michael; Brown, Steven; Christianson, Bruce; Dixon, Laurence (2000). "Diferenciación automática de algoritmos". Revista de Matemática Computacional y Aplicada . 124 (1–2): 171–190. Bibcode :2000JCoAM.124..171B. doi :10.1016/S0377-0427(00)00422-2. hdl : 2299/3010 .
^ Maximilian E. Schüle, Harald Lang, Maximilian Springer, Alfons Kemper , Thomas Neumann , Stephan Günnemann (2021). "Aprendizaje automático en base de datos con SQL en GPU". 33.ª Conferencia internacional sobre gestión de bases de datos científicas y estadísticas . págs. 25–36. doi :10.1145/3468791.3468840. ISBN . 9781450384131. Número de identificación del sujeto 235386969.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Maximilian E. Schüle, Harald Lang, Maximilian Springer, Alfons Kemper , Thomas Neumann , Stephan Günnemann (2022). "SQL recursivo y soporte de GPU para aprendizaje automático en base de datos". Bases de datos distribuidas y paralelas . 40 (2–3): 205–259. doi : 10.1007/s10619-022-07417-7 . S2CID : 250412395.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Naumann, Uwe (abril de 2008). "La acumulación jacobiana óptima es NP-completa". Programación matemática . 112 (2): 427–441. CiteSeerX 10.1.1.320.5665 . doi :10.1007/s10107-006-0042-z. S2CID 30219572.
^ "Biblioteca de prototipos de AADC". 22 de junio de 2022 – vía GitHub.

Lectura adicional

Rall, Louis B. (1981). Diferenciación automática: técnicas y aplicaciones . Apuntes de clase sobre informática. Vol. 120. Springer . ISBN. 978-3-540-10861-0.
Griewank, Andreas; Walther, Andrea (2008). Evaluación de derivadas: principios y técnicas de diferenciación algorítmica. Otros títulos en Matemáticas Aplicadas. Vol. 105 (2.ª ed.). SIAM . doi :10.1137/1.9780898717761. ISBN. 978-0-89871-659-7.
Neidinger, Richard (2010). "Introducción a la diferenciación automática y a la programación orientada a objetos en MATLAB" (PDF) . SIAM Review . 52 (3): 545–563. CiteSeerX 10.1.1.362.6580 . doi :10.1137/080743627. S2CID 17134969 . Consultado el 15 de marzo de 2013 .
Naumann, Uwe (2012). El arte de diferenciar programas informáticos . Entornos de software y herramientas. SIAM . ISBN. 978-1-611972-06-1.
Henrard, Marc (2017). Explicación de la diferenciación algorítmica en finanzas . Explicación de la ingeniería financiera. Palgrave Macmillan . ISBN 978-3-319-53978-2.

Enlaces externos

www.autodiff.org, "Un sitio de acceso a todo lo que desea saber sobre la diferenciación automática"
Diferenciación automática de programas OpenMP paralelos
Diferenciación automática, plantillas C++ y fotogrametría
Diferenciación automática, enfoque de sobrecarga del operador
Calcular derivadas analíticas de cualquier programa Fortran77, Fortran95 o C a través de una interfaz basada en web Diferenciación automática de programas Fortran
Descripción y código de ejemplo para la diferenciación automática hacia adelante en Scala Archivado el 3 de agosto de 2016 en Wayback Machine
finmath-lib diferenciación automática estocástica, Diferenciación automática para variables aleatorias (implementación Java de la diferenciación automática estocástica).
Diferenciación algorítmica adjunta: calibración y teorema de función implícita
Artículo e implementación de la diferenciación automática basada en plantillas de C++
Derivados depurables de origen a origen tangente
Griegas exactas de primer y segundo orden por diferenciación algorítmica
Diferenciación algorítmica adjunta de una aplicación acelerada por GPU
Métodos adjuntos en herramientas de software de finanzas computacionales Soporte para diferenciación algorítmica
Más de mil veces la velocidad de cálculo de precios de xVA con procesadores escalables Intel Xeon
Implementación de la serie de Taylor truncada dispersa con el ejemplo VBIC95 para derivadas de orden superior