深度网络现代实践 - 深度前馈网络之反向传播和其他的微分算法篇

序言

反向传播（Backpropagation，简称backprop）是神经网络训练过程中最关键的技术之一，尤其在多层神经网络中广泛应用。它是一种与优化方法（如梯度下降法）结合使用的算法，用于计算网络中各参数的梯度，进而通过调整这些参数来最小化损失函数，从而提高模型的预测准确性和泛化能力。微分算法在机器学习中占据核心地位，主要用于计算复杂函数的梯度。反向传播作为其中的一种，特别适用于神经网络中的梯度计算。其基本原理是利用链式法则，通过计算图中每个节点的梯度来逐步反向传播误差信号，从而实现对网络参数的优化。

反向传播和其他的微分算法

• 当我们使用前馈神经网络接收输入$\mathbf{x}$并产生输出$\hat{\mathbf{y}}$时，信息通过网络向前流动。
• 前向传播（forward propagation）
  • 输入$\mathbf{x}$提供初始信息，然后传播到每一层的隐藏单元，最终产生输出$\hat{\mathbf{y}}$
• 反向传播（back propagation）
  • 在训练过程中，前向传播可以持续向前直到它产生一个标量代价函数$J(\mathbf{\theta })$。反向传播（back propagation），经常简称为backprop，允许来自代价函数的信息通过网络向后流动，以便计算梯度。
  • 计算梯度的解析表达式是很直观的，但是数值化地求解这样的表达式在计算上可能是昂贵的。反向传播算法使用简单和廉价的程序来实现这个目标。
  • 反向传播这个术语经常被误解为用于多层神经网络的整个学习算法。实际上，反向传播仅指用于计算梯度的方法，而另一种算法，例如随机梯度下降，使用该梯度来进行学习。
  • 此外，反向传播仅适用于多层神经网络，但原则上它可以计算任何函数的导数（对于一些函数，正确的响应是报告函数的导数是未定义的）。
  • 特别地，我们会描述如何计算一个任意函数$f$的梯度${\nabla }_{x}f(\mathbf{x},\mathbf{y})$
    • 其中$\mathbf{x}$是一组变量，我们需要它们的导数
    • 而$\mathbf{y}$是另外一组函数的输入变量，但我们并不需要它们的导数。
  • 在学习算法中，我们最常需要的梯度是成本函数关于参数的梯度，即$\nabla \theta J(\theta )$。许多机器学习任务涉及计算其他导数，作为学习过程的一部分，或者用来分析学习的模型。反向传播算法也适用于这些任务，并且不限于计算成本函数关于参数的梯度。通过网络传播信息来计算导数的想法是非常通用的，并且可以用于计算诸如具有多个输出的函数$f$的$\text{Jacobi}$矩阵的值。我们这里描述的是最常用的情况，$f$只有单个输出。

计算图（computational graphs）

• 到目前为止我们已经用相对非正式的图形语言讨论了神经网络。为了更精确地描述反向传播算法，使用更精确的计算图（computational graphs）语言是很有帮助的。

• 将计算形式化为图形的方法有很多。这里，我们使用图中的每一个节点来表示一个变量。变量可以是标量、向量、矩阵、张量、或者甚至是另一类型的变量。

• 为了形式化我们的图形，我们还需要引入操作 (operation)。操作是一个或多个变量的简单函数。我们的图形语言伴随着一组被允许的操作。可以通过将多个操作组合在一起来描述比该组中的操作更复杂的函数。

• 不失一般性，我们定义一个操作仅返回单个输出变量。这并没有失去一般性，因为输出变量可以有多个条目，例如向量。反向传播的软件实现通常支持具有多个输出的操作，但是我们在描述中避免这种情况，因为它引入了对概念理解不重要的许多额外细节。

• 如果变量$y$是变量$x$通过一个操作计算得到的，那么我们画一条从$x$到$y$的有向边。我们有时用操作的名称来注释输出的节点，当上下文很明确时有时也会省略这个标注。

• 例如，计算图的示例
  

• 说明：

  • 图(a)：使用乘法符x操作计算$z=xy$的计算图。
  • 图(b)：用于逻辑回顾预测$\hat{y}=\sigma ({\mathbf{x}}^{\top }\mathbf{w}+b)$的计算图。注：一些中间表达式在代数表达式中没有名称，但在图形中却需要。
  • 图©：表达式 H = max ⁡ { 0 , X W + b } H=\max\{0, \boldsymbol{XW}+b\} H=max{0,XW+b}的计算图。在给定包含小批量输入数据的设计矩阵$\mathbf{X}$时，它计算整流线性单元激活的设计矩阵$\mathbf{H}$。
  • 图(d)：示例a-c对每个变量最多只实施一个操作，但是对变量实施多个操作也是可能的。这里我们展示一个计算图，它对线性回归模型的权重$\mathbf{w}$实施多个操作。这个权重不仅用于预测$\hat{y}$，也用于权重衰减惩罚项$\lambda {\sum }_i{w}_i^2$

微积分中的链式法则（chain rule of calculus）

• 微积分中的链式法则（为了不与概率中的链式法则相混淆）用于计算复合函数的导数。反向传播是一种计算链式法则的算法，使用高效的特定运算顺序。
• 反向传播算法应用标量情况
  • 设$x$是实数，$f$和$g$是从实数映射到实施的函数。
    • 假设$y=g(x)$并且$z=f(g(x))=f(y)$。
    • 那么，链式法则，即$\frac{dz}{dx}=\frac{dz}{dy}\frac{dy}{dx}$，给出了复合函数$z=f(g(x))$关于$x$的导数。
• 我们可以将这种标量情况进行扩展，即应用于向量情况
  • 假设$\mathbf{x}\in {\mathbb{R}}^m$，$\mathbf{y}\in {\mathbb{R}}^n$，$g$是${\mathbb{R}}^m$到${\mathbb{R}}^n$的映射，$f$是${\mathbb{R}}^n$到$\mathbb{R}$的映射。
  • 如果$\mathbf{y}=g(\mathbf{x})$并且$z=f(\mathbf{y})$，那么链式法则，即$\frac{\partial z}{\partial {\mathbf{x}}_i}=\sum _j\frac{\partial z}{\partial y_i}\frac{\partial y_i}{\partial x_i}$，给出了复合函数$z=f(g(\mathbf{x}))$关于$\mathbf{x}$的导数。
  • 使用向量记法，可以等价地写成：${\nabla }_{\mathbf{x}}z={\left(\frac{\partial \mathbf{y}}{\partial \mathbf{x}}\right)}^{\top }{\nabla }_{\mathbf{y}}z$。其中$\frac{\partial \mathbf{y}}{\partial \mathbf{x}}$是$g$的$n\times m$的Jacobi矩阵。
  • 从这里我们看到变量$\mathbf{x}$的梯度可以通过将$\text{Jacobi}$矩阵$\frac{\partial \mathbf{y}}{\partial \mathbf{x}}$是$g$的$n\times m$乘以梯度${\nabla }_{\mathbf{y}}z$来得到。反向传播算法由图中每一个这样的$\text{Jacobi}$矩阵的乘积操作所组成的。
• 反向传播算法应用于张量的情况
  • 通常我们不将反向传播算法仅用于向量，而是应用于任意维度的张量。
  • 从概念上讲，这与使用向量的反向传播完全相同。
  • 唯一的区别是如何将数字排列成网格以形成张量。
  • 我们可以想象，在我们运行反向传播之前，将每个张量变平为一个向量，计算一个向量值梯度，然后将该梯度重新构造成一个张量。
  • 从这种重新排列的观点上看，反向传播仍然只是将$\text{Jacobi}$矩阵乘以梯度。
  • 为了表示值$z$对张量$\mathbf{X}$的梯度，我们记为：${\nabla }_{\mathbf{X}}z$，就像$\mathbf{X}$是向量一样。$\mathbf{X}$的索引现在有多个坐标。
    • 例如，一个3维的张量由三个坐标索引。我们可以通过使用单个变量$i$来表示完整的索引元组，从而完全抽象出来。
    • 对所有可能的元组$i$，${\left({\nabla }_{\mathbf{X}}z\right)}_i$给出$\frac{\partial z}{\partial X_i}$
    • 这与向量中索引的方式完全一致，${\left({\nabla }_{\mathbf{x}}z\right)}_i$给出$\frac{\partial z}{\partial x_i}$
    • 使用这种记法，我们可以写出适用于张量的链式法则。
    • 如果$\mathbf{Y}=g(\mathbf{X})$并且$z=f(\mathbf{Y})$，那么张量的链式法则，即${\nabla }_{\mathbf{X}}z=\sum _j({\nabla }_{\mathbf{X}}{\mathbf{Y}}_j)\frac{\partial z}{\partial {\mathbf{Y}}_j}$

递归地使用链式法则来实现反向传播算法

• 使用链式法则，可以直接写出某个标量对于计算图中任何产生该标量的节点的梯度的代数表达式。然而，实际在计算机中计算该表达式时会引入一些额外的考虑。

• 具体来说，许多子表达式可能在梯度的整个表达式中重复若干次。任何计算梯度的程序都需要选择是存储这些子表达式还是重新计算它们几次。

  • 例如，计算梯度时导致重复子表达式的计算图。
    

  • 说明：

    • 令$w\in \mathbb{R}$为图的输入。
    • 我们对链中的每一步使用相同的操作函数：$f:\mathbb{R}\to \mathbb{R}$，这样$x=f(w),y=f(x),z=f(y)$。
    • 为了计算$\frac{\partial z}{\partial w}$，我们应用公式：$\frac{dz}{dx}=\frac{dz}{dy}\frac{dy}{dx}$得到：
      $\{\begin{array}{l}\begin{array}{rl}\frac{\partial z}{\partial w}& =\frac{\partial z}{\partial y}\frac{\partial y}{\partial x}\frac{\partial x}{\partial w}\\ & =f^{\prime }(y)f^{\prime }(x)f^{\prime }(w)\text{公式1}\\ & =f^{\prime }(f(f(w)))f^{\prime }(f(w))f^{\prime }(w)\text{公式2}\end{array}\end{array}$
    • 公式1：
      • 建议我们采用的实现方式是，仅计算$f(w)$的值一次并将它存储在变量$x$中。
      • 这是反向传播算法所采用的方法。
    • 公式2：
      • 提供了一种替代方法，其中子表达式$f(w)$出现了不止一次。
      • 在替代方法中，每次只在需要时重新计算$f(w)。
      • 当存储这些表达式的值所需的存储较少时，公式2的反向传播方法显然是较优的，因为它减少了运行时间。
      • 然而，公式2也是链式法则的有效实现，并且当存储受限时它是有用的。

• 上图给出了一个例子来说明这些重复的子表达式是如何出现的。在某些情况下，计算两次相同的子表达式纯粹是浪费。在复杂图中，可能存在指数多的这种计算上的浪费，使得简单的链式法则不可实现。在其他情况下，计算两次相同的子表达式可能是以较高的运行时间为代价来减少内存开销的有效手段。

• 我们首先给出一个版本的反向传播算法，它指明了梯度的直接计算方式（算法2以及相关的正向计算的算法1，按照它实际完成的顺序并且递归地使用链式法则。可以直接执行这些计算或者将算法的描述视为用于计算反向传播的计算图的符号表示。然而，这些公式并没有明确地操作和构造用于计算梯度的符号图。这些公式在后面的内容中给出，其中我们还推广到了包含任意张量的节点。

• 首先考虑描述如何计算单个标量 $u^{(n)}$（例如训练样例上的损失函数）的计算图。

  • 我们想要计算这个标量对$n_i$个输入节点$u^{(1)}$到$u^{(n_i)}$的梯度。
  • 换句话说，我们希望对所有的 i ∈ { 1 , 2 , … , n i } i\in\{1,2,\dots,n_i\} i∈{1,2,…,ni​}，计算$\frac{\partial u^{(n)}}{\partial u^{(i)}}$。
  • 在用反向传播计算梯度来实现参数的梯度下降时， $u^{(n)}$将对应单个或者小批量实例的代价函数，而$u^{(1)}$ 到$u^{(n_i)}$则对应于模型的参数。

• 我们将假设图的节点已经以一种特殊的方式被排序，使得我们可以一个接一个地计算他们的输出，从$u^{(n_i+1)}$开始，一直上升到$u^{(n)}$。如算法1中所定义的，每个节点$u^{(i)}$与操作$f^{(i)}$相关联，并且通过对该函数求值得到：$u^{(i)}=f({\mathbb{A}}^{(i)})$，其中${\mathbb{A}}^{(i)}$是$u^{(i)}$所有双亲节点的集合。

• 算法1

  ---

  计算将$n_i$个输入$u^{(1)}$到$u^{(n_i)}$映射到一个输出$u^{(n)}$的程序。
  这定义了一个计算图，其中每个节点通过将函数$f^{(i)}$应用到变量集合${\mathbb{A}}^{(i)}$上来计算$u^{(i)}$的值，${\mathbb{A}}^{(i)}$包含先前节点$u^{(j)}$的值满足$j<i$且$j\in Pa(u^{(i)})$。
  计算图的输入是向量$\mathbf{x}$，并且被分配给前$n_i$个节点$u^{(1)}$到$u^{(n_i)}$。
  计算图的输出可以从最后一个节点$u^{(n)}$读出。

  ---

  伪代码：
  f o r i = 1 , … , n i d o u ( i ) ← x i e n d f o r f o r i = n i + 1 , … , n d o A ( i ) ← { u ( j ) ∣ j ∈ P a ( u ( i ) ) } u ( i ) ← f ( i ) ( A ( i ) ) e n d f o r r e t u r n u ( n ) \bold{for}\quad i=1,\dots,n_i \quad \bold{do}\\ \qquad u^{(i)} \gets x_i\\ \bold{end}\quad\bold{for}\\ \bold{for}\quad i=n_i+1,\dots,n \quad \bold{do}\\ \qquad \mathbb{A}^{(i)} \gets \{u^{(j)} \mid j\in Pa(u^{(i)})\}\\ \qquad u^{(i)} \gets f^{(i)}(\mathbb{A}^{(i)})\\ \bold{end}\quad\bold{for}\\ \bold{return}\quad u^{(n)} fori=1,…,ni​dou(i)←xi​endforfori=ni​+1,…,ndoA(i)←{u(j)∣j∈Pa(u(i))}u(i)←f(i)(A(i))endforreturnu(n)

  ---

• 算法1说明：

  • 算法1详细说明了前向传播的计算，我们可以将其放入图$\mathcal{G}$中。
  • 为了执行反向传播，我们可以构造一个依赖于$\mathcal{G}$并添加额外一组节点的计算图。这形成了一个子图$\mathcal{B}$，它的每个节点都是$\mathcal{G}$的节点。
  • $\mathcal{B}$中的计算顺序完全相反，而且$\mathcal{B}$的每个节点计算导数$\frac{\partial u^{(n)}}{\partial u^{(i)}}$与前向图中的节点$u^{(i)}$相关联。
  • 这通过对标量输出$u^{(n)}$使用链式法则来完成：$\frac{\partial u^{(n)}}{\partial u^{(j)}}=\sum _{i:j\in Pa(u^{(i)})}\frac{\partial u^{(n)}}{\partial u^{(i)}}\frac{\partial u^{(i)}}{\partial u^{(j)}}$。注：在算法2中详细说明

• 子图$\mathcal{B}$恰好包含每一条对应着$\mathcal{G}$中从节点$u^{(j)}$到节点$u^{(i)}$的边。从节点$u^{(j)}$到节点$u^{(i)}$的边对应着计算$\frac{\partial u^{(i)}}{\partial u^{(j)}}$。

• 另外，对于每个节点都要执行一个内积，内积的一个因子是对于$u^{(j)}$孩子节点$u^{(i)}$的已经计算的梯度，另一个因子是对于相同孩子节点$u^{(i)}$的偏导数$\frac{\partial u^{(i)}}{\partial u^{(j)}}$组成的向量。

• 总而言之，执行反向传播所需的计算量与$\mathcal{G}$中的边的数量成比例，其中每条边的计算包括计算偏导数（节点关于它的一个双亲节点的偏导数）以及执行一次乘法和一次加法。下面，我们将此分析推广到张量值节点，这只是在同一节点中对多个标量值进行分组并能够更有效的实现。

• 反向传播算法被设计为减少公共子表达式的数量而不考虑存储的开销。

  • 具体来说，它执行了图中每个节点一个$\text{Jacobi}$乘积的数量的计算。
  • 这可以从算法2中看出，反向传播算法访问了图中的节点$u^{(j)}$到节点$u^{(i)}$ 的每条边一次，以获得相关的偏导数$\frac{\partial u^{(i)}}{\partial u^{(j)}}$。
  • 反向传播因此避免了重复子表达式的指数爆炸。然而，其他算法可能通过对计算图进行简化来避免更多的子表达式，或者也可能通过重新计算而不是存储这些子表达式来节省内存。
  • 我们将在描述完反向传播算法本身后再重新审视这些想法。

全连接MLP中反向传播算法的计算

• 为了阐明反向传播的上述定义，让我们考虑一个与全连接的多层MLP相关联的特定图。
• 算法3首先给出了前向传播，它将参数映射到与单个训练样例（输入，目标）($\mathbf{x},\mathbf{y}$)相关联的有监督损失函数$L(\hat{\mathbf{y}},\mathbf{y})$，其中$\hat{\mathbf{y}}$是当$\mathbf{x}$提供输入时神经网络的输出。
• 算法4随后说明了将反向传播应用于改图所需的相关计算。
• 算法3和算法4是简单而直观的演示。然而，它们专门针对特定的问题。
• 现在的软件实现基于之后符号到符号的导数中描述的一般形式的反向传播，它可以通过明确地操作用于表示符号计算的数据结构，来适应任何计算图。

符号到符号的导数

• 代数表达式和计算图都对符号 (symbol) 或不具有特定值的变量进行操作。这些代数或者基于图的表达式被称为符号表示 (symbolic representation)。当我们实际使用或者训练神经网络时，我们必须给这些符号赋值。我们用一个特定的数值 (numeric value) 来替代网络的符号输入$\mathbf{x}$，例如$[1.2,3,765,-1.8{]}^{\top }$。

• 一些反向传播的方法采用计算图和一组用于图的输入的数值，然后返回在这些输入值处梯度的一组数值。我们将这种方法称为“符号到数值”的微分。这种方法用在诸如 Torch(Collobert et al., 2011b) 和 Caffe(Jia, 2013) 之类的库中。

• 另一种方法是采用计算图以及添加一些额外的节点到计算图中，这些额外的节点提供了我们所需导数的符号描述。这是 Theano(Bergstra et al., 2010b; Bastien et al., 2012b) 和 TensorFlow(Abadi et al., 2015) 采用的方法。

• 例如，使用符号到符号的方法计算导数的示例
  

• 说明：

  • 使用符号到符号的方法计算导数的示例。在这种方法中，反向传播算法不需要访问任何实际的特定数值。相反，它将节点添加到计算图中来描述如何计算这些导数。
  • 通用图形求值引擎可以在随后计算任何特定数值的导数。
  • 左图：在这个例子中，我们从表示$z=f(f(f(w)))$的图开始。
  • 右图：我们运行反向传播算法，指导它构造表达式$\frac{\partial z}{\partial w}$对应的图。在这个例子中，我们不解释反向传播算法如何工作。我们目的只是说明想要的结构是什么：具有导数的符号描述的计算图。

• 上图给出了该方法如何工作的一个例子。这种方法的主要优点是导数可以使用与原始表达式相同的语言来描述。因为导数只是另外一张计算图，可以再次运行反向传播，对导数再进行求导以得到更高阶的导数。高阶导数的计算在高阶微分中描述。

• 我们将使用后一种方法，并且使用构造导数的计算图的方法来描述反向传播算法。图的任意子集后来都可以使用特定的数值来求值。这允许我们避免完全指明每个操作应该在何时计算。相反，通用的图计算引擎只要当一个节点的父节点的值都可用时就可以进行求值。

• 基于符号到符号的方法的描述包含了符号到数值的方法。符号到数值的方法可以理解为执行了与符号到符号的方法中构建图的过程中完全相同的计算。关键的区别是符号到数值的方法不会显示出图形。

一般化的反向传播

• 反向传播算法非常简单。

• 为了计算某个标量$z$对图中它的一个祖先$\mathbf{x}$的梯度，我们首先观察到对$z$的梯度由$\frac{\partial z}{\partial z}=1$给出。我们然后可以计算对图中$z$的操作的$\text{Jacobi}$矩阵。我们继续乘以$\text{Jacobi}$矩阵，以这种方式向后穿过图，直到我们到达$\mathbf{x}$。对于从$z$触发可以经过两个或更多路径向后行进而到达的任意节点，我们简单的对该节点来自不同路径上的梯度进行求和。

• 算法2

  ---

  反向传播算法的简化版本，用于计算$u^{(n)}$对图中变量的导数。
  这个示例旨在通过演示所有变量都是标量的简化情况来进一步理解反向传播算法，这里我们 希望计算关于$u^{(1)},\dots ,u^{(n)}$的导数。这个简化版本计算了关于图中所有节点的导数。
  假定与每条边相关联的偏导数计算需要恒定的时间的话，该算法的计算成本与图中边的数量成比例。
  这与前向传播的计算次数具有相同的阶。每个$\frac{\partial u^{(i)}}{\partial u^{(j)}}$的父节点$u^{(j)}$的函数，从而将前向图的节点链接到反向传播图中添加的节点。

  ---

  伪代码：
  运行前向传播(算法1)以获得网络激活
  初始化grad_table，是一种存储计算过的导数的数据结构
  $\text{grad\_table}[u^{(n)}]$是存储$\frac{\partial u^{(n)}}{\partial u^{(i)}}$的计算值
  grad_table [ u ( n ) ] ← 1 f o r j = n − 1 down to 1 d o The next line computes ∂ u ( n ) ∂ u ( j ) = ∑ i : j ∈ P a ( u ( i ) ) ∂ u ( n ) ∂ u ( i ) ∂ u ( i ) ∂ u ( j ) using stored values: grad_table [ u ( j ) ] ← ∑ i : j ∈ P a ( u ( i ) ) grad_table [ u ( i ) ] ⋅ ∂ u ( i ) ∂ u ( j ) e n d f o r r e t u r n { grad_table [ u ( i ) ] ∣ i = 1 , … , n i } \text{grad\_table}[u^{(n)}] \gets 1\\ \bold{for}\quad j=n-1 \quad\text{down to}\quad 1 \quad \bold{do}\\ \qquad \text{The next line computes}\quad \displaystyle\frac{\partial u^{(n)}}{\partial u^{(j)}}=\sum_{i:j\in Pa(u^{(i)})} \frac{\partial u^{(n)}}{\partial u^{(i)}} \frac{\partial u^{(i)}}{\partial u^{(j)}} \quad\text{using stored values:} \\ \qquad \text{grad\_table}[u^{(j)}] \gets \sum_{i:j\in Pa(u^{(i)})} \text{grad\_table}[u^{(i)}] \cdot \frac{\partial u^{(i)}}{\partial u^{(j)}}\\ \bold{end}\quad\bold{for} \\ \bold{return}\quad \{\text{grad\_table}[u^{(i)}]\mid i=1,\dots,n_i\} grad_table[u(n)]←1forj=n−1down to1doThe next line computes∂u(j)∂u(n)​=i:j∈Pa(u(i))∑​∂u(i)∂u(n)​∂u(j)∂u(i)​using stored values:grad_table[u(j)]←i:j∈Pa(u(i))∑​grad_table[u(i)]⋅∂u(j)∂u(i)​endforreturn{grad_table[u(i)]∣i=1,…,ni​}

  ---

总结

反向传播算法和自动微分技术是神经网络训练过程中不可或缺的组成部分。它们通过高效地计算梯度，使得神经网络的参数优化成为可能。反向传播算法利用链式法则，通过反向传播误差信号来逐层调整网络参数，而自动微分技术则通过构建计算图来自动完成这一复杂的计算过程。这些技术的结合，极大地简化了神经网络的训练过程，提高了模型的训练效率和性能。

本章涉及知识点参考往期内容

应用数学与机器学习基础 - 线性代数篇
深度网络现代实践 - 深度前馈网络之基于梯度的学习篇