当前位置：首页 > news >正文

反向传播和其他微分算法

news 来源：原创 2024/5/18 1:20:41

当我们使用前馈神经网络接收输入 $x$ ，并产生输出 $\tiny \hat{y}$ 时，信息通过网络前向流动。输入x并提供初始信息，然后传播到每一层的隐藏单元，最终产生输出 $\tiny \hat{y}$ 。这称之为前向传播。在训练过程中，前向传播可以持续前向直到它产生一个标量代价函数 $\tiny J(\theta)$ 。反向传播算法，经常简称为backprop，允许来自代价函数的信息通过网络向后流动，以便计算梯度。

计算梯度的解析表达式是很直观的，但是数值化地求解这样的表达式在计算上的代价可能很大。反向传播算法使用简单和廉价的程序来实现这个目标。反向传播这个属于经常被无解为用于多层神经网络。实际上，反向传播仅指用于计算梯度的方法，而另一种算法，例如随机梯度下降，使用该梯度来进行学习。此外，反向传播算法经常被误解为仅适用于多层神经网络，但是原则上它可以计算任何函数的导数(对于一些函数，正确的响应是报告函数中的导师是未定义的)。特别地，我们会描述如何计算一个任意函数f的梯度 $\tiny \bigtriangledown _xf(x,y)$ ，其中x是一组变量，我们需要它们的导数，而y是函数的另外一组输入变量，但我们并不需要它们的导数。在学习算法中，我们最常需要的梯度是代价函数关于参数的梯度，即 $\tiny \bigtriangledown _{\theta}f(x,y)$ ，其中x是一组变量，我们需要它们的导数，而y是函数的另外一组输入变量，但我们并不需要它们的导数。在学习算法中，我们最常需要的梯度是代价函数关于参数的梯度，即 $\tiny \bigtriangledown _{\theta}J(\theta)$ 。许多机器学习任务需要计算其他导数，来作为学习过程的一部分，或者用来分析学得的模型。反向传播算法也适用于这些任务，不局限于计算代价函数关于参数的梯度。通过在网络中传播信息来计算导数的想法非常普遍，它还可以用于计算诸如多输出函数f的Jacobian的值。我们这里描述的是最常用的情况，其中 $\tiny f$ 只有两个输出。

一、计算图

到目前为止，我们已经用相对非正式的图形语言讨论了神经网络。为了更精确地描述反向传播算法，使用更精确的计算图(computational graph)语言是很有帮助的。将计算图形式化为图形的方法有很多。这里，我们使用图中的每一个节点来表示一个变量。变量可以是标量、向量、矩阵、张量或者甚至是另一类的变量。为了形式化图形，我们还需引入操作这一概念。操作时指一个或多个变量的简单函数。图形语言伴随着一组被允许的操作。我们可以通过将多个操作复合在一起来描述更为复杂的变量。为了不失一般性，我们定义一个操作仅返回单个输出变量。这并没有失去一般性，是因为输出变量可以有多个条目，例如向量。反向传播的软件实现通常支持具有多个输出的操作，但是我们在描述中避免这种情况，因为它引入了对概念理解不重要的许多额外细节。

(a)使用乘操作计算z=xy的图。

(b)用于逻辑预测 $\tiny y=\sigma (x^Tw+b)$ 的图。一些中间表达式在代数表达式中没有名称，但在图形中却需要。我们需要简单地将第i个这样的变量命名为 $\tiny u^{(i)}$

(c)表达式 $\tiny H=max\{0,xW+b\}$ 的计算图，在给定包含小批量输入数据的设计矩阵X时，它计算整流线性单元激活的设计矩阵H。

(d)示例(a)和(c)对每个变量最多只实施一个操作，但是对于变量实施多个操作也是可能的。这里我们展示一个计算图，它对线性回归模型的权重w实施多个操作。这个权重不仅用于预测y，也用于权重衰减惩罚 $\tiny \lambda\sum_iw^2_i$

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

二、微分中的链式法则

微分中的链式法则(为了不与概率中的链式法则相混淆)用于计算复合函数的导数。反向传播是一种计算链式法则的算法，使用高效的特定运算顺序。

设x是实数，f和g是从实数映射到实数的函数。假设y=g(x)并且z=f(g(x))=f(y)。那么链式法则是说

$\tiny \frac{\partial z}{\partial x}=\frac{\partial z}{\partial y}\frac{\partial y}{\partial x}$

我们可以将这种标量情况进行扩展。假设 $\tiny x\in R^m$ ， $\tiny y\in R^n$ ，g是从 $\tiny R^m$ 到 $\tiny R^n$ 的映射，f是从 $\tiny R^n$ 到 $\tiny R$ 的映射。如果 $\tiny y=g(x)$ 并且 $\tiny z=f(y)$ ，那么

$\tiny \frac{\partial z}{\partial x_i}=\sum_j\frac{\partial z}{\partial y_j}\frac{\partial y_j}{\partial x_i}$

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

$\tiny \bigtriangledown_x z=(\frac{\partial y}{\partial x})^T\bigtriangledown _yz$

这里 $\tiny \frac{\partial y}{\partial x}$ 是的nxm的Jacobian矩阵。

从这里我们看到，变量x的梯度可以通过Jacobian矩阵 $\tiny \frac{\partial y}{\partial x}$ 和梯度 $\tiny \bigtriangledown _y z$ 相乘来得到。反向传播算法由图中每一个这样的Jacobian梯度的乘积操作所组成。通常我们将反向传播算法应用于任意维度的张量，而不仅仅用于向量。从概念上讲，这与使用向量的反向传播完全相同。唯一的区别是如何将数字排列成网格以形成张量。我们可以想象，在运行反向传播之前，将每个张量变平为一个向量，计算一个向量值梯度，然后将该梯度重新构造成一个张量。从这种重新排列的观点上看，反向传播仍然是将Jacobian乘以梯度。

为了表示z关于X的梯度，我们记为 $\tiny \bigtriangledown _X z$ ，就像X是向量一样。X的索引现在有多个坐标------例如，一个3维的张量有3个坐标索引。我们可以通过使用单个变量i来表示完整的索引元组，从而完全抽象出来。对所有可能的元组 $\tiny i$ ，( $\tiny \bigtriangledown _Xz$ )给出 $\tiny \frac{\partial z}{\partial X_i}$ 。这与向量中索引的方式完全一致，( $\tiny \bigtriangledown _xz$ )给出 $\tiny \frac{\partial z}{\partial x_i}$ 。使用这种记法，我们可以写出适用于张量的链式法则。如果 $\tiny Y=g(X)$ 并且 $\tiny z=f(Y)$ ，那么

$\tiny \bigtriangledown _Xz=\sum_j(\bigtriangledown _XY_j)\frac{\partial z}{\partial Y_j}$

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

使用链式法则，我们可以直接写出某个标量关于计算图中任何产生该标量的节点的梯度的代数表达式。然而，实际在计算机中计算该表达式时会引入一些额外的考虑。具体来说许多子表达式可能在梯度的整个表达式中重复若干次。任何计算梯度的程序都需要选择是存储这些子表达式还是重新计算它们几次。下图给出了一个例子说明这些重复的子表达式是如何出现的。在某些元素下，计算两次相同的子表达式纯粹是浪费。在复杂图中，可能存在指数多的这种计算上的浪费，使得简单的链式法则不可实现。在其他情况下，计算两次相同的子表达式可能是以提高的运行时间为代价来减少内存开销的有效手段。

$\tiny \frac{\partial }{\partial x} \\ =\frac{\partial }{\partial x}\frac{\partial }{\partial x}\frac{\partial }{\partial x}\\ =f'(y)f'(x)f'(w)\\ =f'(f'(f(w)))f'(f(w))f'(w)$

我们首先给出了一个版本的反向传播算法，它指明了梯度的直接计算方式，按照它实际完成的顺序并且递归地使用链式法则。我们可以直接执行这些计算或者将算法的藐视视为用于计算反向传播的计算图的符号表示。然而，这些公式并没有明确地操作和构造用于计算梯度的符号图。首先考虑描述如何计算单个标量 $\tiny u^{(n)}$ (例如样本上的损失函数)的计算图。我们想要计算这个标量对 $\tiny n_i$ 个输入节点 $\tiny u^{(1)}$ 到 $\tiny u^{n_i}$ 的梯度。欢聚话说，我们希望对所有的 $\tiny i\in\{ 1,2,...,n_i\}$ 计算 $\tiny \frac{\partial u^{(n)}}{\partial u^{(i)}}$ 。在使用反向传播计算梯度来实现参数的梯度下降时， $\tiny u^{(n)}$ 将对应单个或者小批量实例的代价函数，而 $\tiny u^{(1)}$ 到 $\tiny u^{(n_i)}$ 则对应于规模的参数。

假设图的节点已经以一种特殊的方式被排列，使得我们可以一个接一个地计算他们的输出，从 $\tiny u^{n_i+1}$ 开始，一直升到 $\tiny u^{(n)}$ 。如下列算法所定义的，每个节点 $\tiny u^{(i)}$ 与操作 $\tiny f^{(i)}$ 相关联，并且通过对以下函数求值来得到

$\tiny u^{(i)}=f(A^{(i)})$

其中 $\tiny A^{(i)}$ 是 $\tiny u^{(i)}$ 所有父节点的集合。

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

$\tiny \frac{\partial }{\partial x}=\sum_{i:j\in Pa(u^{(i)})}\frac{\partial u^{(n)}}{\partial u^{(i)}}\frac{\partial u^{(i)}}{\partial u^{(j)}}$

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

for i = 1,..., $\tiny n_i$ do

     $\tiny u^{(i)}\leftarrow x_i$

end for

for i = $\tiny n_i +1$ ,...,n do

     $\tiny A^{(i)}\leftarrow \{ u^{(j)}|j\in Pa(u^{(i)})\}$

     $\tiny u^{(i)}\leftarrow f^{(i)}(A^{(i)})$

end for

return $\tiny u^{(n)}$

子图B恰好包含每一条对应着g中从节点 $\tiny u^{(j)}$ 到节点 $\tiny u^{(i)}$ 的边。从 $\tiny u^{(j)}$ 到 $\tiny u^{(i)}$ 的边对应着计算 $\tiny \frac{\partial u^{(i)}}{\partial u^{(j)}}$ 。另外，对于每个节点都要执行一个内积，内积的一个因子是对于 $\tiny u^j$ 子节点 $\tiny u^{(i)}$ 的已经计算的梯度，另一个因子是对于相同的子节点 $\tiny u^{(i)}$ 的偏导数 $\tiny \frac{\partial u^{(i)}}{\partial u^{(j)}}$ 组成的向量。总而言之，执行反向传播所需的计算量与g中的边的数量成正比，其中每条边的计算包括计算偏导数(节点关于它的一个父节点的偏导数)以及执行一次乘法和一次加法。下面，我们将此分析推广到张量值节点，这只是在同一节点中对多个标量值进行分组并能够更高效的实现。

反向传播算法被设计成减少公共子表达式的数量而不是存储的开销。具体来说，它大约对图中的每个节点执行一个Jacobian乘积。这可以从下列算法中看出，反向传播算法访问了图中的节点 $\tiny u^{(j)}$ 到节点 $\tiny u^{(i)}$ 的每条边一次，以获得相关的偏导数 $\tiny \frac{\partial u^{(i)}}{\partial u^{(j)}}$ 。反向传播因此避免了重复子表达式的指数爆炸。然而，其他算法可能通过对计算图进行简化来避免更多的子表达式，或者也可能通过重新计算而不是存储这些子表达式来节省内存。

运行前向传播获得网络的激活。

初始化grad_table用于存储计算好的导数的数据结构，grad_table将存储 $\tiny \frac{\partial u^{(n)}}{\partial u^{(i)}}$ 计算好的值。

grad_table $\tiny [u^{(n)}]\leftarrow 1$

for j = n-1 down to 1 do

下一行使用存储的值计算 $\tiny \frac{\partial u^{(n)}}{\partial u^{(i)}}=\sum_{i:j\in P\alpha (u^{(i)})}\frac{\partial u^{(n)}}{\partial u^{(i)}} \frac{\partial u^{(i)}}{\partial u^{(j)}}$

grad_table $\tiny [u^{(j)}]\leftarrow \sum_{i:j\in P\alpha(u^{(i)})}$ grad_table $\tiny [u^{(i)}] \frac{\partial u^{(i)}}{\partial u^{(j)}}$

end for

return {grad_table $\tiny [u^{(i)}]|i=1,...,n_i$ }

四、全链接MLP中的反向传播计算

为了阐明反向传播的上述定义，让我们考虑一个域全连接的多层MLP相关联的特定图。下面的算法首先给出了前向传播，它将参数映射到与单个训练样本(输入，目标)(x,y)相关联的监督损失函数 $\tiny L(\hat{y},y)$ ，其中 $\tiny \hat{y}$ 是当x提供输入的神经网络的输出。典型深度神经网络中的前向传播和代价函数的计算。损失函数 $\tiny L(\hat{y},y)$ 取决于输出 $\tiny \hat{y}$ 和目标y。为了获得总代价J，损失函数可以加上正则项 $\tiny \Omega (\theta)$ ，其中 $\tiny \theta$ 包含所有参数(权重和偏置)。

Requires：网络深度，l

Requires： $\tiny W^{(i)}, i\in \{1,...,l\}$

Requires：x，程序的输入

Requires：目标输出

$\tiny h^{(0)}=x$

for k = 1,...,l do

$\tiny a^{(k)}=b^{(k)}+W^{(k)}h^{(k-1)}$

$\tiny h^{(k)}=f(a^{(k)})$

end for

$\tiny \hat{y}=h^{(l)}$

$\tiny J=L(\hat{y},y)+\lambda \Omega (\theta)$

五、符号到符号的导数

代数表达式和计算图都对符号或不具有特定值的变量进行操作。这些代数或者基于图的表达式被称为符号表示。当实际使用或者训练神经网络时，我们必须给这些符号赋特定的值。我们用一个特定的数值来替代网络的符号输入x。

在前向计算完成后，计算顶层的梯度。

$\tiny g\leftarrow \bigtriangledown _{\hat{y}}L(\hat{y},y)$

for k = 1,l-1, ... , 1 do

       讲关于层输出的梯度转换为非线性激活输入前的梯度(如果f是逐元素的，则逐元素地相乘)：

       $\tiny g\leftarrow \bigtriangledown _{a^{k}}J=g\odot f'(a^{(k)})$

      计算权重和偏置的梯度(如果需要的话，还要包括正则项);

      $\tiny \bigtriangledown _{W^{(k)}}J=gh^{(k-1)T}+\lambda\bigtriangledown _{W^{(k)}\Omega (\theta)}$

一些反向传播的方法采用计算图和一组用于图的输入的数值，然后返回在这些输入值处梯度的一组数值。我们将这种方法称为符号到数值的微分。这种方法用在Torch和Caffe的库中。

另一种方法是采用计算图以及添加一些额外的节点到计算图中。这些额外的节点提供了我们所需导数的符号描述。这是Theano和Tensorflow所采用的方法。下图给出了该方法如何工作的一个例子。

这种方法的主要优点是导师可以使用与原始表达式相同的语言来描述。因为导数只是另外一张计算图，我们可以再次运行反向计算，我们可以再次运行反向传播，对导数再进行求导数就能得到更高阶的导数。

六、一般化的反向传播

反向传播算法非常简单。为了计算某个标量z关于图中它的一个祖先x的梯度，首先观察到它关于z的梯度由 $\tiny \frac{\partial z}{\partial z}=1$ 给出。然后，我们可以计算图中z的每个父亲点的梯度，通过现有的梯度乘以产生z的操作的Jacobian。我们继续乘以Jacobian，以这种方式向后穿过图，直到达到x。对于从z出发可以经过两个或更多路径向后行进而达到的任意节点，我们简单地对该节点来自不同路径上的梯度进行求和。更正式地，图g中的每个节点对应着一个变量。为了实现最大的一般化。我们将这个变量描述为一个张量V。张量通常可以具有任意维度，并且包含标量、向量好矩阵。我们假设每个变量V与下列子程序相关联：

get_opreration(V)：它返回用于计算V的操作，代表了在计算图中流入V的边。例如，可能有一个python或者C++的类标书矩阵乘法操作，以及get_operation(V)返回一个指向相应C++类的实例的指针。

get_consumers(V,g)：它返回一组变量，是计算图g中V的父节点。

get_inputs(V,g)：它返回一组变量，是计算图g中V的父节点。

每个操作op也与bprop操作相关联。每个操作负责了解如何通过它参与的图中的边来反向传播。例如，我们可以使用矩阵乘法操作来产生变量C=AB。假设标量z关于C的梯度是G。矩阵乘法操作负责定义两个反向传播规则，每个规则对应于一个输入变量。如果我们调用bprop方法来请求关于A的梯度，那么在给定输出的梯度为G的情况下，矩阵乘法操作的bprop方法必须说明关于A的梯度是 $\tiny GB^T$ 。类似地，如果我们调用bprop方法来请求关于B的梯度，那么矩阵操作负责实现bprop方法并指定希望的梯度是 $\tiny A^TG$ 。反向传播算法本身并不需要知道任何微分法则。它只需要使用正确的参数调用每个操作的bprop方法即可。正式地，op.bprop(inputs,X,G)必须返回

$\tiny \sum_i(\bigtriangledown _Xop.f(inputs)_i)G_i$

这里，inputs是提供给操作的一组输入，op.f是操作实现的数学函数，X是输入，我们想要计算关于它的梯度，G是操作对于输出的梯度。op.bprop方法应该总是假装它的所有输入彼此不同，即使它们不是。例如，如果mul操作传递连个x来计算 $\tiny x^2$ ，op.bprop方法应该仍然返回x作为对于两个输入的函数。反向传播算法后面会将这些变量加起来获得2x，这是x上总的正确的导数。

反向传播算法的软件实现通常提供操作和其bprop方法，所以深度学习软件库的用户能够使用诸如矩阵乘法、指数运算、对数运算等常用操作构建的图进行反向传播。构建反向传播新实现的软件工程师或者需要向现有库函数添加自己的操作的高级用户通常必须手动为新操作推导op.bprop方法。

Require：T，需要计算梯度的目标变量集

Require：g，计算图

Require：z，要微分的变量

令g'为g剪纸后的计算图，其中包括z的祖先以及T中节点的后代。

初始化grad_table，它是关联张量和对用导数的数据结构。

grad_table $\tiny [z]\leftarrow 1$

for V in T do

build_grad(V,g,g',grad_table)

end for

Return grad_table restricted to T

如果我们假设每个操作的执行都有记为计算图的基本单位，它实际上可能包含许多算术运损(例如，我们可能将矩阵乘法视为单个操作)。在具有n个节点的图中计算梯度，将永远不会执行超过 $\tiny O(n^2)$ 个操作，或者存储超过 $\tiny O(n^2)$ 个操作的输出。这里我么是对计算图中的操作进行计数，而不是由底层硬件执行的单独操作，所以重要的是，要记住每个操作的运行时间可能是高度可变的。例如，两个矩阵相乘可能对应着图中的一个单独的操作。但这两个矩阵可能每个都包含上百万个元素。我么可以看到，计算梯度至多需要 $\tiny O(n^2)$ 个操作的输出，因为在最坏的情况下，前向传播的步骤将在原始图的全部n个节点上运行(取决于我们想要计算的值，可能不需要执行整个图)。反向传播算法在原始图的每条边添加一个Jacobian矩阵，可以用O(1)个节点来表达。因为计算图是又向无环图，它至多有的O(n^2)条边。对于实践中常用图的类型，情况会更好。大多数神经网络的代价函数大致是链式结构的，使得反向传播只有O(n)的成本。这远远胜过简单的方法，简单的方法可能需要在指数级的节点上运算。这种潜在的指数级代价可以通过非递归地扩展和重写递归链式法则来看出：

$\tiny \frac{\partial u^{(n)}}{\partial u^{(j)}}=\sum_{path(u^{(\pi _1)},u^{(\pi _2)},...,u^{(\pi _t)})from\pi _1= to \pi_t=n}$

Require V，应该被加到g和grad_table的变量。

Require： g，要修改的图。

Require：g'，根据参与梯度的节点g的受限图。

Require：gard_table，将节点映射到对应梯度的数据结构。

if V is in grad_table then

      Return grad_table[V]

end if

$\tiny i\leftarrow 1$

for C in get_consumers(V,g') do

   op $\tiny \leftarrow$ get_operation(C)

   D $\tiny \leftarrow$ build_grad(C,g,g',grad_table)

   $\tiny G^{(i)}\leftarrow$ op.bprop(get_inputs(C,g'),V,D)

   $\tiny i\leftarrow i+1$

end foe

$\tiny G\leftarrow \sum_i G^{(i)}$

插入G和将其生成到G中的操作

Retuen G

由于节点j到节点n的路径数目可以关于这些路径的长度上的指数地增长，所以上述求和符号中的项数(这些路径的数目)，可能以前向传播图的深度的指数级增长。会产生如此大的成本是因为对于 $\tiny \frac{\partial u^{(i)}}{\partial u^{(j)}}$ ，相同的计算会重复进行很多次。为了避免这种重新计算，我么可以将反向传播看作是一种填充算法，利用存储的中间结果 $\tiny \frac{\partial u^{(i)}}{\partial u^{(j)}}$ 来进行填充。图中的每个节点对应着表中的一个位置，这个位置存储对该节点的梯度。通过顺序填充这些表的条目，反向传播算法避免了重复计算许多公共子表达式，这种表填充策略有时被称为动态规划。