深度前馈网络（四）

我们考虑一个与全连接多层感知机相关联的特定图，下面第一个算法首先给出了前向传播，它将参数映射到与单个训练样本 ( x , y ) (x, y) (x,y)（输入，目标）相关联的监督损失函数 L ( y ^ , y ) L(hat {y}, y) L(y^​,y)，其中，戴帽的 y y y是神经网络在得到输入 x x x后的实际输出。下面第二个算法说明了将反向传播应用于该图所需要的相关计算。

首先讨论第一个算法，即典型深度神经网络中的前向传播和代价函数的计算。为了获得总代价 J J J，损失函数 L ( y ^ , y ) L(hat {y}, y) L(y^​,y)可以加上正则项 Ω ( θ ) Omega (theta ) Ω(θ)，其中， θ theta θ包含所有的权重和偏执组成的参数。为了简单起见，该算法仅仅演示使用单个输入样本 x x x，实际上应该是小批量的输入。另外，假设网络深度是 l l l，则模型的权重矩阵是： W ( i ) , i ∈ { 1 , ⋯   , l } W^{(i)}, i in left { 1, cdots , l right } W(i),i∈{1,⋯,l}，模型的偏执参数是： b ( i ) , i ∈ { 1 , ⋯   , l } b^{(i)}, i in left { 1, cdots , l right } b(i),i∈{1,⋯,l}，那么，该算法如下：

1. 利用输入进行初始化： h ( 0 ) = x h^{(0)} = x h(0)=x。
2. 遍历网络深度 k = 1 , ⋯   , l k = 1, cdots , l k=1,⋯,l进行下面的计算：
   a ( k ) = b ( k ) + W ( k ) h k − 1 a^{(k)} = b^{(k)} + W^{(k)}h^{k-1} a(k)=b(k)+W(k)hk−1
   h ( k ) = f ( a ( k ) ) h^{(k)} = f(a^{(k)}) h(k)=f(a(k))
3. 得到神经网络的输出： y ^ = h ( l ) hat {y} = h^{(l)} y^​=h(l)。
4. 最后获得总代价： J = L ( y ^ , y ) + λ Ω ( θ ) J = L(hat {y}, y) + lambda Omega (theta ) J=L(y^​,y)+λΩ(θ)

接着讨论第二个算法，该算法说明了如何计算 J J J关于参数 W W W和 b b b的梯度，这是上一个算法的反向计算。它不止使用了输入 x x x和目标 y y y，该计算对每一层 k k k都产生了对激活函数 a ( k ) a^{(k)} a(k)的梯度，从输出层开始，一直向后计算，直到一个隐藏层。这些梯度可以看作对每层的输出应该如何调整从而减小误差的指导，根据这些梯度可以获得对每层参数的梯度。权重和偏置上的梯度可以立即用于随机梯度更新的一部分（梯度算出来后即可执行更新），或者可以与其它基于梯度的优化算法一起使用。算法如下：

1. 在前向计算完成后，首先计算顶层的梯度： g ⟵ ∇ y ^ J = ∇ y ^ L ( y ^ , y ) mathcal{g} longleftarrow nabla _{hat{y} } J = nabla _{hat{y}}L(hat{y} , y) g⟵∇y^​​J=∇y^​​L(y^​,y)。
2. 遍历各层： k = l , l − 1 , ⋯   , 1 k = l, l-1, cdots , 1 k=l,l−1,⋯,1，进行下面的计算：
   首先， 将关于每一层输出的梯度转换为非线性激活输入前的梯度（如果 f f f是逐元素的，则逐元素的相乘），如下：
   g ← ∇ a ( k ) J = g   ⊙   f ′ ( a ( k ) ) mathcal{g} gets nabla _{a^{(k)}} J = mathcal{g} odot f{}' (a^{(k)}) g←∇a(k)​J=g ⊙ f′(a(k))
   接着，计算关于权重和偏置的梯度（如有必要的话，还应该包括正则项），如下：
   ∇ b ( k ) J = g + λ ∇ b ( k ) Ω ( θ ) nabla _{b^{(k)}} J = mathcal {g} + lambda nabla _{b^{(k)}} Omega (theta ) ∇b(k)​J=g+λ∇b(k)​Ω(θ)
   ∇ W ( k ) J = g ( h ( k − 1 ) ) T + λ ∇ W ( k ) Ω ( θ ) nabla _{W^{(k)}} J = mathcal{g} (h^{(k-1)} )^T + lambda nabla _{W^{(k)}} Omega (theta ) ∇W(k)​J=g(h(k−1))T+λ∇W(k)​Ω(θ)
   最后，计算更新关于下一更低的隐藏层的传播梯度，如下：
   g ← ∇ h ( k − 1 ) J = ( W ( k ) ) T g mathcal {g} gets nabla _{h^{(k-1)}} J = (W^{(k)})^T mathcal{g} g←∇h(k−1)​J=(W(k))Tg

代数表达式和计算图都是对符号（symbol），或者不具有特定值的变量进行操作，这些代数表达式和基于图的表达式被称为符号表示。当实际使用或者训练神经网络时，我们必须给这些符号赋特定的值，比如用一个特定的数值（例如 [ 1.2 , 3 , 734 , − 13 ] T [1.2, 3, 734, -13]^T [1.2,3,734,−13]T）来替代网络的符号（例如输入 x T x^T xT）。

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

另外一种方法是，采用计算图，以及添加一些额外的节点到计算图中，这些额外的节点提供 了我们所需的导数的符号描述，我们将这种方法称为符号到符号的微分（自己命名）。在这种方法中，反向传播算法不需要访问任何实际的特定数值，相反，它将节点添加到计算图中来描述如何计算这些导数，所以，可以通过图形求值引擎可以计算任何特定数值的导数。换言之，这种方法里面，导数可以使用与原始表达式相同的语言来描述。

我们将使用后一种方法，并且将通过使用构造导数的计算图的方法来描述反向传播算法。

为了计算某个标量 z z z关于计算图中它的一个祖先 x x x（向量）的梯度。首先，观察到它关于 z z z的梯度由 d z d z = 1 frac{mathrm{d} z}{mathrm{d} z} = 1 dzdz​=1给出。然后，我们可以计算对图中的 z z z的每个父节点的梯度，通过现有的梯度乘以产生 z z z的操作的雅可比。我们可以继续乘以雅可比，以这种方式穿过图，直到到达 x x x。对于从 z z z出发，可以经过两个或者更多路径向后行进，从而到达任意节点，我们简单的对该节点来自不同路径的梯度进行求和。

更正式地，图 G mathcal{G} G中的每个节点对应着一个变量，为了实现最大的一般化，我们将这个变量描述为一个张量 V mathsf{V} V，同时，我们假设每个变量 V mathsf{V} V和下列子程序相关联：

• get_operation( V mathsf{V} V)：该程序返回用于计算 V mathsf{V} V的操作，代表了在计算图中流入 V mathsf{V} V的边。
• get_consumers( V , G mathsf{V}, mathcal{G} V,G)：该程序返回一组变量，是计算图 G mathcal{G} G中 V mathsf{V} V的子节点们。
• get_inputs( V , G mathsf{V}, mathcal{G} V,G)：该程序返回一组变量，是计算图 G mathcal{G} G中 V mathsf{V} V的父节点们。

每个操作op也和bprop操作相关联。通常，为了表示 z z z关于张量 X mathsf{X} X的梯度，我们记为： ∇ X z nabla _{mathsf{X} } z ∇X​z。我们使用 i i i来表示张量的完整的索引元组，比如，对于所有可能的元组 i i i，我们有 ( ∇ X z ) i = ∂ z ∂ X i (nabla _{mathsf{X}} z) _i = frac{partial z}{partial mathsf{X}_i } (∇X​z)i​=∂Xi​∂z​，这种表示方式和向量中的索引形式完全一样。通过这种方法，我们可以写出张量： Y = g ( X ) ,   z = f ( Y ) mathsf{Y} = mathcal{g}(mathsf{X} ), z = f(mathsf{Y}) Y=g(X), z=f(Y)的链式法则：
∇ X z = ∑ j ( ∇ X Y j ) ∂ z ∂ Y j nabla _{mathsf{X}} z = sum_{j}^{} ({color{Green} nabla _{mathsf{X}} mathsf{Y}_j } ) frac{partial z}{partial mathsf{Y}_j} ∇X​z=j∑​(∇X​Yj​)∂Yj​∂z​回到bprop操作上来，该操作可以计算上式所描述的雅可比向量积，这是反向传播算法能够实现很大通用性的原因，每个操作负责了解如何通过它参与的图中的边来反向传播。另外，反向传播算法并不需要知道任何微分法则，这由具体的研究数据自己定义，但是，在实际计算的时候，总得确定一个具体的微分法则，比如是矩阵的微分法则，还是标量的微分法则等等。所以，这里的bprop操作就是一个求微分的操作，即op.bprop(inputs, X mathsf{X} X, G mathsf{G} G)操作必须返回：
∑ j ( ∇ X o p . f ( i n p u t s ) j ) G j sum_{j}^{} (nabla _{mathsf{X}} {color{Red} op.f(inputs)_j} ) mathsf{G}_j j∑​(∇X​op.f(inputs)j​)Gj​这里，inputs是提供给操作的一组输入，op.f是操作实现的数学函数， X mathsf{X} X是输入， G mathsf{G} G是操作对于输出的梯度。
op.bprop方法应该总是假装它的输入彼此不同，即使它们不是。反向传播算法的软件通常提供操作和它的bprop方法。

下面介绍反向传播算法最外围的骨架，这部分主要做简单的设置和清理工作，大部分重要的工作在另外一个程序build_grid中，后续介绍：

已知： T mathbb{T} T是需要计算梯度的目标变量集合， G mathcal{G} G是计算图， z z z是需要做微分的变量。
假设： G ′ mathcal{G} ^prime G′是 G mathcal{G} G剪枝后的计算图，其中仅包括 z z z的祖先以及 T mathbb{T} T中节点的后代。
算法流程：

1. 初始化一个grad_table，它是关联张量和对应导数的数据结构：
   g r a d _ t a b l e [ z ] ← 1 grad_table[z] gets 1 grad_table[z]←1
2. 遍历 T mathbb{T} T中的元素 V mathsf{V} V，执行以下算法：
   build_grad( V mathsf{V} V, G mathcal{G} G, G ′ mathcal{G}^{prime} G′, g r a d _ t a b l e grad_table grad_table)
3. 最后返回 g r a d _ t a b l e grad_table grad_table

我们呢这里简单的讨论一下反向传播算法的计算成本问题。首先，我们假设每个操作的执行都有相同开销，那么可以依据执行操作的数量来分析计算成本。注意，这里我们将一个操作记为计算图的基本单位，而不在意它实际有多少数学或者计算机计算步骤。在具有n个节点的计算图中计算梯度，永远不会超过 O ( n 2 ) O(n^2) O(n2)的时间和空间复杂度。在最坏的情况下，前向传播的步骤将在原始图的全部n个节点上运行，而反向传播算法将在原始图的每一条边添加一个雅可比向量积，可以用 O ( 1 ) O(1) O(1)个节点来表达。因为计算图是有向无环图，所以，它最多有 O ( n 2 ) O(n^2) O(n2)个边，实际上，大多数神经网络的代价函数大致是链式结构的，使得反向传播只有 O ( n ) O(n) O(n)的成本。
我们可以将反向传播算法看成一种表填充算法，利用存储中间结果 ∂ u ( n ) ∂ u ( i ) frac{partial u_{(n)}}{partial u_{(i)}} ∂u(i)​∂u(n)​​来对表进行填充，图中的每一个节点对应着表中的一个位置，这个位置存储对该节点的梯度，通过顺序填充这些表的条目，反向传播算法避免了重复计算许多公共子表达式，这种策略有时候被称为动态规划。

最后，再介绍一下反向传播算法的内循环子程序 build_grad( V mathsf{V} V, G mathcal{G} G, G ′ mathcal{G}^{prime} G′, g r a d _ t a b l e grad_table grad_table)，具体算法如下：

已知： V mathsf{V} V是应该被加到 G mathcal{G} G和 g r a d _ t a b l e grad_table grad_table的变量， G mathcal{G} G是要被修改的图， G ′ mathcal{G}^{prime} G′是根据参与梯度的节点 G mathcal{G} G的受限图， g r a d _ t a b l e grad_table grad_table是将节点映射到对应梯度的数据结构。
算法流程：

1. 如果 V mathsf{V} V已经在 g r a d _ t a b l e grad_table grad_table中，则直接返回 g r a d _ t a b l e [ V ] grad_table[mathsf{V}] grad_table[V]。
2. 初始化变量 i i i，如下：
   i ← 1 i gets 1 i←1
3. 遍历get_consumers( V mathsf{V} V, G ′ mathcal{G}^ prime G′)得到的全部元素，其中任意一个元素是 C mathsf{C} C，则做如下更新：
   o p ← g e t _ o p e r a t i o n ( C ) op gets get_operation(mathsf{C}) op←get_operation(C)
   D ← b u i l d _ g r i d ( C , G , G ′ , g r a d _ t a b l e ) mathsf{D} gets build_grid(mathsf{C}, mathcal{G}, mathcal{G}^prime, grad_table) D←build_grid(C,G,G′,grad_table)
   G ( i ) ← o p . b p r o p ( g e t _ i n p u t s ( C , G ′ ) , V , D ) mathsf{G}^{(i)} gets op.bprop(get_inputs(mathsf{C}, mathcal{G}^prime), mathsf{V}, mathsf{D}) G(i)←op.bprop(get_inputs(C,G′),V,D)
   i ← i + 1 i gets i + 1 i←i+1
4. 更新 G mathsf{G} G，如下：
   G ← ∑ i G ( i ) mathsf{G} gets {textstyle sum_{i}^{} mathsf{G}^{(i)} } G←∑i​G(i)
5. 更新梯度表，如下：
   g r a d _ t a l b e [ V ] = G grad_talbe[mathsf{V}] = mathsf{G} grad_talbe[V]=G
6. 插入 G mathsf{G} G，以及将其生成到 G mathcal{G} G中的操作。
7. 最后返回 G mathsf{G} G的值。

正如前面提到的，我们将操作的定义限制为返回单个张量的函数。实际上，大多数软件支持返回多个张量的操作，这样效率更高。

另外，反向传播中经常涉及到将许多张量加在一起，这里牵扯到内存消耗问题，在朴素方法中，将分别计算这些张量中的每一个，然后对这些张量进行求和，这里有过高的存储瓶颈，可以通过保持一个缓冲器，并且在计算时将每个值加到该缓冲器，从而避免该瓶颈。

其他诸如数据类型、具体微分的定义等问题需要结合具体项目认真考量。

深度学习在一定程度上发展了自己关于如何进行微分的文化态度，一般来说，自动微分领域是关心如何以算法方式计算导数。

这里描述的反向传播算法只是自动微分的一种方法，它是一种称为反向模式累加的更广泛类型的技术的特殊情况，其他方法以不同的顺序来计算链式法则的子表达式。确定一种计算的顺序使得计算开销最小，是困难的事情，找到计算梯度的最优操作序列是NP完全问题，在这种意义下，可能需要将代数表达式简化为它们最廉价的形式。

当前向图具有单个输出节点，兵器每个偏导数 ∂ u ( i ) ∂ u ( j ) frac{partial u^{(i)}}{partial u^{(j)}} ∂u(j)∂u(i)​都具有恒定的计算量，反向传播算法保证梯度计算的计算数目和前向传播的是同一个量级，总的计算量和边的数目有关系。但是，可能通过对反向传播算法构建的计算图进行简化来减少这些计算量，并且这是NP完全问题。

之前我们的反向传播仅仅用于计算标量的梯度，但是，可以拓展到计算雅可比矩阵（该雅可比矩阵要么来自于图中的 k k k个不同的标量节点，要么来源于包含 k k k个值的张量值节点）。朴素的是实现可能需要 k k k倍的计算：对于原始前向图中的每个内部标量节点，计算 k k k个梯度。当图的输出数目大于输入的数目时，有时候更偏向于使用另外一种形式的自动微分，称为前向模式累加。

前向模式和后向模式类似于矩阵的左乘和右乘，例如：
A B C D ABCD ABCD其中的矩阵可以认为是雅可比矩阵。如果 D D D是列向量，而 A A A是有很多行的矩阵，这对应于一幅具有单个输出和多个输入的图，并且从最后开始乘，反向进行，只要“矩阵-向量”的乘机，这对应反向模式。相反，从左边开始乘，将涉及一系列的“矩阵-矩阵”乘积，计算代价昂贵。然而，如果 A A A的行数小于 D D D的列数，则从左到右计算更为简便，这对应于前向模式。

一些软件框架支持使用高阶导数，这些库使用一种数据结构来描述要被微分的原始函数，同时，使用相同的数据结构来描述这个函数的导数表达式，这样，符号微分机制就可以应用于导数，从而产生高阶导数。