如何理解反向传播算法_反向传播算法的复杂度

如何理解反向传播算法

对于一个算法或者模型的理解可以分为直观理解，算法理解和数学证明三个层次。直观的理解能够启发思维，算法层面的理解能够消除歧义，数学证明能够提供更一般化的问题描述，为潜在的问题提供分析工具。本文试图从这三个层面对神经网络中的反向传播算法做简单的总结，文中大量的图片和公式来源于《神经网络与深度学习》一书第二章1，后续不在 一一引用。

神经网络模型的数学表示

反向传播算法是神经网络的一种权重更新算法，最早提出于20世纪70年代，直到论文 2 的出现才逐渐受到重视，后续成为神经网络学习的主流算法之一。在给出具体的数学描述之前，这里首先给出神经网络模型中所使用的数学符号的含义。

我们使用 $\omega_{jk}^l$ 表示第$l-1$层的第$k$个神经元与第$l$层的第$j$个神经元的连接权重。如下图所示，$\omega_{24}^3$是 第2层的第4个神经元到第三层的第2个神经元的权重。这里$j$与$k$的书写顺序初看比较别扭，需要稍微留意一下。

与此相似，我们使用$b^l_j$表示第$l$层的第$j$个神经元的偏置，$a_j^l$表示第$l$层的第$j$个神经元的激活值，如下图所示。

使用$\sigma$表示激活函数，第$l-1$层到第$l$层的前向传播可以表示为：

$$a_j^l = \sigma(\sum_k\omega_{jk}^la_k^{l-1}+b_j^l)\tag{1}$$
上述的求和是遍历第$l-1$层的所有神经元。

为了方便进行矩阵化的描述，我们使用$\omega^l$表示第$l$层的权重矩阵，矩阵的第$j$行$k$列的元素就是$\omega_{jk}^l$。使用$b^l$表示偏置向量，$a^l$表示激活值得向量。那么前向传播的向量表示为：

$$a^l = \sigma(\omega^la^{l-1}+b^l)\tag{2}$$
为了表示方便，我们又引入中间变量 $z^l = \omega^la^{l-1}+b^l$ 表示线性组合部分，当然对于向量中的单个元素有： $z_j^l = \sum_k \omega^l_{jk}a^{l-1}_k + b_j^l$ 。

一个$L$层的神经网络可以表示为：

$$a^0 = x \\ z^l = w^la^{l-1} \\ a^l = \sigma(z^l) \\ \vdots \\ \hat y = a^L\tag{3}$$

对代价函数的基本假设

代价函数度量模型输出与真实值的拟合程度。反向传播算法解决的基本问题就是通过不断更新权重来最小化代价函数。一个典型的二次的代价函数可以表示为：

$$C = \frac{1}{2n}\sum_x||y(x)-a^L(x)||^2\tag{4}$$
其中， $n$表示训练集的样本数量，$x$是单个样本， $y(x)$是对应的期望得到的输出， $L$是神经元的总层数。这里我们对代价函数做出两个基本假设。

假设一：代价函数可以表示为单个样本代价函数的平均，即代价函数可以写作：$C= \frac{1}{n}\sum_xC_x$，其中 $C_x$是单个样本的代价。

做出这个假设是因为我们后面讨论的梯度算法计算的是$\partial C_x/\partial \omega$ 和 $\partial C_x / \partial b$，这样我们就可以通过求平均的方式得到$\partial C/ \partial \omega$ 和 $\partial C/\partial b$。后续在反向传播算法的描述中，为了简化表示，$C_x$一般简记为$C$。

假设二：代价函数依赖于神经网络最后一层的输出值，也就是说$C = C(a^L)$，这应该是一个比较显然的假设。

反向传播算法

反向传播算法解决的基本问题就是通过不断更新权重来最小化代价函数，一个自然的想法是通过梯度下降的方法来实现。牵涉到计算$\partial C/\partial \omega_{jk}^l$。然后通过 $\omega_{jk}^l =\omega_{jk}^l - \alpha\frac{\partial C}{\partial \omega_{jk}^l}$ 更新权重，其中$\alpha$是学习率。反向传播算法就是通过误差反向传播的算法给出一个步骤来计算偏导数$\partial C/\partial \omega_{jk}^l$。

首先我们定义第$l$层第$j$个神经元的输入误差：

$$\begin{eqnarray} \delta^l_j \equiv \frac{\partial C}{\partial z^l_j} \tag{5}\end{eqnarray}$$
反向传播算法就是利用 $\delta^l_j$来作为中间变量计算 $\partial C_x/\partial \omega$ 和 $\partial C_x / \partial b$ 。

反向传播算法利用四个等式来最终确定最终的偏导数，在具体介绍算法之前，我们首先引入符号$\bigodot$来表示两个矩阵对应元素相乘的操作，比如：

$$\begin{eqnarray} \left[\begin{array}{c} 1 \\ 2 \end{array}\right] \odot \left[\begin{array}{c} 3 \\ 4\end{array} \right] = \left[ \begin{array}{c} 1 * 3 \\ 2 * 4 \end{array} \right] = \left[ \begin{array}{c} 3 \\ 8 \end{array} \right]. \end{eqnarray}$$
下面给出是个基本的等式，并给出证明。

等式一：输出层的误差公式

$$\begin{eqnarray} \delta^L_j = \frac{\partial C}{\partial a^L_j} \sigma'(z^L_j). \tag{BP1}\end{eqnarray}$$
该等式计算输出层的误差。等式 BP1的证明是比较直观的，可以通过微积分中的链式法则很容易计算得到。

首先，

$$\delta_j^L = \frac{\partial C}{\partial z^L_j} = \sum_k \frac{\partial C}{ \partial a_k^L}\frac{\partial a_k^L}{\partial z_j^L} \tag{6}$$
显然：
$$\frac{\partial a_k^l}{\partial z_j^l} = \begin{cases} 0, & j\ne k \\ \sigma(z_j^L), & j=k \end{cases} \tag{7}$$
带入式(6)即可得到 $BP1$ ，证毕。我们也给出BP1向量化的等价描述：
$$\begin{eqnarray} \delta^L = \nabla_a C \odot \sigma'(z^L). \tag{BP1a}\end{eqnarray}$$
等式二：给定输入误差 $\delta^{l+1}$时， $\delta^{l}$的计算：
$$\begin{eqnarray} \delta^l = ((w^{l+1})^T \delta^{l+1}) \odot \sigma'(z^l), \tag{BP2}\end{eqnarray}$$
同理，利用链式法则
$$\begin{eqnarray} \delta^l_j & = & \frac{\partial C}{\partial z^l_j} \\ & = & \sum_k \frac{\partial C}{\partial z^{l+1}_k} \frac{\partial z^{l+1}_k}{\partial z^l_j} \\ & = & \sum_k \delta^{l+1}_k\frac{\partial z^{l+1}_k}{\partial z^l_j}, \end{eqnarray} \tag{8}$$
而根据前向传播的关系：
$$\begin{eqnarray} z^{l+1}_k = \sum_j w^{l+1}_{kj} a^l_j +b^{l+1}_k = \sum_j w^{l+1}_{kj} \sigma(z^l_j) +b^{l+1}_k. \tag{9}\end{eqnarray}$$
则有
$$\begin{eqnarray} \frac{\partial z^{l+1}_k}{\partial z^l_j} = w^{l+1}_{kj} \sigma'(z^l_j). \tag{10}\end{eqnarray}$$
代入式(8)得到：
$$\begin{eqnarray} \delta^l_j = \sum_k w^{l+1}_{kj} \delta^{l+1}_k \sigma'(z^l_j). \tag{11}\end{eqnarray}$$
同样，可以写成矩阵的形式，即可得到BP2。

等式三：给定$\delta^l_j$ 关于偏重$b_j^l$的偏导的计算

$$\begin{eqnarray} \frac{\partial C}{\partial b^l_j} = \delta^l_j. \tag{BP3}\end{eqnarray}$$
根据： $z_j^l = \sum_k \omega^l_{jk}a^{l-1}_k + b_j^l$ 得到 $\frac{\partial z_j^l}{\partial b_j^l} = 1$ 。那么
$$\begin{eqnarray} \frac{\partial C}{\partial b^l_j} & = \frac{\partial C}{\partial z_j^l} \frac{\partial z_j^l}{\partial b_j^l} \\ & = \delta_j^l\end{eqnarray}$$
问题得证，同样矩阵形式描述为：
$$\begin{eqnarray} \frac{\partial C}{\partial b^l} = \delta^l \tag{12}\end{eqnarray}$$

等式四：给定$\delta^l_j$ 关于偏重$\omega_{jk}^l$的偏导的计算

$$\begin{eqnarray} \frac{\partial C}{\partial w^l_{jk}} = a^{l-1}_k \delta^l_j. \tag{BP4}\end{eqnarray}$$

同样，根据$z_j^l = \sum_k \omega^l_{jk}a^{l-1}_k + b_j^l$，得到 $\frac{\partial z_j^l}{\partial \omega_{jk}^l} = a_k^{l-1}$。那么：

$$\begin{eqnarray} \frac{\partial C}{\partial \omega^l_{jk}} & = \frac{\partial C}{\partial z_j^l} \frac{\partial z_j^l}{\partial \omega_{jk}^l} \\ & = \delta_j^l a_k^{l-1}\end{eqnarray}$$
得证，同样我们可以采用矩阵形式描述：
$$\begin{eqnarray} \frac{\partial C}{\partial w^{l}} = \delta^{l}{(a^{l-1})}^T , \tag{13}\end{eqnarray}$$
至此，反向传播算法中四个基础的等式证明完毕。这里做个总结：

BP1计算最后一层的输入误差，然后可以利用BP2迭代的计算每一层的输入误差$\delta_l^j$。在各层输入误差计算完毕之后就可以通过BP3和BP4计算各个参数对应的偏导数。反向传播算法的算法描述为：

1. 输入 x: 设置初始值 $a^{0} = x$
2. 前向传播：对于$l = 1, 2, \dots, L$，计算 $z^{l} = w^l a^{l-1}+b^l$ 以及 $a^l = \sigma(z^l)$。
3. 计算最后一层的误差 $\delta^L = \nabla_a C \odot \sigma'(z^L).$
4. 反向传播算法 对于 $l = L-1, L-2, \dots, 1$，计算 $\delta^l = ((w^{l+1})^T \delta^{l+1}) \odot \sigma'(z^l)$ ；
5. 计算各个参数对应的梯度 $\frac{\partial C}{\partial b^l} = \delta^l$ ，$\frac{\partial C}{\partial w^{l}} = \delta^{l}{(a^{l-1})}^T$

从公式的角度，我们对学习过程可以获得以下理解：

1. $\delta^l$的计算依赖于$\sigma$。比如对于激活函数$\sigma(z) = \frac{1}{1+e^{-z}}$，在靠近0或1，也成为饱和状态时，其导数$\sigma'(z)$接近0，那么BP2中等式第二项接近0，导致$\delta$接近0。那么后续计算的梯度同样会接近0，从而产生梯度消失的问题；所以，实践中为了加快学习速度会采用梯度不会饱和的激活函数，如RELU函数。
2. 当$a^l$接近0时，从BP4中可以看出，同样会导致梯度接近0，同样会导致参数学习过慢。

反向传播的直观理解

反向传播算法的思路来源是什么？设想反向传播算法出现以前，利用梯度下降法寻找最优参数是一个非常自然的思路，那么面临的问题同样是计算 $\partial C / \partial \omega$ 的问题。在看到解析求解梯度的困难后，很自然的想法可能是通过式(14)计算梯度。

$$\begin{eqnarray} \frac{\partial C}{\partial w_{j}} \approx \frac{C(w+\epsilon e_j)-C(w)}{\epsilon}, \tag{14}\end{eqnarray}$$
然而，这样的计算在问题复杂度增加时会面临很大的问题。对于大型的深度网络，参数数量很容易达到 $10^4$的数量级，那么按照式(14)就需要计算相应次数的前向传播才能得到估计的梯度，这在计算上是不可行的。对照反向传播算法，只需要进行一次前向传播和一次反向传播就可以完成梯度的计算，而且反向传播的计算复杂度与前向传播的复杂度是一致的。那么反向传播算法的计算效率是如何提升的呢？我们通过一个图示法进行说明。

假设，我们想计算$\omega_{jk}^l$ 的波动对代价值的影响，那么它的波动就会形成一个传播路径，最终产生$\Delta C$。

而且有：

$$\begin{eqnarray} \Delta C \approx \frac{\partial C}{\partial w^l_{jk}} \Delta w^l_{jk}. \tag{15}\end{eqnarray}$$
那么，在这种情况下，很自然的想法是通过 $\Delta C$与 $\Delta\omega_{jk}^l$ 来估计 $\frac{\partial C}{\partial w^l_{jk}}$。事实上，如果能将 $\Delta C$归因到是哪些参数引起的，那么问题也就解决了，反向传播的思路就是利用逐层误差再加上微积分的链式规则推导得出的。

这里再提一下新理论的发展过程，一个理论的创新是非常复杂的，不断演化的过程。比如我们这里看到的反向传播的理论非常的简单明了，但这背后可能包含了很多非常复杂的演进过程。一个新的理论的发展过程往往是这样的：最开始只是一个非常粗略的想法加上非常复杂但甚至包含错误的证明，然后等引起关注之后，会有更多的人参与进来，随之更简洁更有效的证明方法，才会被提出和改进，经过这样反复的迭代最后才形成我们看到的结果。举个简单例子，对于式(5)中误差的定义，如果我们最开始将其定义为：$\delta^l_j = \frac{\partial C}{\partial a^l_j}$ ，那么后续的推导和证明就会非常复杂，而对于$\delta_j^l$的定义就是不断这么摸索而来的结果。

总结

本文介绍了反向传播的原理与算法，同时给出了一个可以说是直观理解也可以说是算法的思想来源的说明。反向传播在深度学习，神经网络学习中具有非常普遍的应用。当然，目前同深度学习遭受到的质疑一样，反向传播也遭受了一些质疑3。但不管怎么说，掌握反向传播算法的原理才能更好的改进它。博客4 包含了从第一行代码开始写神经网络的教程，感兴趣的同学可以以其为案例尝试编程实现一下。

参考文献