logo
BosonNLP Blog

当我们在谈深度学习时,到底在谈论什么(二)

Alt text

后向传播

上一次的分享我们提到了神经网络的几个基本概念,其中提到了随机梯度下降(SGD)算法是神经网络学习(或者更通用的,一般性参数优化问题)的主流方法。概念上,神经网络的学习非常简单,可以被归纳为下面的步骤:(a) 构造神经网络结构(选择层数、激活函数等);(b) 初始化构造出的神经网络参数\(w\);(c) 对于给定的训练样本\((x, y)\)与当前的\(w\),计算梯度\(\triangledown w\);(d) 通过(随机)梯度下降算法更新\(w\)。例如,不考虑任何正则化因子情况的最简单参数更新为

$$w = w - \eta\triangledown w.$$

神经网络的初学者往往会发现,上述四个步骤当中,对于给定样本\((x,y)\),计算其梯度是最不直观的一个步骤。本文我们玻森(bosonnlp.com)的讨论就围绕解决梯度\(\triangledown w\)的核心算法:后向传播算法来展开。

首先理清一个概念,步骤(d)的梯度下降算法是一种优化算法,而我们要讨论的后向传播算法,是计算步骤(c)中所需要梯度\(\triangledown w\)的一种算法。下面的讨论,我们首先完成单参数(即只有一个参数\(w\in\mathbb R\)需要学习)的特例情况下的推导,进而通过动态规划(Dynamic programming)思想,将其推导泛化到多变量的情况。需要注意的是,虽然后向传播概念上并不复杂,所用到的数学工具也很基本,但由于所涉及的变量较多、分层等特点,在推导的时候需要比较仔细,类似绣花。

单参数情况

特例

在讨论后向传播算法之前,我们简单回顾一下单变量微积分中的求导规则。来看个例子,假设我们有一个极端简化的网络,其中只有一个需要学习的参数\(w\),形式如下

$$y = w^2x +1.$$

并且假设损失函数Cost为平方误差(MSE)。

$$\text{Cost}(y, \bar y)= \frac{1}{2}(y - \bar y)^2.$$

假设我们只有一个训练样本\((x, y)= (1, 1)\)。因为这个形式非常简单,我们试试将该样本直接带入损失函数:

$$\text{Cost}(y, \bar y)= \frac{1}{2}(w^2\cdot1 + 1 - 1)^2= \frac{1}{2}w^4.$$

显然当\(w=0\)时,我们可以让损失函数为0,达到最优。下面让我们假装不知道最优解,考虑如何用梯度下降方法来求解。假设我们猜\(w_0=2\)为最优,带入计算得到

$$\text{Cost}(y, \bar y)= \frac{1}{2}w^4= 8.$$

嗯,不算太坏的一个初始值。让我们计算其梯度,或者损失函数关于\(w\)的导数。

$$\text{Cost}'(y, \bar y)= \left(\frac{1}{2}w^4\right)' = 2*w^3.$$

设置学习率参数\(\eta=0.02\),我们可以通过梯度下降方法来不断改进\(w\),以达到降低损失函数的目的。三十个迭代的损失函数变化如下:

Alt text

生成上图采用的是如下Python代码

import matplotlib.pyplot as plt

w0, eta, n_iter = 2, 0.02, 30
gradient_w = lambda w: 2*(w**3)
cost = lambda w: 0.5*(w**4)
costs = []
w = w0
for i in range(n_iter):
    costs.append(cost(w))
    w = w - eta*gradient_w(w)

# gradient
descentplt.plot(range(n_iter), costs)

可以发现,经过30次迭代后,我们的参数\(w\)从初始的2改进到了0.597,正在接近我们的最优目标\(w^*=0\)

对于一般\(f(w)\)的情况

回忆一下,上面的结果是基于我们给定 \(y = w^2x +1.\)下得到的,注意这里我们假设输入信号\(x\)为常量。我们将上面的求解步骤做一点点泛化。

$$y = f(w)$$

重复上面的求解

$$\text{Cost}(y, \bar y)= \frac{1}{2}(y - \bar y)^2 = \frac{1}{2}\left(f(x)- \bar y\right)^2$$

关于w求导,

$$\text{Cost}'(y, \bar y)= \left[f(w)- \bar y\right](f(w)- \bar y)'\\= \left[f(w)- \bar y\right]f'(w).$$

注意,上面求导用到了链式法则(Chain Rule),即

$$\left(f(g(w)\right)' = f'(g(w))g'(w),$$

或者写成偏导数形式:

$$\frac{\partial f}{\partial w}= \frac{\partial f}{\partial g}\frac{\partial g}{\partial w}.$$

对于一般性损失函数的情况

上式推导基于损失函数为平方最小下得出,那么我们再泛化一点,对于任意给定的可导损失函数,其关于\(w\)的梯度:

$$\text{Cost}'(y, \bar y)= \triangledown \text{Cost}(f(w), \bar y)f'(w),$$

其中\(\triangledown \text{Cost}(f(w), \bar y)\)是损失函数关于\(f(w)\)的导数。实际上这个形式很通用,对于任意特定的损失函数和神经网络的激活函数,都可以通过这个式子进行梯度计算。譬如,对于一个有三层的神经网络

$$f(w)= f_3(f_2(f_1(w))),$$

同样通过链式法则,

$$f'(w)= f_3'(f_2(f_1(w)))f_2'(f_1(w))f_1'(w).$$

上式看上去比较复杂,我们可以在符号上做一点简化。令每一层网络得到的激活函数结果为\(a_i\),即\(a_1 = f_1(w), a_2 = f_2(f_1(w))\), 那么:

$$f'(w)= f_3'(a_2)f_2'(a_1)f_1'(w).$$

即:不论复合函数\(f\)本身有多么复杂,我们都可以将其导数拆解成每一层函数\(f_i\)的导数的乘积。

$$f'(w)= f'_1(w)\prod_{i=2}^{L}f'_{i}(a_{i-1}).$$

上面的推导我们给出了当神经网络仅仅被一个可学习参数\(w\)所刻画的情况。一句话总结,在单参数的网络推导中,我们真正用到的唯一数学工具就是链式法则。实际问题中,我们面对的参数往往是数以百万计的,这也就是为什么我们无法采用直觉去“猜”到最优值,而需要用梯度下降方法的原因。下面我考虑在多参数情况下,如何求解梯度。

多参数情况

首先,不是一般性的,我们假设所构建的为一个\(L\)层的神经网络,其中每一层神经网络都经过线性变换和非线性变换两个步骤(为简化推导,这里我们略去对bias项的考虑):

$$z^l = W^l a^{l-1}\quad(线性变换)\\a^l = f_l(z^l)\quad(非线性变换)$$

定义网络的输入\(a^0 = x \in\mathbb R^n\),而\(a^L\)作为输出层。一般的,我们令网络第\(l\)层具有\(n_l\)个节点,那么\(a^l, z^l\in\mathbb R^{n_l}, W^l \in\mathbb R^{n_l\times n_{l-1}}\)。注意此时我们网络共有\(N=n_0 n_1+\cdots+n_{L-1}n_L\)个参数需要优化。

为了求得梯度\(\triangledown w\),我们关心参数\(W^l_{ji}\)关于损失函数的的导数:\(\frac{\partial\text{Cost}}{\partial W^l_{ji}}\),但似乎难以把\(W^l_{ji}\)简单地与损失函数联系起来。问题在哪里呢?事实上,在单参数的情况下,我们通过链式法则,成功建立第一层网络的\(w\)参数与最终损失函数的联系。譬如,\(f(w)= f_2(f_1(w))\)\(w\)的改变影响\(f_1\)函数的值,而连锁反应影响到\(f_2\)的函数结果。那么,对于\(W^l_{ji}\)值的改变,会影响\(z^{l}_j\),从而影响\(a^{l}_j\)。通过\(W^{l+1}\)的线性变换(因为\(z^{l+1}= W^{l+1}a^{l}\)),\(a^{l}_j\)的改变将会影响到每一个\(z^{l+1}_k (1\le k \le n_{l+1})\)

Alt text

将上面的思路写下来:

$$ \begin{align*} \frac{\partial\text{Cost}}{\partial W^l_{ji}}& = \frac{\partial\text{Cost}}{\partial z^l_j}\frac{\partial z^l_j}{\partial W^l_{ji}}\\ & = \frac{\partial\text{Cost}}{\partial a^l_j}\frac{\partial a^l_j}{\partial z^l_j}\frac{\partial z^l_j}{\partial W^l_{ji}}\\ & = \sum_k \frac{\partial\text{Cost}}{\partial a^{l+1}_k}\frac{\partial a^{l+1}_k}{z^{l+1}_k}\frac{z^{l+1}_k}{\partial a^l_j}\frac{\partial a^l_j}{\partial z^l_j}\frac{\partial z^l_j}{\partial W^l_{ji}}\\ & = \sum_k \frac{\partial\text{Cost}}{\partial a^{l+1}_k}f'_{l+1}(z^{l+1}_k)W^{l+1}_{kj}f'_l(z^l_j)a^{l-1}_i \\ & = \sum_{k, m}\frac{\partial\text{Cost}}{\partial a^{l+2}_m}f'_{l+2}(z^{l+2}_m)W^{l+2}_{mk}f'_{l+1}(z^{l+1}_k)W^{l+1}_{kj}f'_l(z^l_j)a^{l-1}_i \end{align*} $$

可以通过上式不断展开进行其梯度计算。这个方式相当于我们枚举了每一条\(W^l_{ji}\)改变对最终损失函数影响的路径。通过简单使用链式法则,我们得到了一个指数级复杂度的梯度计算方法。稍仔细观察可以发现,这个是一个典型的递归结构(为什么呢?因为\(z^l = W^l a^{l-1}\)定义的是一个递归结构),可以采用动态规划(Dynamic programming)方法,通过记录子问题答案而进行快速求解。设\(\delta^l_i=\frac{\partial Cost}{\partial z^l_i}\)用于动态规划的状态记录。我们先解决最后一层的边界情况:

$$\delta^L_i = \frac{\partial\text{Cost}}{\partial z^L_i}= \sum_j \frac{\partial\text{Cost}}{\partial a^L_j}\frac{\partial a^L_j}{\partial z^L_i}.$$

上式为通用形式。对于Sigmoid, Tanh等形式的element-wise激活函数,因为可以写成\(a^L_j=f_L(z^L_j)\)的形式,所示上式可以简化为:

$$\delta^L_i =\frac{\partial\text{Cost}}{\partial z^L_i}= \frac{\partial\text{Cost}}{\partial a^L_i}\frac{\partial a^L_i}{\partial z^L_i}= \triangledown\text{Cost}(a^L_i, \bar y)f'_L(z_i^L).$$

即该情况下,最后一层的关于\(z_i^L\)的导数与损失函数在\(a^L_i\)导数和最后一层激活函数在\(z_i^L\)的导数相关。注意当选择了具体的损失函数和每层的激活函数后,\(\triangledown\text{Cost}\)\(f'_i\)也被唯一确定了。下面我们看看动态规划的状态转移情况:

$$\delta^l_i = \frac{\partial\text{Cost}}{\partial z^l_i}= \sum_j \frac{\partial\text{Cost}}{\partial z^{l+1}_j}\frac{\partial z^{l+1}_j}{\partial z^l_i}\\=\sum_j \delta^{l+1}_j W^{l+1}_{ji}f'_l(z^l_i),$$

成功建立\(\delta^l\)\(\delta^{l+1}\)的递推关系,所以整个网络的\(\delta^l_i\)可以被计算出。在确定了\(\delta^l_i\)后,我们的对于任意参数\(W^l_{ji}\)的导数可以被简单表示出:

$$\frac{\partial\text{Cost}}{\partial W^l_{ji}}= \frac{\partial\text{Cost}}{\partial z^l_j}\frac{\partial z^l_j}{\partial W^l_{ji}}\\= \delta^l_j a^{l-1}_i.$$

至此,我们通过链式法则和动态规划的思想,不失一般性的得到了后向传播算法的推导。


讨论

1. 后向传播算法的时间复杂度是多少?

不难看出,为了进行后向传播,我们首先需要计算每一层的激活函数,即\(a^l (1\le l \le L)\),这一步与后向传播相对,通常称为前向传播,复杂度为\(O(N)\),与网络中参数的个数相当。而后向传播的步骤,通过我们的状态转移的推导,也可以看出其复杂度为\(O(N)\),所以总的时间复杂度为\(O(N)\)。需要注意的是,采用mini-batch的方式优化时,我们会将\(b\)个样本打包进行计算。这本质上将后向传播的矩阵-向量乘积变成了矩阵-矩阵乘积。对于任意两个\(n\times n\)的矩阵的乘法,目前理论最优复杂度为\(O(n^{2.3728})\)的类Coppersmith–Winograd算法。这类算法由于常数巨大,不能很好利用GPU并行等限制,并没有在真正在机器学习或数值计算领域有应用。寻求智力挑战的朋友可阅读Powers of tensors and fast matrix multiplication

2. 对于后向传播的学习算法,生物上是否有类似的机制?

这是一个有争议的问题。Hinton教授在其How to do backpropagation in a brain演讲当中,讲到了人们对于后向传播不能在生物学上实现的三个原因:a) 神经元之间不传播实数信号,而通过尖峰信号(spikes)沟通。Hinton解释说通过Poisson过程,意味着可以传递实数信号,并且采用spike而不是实数进行信号传递是一个更鲁邦的过程。b) 神经元不会求导(\(f'_l(\cdot)\))。Hinton说通过构建filter可以实现(数值)求导过程。c) 神经元不是对称的?或者说神经元连接不是一个无向图而是有向图。这意味着通过前向传播\(W^l a^{l-1}\)与后向传播的\(W^l\)并不应该是一个\(W\)。Hinton教授解释说,通过一些数值实验发现,其实即便前向后向的\(W\)不对称(比如让后向传播的W为固定的随机矩阵),采用类似的梯度算法也可以收敛到不错的解。我不同意Hinton教授的观点。其解释在逻辑上混淆一个基本常识:大脑可以做到并不意味着大脑事实是这样完成运算的。其实我们已经看到,通过与非门也可以完成所有的函数运算,但这并不代表我们大脑里面一定装载了10亿个与非门。而有大量证据表明(如能耗,小样本学习),后向传播算法与真实大脑学习的机制相去甚远。所以我觉得更合理的对待,仍然是将后向传播作为一种高效计算嵌套函数梯度的数值算法工具,而不必强行将其附会成大脑的工作原理。

下一次分享,我们主要从优化算法的正则化(Regularization)的角度进行讨论,欢迎关注~