第2章
Chapter Two
反向传播算法

2.1 导数和导数的应用

作为深度学习的基础算法，反向传播算法（Back Propagation，BP）是最著名的人工智能算法之一。也许你对它并不陌生，但是BP算法的实质是什么呢？为什么这个算法就能帮助人工神经元网络优化参数？要回答这两个问题，我们不得不从高等数学中的导数说起。请不要急于把这本书或者这一章丢到一边。我知道，即使是高等数学考得还不错的学生，也有很大概率对它不感兴趣。下面我们将通过实际例子讲导数，例如怎么用导数求解平方根，然后自然过渡到深度学习。你会发现，这是一段奇妙的数学之旅。

2.1.1 导数

导数就是函数在某一点处的切线的斜率，如图2－1所示。更进一步，导数是函数因变量y的变化与自变量x的变化的比值的极限。即：

这个公式告诉我们：根据导数，我们有可能根据y的变化推断x的变化。

设有函数y＝f（x），现在我们的目标是求出当y＝y^∗时x的值，即求x^∗满足f（x^∗）＝y^∗。这其实是一件非常有意义的事。例如，根据函数y＝x²我们可以很容易算出任意一个数的平方。但是反过来，当y＝2时x应该等于几就不好计算了。这个问题实际上就是求2的平方根。

那么怎么办呢？方法就是先给x一个初值，例如1，然后计算出对应的y值，显然也是1。再计算y的当前值与目标值2之间的误差Δy＝y^∗－y，根据Δy和导数再不断地调整x的值以尽量减少Δy的绝对值。当Δy＝0时，对应的x就是2的平方根。

根据问题分解方法，我们现在要考虑的子问题是如何根据Δy和导数调整x的值。这其实并没有想象中那么困难。假设Δy＞0，此时如果导数y′也大于0，则意味着我们应该把x往右移动，即令Δx＞0，这样才有可能得到更大的y，如图2－2所示。

再把其他3种情况也考虑在内，我们可以得出一个非常有意思的结论。

梯度下降法（Gradient Descent，GD）第一个公式如下：

其中a是一个大于0的调整因子，又叫作步长。Δy决定了Δx的变化方向，a决定了变化步长。我们可以使用如下迭代算法计算出x^∗。

算法2－1 根据导数迭代求解最优解（迭代求解算法）

1）给x赋予一个随机初值。

2）按照一定循环条件，反复执行：

a）计算Δy＝y^∗－y。

b）根据式（2－1）或者式（2－2）（后面介绍）求Δx。

c）令x＝x+Δx。

其中的循环条件可以是|Δy|＜ε（ε是事先指定的一个小正数），可以是固定的循环次数，也可以是这两个条件的或。下面以这个算法为基础，令a＝0.01，按照固定循环次数试着求1～10的平方根。代码如下：

输出结果如下：

sqrt（1）＝1.00000000

sqrt（2）＝1.41421352

sqrt（3）＝1.73205081

sqrt（4）＝2.00000000

sqrt（5）＝2.23606798

sqrt（6）＝2.44948974

sqrt（7）＝2.64575131

sqrt（8）＝2.82842712

sqrt（9）＝3.00000000

sqrt（10）＝3.16227766

我们看到，这个结果是相当准确的。有趣的是，式（2－1）是一个通用公式。只要选取合适的步长，并且函数y＝f（x）在定义域区间内处处可导^[1]，就能用类似的方法求解f的反函数^[2]（又叫逆函数，以下我们无差别地使用这两个概念）。

2.1.2 梯度下降法求函数的最小值

如果y^∗是事先不确定的，那么我们就不能直接使用式（2－1）。例如，求y的最小值和最大值。求y的最大值可以转化为求－y的最小值，所以我们只需考虑如何求y的最小值即可。

假设我们用迭代法求解函数y＝f（x）的最小值，并且当前x＝x₁。如果导数值f′（x₁）＞0，如图2－3所示，则意味着当x＞x₁时因变量y的变化趋势是增大的。所以，为了获得更小的y值，应该让x变小，即Δx＜0。如果f′（x₁）＜0，如图2－4所示，则意味着当x＞x₁时因变量y的变化趋势是减小。所以，为了获得更小的y值，应该让x变大，即Δx＞0。综上所述，我们可以得到梯度下降法第二个公式，即

式（2－1）和式（2－2）就是梯度下降法（GD）的两个公式。前者用来计算y在特定值y^∗下的解；后者用来求y最小值的解。值得一提的是，式（2－1）的使用可以转为使用式（2－2）。例如，求满足f（x）＝y^∗的x可以转为求下面函数的最小值：

g（x）＝［f（x）－y^∗］²

世界上绝大多数深度学习框架，例如后面要学习的Tensorflow，几乎都是基于GD法的。因此我们后面的学习几乎都是围绕着GD法以及GD法与其他方法的比较进行的。请注意，虽然我们以求最小值为目的推导了式（2－2），但一般情况下，该公式只能求到函数在当前点附近的极小值，其他位置的极小值求不到。因为在极小值点存在＝0，这使得Δx＝0，从而导致无法更新x。

式（2－2）是针对一元函数的，多元函数也有类似的公式。对于多元函数y＝f（x₁，x₂，…，x_n）来说，为了求它的最小值，每个x_i都应该按照下面的公式进行迭代，即多元函数梯度下降法公式：

下面，我们编写程序来求函数y＝（x₁+2）²+（x₂－3）²在什么情况下可取得最小值。

输出结果：

（－1.9999999999999947，2.9999999999999893）

GD法的实质是在函数曲线上，沿着导数所指示的方向，按照步长所规定的距离移动一个点，看看新位置处的y值是不是比原位置的更小或者离y^∗更近。这意味着GD法是通过试探来获得比当前解更优的解的。你也可以采用其他方法进行试探，例如牛顿法、二分法和黄金分割法等。下面以牛顿法为例进行说明。

2.1.3 牛顿法求平方根

所谓牛顿法，其理论根据是：，从而有牛顿法公式：

对比式（2－1）、式（2－2）、式（2－3）和式（2－4），你会发现这些公式的目的都一样，都是为了计算Δx，从而帮助我们计算逆函数。逆函数之所以重要，是因为它的实质是透过现象看本质，透过结果看原因。这是深度学习乃至人工智能的根本目的。下面我们用牛顿法计算平方根。

令y＝x²，则有y′＝2x。代入牛顿法公式有Δx＝，其中p是要求平方根的数。根据算法2－1中的迭代方法，则有：

这就是牛顿法求解平方根的公式。下面我们编写程序来验证这个公式：

输出结果如下：

sqrt（1）＝1.00000000

sqrt（2）＝1.41421356

sqrt（3）＝1.73205081

sqrt（4）＝2.00000000

sqrt（5）＝2.23606798

sqrt（6）＝2.44948974

sqrt（7）＝2.64575131

sqrt（8）＝2.82842713

sqrt（9）＝3.00000000

sqrt（10）＝3.16227767

此代码仅仅循环5次就达到了这样精确的结果，而代码2－1循环5次是远远达不到这个效果的。既然如此，为什么我们不放弃GD法而统一使用牛顿法呢？原因就在于牛顿法计算得到的Δx没有经过步长a的调整，步子往往跨得太大，从而导致最优解x^∗被错过。

如图2－5所示，设有曲线y＝f（x），曲线在A点（x_a，y_a）的切线斜率是y′，切线AB交直线y＝y^∗于B点（x_b，y^∗）。y^∗是目标值。我们的目的是求最优解x^∗，使得f（x^∗）＝y^∗。假设当前x＝x_a，请根据牛顿法求x的下一个值x₂。

解答：切线的斜率满足

而根据牛顿法有：

把y′代入，得：

Δx＝x_b－x_a

所以：

x ₂＝x_a+Δx＝x_b

这意味着切线AB与y＝y^∗的交点B就是x的下一个位置。我们发现x _b不但错过了最优解x^∗，而且离x^∗的距离比x_a还要远。这就是牛顿法的问题，即很容易导致解的发散。换句话说，就是步子跨得太大了。极端情况下，x会越来越发散，永远也到达不了最优解。而GD法利用步长因子a解决了这个问题。

当然，也可以给牛顿法加一个步长因子。问题是牛顿法Δx＝中导数位于分母位置，这就限制了y′，因为其不能等于0。

2.1.4 复合函数和链式法则

根据前面的论述，解决问题是试图透过现象看本质，透过结果看原因，通过函数求解逆函数。而为了求逆函数，我们采用了GD法。后者的实质是求函数对自变量的导数，对多元函数来说就是求偏导。

对于复合函数，可以利用链式法则求偏导。例如，设有函数y＝f（x），z＝g（y），即z＝g（f（x））。如果用GD法求z^∗的解或者求z的最小值，根据链式法则，则有：

若设y＝sin（x），z＝3y²，则有：

上述变量x、y、z之间的依赖关系可以用图2－6表示。图中的结点表示变量，从一个结点指向另一个结点的指针表示后者的计算依赖于前者。前者称为后者的前驱，后者称为前者的后继。我们把这种图称为依赖关系图。依赖关系图一定是一个有向无环图（Directed Acyclic Graph，DAG）。

最简单的依赖关系图犹如一条直线，除最后一个结点外每个结点都有且仅有一个后继，除第一个结点外每个结点都有且仅有一个前驱。我们在所有的有向弧上标记后者对前者的偏导，如图2－6所示。在这样的依赖关系图中计算两个变量之间的偏导，只需把它们之间路径上的所有偏导相乘即可。这就是图示化的链式法则。

2.1.5 多元函数和全微分方程

复合函数有助于我们用一堆简单的函数组合成一个复杂函数。构成复杂函数的另一个方法是利用多元函数。设有多元函数y＝f（x₁，x₂，…，x_n），则有全微分方程：

如果假设式（2－5）中的每一个x_i都是x的函数，即x_i＝f_i（x），i＝1，2，…，n，则有dx_i＝dx，代入式（2－5）得：

可以用图2－7所示的依赖关系图表示。其表明，y对x的偏导等于从x到y的所有可能路径上导数乘积的和。

值得一提的是，这个结论不仅对图2－7和图2－6有效，其对任意形式的关系依赖图都有效，只要它是一个DAG。

例如，在图2－8所示的依赖关系图中，从x到y的所有可能路径有：xacy、xady、xbdy。这些路径上的导数乘积分别是1、－1.5和－1，把这些值相加得到＝－1.5。有了偏导，在GD法的帮助下，我们就可以计算逆函数。

由于深度学习的目的是透过现象看本质，根据原函数计算逆函数，所以依赖关系图和上述计算偏导的过程就构成了整个深度学习大厦的基石。所有深度学习的算法、理论和模型几乎都是建立在这个基础上的。

接下来我们要考虑的问题是：如何优化计算过程，避免重复计算？有没有什么办法帮助我们自动求偏导，自动求解逆函数？

2.1.6 反向传播算法

如图2－8所示，我们在计算y对x的偏导时，有很多路径是共享的，例如弧xa和dy。没有必要对这些路径上的导数乘积进行重复计算。所以我们可以从y出发，沿着有向弧的反方向，每经过一个结点，就看看该结点是否可以计算y对它的偏导。如果能，就进行计算，并访问它的所有前驱结点。这个过程不断地往前推进，直到遇到x结点为止。

而一个结点A是否可计算y对它的偏导，取决于它的所有后继结点是否都已计算了y对其的偏导。如果都算过了，就把这些偏导分别乘以相应结点到A的偏导，再对所有这些乘积求和即可。

如图2－9所示，从y出发，沿着有向弧的反方向，我们首先会遇到d、c两个结点。显然，和都是可以计算的，我们在c、d结点边上分别写上0.5和－0.5。接着，遇到了结点a和b。＝2×0.5+3 ×（－0.5）＝－0.5，＝－2 ×（－0.5）＝1.0，在a、b结点边上分别写上－0.5和1.0。最后计算＝1 ×（－0.5）－1 ×1.0＝－1.5。计算过程中不需要重复计算共享路径上的偏导乘积。这就是反向传播算法（Back Propagation，BP）。

算法2－2 反向传播算法（BP）

deriv（y，graph）

说明：在有向图graph上计算，x是任何y所依赖的结点。

1）构建一个字典＝｛y：1｝，用来保存y对每个结点的偏导。其中y对自己的偏导是1。▽

2）构建集合open＝｛y｝，用来保存可以计算偏导的结点。

3）当open集合不为空时，反复执行：

a）任取open中的一个元素t。

b）从open集合中删除t。

c）sum＝0。

d）对t的每个后继结点p，执行：

sum＝sum+▽［p］

e）令▽［t］ ＝sum。

f）对t的每个前驱q，如果q的所有后继都在字典▽中出现，就把q加入集合open。

算法2－1指明了如何利用导数迭代求解最优解，而算法2－2给出了求解复杂函数偏导数的方法。

既然y对x的偏导等于从x到y的所有可能路径上导数乘积的和，那么正向传播（FP）也能计算这个值。甚至FP算法有一个优点：每计算完一个结点就可以释放这个结点所占内存，无须再保留这个结点。而BP算法在计算偏导时可能要为某些结点保存函数值，例如函数f（x）＝的导函数f′（x）＝f（x）［1－f（x）］。那我们为什么推荐使用BP算法而不是FP算法来计算偏导呢？

首先，BP算法保证了只有必要结点的导数值和/或函数值会被计算，无关结点不会被涉及。其次，更重要的是，BP算法每计算一个结点就能得到y对该结点的偏导。也就是说，一次BP计算可以把y对所有相关变量的偏导都计算出来，而FP算法只能计算y对x的偏导。

2.1.7 梯度

前面章节中提到了梯度下降法GD，但是没有严格说明什么是梯度。算法2－2中为了计算y对任何一个所依赖的结点的偏导数，使用了字典▽，用来保存结点的偏导数。这个偏导数就是该结点的梯度。偏导数和梯度概念的区别在于：梯度特别强调是网络的最后一个结点对当前结点的偏导数；而偏导数不强调是最后一个结点，任何两个结点之间都可以有偏导数。梯度用符号▽表示。结点x的梯度记为▽_x。梯度有以下性质：

1）▽_y＝1，y是网络的最后一个结点。

2）▽_x＝，y_i是x的第i个后继。

注意，梯度不是微分，▽_x不等价于dx。

2.1.8 分段求导

由于GD法要用到导数，所以人们很容易认为，GD法和BP算法只适合于求解在定义域内处处可导的函数的逆函数。真的是这样吗？我们考虑函数y＝|x|。显然，它在x＝0处没有切线，因而也就不可导，如图2－10所示。

那是不是就意味着GD法和BP算法不能使用在y＝|x|这类如此简单的函数上？答案是能，只要函数在定义域内任意一点存在左导数或者右导数即可。

极限称为函数点a的右导数，极限称为函数点a的左导数。以左导数为例，如果左导数存在，意味着x从左边接近a时，计算导数的极限是存在的。

用数学语言来说，连续函数f（x）在某一点a不可导的充分必要条件是：

例如在图2－10中，x＝0处的左右切线斜率分别是－1和1。所以不可导并不意味着左右导数不存在，只是这两个值不等罢了。而GD法是一个迭代算法，是根据x的当前值计算它的下一个值（见算法2－1），即使是多元复合函数也是如此。所以在遇到不可导点a前，我们必然要么处在它的左边，要么处在它的右边。计算不会因为a点的导数不存在而崩溃。即使到达a点，也可以根据之前自变量位于a的哪一边，用a的左导数或者右导数代替，计算仍然不会崩溃。

基于此，GD法仅要求函数连续即可。其实质就是以不可导点为分界，把函数定义域分成若干段，然后对每段分别求导。这大大降低了GD法的应用门槛。以我们后面要学的Tensorflow为例，它允许用户使用几乎所有可能的函数。某些不可导函数，例如relu（），甚至在其中扮演了极其重要的角色。