随时间反向传播 （BackPropagation Through Time，BPTT）¶
RNN（循环神经网络，Recurrent Neural Network）是一种具有长时记忆能力的神经网络模型，被广泛应用于序列标注（Sequence Labeling）问题。在序列标注问题中，模型的输入是一段时间序列，记为$\mathbf{x}=\{x_1,x_2,...,x_T\}$，我们的目标是为输入序列的每个元素打上标签集合中的对应标签，记为$\mathbf{y}=\{y_1,y_2,...,y_T\}$。
NLP中的大部分任务（比如分词、实体识别、词性标注）都可以最终归结为序列标注问题。这类问题中，输入是语料库中一段由$T$个词（或字）构成的文本$\mathbf{x}=\{x_1,x_2,...,x_T\}$（其中$x_t$表示文本中的第$t$个词）；输出是每个词对应的标签，根据任务的不同标签的形式也各不相同，但本质上都是针对每个词根据它的上下文进行标签的分类。
一个典型的RNN的结构如下图所示：
从图中可以看到，一个RNN通常由三层组成，分别是输入层、隐藏层和输出层。与一般的神经网络不同的地方是，RNN的隐藏层存在一条有向反馈边，正是这种反馈机制赋予了RNN记忆能力。要理解左边的图可能有点难度，我们可以将其展开为右边这种更直观的形式，其中RNN的每个神经元接受当前时刻的输入$x_t$以及上一时刻隐单元的输出$h_{t-1}$，计算出当前神经元的输入$s_t$，经过激活函数变换得到输出$h_t$，并传递给下一时刻的隐单元。此外，我们还需要注意到RNN中每个时刻上的神经元的参数都是相同的（类似CNN的权值共享），这么做一方面是减小参数空间，保证泛化能力；另一方面是为了赋予RNN记忆能力，将有用信息存储在$W_{in},W_{rec},W_{out}$三个矩阵中。
由于RNN是一种基于时序数据的神经网络模型，因此传统的BP算法并不适用于该模型的优化，这要求我们提出新的优化算法。RNN中最常用的优化算法是随时间反向传播（BackPropagation Through Time，BPTT），下文将叙述BPTT算法的数学推导。
符号注解¶
在进一步讨论BPTT之前，先来总结一下本文要用到的数学符号。
| 符号 | 解释 |
|---|---|
| $K$ | 词汇表的大小 |
| $T$ | 句子的长度 |
| $H$ | 隐藏层单元数 |
| $\mathbf{x}=\{x_1,x_2,...,x_T\}$ | 句子的单词序列 |
| $x_t\in\mathbb{R}^{K\times 1}$ | 第$t$个时刻RNN的输入，one-hot vector |
| $\hat{y}_t\in\mathbb{R}^{K\times 1}$ | 第$t$时刻softmax层的输出，估计每个词出现的概率 |
| $y_t\in\mathbb{R}^{K\times 1}$ | 第$t$时刻的label，为每个词出现的概率，one-hot vector |
| $E_t$ | 第$t$个时刻（第$t$个word）的损失函数,定义为交叉熵误差$E_t=-y_t^Tlog(\hat{y}_t)$ |
| $E$ | 一个句子的损失函数，由各个时刻（即每个word）的损失函数组成,$E=\sum\limits_t^T E_t$（注： 由于我们要推导的是SGD算法， 更新梯度是相对于一个训练样例而言的， 因此我们一次只考虑一个句子的误差，而不是整个训练集的误差（对应BGD算法）） |
| $s_t\in\mathbb{R}^{H\times 1}$ | 第$t$个时刻RNN隐藏层的输入 |
| $h_t\in\mathbb{R}^{H\times 1}$ | 第$t$个时刻RNN隐藏层的输出 |
| $z_t\in\mathbb{R}^{K\times 1}$ | 输出层的汇集输入 |
| $\delta^{(t)}_k=\frac{\partial E_t}{\partial s_k}$ | 第$t$个时刻损失函数$E_t$对第$k$时刻带权输入$s_k$的导数 |
| $r_t=\hat{y}_t-y_t$ | 残差向量 |
| $W_{in}\in\mathbb{R}^{H\times K}$ | 从输入层到隐藏层的权值 |
| $W_{rec}\in\mathbb{R}^{H\times H}$ | 隐藏层上一个时刻到当前时刻的权值 |
| $W_{out}\in\mathbb{R}^{K\times H}$ | 隐藏层到输出层的权值 |
上述符号之间的关系：
$$\left\{\begin{aligned}&s_t=W_{rec}h_{t-1}+W_{in}x_t\\&h_t=tanh(s_t)\\&z_t=W_{out}h_t\\& \hat{y}_t=\mathrm{softmax}(z_t)\\&E_t=-y_t^Tlog(\hat{y}_t)\\&E=\sum\limits_t^T E_t \end{aligned}\right.$$
这里有必要对上面的一些符号进行进一步解释。
- 本文只讨论输入为one-hot vector的情况，这种向量的特点是茫茫0海中的一个1，即只用一个1表示某个单词的出现；其余的0均表示单词不出现。
- RNN要预测的输出是一个one-hot vector，表示下一个时刻各个单词出现的概率。
- 由于$y_t$是one-hot vector，不妨假设$y_{t,j}=1(y_{t,i}=0,i\neq j)$，那么当前时刻的交叉熵为$E_t=-y_t^T \log(\hat{y}_t)=-\log(\hat{y}_{t,j})$。也就是说如果$t$出现的是第$j$个词，那么计算交叉熵时候只要看$\hat{y}_t$的第$j$个分量即可。
- 由于$x_t$是one-hot向量，假设第$j$个词出现，则$W_{in}x_t$相当于把$W_{in}$的第$j$列选出来，因此这一步是不用进行任何矩阵运算的，直接做下标操作即可。
BPTT与BP类似，是在时间上反传的梯度下降算法。RNN中，我们的目的是求得$\frac{\partial E}{\partial W_{in}},\frac{\partial E}{\partial W_{rec}},\frac{\partial E}{\partial W_{out}}$，根据这三个变化率来优化三个参数$W_{in},W_{rec},W_{out}$。注意到$\frac{\partial E}{\partial W_{in}}=\sum\limits_t \frac{\partial E_t}{\partial W_{in}}$，因此我们只要对每个时刻的损失函数求偏导数再加起来即可。矩阵求导有两种布局方式：分母布局（Denominator Layout）和分子布局（Numerator Layout），关于分子布局和分母布局的区别，请参考文献3。如果这里采用分子布局，那么更新梯度时还需要将梯度矩阵进行一次转置，因此出于数学上的方便，后续的矩阵求导都将采用分母布局
1.计算$\frac{\partial E_t}{\partial W_{out}}$¶
注意到$E_t$是$W_{out}$的复合函数，参考文献3中Scalar-by-matrix identities一节中关于复合矩阵函数求导法则（右边的是分母布局）：
我们有：
$$ \begin{aligned}\frac{\partial E_t}{\partial W_{out}(i,j)}&=tr\bigg( \big( \frac{\partial E_t}{\partial z_t}\big)^T\cdot \frac{\partial z_t}{\partial W_{out}(i,j)}\bigg)\\&=tr\bigg((\hat{y}_t-y_t)^T\cdot\begin{bmatrix}0\\ \vdots \\ \frac{\partial z_{t}^{(i)}}{\partial W_{out}(i,j)}\\\vdots\\0\end{bmatrix}\bigg)\\&=r_t^{(i)} h_t^{(j)}\end{aligned}$$
其中$r_t^{(i)}=(\hat{y}_t-y_t)^{(i)}$表示残差向量第$i$个分量，$h_t^{(j)}$表示$h_t$的第j个分量。
上述结果可以改写为：
$$ \frac{\partial E_t}{\partial W_{out}}=r_t\otimes h_t$$
$$ \frac{\partial E}{\partial W_{out}} = \sum_{t=0}^T r_t\otimes h_t $$
其中$\otimes$表示向量外积。
2.计算$\frac{\partial E_t}{\partial W_{rec}}$¶
由于$W_{rec}$是各个时刻共享的，所以$t$时刻之前的每个时刻$W_{rec}$的变化都对$E_t$有贡献，反过来求偏导时，也要考虑之前每个时刻$W_{rec}$对$E$的影响。我们以$s_k$为中间变量，应用链式法则：
$$ \frac{\partial E_t}{\partial W_{rec}} = \sum_{k=0}^t \frac{\partial s_k}{\partial W_{rec}} \frac{\partial E_t}{\partial s_k}$$
但由于$\frac{\partial s_k}{\partial W_{rec}}$（分子向量，分母矩阵）以目前的数学发展水平是没办法求的，因此我们要求这个偏导，可以拆解为$E_t$对$W_{rec}(i,j)$的偏导数：
$$ \frac{\partial E_t}{\partial W_{rec}(i,j)} = \sum_{k=0}^t tr[(\frac{\partial E_t}{\partial s_k})^T \frac{\partial s_k}{\partial W_{rec}(i,j)}]= \sum_{k=0}^t tr[(\delta_k^{(t)})^T\frac{\partial s_k}{\partial W_{rec}(i,j)}]$$
其中，$\delta^{(t)}_k=\frac{\partial E_t}{\partial s_k}$，遵循
$$s_k\to h_k\to s_{k+1}\to ...\to E_t$$
的传递关系，应用链式法则有：
$$\delta^{(t)}_k=\frac{\partial h_k}{\partial s_k}\frac{\partial s_{k+1}}{\partial h_k} \frac{\partial E_t}{\partial s_{k+1}}=diag(1-h_k\odot h_k)W_{rec}^T\delta^{(t)}_{k+1}=(W_{rec}^T\delta^{(t)}_{k+1})\odot (1-h_k\odot h_k)$$
其中，$\odot$表示向量点乘（element-wise product）。注意$E_t$求导时链式法则的顺序，$E_t$是关于$s_k$的符合函数，且求导链上的每个变量都是向量，根据参考文献3，这种情况下应用分母布局的链式法则，方向应该是相反的。
接下来计算$\delta^{(t)}_t$：
$$\delta^{(t)}_t=\frac{\partial E_t}{\partial s_t}=\frac{\partial h_t}{\partial s_t}\frac{\partial z_t}{\partial h_t}\frac{\partial E_t}{\partial z_t}=diag(1-h_t\odot h_t)\cdot W_{out}^T\cdot(\hat{y}_t-y_t)=(W_{out}^T(\hat{y}_t-y_t))\odot (1-h_t\odot h_t)$$
于是，我们得到了关于$\delta$ 的递推关系式：
$$\left\{\begin{aligned}\delta^{(t)}_t&=(W_{out}^T r_t)\odot (1-h_t\odot h_t)\\ \delta^{(t)}_k&=(W_{rec}^T\delta^{(t)}_{k+1})\odot (1-h_k\odot h_k)\end{aligned}\right.$$
由$\delta^{(t)}_t$出发，我们可以往前推出每一个$\delta$，
将$\delta^{(t)}_0,...,\delta^{(t)}_t$代入$ \frac{\partial E_t}{\partial W_{rec}(i,j)} $有：
$$ \frac{\partial E_t}{\partial W_{rec}(i,j)} = \sum_{k=0}^t \delta_k^{(t)} h_{k-1}^{(j)} $$
将上式写成矩阵形式：
$$ \frac{\partial E_t}{\partial W_{rec}} = \sum_{k=0}^t \delta^{(t)}_k \otimes h_{k-1} \\\frac{\partial E}{\partial W_{rec}}=\sum_{t=0}^T \sum_{k=0}^t \delta^{(t)}_k \otimes h_{k-1}$$
不失严谨性，定义$h_{-1}$为全0的向量。
3.计算$\frac{\partial E_t}{\partial W_{in}}$¶
按照上述思路，我们可以得到
$$ \frac{\partial E_t}{\partial W_{in}} = \sum_{k=0}^t \delta_k \otimes x_{k} $$
由于$x_k$是个one-hot vector，假设$x_k(m)=1$，那么我们在更新$W$时只需要更新$W$的第$m$列即可。
参数更新¶
我们有了$E_t$关于各个参数的偏导数，就可以用梯度下降来更新各参数了：
$$\begin{aligned}&W_{in}:=W_{in}-\lambda \sum_{t=0}^T \sum_{k=0}^t \delta_k \otimes x_{k} \\& W_{rec}:=W_{rec}-\lambda \sum_{t=0}^T \sum_{k=0}^t \delta_k \otimes h_{k-1}\\ &W_{out} :=W_{out}-\lambda \sum_{t=0}^T r_t \otimes h_t\end{aligned}$$其中$r_t=\hat{y}_t-y_t$，$\delta_t=\frac{\partial E_t}{\partial s_t}=(W_{out}^T r_t)\odot (1-h_t\odot h_t)$，$\lambda>0$表示学习率
一些个人思考¶
- 为什么RNN中要对隐藏层的输出进行一次运算$z_t=W_{out}h_t$，然后再对$z_t$进行一次softmax，而不是直接对$h_t$进行softmax求得概率？为什么要有$W_{out}$这个参数？
答：
$x_t$是一个$K\times 1$的向量，我们要将它映射到一个$H\times 1$的$h_t$（其中$H$是隐神经元的个数），从$x_t$到$h_t$相当于对词向量做了一次编码；最终我们要得到的是一个$K\times 1$的向量（这里$K$是词汇表大小），表示每个词接下来出现的概率，所以我们需要一个矩阵$K\times H$的$W_{out}$来将$h_t$映射回原来的空间去，这个过程相当于解码。因此，RNN可以理解为一种编解码网络。 - $W_{in},W_{rec},W_{out}$三个参数分别有什么意义？
答：
$W_{in}$将$K\times 1$的one-hot词向量映射到$H\times 1$隐藏层空间，将输入转化为计算机内部可理解可处理的形式，这个过程可以理解为一次编码过程；$W_{rec}$则是隐含层到自身的一个映射，它定义了模型如何结合上文信息，在编码中融入了之前的“记忆”；$W_{in},W_{rec}$结合了当前输入单词和之前的记忆，形成了当前时刻的知识状态。$W_{out}$是隐含层到输出的映射，$z=W_{out}h$是映射后的分数，这个过程相当于一次解码。这个解码后的分数再经过一层softmax转化为概率输出来，我们挑选概率最高的那个作为我们的预测。作为总结， RNN的记忆由两部分构成，一部分是当前的输入，另一部分是之前的记忆。 - BPTT和BP的区别在哪？为什么不能用BP算法训练RNN？
答：BP算法只考虑了误差的导数在上下层级之间梯度的反向传播；而BPTT则同时包含了梯度在纵向层级间的反向传播和在时间维度上的反向传播，同时在两个方向上进行参数优化。 - 文中词$x_t$的特征是一个one-hot vector，这里能不能替换为word2vec训练出的词向量？效果和性能如何？
答：RNNLM本身自带了训练词向量的过程。由于$x_t$是one-hot向量，假设出现的词的索引为$j$，那么$W_{in}x_t$就是把$W_{in}$的第$j$列$W[:,j]$取出，这个列向量就相当于该词的词向量。实际上用语言模型训练词向量的思想最早可以追溯到03年Bengio的一篇论文《A neural probabilistic language model 》，这篇论文中作者使用一个神经网络模型来训练n-gram模型，顺便学到了词向量。本文出于数学推导以及代码实现上的方便采用了one-hot向量作为输入。实际工程中，一般采用one-hot方式来训练词向量，而word2vec可以作为词向量的一个较好的初始值；当然也可以将词向量固定为word2vec来训练（即不更新），但是这样做一般效果较差。
参考：
1.使用RNN解决NLP中序列标注问题的通用优化思路
2.wildml的rnn tutorial part3
3.Matrix Calculus Wiki
4.《神经网络与深度学习讲义》 邱锡鹏
没有评论:
发表评论