反向传播算法（BP）

人工智能领域的算法真是日新月异啊，最近CMU和Google Brain又提出了XLNet。
这篇博文还是从基础算法入手，介绍一下Back Propagation（简称BP），主要分为两个部分：反向传播的基本原理和RNN的反向传播算法，最后给出代码实现。

Back Propagation

之前介绍过牛顿迭代法：当我们想要优化一个目标函数时，需要在每次迭代的时候对变量/参数进行更新，而更新参数的最重要的部分就是求目标函数对参数的导数了。
下面对最简单的神经网络进行BP算法的公式推导：$tag$
下图是一个只有两个神经元的网络（图片修改自李弘毅老师的PPT），输入样本为一个二维的向量$\vec x$，输出为一个数$y$，现在假设loss函数是$l=|| y - \hat y ||_2^2$，那么要求的便是$\frac {\partial l}{\partial w_i}$ 以及$\frac {\partial l}{\partial b}$ （把$w$和$b$合并成一个向量$W$也是可以的）。

图中，$\sigma$表示sigmiod函数。

首先思考一下，这个导数如果让你计算应该怎么做呢？

因为loss函数里与$w$, $b$参数相关的就只有$y$了，而$y$由$z'$ 得出，$z'$ 由线性函数$wx+b$得到…那自然会想到用chain rule来求导了。

整理一下思路：

$$y=\sigma(z') \\ z'=w_{21}a+b_2 \\ a=\sigma(z) \\ z=w_{11}x_1+w_{12}x_2+b_1 \tag {1}$$

那么求导如下：

$$\frac {\partial l}{\partial y} = 2(y-\hat y) \\ \frac {\partial y}{\partial w_{11}} = \frac {\partial y}{\partial z'} \cdot \frac {\partial z'}{\partial a} \cdot \frac {\partial a}{\partial z} \cdot \frac {\partial z}{\partial w_{11}} = \sigma(z')[1-\sigma(z')]\cdot w_{21} \cdot \sigma(z)[1-\sigma(z)] \cdot x_1 \\ \frac {\partial y}{\partial b_1} = \frac {\partial y}{\partial z'} \cdot \frac {\partial z'}{\partial a} \cdot \frac {\partial a}{\partial z} \cdot \frac {\partial z}{\partial b_1} = \sigma(z')[1-\sigma(z')]\cdot w_{21} \cdot \sigma(z)[1-\sigma(z)] \cdot 1 \tag{2}$$

这么求解貌似是可以的，however, 没有任何技巧可言，当网络结构有变化的时候，算法变的异常难写，比如：一层多个神经元的情况，两层之间非全连接的情况，某些神经元共享参数的情况等，想想都可怕，想要写个general的算法几乎不可能，另外还有计算量需要被考虑。

还好聪明人总是有的，考虑到$l$对$w$和对$b$求导过程其实是一样的，下面就仅介绍$y$对$w$的BP求导过程。

对于上面的问题，先只看第一层神经元的参数更新（其实对于任意层任意神经元都有下式的关系）：

$$\frac {\partial l}{\partial w} = \frac {\partial l}{\partial z} \frac {\partial z}{\partial w}$$

接下来分别计算$\frac {\partial l}{\partial z}$和$\frac {\partial z}{\partial w}$:
正向计算：

$$\frac {\partial z}{\partial w_{11}} = x_1 \\ \frac {\partial z}{\partial w_{12}} = x_2 \tag {3}$$

从式（3）可以看出正向计算有个非常好的性质，$x_1, x_1$就是神经元的值，这都已经在正向传播时计算过了！

反向计算：

$$\frac {\partial l}{\partial z} = \frac {\partial l}{\partial a} \frac {\partial a}{\partial z} \tag {4}$$

这其中，$\frac {\partial a}{\partial z}$很简单，sigmiod求导就ok了，而且$\sigma(x)'=\sigma(x)[1-\sigma(x)]$，nice，又可以用现成的结果了。

而对于$\frac {\partial l}{\partial a}$的计算比较棘手了，因为：

$$\frac {\partial l}{\partial a} =\frac {\partial l}{\partial z'} \frac {\partial z'}{\partial a} = \frac {\partial l}{\partial z'}\cdot w_{21} \tag {5}$$

其中$w_{21}$就是神经元间的连接权重参数，对于比较复杂的网络，计算$\frac {\partial l}{\partial a}$ 可以进行递归计算。如果被计算的$\frac {\partial l}{\partial z'}$是神经网络的最后一层（output layer），问题就变的简单了：

$$\frac {\partial l}{\partial z'}= \frac {\partial l}{\partial y} \frac {\partial y}{\partial z'} \tag{6}$$

结束了，，

$$\frac {\partial l}{\partial z} = \sigma(z)'[\frac {\partial l}{\partial z'}\cdot w_{21}]$$

再看一下反向计算$\frac {\partial l}{\partial z}$：因为$\frac {\partial a}{\partial z}$比较好求，是一个常数，sigmoid函数在该神经元上的求导就得到了；$\frac {\partial l}{\partial a}$呢则可以使用递归方法，只要求出output layer的$\frac {\partial l}{\partial z'}$就ok。从下图来看，就是input为$\frac {\partial l}{\partial z'}$，然后按照同样的网络反方向计算一次，和正向传播的不同之处仅仅在于sigmoid（非线性转换/激活函数）变成先求导再相乘，结构清晰，计算量也大幅度下降。

最后总结一下：正向传播和反向传播 相乘就可以计算出所有的参数更新梯度。

插句话：
神经网络中常用的优化算法是随机梯度下降法（SGD），实践中常用的是adam优化器（一种自适应步长/学习率的优化算法），理论上梯度下降做自适应步长也很简单，不过需要求Hessian矩阵，而对于上千万甚至上亿个参数的目标函数来说，计算量实在是太大了。

RNN怎么做BP

RNN的结构和前馈神经网络有所不同，所以反向传播和上述也略有不同，这里要介绍的算法叫做Backpropagation Through Time (BPTT)。这里假设读者对RNN、LSTM、GRU等算法已经有所了解了，就提纲挈领的介绍一下BPTT特别之处。

• 主要的不同点还是要看公式，RNN的在$t$时刻输出神经元的值可以用下式表示： $$a_{k,t} = \sigma (U_{k}a_{k,t-1} + W_{k}a_{k-1,t} +b_{k})$$ 式中$U_{k}$与上一时刻的计算结果相关
• 所以计算上多了一个时间相关项，其他的和之前说的没有什么不一样，$\frac {\partial l}{\partial W_{k}^{h}}$的计算也有一个递归的过程： $$\frac {\partial l^{n,t}}{\partial a_j^{k,t}} = \sum_s \frac {\partial l^{n,t}}{\partial z_s^{k+1,t}} \cdot \frac {\partial z_s^{k+1,t}}{\partial a_j^{k,t}} + \sum_s \frac {\partial l^{n,t}}{\partial z_s^{k,t+1}} \cdot \frac {\partial z_s^{k,t+1}}{\partial a_j^{k,t}} \\ \frac {\partial l^{n,t}}{\partial a_j^{k,t}} = \sum_s \frac {\partial l^{n,t}}{\partial z_s^{k+1,t}} \cdot W_{j,s}^{k+1} + \sum_s \frac {\partial l^{n,t}}{\partial z_s^{k,t+1}} \cdot U_{j,s}^{k}$$ 所以反向计算从最后时刻（latest）最后一层开始就好了
• 也可以认为就是结构上与前馈网络有所不同（如下图所示），对于每一个$y$都有一个loss，这里需要对每一个loss计算梯度，加起来就是整个需要更新的梯度了

一个简单的many2many形式的RNN展开图，图片来自这里。

代码实现

这里对基础版的反向传播算法进行代码实现，代码主要来自这里，但是原版代码有一点点错误，已被我修改，修改的版本可以点击这里进行查看。核心代码如下：

def feedforward(self, x):  # 正向计算
    # return the feedforward value for x
    a = np.copy(x)
    z_s = []
    a_s = [a]
    for i in range(len(self.weights)):
        activation_function = self.getActivationFunction(self.activations[i])
        z_s.append(self.weights[i].dot(a) + self.biases[i])
        a = activation_function(z_s[-1])
        a_s.append(a)
    return (z_s, a_s)

def backpropagation(self,y, z_s, a_s):  # 反向计算
    dw = []  # dl/dW
    db = []  # dl/db
    deltas = [None] * len(self.weights)  # delta = dl/dz  known as error for each layer
    # insert the last layer error
    deltas[-1] = ((y-a_s[-1])*(self.getDerivitiveActivationFunction(self.activations[-1]))(z_s[-1]))
    # Perform BackPropagation
    for i in reversed(range(len(deltas)-1)):
        deltas[i] = self.weights[i+1].T.dot(deltas[i+1])*(self.getDerivitiveActivationFunction(self.activations[i])(z_s[i]))
    #a= [print(d.shape) for d in deltas]
    batch_size = y.shape[1]
    db = [d.dot(np.ones((batch_size,1)))/float(batch_size) for d in deltas]
    dw = [d.dot(a_s[i].T)/float(batch_size) for i,d in enumerate(deltas)]
    # return the derivitives respect to weight matrix and biases
    return dw, db

下篇将会对算法代码进行剖析。

总结

反向传播算法1974年被提出，不过当时没有受到重视，2010年开始，得益于该算法和GPU算力的提升，人工智能开始迅速发展。

Reference

1. Werbos, P. (1974). Beyond Regression:” New Tools for Prediction and Analysis in the Behavioral Sciences. Ph. D. dissertation, Harvard University.
2. https://medium.com/@a.mirzaei69/implement-a-neural-network-from-scratch-with-python-numpy-backpropagation-e82b70caa9bb
3. https://www.youtube.com/watch?v=UTojaCzMoOs
4. http://corochann.com/recurrent-neural-network-rnn-introduction-1286.html
5. https://www.youtube.com/watch?v=esgbmJ6SnSY