Diferenciación automática - Automatic differentiation

En matemáticas y álgebra computacional , diferenciación automática ( AD ), también llamado diferenciación algorítmica , diferenciación computacional , auto-diferenciación , o simplemente autodiff , es un conjunto de técnicas para evaluar el derivado de una función especificada por un programa de ordenador. AD aprovecha el hecho de que todo programa 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, sin, cos, etc.). Al aplicar la regla de la cadena repetidamente a estas operaciones, las derivadas de orden arbitrario se pueden calcular automáticamente, con precisión de trabajo y utilizando como máximo un pequeño factor constante más operaciones aritméticas que el programa original.

La diferenciación automática es distinta de la diferenciación simbólica y la diferenciación numérica (el método de las diferencias finitas). La diferenciación simbólica puede conducir a un código ineficiente y enfrenta la dificultad de convertir un programa de computadora en una sola expresión, mientras que la diferenciación numérica puede introducir errores de redondeo en el proceso de discretización y cancelación. Ambos métodos clásicos tienen problemas para calcular derivadas más altas, donde la complejidad y los errores aumentan. Finalmente, ambos métodos clásicos son lentos para 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.

La regla de la cadena, acumulación hacia adelante y hacia atrás.

Fundamental para AD es la descomposición de diferenciales proporcionada por la regla de la cadena . Por la composición simple

la regla de la cadena da

Por lo general, se presentan dos modos distintos de AD, acumulación hacia adelante (o modo hacia adelante ) y acumulación hacia atrás (o modo hacia atrás ). La acumulación hacia adelante especifica que uno atraviesa la regla de la cadena de adentro hacia afuera (es decir, primero calcula y luego y al final ), mientras que la acumulación inversa tiene el recorrido de afuera hacia adentro (primero calcula y luego y al final ). Más sucintamente, ${\ displaystyle dw_ {1} / dx}$${\ displaystyle dw_ {2} / dw_ {1}}$${\ Displaystyle dy / dw_ {2}}$${\ Displaystyle dy / dw_ {2}}$${\ displaystyle dw_ {2} / dw_ {1}}$${\ displaystyle dw_ {1} / dx}$

1. La acumulación hacia adelante calcula la relación recursiva: con , y,${\ Displaystyle {\ frac {dw_ {i}} {dx}} = {\ frac {dw_ {i}} {dw_ {i-1}}} {\ frac {dw_ {i-1}} {dx}} }$${\ Displaystyle w_ {3} = y}$
2. la acumulación inversa calcula la relación recursiva: con .${\ Displaystyle {\ frac {dy} {dw_ {i}}} = {\ frac {dy} {dw_ {i + 1}}} {\ frac {dw_ {i + 1}} {dw_ {i}}} }$${\ Displaystyle w_ {0} = x}$

Acumulación hacia adelante

En adelante acumulación AD, primero se fija la variable independiente con respecto al cual la diferenciación se realiza y calcula la derivada de cada sub- expresión de forma 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 los jacobianos .

En comparación con la acumulación inversa, la acumulación directa es natural y fácil de implementar, ya que el flujo de información derivada coincide con el orden de evaluación. Cada variable w se aumenta con su derivada ẇ (almacenada como un valor numérico, no como una expresión simbólica),

como se indica con el punto. A continuación, las derivadas se calculan en sincronía con los pasos de evaluación y se combinan con otras derivadas mediante la regla de la cadena.

Como ejemplo, considere la función:

Para mayor claridad, las sub-expresiones individuales se han etiquetado con las variables w _i .

La elección de la variable independiente a la que se realiza la diferenciación afecta a los valores semilla ẇ ₁ y ẇ ₂ . Dado el interés en la derivada de esta función con respecto ax ₁ , los valores semilla deben establecerse en:

Con los valores de semilla establecidos, los valores se propagan usando la regla de la cadena como se muestra. La Figura 2 muestra una descripción pictórica de este proceso como un gráfico computacional.

Operaciones para calcular el valor	Operaciones para calcular la derivada
${\ Displaystyle w_ {1} = x_ {1}}$	${\ Displaystyle {\ dot {w}} _ {1} = 1}$ (semilla)
${\ Displaystyle w_ {2} = x_ {2}}$	${\ Displaystyle {\ dot {w}} _ {2} = 0}$ (semilla)
${\ Displaystyle w_ {3} = w_ {1} \ cdot w_ {2}}$	${\ Displaystyle {\ dot {w}} _ {3} = w_ {2} \ cdot {\ dot {w}} _ {1} + w_ {1} \ cdot {\ dot {w}} _ {2} }$
${\ Displaystyle w_ {4} = \ sin w_ {1}}$	${\ Displaystyle {\ dot {w}} _ {4} = \ cos w_ {1} \ cdot {\ dot {w}} _ {1}}$
${\ Displaystyle w_ {5} = w_ {3} + w_ {4}}$	${\ Displaystyle {\ dot {w}} _ {5} = {\ dot {w}} _ {3} + {\ dot {w}} _ {4}}$

Para calcular el gradiente de esta función de ejemplo, que requiere las derivadas de f con respecto no solo a x ₁ sino también a x ₂ , se realiza un barrido adicional sobre el gráfico computacional utilizando los valores semilla . ${\ Displaystyle {\ dot {w}} _ {1} = 0; {\ dot {w}} _ {2} = 1}$

La complejidad computacional de un barrido de acumulación hacia adelante es proporcional a la complejidad del código original.

La acumulación hacia adelante es más eficiente que la acumulación inversa para las funciones f  : R ⁿ → R ^m con m ≫ n ya que solo son necesarios n barridos, en comparación con m barridos para la acumulación inversa.

Acumulación inversa

En la acumulación de AD inversa, la variable dependiente a ser diferenciada es fijo y el derivado se calcula con respecto a cada sub- expresió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:

En la acumulación inversa, la cantidad de interés es el adjunto , denotado con una barra ( w̄ ); es una derivada de una variable dependiente elegida con respecto a una subexpresión w :

La acumulación inversa atraviesa la regla de la cadena de afuera hacia adentro, o en el caso del gráfico computacional de la Figura 3, de arriba hacia abajo. La función de ejemplo tiene valores escalares y, por lo tanto, solo hay una semilla para el cálculo derivado 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 directa, 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 lista de Wengert (o "cinta"), que puede consumen una cantidad significativa de memoria 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 salvar estados intermedios.

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

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 agregando un nodo adjunto para cada nodo primario, conectado por bordes adjuntos que son paralelos a los bordes primarios 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 provoca un abanico en el adjunto; fanout en el primario causa adición en el adjunto; una función unaria y = f  ( x ) en el primario causa x̄ = ȳ f  ′ ( x ) en el adjunto; etc.

La acumulación inversa es más eficiente que la acumulación directa para las funciones f  : R ⁿ → R ^m con m ≪ n, ya que solo son necesarios m barridos, en comparación con n barridos para la acumulación directa.

El modo inverso AD fue publicado por primera vez en 1976 por Seppo Linnainmaa .

La propagación hacia atrás de errores en perceptrones multicapa, una técnica utilizada en el aprendizaje automático , es un caso especial de AD en modo inverso.

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

La acumulación hacia adelante y hacia atrás son solo dos formas (extremas) de atravesar la regla de la cadena. El problema de calcular un jacobiano completo de f  : R ⁿ → 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 . Para esta prueba es fundamental la idea de que pueden existir dependencias algebraicas entre los parciales locales que etiquetan los bordes del gráfico. En particular, dos o más etiquetas de borde pueden reconocerse como iguales. La complejidad del problema sigue abierta si se asume que todas las etiquetas de los bordes son únicas y algebraicamente independientes.

Diferenciación automática mediante 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 suave infinitesimal ). Usando solo esto, la aritmética regular da ${\ Displaystyle \, x}$${\ Displaystyle x + x '\ varepsilon}$${\ Displaystyle x '}$${\ Displaystyle \ varepsilon}$${\ displaystyle \ varepsilon ^ {2} = 0}$

e igualmente para la resta y la división.

Ahora, los polinomios se pueden calcular en esta aritmética aumentada. Si entonces ${\ Displaystyle P (x) = p_ {0} + p_ {1} x + p_ {2} x ^ {2} + \ cdots + p_ {n} x ^ {n}}$

donde denota la derivada de con respecto a su primer argumento y , llamada semilla , se puede elegir arbitrariamente. ${\ Displaystyle P ^ {(1)}}$${\ Displaystyle P}$${\ Displaystyle 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. Al extender los resultados anteriores sobre polinomios a

funciones analíticas, se obtiene una lista de la aritmética básica y algunas funciones estándar para la nueva aritmética: ${\ Displaystyle \ langle x, x '\ rangle}$

$${\ Displaystyle {\ begin {alineado} \ 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 '\ 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 & = \ izquierda \ langle \ log (u), u '/ u \ derecha \ rangle \ quad (u> 0) \\\ izquierda \ langle u, u' \ derecha \ rangle ^ {k} & = \ izquierda \ langle u ^ {k}, ku ^ {k-1} u '\ right \ rangle \ quad (u \ neq 0) \\\ left | \ left \ langle u, u' \ right \ rangle \ right | & = \ left \ langle \ left | u \ right |, u '{\ mbox {sign}} u \ right \ rangle \ quad (u \ neq 0) \ end {alineado}}}$$

y en general para la función primitiva , ${\ Displaystyle g}$

$${\ Displaystyle g (\ langle u, u '\ rangle, \ langle v, v' \ rangle) = \ langle g (u, v), g_ {u} (u, v) u '+ g_ {v} ( u, v) v '\ rangle}$$

donde y son las derivadas de con respecto a su primer y segundo argumento, respectivamente. ${\ Displaystyle g_ {u}}$${\ Displaystyle g_ {v}}$${\ Displaystyle 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 ahora se encuentra calculando usando la aritmética anterior, que da como resultado. ${\ Displaystyle \ langle u, u '\ rangle}$${\ Displaystyle c}$${\ Displaystyle \ langle c, 0 \ rangle}$${\ Displaystyle f: \ mathbb {R} \ to \ mathbb {R}}$${\ Displaystyle x_ {0}}$${\ Displaystyle f (\ langle x_ {0}, 1 \ rangle)}$${\ Displaystyle \ langle f (x_ {0}), f '(x_ {0}) \ rangle}$

Argumentos y funciones vectoriales

Las funciones multivariadas se pueden manejar con la misma eficiencia y los mismos mecanismos que las funciones univariadas mediante la adopción de un operador derivado direccional. Es decir, si es suficiente para calcular , la derivada direccional de at en la dirección , esto puede calcularse usando la misma aritmética que arriba. Si se desean todos los elementos de , entonces se requieren evaluaciones de funciones. Tenga en cuenta que en muchas aplicaciones de optimización, la derivada direccional es suficiente. ${\ Displaystyle y '= \ nabla f (x) \ cdot x'}$${\ Displaystyle y '\ in \ mathbb {R} ^ {m}}$${\ Displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R} ^ {m}}$${\ Displaystyle x \ in \ mathbb {R} ^ {n}}$${\ Displaystyle x '\ in \ mathbb {R} ^ {n}}$${\ Displaystyle (\ 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)}$${\ Displaystyle \ nabla f}$${\ Displaystyle n}$

Alto orden y muchas variables

La aritmética anterior se puede generalizar para calcular las 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 polinomial 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 modo directo AD 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 se implementa generalmente usando una de dos estrategias: transformación del código fuente o sobrecarga del operador .

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 de tiempo de compilación. Sin embargo, la implementación de la herramienta AD en sí es más difícil.

Sobrecarga del operador (OO)

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

La sobrecarga del operador es una posibilidad para el código fuente escrito en un lenguaje que lo admita. Los objetos para números reales y operaciones matemáticas elementales deben sobrecargarse para adaptarse a la aritmética aumentada que se muestra arriba. Esto no requiere cambios en la forma o secuencia de operaciones en el código fuente original para que la función sea diferenciada, pero a menudo requiere cambios en los tipos de datos básicos para números y vectores para soportar la sobrecarga y, a menudo, también implica la inserción de operaciones especiales de marcado.

La sobrecarga del operador para la acumulación hacia adelante es fácil de implementar y también es posible para la acumulación hacia atrás. Sin embargo, los compiladores actuales se quedan atrás en la optimización del código en comparación con la acumulación directa.

La sobrecarga del operador, tanto para acumulación directa como inversa, puede ser adecuada para aplicaciones en las que los objetos son vectores de números reales en lugar de escalares. Esto se debe a que la cinta comprende operaciones vectoriales; esto puede facilitar implementaciones computacionalmente eficientes donde cada operación vectorial realiza muchas operaciones escalares. Se pueden usar técnicas de diferenciación algorítmica de vectores adjuntos (vector AAD), por ejemplo, para diferenciar valores calculados mediante simulación Monte-Carlo.

Ejemplos de implementaciones de diferenciación automática con sobrecarga de operadores en C ++ son las bibliotecas Adept y Stan .

Ver también

• Programación diferenciable

Notas

Referencias

Otras lecturas

• Rall, Louis B. (1981). Diferenciación automática: técnicas y aplicaciones . Apuntes de conferencias en Ciencias de la Computación. 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. 105 (2ª ed.). SIAM . ISBN 978-0-89871-659-7. Archivado desde el original el 23 de marzo de 2010 . Consultado el 21 de octubre de 2009 .
• Neidinger, Richard (2010). "Introducción a la diferenciación automática y programación orientada a objetos de MATLAB" (PDF) . Revisión SIAM . 52 (3): 545–563. CiteSeerX  10.1.1.362.6580 . doi : 10.1137 / 080743627 . Consultado el 15 de marzo de 2013 .
• Naumann, Uwe (2012). El arte de diferenciar programas informáticos . Herramientas-Software-Entornos. 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
• Calcule 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 directa en Scala
• finmath-lib extensiones de diferenciación automática , 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 diferenciación automática basada en plantillas de C ++

Derivados depurables tangentes de origen a origen

[1] , Griegos exactos de primer y segundo orden por diferenciación algorítmica

[2] , Diferenciación algorítmica adjunta de una aplicación acelerada por GPU

[3] , Métodos adjuntos en soporte de herramientas de software de finanzas computacionales para diferenciación algorítmicaop