Según Wikipedia, la diferenciación en modo forward es preferida cuando $f: \mathbb{R}^n \mapsto \mathbb{R}^m$ , m >> n. No puedo ver ningún beneficio computacional. Tomemos un ejemplo simple: $f(x,y) = \sin(xy)$. Podemos visualizarlo como un gráfico con cuatro nodos y 3 bordes. El nodo superior es $\sin(xy)$, el nodo un nivel más abajo es $xy$ y los dos nodos iniciales son $x$ y $y$. Las derivadas en los nodos son $\cos(xy)$, $x$ y $y$. Para ambos modos de diferenciación, forward y reverse, tenemos que calcular estas derivadas. ¿Cómo es que el modo de diferenciación inversa es computacionalmente superior aquí?
Respuestas
¿Demasiados anuncios?
La regla de la cadena establece que para calcular el Jacobiano de una operación debemos multiplicar los Jacobianos de todas las suboperaciones juntas. La diferencia entre la auto-diferenciación en modo directo e inverso es el orden en el que multiplicamos esos Jacobianos.
En tu caso, solo tienes dos suboperaciones: $xy$ y $\sin()$, lo que lleva a una sola multiplicación de matrices, por lo que no es realmente instructivo. Sin embargo, consideremos una operación con 3 suboperaciones. Toma la función: $$ \mathbf{y} = f(\mathbf{x}) = r(q(p(\mathbf{x}))) $$ donde $\bf{x}$ y $\bf{y}$ son vectores de diferentes longitudes. Podemos descomponer esto en: $$ \mathbf{a} = p(\mathbf{x}),~~ \mathbf{b} = q(\mathbf{a}),~~ \mathbf{y} = r(\mathbf{b}). $$ Esto nos da el Jacobiano $$ \underbrace{\frac{\partial \mathbf{y}}{\partial \mathbf{x}}}_{|\mathbf{y}|\times|\mathbf{x}|} = \underbrace{\frac{\partial r(\mathbf{b})}{\partial \mathbf{b}}}_{|\mathbf{y}|\times|\mathbf{b}|} \underbrace{\frac{\partial q(\mathbf{a})}{\partial \mathbf{a}}}_{|\mathbf{b}|\times|\mathbf{a}|} \underbrace{\frac{\partial p(\mathbf{x})}{\partial \mathbf{x}}}_{|\mathbf{a}|\times|\mathbf{x}|}, $$ con el tamaño de cada matriz indicado debajo de la matriz. El tiempo necesario para calcular cada uno de esos Jacobianos intermedios es fijo, pero el orden en el que los multiplicamos juntos cambia el número de operaciones requeridas para hacerlo. La auto-diferenciación en modo directo calcularía $$ \frac{\partial \mathbf{y}}{\partial \mathbf{x}} = \frac{\partial r(\mathbf{b})}{\partial \mathbf{b}}\left(\frac{\partial q(\mathbf{a})}{\partial \mathbf{a}}\frac{\partial p(\mathbf{x})}{\partial \mathbf{x}}\right), $$ que implica $|\mathbf{x}|\cdot|\mathbf{a}|\cdot|\mathbf{b}|+|\mathbf{x}|\cdot|\mathbf{b}|\cdot|\mathbf{y}|$ multiplicaciones*, que se simplifica a $|\mathbf{x}|\cdot|\mathbf{b}|\cdot(|\mathbf{a}|+|\mathbf{y}|)$. En contraste, la auto-diferenciación en modo inverso calcularía $$ \frac{\partial \bf{y}}{\partial \bf{x}} = \left(\frac{\partial r(\bf{b})}{\partial \bf{b}}\frac{\partial q(\bf{a})}{\partial \bf{a}}\right)\frac{\partial p(\bf{x})}{\partial \bf{x}}, $$ que implica $|\mathbf{y}|\cdot|\mathbf{a}|\cdot|\mathbf{b}|+|\mathbf{y}|\cdot|\mathbf{a}|\cdot|\mathbf{x}|$ multiplicaciones, que se simplifica a $|\mathbf{y}|\cdot|\mathbf{a}|\cdot(|\mathbf{b}|+|\mathbf{x}|)$.
Asumiendo por simplicidad que la dimensionalidad de las variables aumenta o disminuye monótonamente a través de la computación, en el caso de que $|\mathbf{y}|\ge|\mathbf{b}|\ge|\mathbf{a}|\ge|\mathbf{x}|$, podemos ver que la auto-diferenciación en modo directo resulta en el mismo número o menos operaciones, ya que $\frac{|\mathbf{y}|\cdot|\mathbf{a}|}{|\mathbf{x}|\cdot|\mathbf{b}|}\ge\frac{|\mathbf{y}|+|\mathbf{a}|}{|\mathbf{x}|+|\mathbf{b}|}$, por lo tanto $|\mathbf{y}|\cdot|\mathbf{a}|\cdot(|\mathbf{b}|+|\mathbf{x}|)\ge|\mathbf{x}|\cdot|\mathbf{b}|\cdot(|\mathbf{a}|+|\mathbf{y}|)$. De manera similar, si $|\mathbf{y}|\le|\mathbf{b}|\le|\mathbf{a}|\le|\mathbf{x}|$ entonces la auto-diferenciación en modo inverso resulta en el mismo número o menos operaciones.
Esto significa que la auto-diferenciación en modo inverso (también conocida como retropropagación) suele ser más rápida cuando $f: \mathbb{R}^n \mapsto \mathbb{R}^m, m << n$, es decir, la salida de la función de costo es de baja dimensionalidad (por ejemplo, una función de pérdida escalar), pero la entrada es de alta dimensionalidad (por ejemplo, píxeles en una imagen, o palabras en un texto de entrada), como suele ser el caso en el entrenamiento de redes neuronales.
Este razonamiento sobre si es preferible la auto-diferenciación en modo directo o inverso se extiende a cadenas más largas de Jacobianos. Sin embargo, pueden ocurrir excepciones, por ejemplo, cuando la menor dimensionalidad de las variables ocurre ni al inicio ni al final de la función, sino en algún punto intermedio. En tales casos, el ordenamiento óptimo de multiplicaciones de matrices no será completamente en modo directo o inverso, sino un esquema híbrido.
He discutido consideraciones teóricas/idealizadas, pero también hay consideraciones prácticas. Por ejemplo, la auto-diferenciación en modo inverso requiere un paso hacia adelante a través del código para calcular los valores, luego un paso hacia atrás para calcular las derivadas. Durante el paso hacia adelante, es necesario almacenar un rastro de los valores para poder calcular el paso hacia atrás. Esto aumenta la complejidad de implementar y ejecutar la auto-diferenciación en modo inverso.
*El número de multiplicaciones escalares necesarias para multiplicar dos matrices de tamaños $a\times b$ y $b\times c$ es $a\cdot b\cdot c$.
devin_s
Puntos
1009
Una analogía podría ayudar. Deja que $\bf A$, $\bf B$, y $\bf C$ sean matrices con dimensiones tales que $\bf ABC$ esté bien definido. Hay dos formas obvias de calcular este producto, representadas por $(\bf AB)\bf C$ y $\bf A(\bf BC)$. Cuál de esas requerirá menos multiplicaciones y sumas depende de las dimensiones de las matrices. Por ejemplo, si $\bf C$ tiene ancho 1 entonces la segunda forma será más rápida, o al menos no más lenta. Es eficiente multiplicar por matrices delgadas o cortas temprano.
Si $\bf A$, $\bf B$, y $\bf C$ corresponden a jacobianos de varios pasos en el grafo de cálculo, entonces creo que $\bf C$ tener ancho $1$ corresponde al caso cuando $m=1$.
