Question

1. 反向传播算法是一种利用链式法则计算微分的算法。

2. 在一维的情况下，链式法则为： $ MathJax-Element-43 $ 。

3. 在多维情况下，设： $ MathJax-Element-44 $ ， $ MathJax-Element-54 $ 为 $ MathJax-Element-46 $ 到 $ MathJax-Element-50 $ 的映射且满足 $ MathJax-Element-48 $ ， $ MathJax-Element-143 $ 为 $ MathJax-Element-50 $ 到 $ MathJax-Element-51 $ 的映射且满足 $ MathJax-Element-52 $ 。则有：

   $ \frac{\partial z}{\partial x_i}=\sum_{j=1}^{n}\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_i},\quad i=1,2,\cdots,m $

   使用向量记法，可以等价地写作：

   $ \nabla_{\mathbf{\vec x}} z=\left(\frac{\partial \mathbf{\vec y}}{\partial \mathbf{\vec x}}\right)^{T} \nabla_{\mathbf{\vec y}} z $

   其中： $ MathJax-Element-53 $ 为 $ MathJax-Element-54 $ 的 $ MathJax-Element-55 $ 阶雅可比矩阵， $ MathJax-Element-56 $ 为 $ MathJax-Element-284 $ 对 $ MathJax-Element-344 $ 的梯度， $ MathJax-Element-59 $ 为 $ MathJax-Element-284 $ 对 $ MathJax-Element-302 $ 的梯度：

   $ \nabla_{\mathbf{\vec x}} z=\begin{bmatrix} \frac{\partial z}{\partial x_1}\\ \frac{\partial z}{\partial x_2}\\ \vdots\\ \frac{\partial z}{\partial x_m} \end{bmatrix}\quad \nabla_{\mathbf{\vec y}} z=\begin{bmatrix} \frac{\partial z}{\partial y_1}\\ \frac{\partial z}{\partial y_2}\\ \vdots\\ \frac{\partial z}{\partial y_n} \end{bmatrix}\quad \frac{\partial \mathbf{\vec y}}{\partial \mathbf{\vec x}}=\begin{bmatrix} \frac{\partial y_1}{\partial x_1}&\frac{\partial y_1}{\partial x_2}&\cdots&\frac{\partial y_1}{\partial x_m}\\ \frac{\partial y_2}{\partial x_1}&\frac{\partial y_2}{\partial x_2}&\cdots&\frac{\partial y_2}{\partial x_m}\\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial y_n}{\partial x_1}&\frac{\partial y_n}{\partial x_2}&\cdots&\frac{\partial y_n}{\partial x_m}\\ \end{bmatrix} $

   反向传播算法由很多这样的雅可比矩阵与梯度的乘积操作组成。

1.1 张量链式法则

1. 链式法则不仅可以作用于向量，也可以应用于张量：

   • 首先将张量展平为一维向量。
   • 然后计算该向量的梯度。
   • 然后将该梯度重新构造为张量。

2. 记 $ MathJax-Element-62 $ 为 $ MathJax-Element-284 $ 对张量 $ MathJax-Element-298 $ 的梯度。 $ MathJax-Element-298 $ 现在有多个索引（如：二维张量有两个索引），可以使用单个变量 $ MathJax-Element-199 $ 来表示 $ MathJax-Element-298 $ 的索引元组（如 $ MathJax-Element-68 $ 表示：一个二维张量的索引，每个维度三个元素）。

   这就与向量中的索引方式完全一致： $ MathJax-Element-69 $ 。

   如：

   $ \mathbf X=\begin{bmatrix} x_1&x_2&x_3\\ x_4&x_5&x_6\\ x_7&x_8&x_9\\ \end{bmatrix} $

   则有：

   $ \nabla_{\mathbf X} z=\begin{bmatrix} \frac{\partial z}{\partial x_1}&\frac{\partial z}{\partial x_2}&\frac{\partial z}{\partial x_3}\\ \frac{\partial z}{\partial x_4}&\frac{\partial z}{\partial x_5}&\frac{\partial z}{\partial x_6}\\ \frac{\partial z}{\partial x_7}&\frac{\partial z}{\partial x_8}&\frac{\partial z}{\partial x_9}\\ \end{bmatrix} $

3. 设 $ MathJax-Element-212 $ ，用单个变量 $ MathJax-Element-217 $ 来表示 $ MathJax-Element-216 $ 的索引元组。则张量的链式法则为：

   $ \frac{\partial z}{\partial x_i}=\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_i} \; \Rightarrow \nabla_{\mathbf X} z=\sum_{j}(\nabla_{\mathbf X} y_j)\frac{\partial z}{\partial y_j} $

   如：

   $ \mathbf X=\begin{bmatrix} x_1&x_2&x_3\\ x_4&x_5&x_6\\ x_7&x_8&x_9\\ \end{bmatrix} $

   则有：

   $ \nabla_{\mathbf X} z=\begin{bmatrix} \sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_1}&\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_2}&\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_3}\\ \sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_4}&\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_5}&\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_6}\\ \sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_7}&\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_8}&\sum_j \frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_9}\\ \end{bmatrix} $

   .

1.2 重复子表达式

1. 给定计算图以及计算图中的某个标量 $ MathJax-Element-284 $ ，根据链式法则可以很容易地写出 $ MathJax-Element-284 $ 对于产生 $ MathJax-Element-284 $ 的任意节点的梯度的数学表达式。

   但是在计算该表达式的时候，许多子表达式可能在计算整个梯度表达式的过程中重复很多次。

   

   如图中：

   $ x=f(w)\\ y=f(x)\\ z=f(y)\\ \Rightarrow \frac{dz}{dw}=\frac{dz}{dy}\frac{dy}{dx}\frac{dx}{dw}\\ = f^{\prime}(y)f^{\prime}(x)f^{\prime}(w)\\ =f^{\prime}(f(f(w)))f^{\prime}(f(w))f^{\prime}(w) $

   可以看到 $ MathJax-Element-77 $ 被计算多次。

   • 在复杂的计算图中，可能存在指数量级的重复子表达式，这使得原始的链式法则几乎不可实现。

   • 一个解决方案是：计算 $ MathJax-Element-77 $ 一次并将它存储在 $ MathJax-Element-78 $ 中，然后采用 $ MathJax-Element-79 $ 来计算梯度。

     这也是反向传播算法采用的方案：在前向传播时，将节点的中间计算结果全部存储在当前节点上。其代价是更高的内存开销。

2. 有时候必须重复计算子表达式。这是以较高的运行时间为代价，来换取较少的内存开销。