2
雷锋网按：如果对人工智能稍有了解的小伙伴们，或多或少都听过反向传播算法这个名词，但实际上BP到底是什么？它有着怎样的魅力与优势？本文发布于 offconvex.org，作者 Sanjeev Arora与 Tengyu Ma，雷锋网对此进行了编译，未经许可不得转载。
目前网络上关于反向传播算法的教程已经很多，那我们还有必要再写一份教程吗？答案是‘需要’。
为什么这么说呢？我们教员Sanjeev最近要给本科生上一门人工智能的课，尽管网上有很多反向传播算法的教程，但他却找不到一份令他满意的教程，因此我们决定自己写一份关于反向传播算法的教程，介绍一下反向传播算法的历史背景、原理、以及一些最新研究成果。
PS：本文默认读者具备一定的基础知识（如了解梯度下降、神经网络等概念）。
反向传播算法是训练神经网络的经典算法。在20世纪70年代到80年代被多次重新定义。它的一些算法思想来自于60年代的控制理论。
在输入数据固定的情况下、反向传播算法利用神经网络的输出敏感度来快速计算出神经网络中的各种超参数。尤其重要的是，它计算输出f对所有的参数w的偏微分，即如下所示：∂f/∂wi，f代表神经元的输出，wi是函数f的第i个参数。参数wi代表网络的中边的权重或者神经元的阈值，神经元的激活函数具体细节并不重要，它可以是非线性函数Sigmoid或RELU。这样就可以得到f相对于网络参数的梯度∇f ，有了这个梯度，我们就可以使用梯度下降法对网络进行训练，即每次沿着梯度的负方向（−∇f）移动一小步，不断重复，直到网络输出误差最小。
在神经网络训练过程中，我们需要注意的是，反向传播算法不仅需要准确计算梯度。还需要使用一些小技巧对我们的网络进行训练。理解反向传播算法可以帮助我们理解那些在神经网络训练过程中使用的小技巧。
反向传播算法之所以重要，是因为它的效率高。假设对一个节点求偏导需要的时间为单位时间，运算时间呈线性关系，那么网络的时间复杂度如下式所示：O(Network Size)=O(V+E)，V为节点数、E为连接边数。这里我们唯一需要用的计算方法就是链式法则，但应用链式法则会增加我们二次计算的时间，由于有成千上万的参数需要二次计算，所以效率就不会很高。为了提高反向传播算法的效率，我们通过高度并行的向量，利用GPU进行计算。
注：业内人士可能已经注意到在标准的神经网络训练中，我们实际上关心的是训练损失函数的梯度，这是一个与网络输出有关的简单函数，但是上文所讲的更具有普遍意义，因为神经网络是可以增加新的输出节点的，此时我们要求的就是新的网络输出与网络超参数的偏微分。
反向传播算法适用于有向非循环网络，为了不失一般性，非循环神经网络可以看做是一个多层神经网络，第t+1层神经元的输入来自于第t层及其下层。我们使用f表示网络输出，在本文中我们认为神经网络是一个上下结构，底部为输入，顶部为输出。
规则1：为了先计算出参数梯度，先求出 ∂f/∂u ，即表示输出f对节点u的偏微分。
我们使用规则1来简化节点偏微分计算。下面我将具体说一下∂f/∂u的含义。我们做如下假设，先删除节点u的所有输入节点。然后保持网络中的参数不变。现在我们改变u的值，此时与u相连的高层神经元也会受到影响，在这些高层节点中，输出f也会受到影响。那么此时∂f/∂u就表示当节点u变化时，节点f的变化率。
规则1就是链式法则的直接应用，如下图所示，u是节点 z1,…,zm的加权求和，即u=w1*z1+⋯+wn*zn，然后通过链式法则对w1求偏导数，具体如下：
由上式所示，只有先计算∂f/∂u，然后才能计算∂f/∂w1。
为了计算节点的偏微分，我们先回忆一下多元链式法则，多元链式法则常用来描述偏微分之间的关系。 即假设f是关于变量u1,…,un的函数，而u1,…,un又都是关于变量z的函数，那么f关于z的偏导数如下：
这是链式法则2的一般式，是链式法则的1的子式。这个链式法则很适合我们的反向传播算法。下图就是一个符合多元链式法则的神经网络示意图。
如上图所示，先计算f相对于u1,…,un的偏导数，然后将这些偏导数按权重线性相加，得到f对z的偏导数。这个权重就是u1,…,un对z的偏导，即∂uj/∂z。此时问题来了，我么怎么衡量计算时间呢？为了与教课书中保持一致，我们做如下假设：u节点位于t+1层的，z节点位于t层或t层以下的子节点，此时我们记∂u/∂z的运算时间为单位时间。
我们首先要指出链式法则是包含二次计算的时间。许多作者都不屑于讲这种算法，直接跳过的。这就好比我们在上算法排序课时，老师都是直接讲快速排序的，像那些低效排序算法都是直接跳过不讲的。
朴素算法就是计算节点对ui与uj之间偏导数，在这里节点ui的层级要比uj高。在V*V个节点对的偏导值中包含∂f/∂ui的值，因为f本身就是一个节点，只不过这个节点比较特殊，它是一个输出节点。
我们以前馈的形式进行计算。我们计算了位于t层及t层以下的所有节点对之间的偏导数，那么位于t+1层的ul对uj的偏导数就等于将所有ui与uj的偏导数进行线性加权相加。固定节点j，其时间复杂度与边的数量成正比，而j是有V个值，此时时间复杂度为O(VE)。
反向传播算法如其名所示，就是反向计算偏微分，信息逆向传播，即从神经网络的高层向底层反向传播。
信息协议：节点u通过高层节点获取信息，节点u获取的信息之和记做S。u的低级节点z获取的信息为S⋅∂u/∂z
很明显，每个节点的计算量与其连接的神经元个数成正比，整个网络的计算量等于所有节点运算时间之和，所有节点被计算两次，故其时间复杂度为O(Network Size)。
我们做如下证明：S等于∂f/∂z。
证明如下：当z为输出层时，此时∂f/∂z=∂f/∂f=1
假如对于t+1层及其高层假设成立，节点u位于t层，它的输出边与t+1层的u1,u2,…,um节点相连，此时节点从某个节点j收到的信息为(∂f/∂uj)×(∂uj/∂z)，根据链式法则，节点z收到的总信息为S=
在上文中，关于神经网络、节点计算，我们并没有细讲。下面我们将具体讲一下，我们将节点与节点之间的计算看做是一个无环图模型，许多自动计算微分的工具包（如：autograd，tensorflow）均采用这一模型。这些工具就是通过这个无向图模型来计算输出与网络参数的偏导数的。
我们首先注意到法则1就是对这个的一般性描述，这个之所以不失一般性是因为我们可以将边的权值也看做节点(即叶节点)。这个很容易转换，如下图所示，左侧是原始网络，即一个单节点和其输入节点、输入节点的权重。右侧是将边的权重转换为叶节点。网络中的其它节点也做类似转换。
只要局部偏导数计算的效率足够高，那么我们就可以利用上文所说的信息协议来计算各个节点的偏微分。即对节点u来讲，我们应该先找出它的的输入节点有哪些，即z1,…,zn。然后计算在u的偏微分的基础上计算zj的偏微分，由于输出f对u的偏微分记做S，所以计算输出f对zj的偏微分就是S⋅∂u∂zj
这个算法可以按照如下规则分块计算，首先明确节点u与输入节点z1,…,zn 的关系，然后就是怎么计算偏导数的倍数（权重）S。即S⋅∂u/∂zj。
扩展到向量空间：为了提高偏微分权重的计算效率，我们可以将节点的输出也变为一个向量（矩阵或张量）。此时我们将∂u/∂zj⋅S改写为∂u/∂zj[S], 这个与我们的反向传播算法思想是一致的，在反向传播算法中，y是一个p维向量，x是一个q维向量，y是关于x的函数，我们用∂y/∂x来表示由 ∂yj/∂xi所组成的q*p矩阵。聪明的读者很快就会发现，这就是我们数学中的雅克比矩阵。此外我们还可以证明S与u的维度相同、∂u∂zj[S] 与zj的维度也相同。
如下图所示，W是一个d2*d3的矩阵，Z是一个d1*d2的矩阵，U=WZ故U是一个d1*d3维的矩阵，此时我们计算∂U/∂Z，最终得到一个d2d3×d1d3维的矩阵。但我们在反向传播算法中，这个会算的很快，因为∂U/∂Z[S]=W⊤S，在计算机中我们可以使用GPU来进行类似向量计算。
在许多神经网络框架中，设计者想要是一些神经元的参数能够共享，这些参数包括边的权重或者节点的阈值参数。例如，在卷积神经网络中，同一个卷集核使用的参数都是一样的。简而言之，就是a、b是两个不同的参数，但我们强制要求a与b的值相同，即参数共享。这就好比我们给神经网络新增一个节点u，并且节点u与a和b相连，并且a=u，b=u.，此时根据链式法则，∂f/∂u=(∂f/∂a)⋅(∂a/∂u)+(∂f/∂b)⋅(∂b/∂u)=∂f/∂a+∂f/∂b. 因此，对一个共享参数而言，其梯度就是输出与参数节点之间的中间节点的偏导数之和。
上面我们讲的是非循环神经网络，许多前沿应用（机器翻译、语言理解）往往使用有向循环神经网络。在这种结构的神经网络中会存在记忆单元或注意力机制，在这些单元或机制中往往存在复杂的求导计算。一开始我们使用梯度下降法训练网络，即在时间序列上对神经网络使用反向传播算法，即对这个有向环状结构进行无限循环，每一次循环的网络结构、网络参数都是一样的，但是网络的输入与输出是不一样的。在实际应用中我们会遇到梯度爆炸或梯度消失等问题，这些都会对结果收敛产生影响。为了解决这些问题，我们使用梯度剪切或者长短记忆模型（LSTM）等技术解决上述问题。
环状神经网络可以高效计算梯度的事实促进了有记忆网络甚至数据结构的发展。使用梯度下降法，我们可可以对环状结构神经网络进行优化，寻找最佳参数，使得这个网络可以解决特定计算问题。梯度下降法的极限目前仍在探索中。
在近似线性时间中，我们不仅可以使用梯度下降法，或许我们也可以使用2阶导数对目标函数进行优化。在优化过程中，最关键的一步是计算海森矩阵与一个向量的积，下面我将向大家介绍如何在规模是O(Network size)的神经网络应用上述思想，这个例子与前面所讲稍有不同，我们的初始神经网络应该是一个用反向传播算法进行简单优化过的神经网络。
法则：假设在无环神经网络中，有V个节点，E条边，网络输出为f，叶节点为z1,…,zm，那么必存在一个大小为O(V+E)的网络，这个网络的的输入节点为z1,…,zm，输出节点为∂f/∂z1,…,∂f/∂zm。
上面的定理可以通过在无环神经网络中实现消息直接传递来证明，紧接着我们将解释一下如何计算∇2f(z)⋅v。设g(z)=⟨∇f(z),v⟩ ，有定理可知， g(z)可以由大小是O(V+E)神经网络计算得到，同理我们再次应用法则，在这个大小是O(V+E)的网络计算g(z)的梯度，此时∇g(z)=∇2f(z)⋅v，此时我们就算出了海森矩阵与向量积的积，此时耗费的时间复杂度就是网络规模的大小。
以上便是BP学习过程中需要了解的一些内容，雷锋网希望能让你在学习过程中得到一个比较清晰的思路。当然，也欢迎你关注雷锋网旗下公众号“AI科技评论”与我们交流哦。
via Back-propagation, an introduction
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
