大家好，又见面了，我是你们的朋友全栈君。

RNN学习笔记(一)-简介及BPTT RTRL及Hybrid(FP/BPTT)算法

本文假设读者已经熟悉了常规的神经网络，并且了解了BP算法，如果还不了解的，参见UFIDL的教程。
– 1.RNN结构
– 2.符号定义
– 3.网络unrolled及公式推导
– 4.BPTT
– 5.RTRL
– 6.Hybrid(FP/BPTT)
– 7.参考文献

1.RNN结构

如下图1是一个最简单的RNN：

其中集合$I$为$m$个外部输入节点，左下角的$U$为前一时刻的隐层输出节点，U中的节点数为$n$，并假定U中所有节点的输出都参与到下一时刻的输入。

2.符号定义

定义：
$x_i(t)$:$t$时刻第$i$个输入节点的输出值，且$i∈I∪U$
$s_k(t)$:$t$时刻第$k$个隐层节点的输出值，且$k∈U$
$y_k(t)$:$t$时刻第$k$个输出层节点的输出值，且$k∈U$
$d_k(t)$:$t$时刻隐层第$k$个节点的期望输出（即训练数据）
$w_{li}$:第$i$个输入到第$l$个隐层节点的权重，其中$i∈I，l∈U$
$w_{lk}$:第$k$个输入到第$l$个隐层节点的权重，其中$k，l∈U$
$\tau$:假定网络的起始时刻为$t_0$，当前时刻为$t$，$t'∈[t_0,t)$,$\tau∈(t',t]$
$y_k^*(\tau)$:$\tau$时刻第$k$个输出节点的输出值，且$k∈U,且\tau∈(t_0,t]$,对于所有的$\tau$而言，其实有$y_k(\tau)=y_k^*(\tau)$，这里之所以引入新符号，是为了避免求导运算时混淆1。

再来是一组等式定义：
$s_k(\tau+1)=wx(\tau)$
$e_k(t)=d_k(t)-y_k(t)$
$J(\tau)=\sum\limits_{k∈U}e_k(t)$
$J^{total}(t',t)=\sum\limits_{\tau=t'+1}^{t}J(\tau),t'∈[t_0,t)$
$\epsilon_k(\tau;F)=\frac{\partial F}{\partial y_k(\tau)}$
$e_k(\tau;F)=\frac{\partial F}{\partial y^*_k(\tau)}$
$\delta_k(\tau;F)=\frac{\partial F}{\partial s_k(\tau)}$
$p^k_{ij}(\tau)=\frac {\partial y_k(\tau)}{\partial w_{ij}}$
因为假定$F$只与$y_k(\tau),\tau ∈(t',t]$显式相关，所以，当$\tau≤t'$时，$e_k(\tau;F)=0$。
由于$F$是任意与$y_k(t)$相关的函数，实际应用中，可以取
$F=J(\tau)；F=J^{total}(t',t)$或其它函数。
因为初始状态的输出$y_k(t_0)$为预设值，与$w$之间不存在函数关系，所以当$\tau=t_0$时，$p^k_{ij}(t_0)=0$。

3.网络unrolled及公式推导

将网络按时间展开：

根据上图，下面两个式子成立：
$s_k(t+1)=\sum\limits_{l∈U}w_{kl}y_l(t)+\sum\limits_{l∈I}w_{kl}x^{net}_l(t)=\sum\limits_{l∈U∪I}w_{kl}x_l(t)......(2)$
$y_k(t+1)=f_k(s_k(t+1))......(3)$

显然，$y^*_k(\tau+1),y^*_k(\tau+2),...,y^*_k(t)$可以表示成$s(\tau+1)$的函数，因此，
$F=\mathbb {F}(y^*(t'),y^*(t'+1),...,y_k(\tau),s(\tau+1))=\mathbb {F}$
下面对公式进行进一步的推导：
$\epsilon_k(\tau;F)=\frac{\partial F}{\partial y_k(\tau)}$
$=\frac{\partial \mathbb {F}(y^*(t'),y^*(t'+1),...,y_k(\tau),s(\tau+1))}{\partial y_k(\tau)}$
由复合函数求导法则，上式可进一步变为：
$\frac{\partial \mathbb {F}}{\partial y(t')} \frac{\partial y(t')}{\partial y_k(\tau)}+\frac{\partial\mathbb {F}}{\partial y(t'+1)} \frac{\partial y(t'+1)}{\partial y_k(\tau)}+...+\frac{\partial \mathbb {F}}{\partial y^*(\tau)} \frac{\partial y^*(\tau)}{\partial y_k(\tau)}+\frac{\partial \mathbb {F}}{\partial s(\tau+1)} \frac{\partial s(\tau+1)}{\partial y_k(\tau)}$

当$\tau'<\tau$时，显然$y(\tau')$与$y(\tau)$无关，故上式的前半部分为0,即：
$\epsilon_k(\tau;F)=\frac{\partial \mathbb {F}}{\partial y^*(\tau)} \frac{\partial y^*(\tau)}{\partial y_k(\tau)}+\frac{\partial \mathbb {F}}{\partial s(\tau+1)} \frac{\partial s(\tau+1)}{\partial y_k(\tau)}$

这里：
$\frac{\partial \mathbb {F}}{\partial y^*(\tau)} = \begin{bmatrix}\frac{\partial \mathbb {F}}{\partial y_1^*(\tau)}\\\frac{\partial \mathbb {F}}{\partial y_2^*(\tau)}\\...\\\frac{\partial \mathbb {F}}{\partial y_k^*(\tau)}\\...\\\frac{\partial \mathbb {F}}{\partial y_n^*(\tau)}\\\end{bmatrix}$

$\frac{\partial y^*(\tau)}{\partial y_k(\tau)}= \begin{bmatrix}\frac{\partial y_1^*(\tau)}{\partial y_k^*(\tau)}\\\frac{\partial y_2^*(\tau)}{\partial y_k^*(\tau)}\\...\\\frac{\partial y_k^*(\tau)}{\partial y_k^*(\tau)}\\...\\\frac{\partial y_n^*(\tau)}{\partial y_k^*(\tau)}\\\end{bmatrix}= \begin{bmatrix}0\\0\\...\\1\\...\\0\\\end{bmatrix}$

$\frac{\partial \mathbb {F}}{\partial s(\tau+1)}= \begin{bmatrix}\frac{\partial \mathbb {F}}{\partial s_1(\tau+1)}\\\frac{\partial \mathbb {F}}{\partial s_2(\tau+1)}\\...\\\frac{\partial \mathbb {F}}{\partial s_l(\tau+1)}\\...\\\frac{\partial \mathbb {F}}{\partial s_n(\tau+1)}\\\end{bmatrix}= \begin{bmatrix}\delta_1(\tau+1;F)\\\delta_2(\tau+1;F)\\...\\\delta_l(\tau+1;F)\\...\\\delta_n(\tau+1;F)\\\end{bmatrix}$

$\frac{\partial s(\tau+1)}{\partial y_k(\tau)}= \begin{bmatrix}\frac{\partial s_1^*(\tau+1)}{\partial y_k^*(\tau)}\\\frac{\partial s_2^*(\tau+1)}{\partial y_k^*(\tau)}\\...\\\frac{\partial s_l^*(\tau+1)}{\partial y_k^*(\tau)}\\...\\\frac{\partial s_n^*(\tau+1)}{\partial y_k^*(\tau)}\\\end{bmatrix}= \begin{bmatrix}w_{1k}\\w_{2k}\\...\\w_{lk}\\...\\w_{nk}\\\end{bmatrix}$

代入，上式可以变为：
$\epsilon_k(\tau;F)= \begin{bmatrix}\frac{\partial \mathbb {F}}{\partial y_1^*(\tau)}\\\frac{\partial \mathbb {F}}{\partial y_2^*(\tau)}\\...\\\frac{\partial \mathbb {F}}{\partial y_k^*(\tau)}\\...\\\frac{\partial \mathbb {F}}{\partial y_n^*(\tau)}\\\end{bmatrix}^T \begin{bmatrix}0\\0\\...\\1\\...\\0\\\end{bmatrix}+ \begin{bmatrix}\delta_1(\tau+1;F)\\\delta_2(\tau+1;F)\\...\\\delta_l(\tau+1;F)\\...\\\delta_n(\tau+1;F)\\\end{bmatrix}^T \begin{bmatrix}w_{1k}\\w_{2k}\\...\\w_{lk}\\...\\w_{nk}\\\end{bmatrix}= \frac{\partial \mathbb {F}}{\partial y_k^*(\tau)}+\sum_{l∈U}w_{lk}\delta_l(\tau+1;F)$

所以就有：
$\epsilon_k(\tau;F)=\frac{\partial \mathbb {F}}{\partial y_k^*(\tau)}+\sum_{l∈U}w_{lk}\delta_l(\tau+1;F) =e_k(\tau;F)+\sum_{l∈U}w_{lk}\delta_l(\tau+1;F)$

因为当$\tau=t$时，$\epsilon_k(t;F)=e_k(t;F)$,所以有：

$$\epsilon_k(\tau;F)=\left\{\begin{aligned}e_k(t;F) \ \ if \ \ \tau=t\\e_k(\tau;F)+\sum_{l∈U}w_{lk}\delta_l(\tau+1;F) \ \ if\ \ \tau<t\\\end{aligned}\right.$$

$\delta_k(\tau;F)=\frac {\partial F}{\partial s_k(\tau)}=\frac {\partial F}{\partial y_k(\tau)}\frac {\partial y_k(\tau)}{\partial s_k(\tau)}=\epsilon_k(\tau;F)f'_k(s_k(\tau))$

进一步推导：
$\epsilon_k(\tau;F)=(e_k(\tau;F)+\sum_{l∈U}w_{lk}\delta_l(\tau+1;F))f'_k(s_k(\tau))$
先做如下定义：
$w_{ij}$:第$j$个输入到第$i$个隐层节点的权重（迭代更新之前），其中$i∈U,j∈U∪I$
$w_{ij}(\tau)$:$\tau$时刻第$j$个输入到第$i$个隐层节点的权重（迭代更新之前），其中$\tau∈[t_0,t),i∈U,j∈U∪I$

$\frac {\partial F}{\partial w_{ij}(\tau)}=\frac {\partial F}{\partial s_i(\tau+1)}\frac {\partial s_i(\tau+1)}{\partial w_{ij}(\tau)}=\delta_i(\tau+1;F)x_j(\tau)$

$\frac {\partial F}{\partial w_{ij}}=\sum\limits_{\tau=t_0}^{t-1}\frac {\partial F}{\partial w_{ij}(\tau)}\frac {\partial w_{ij}(\tau)}{\partial w_{ij}}=\sum\limits_{\tau=t_0}^{t-1}\frac {\partial F}{\partial w_{ij}(\tau)}=\sum\limits_{\tau=t_0}^{t-1}\delta_i(\tau+1;F)x_j(\tau)$

4.BPTT(Back Propagation Through Time)

4.1 Real-Time BPTT

算法描述：
令$\tau∈(t_0,t],k∈U$,
$\epsilon_k(t)=e_k(t),$
$\delta_k(\tau)=f'_k(s_k(\tau))\epsilon_k(\tau),$
$\epsilon_k(\tau-1)=\sum\limits_{l∈U}w_{lk}\delta_l(\tau),$
可以看出，算法的公式与BP算法非常相似，算法从t时刻开始，先用等式$\epsilon_k(t)=e_k(t)$求出$\epsilon_k(t)$，然后再用后边两个等式继续向后迭代，直到$t_0$。这里的第一步也被称为错误注入(injecting error),也说是在t时刻注入了$e_k(t)$。

上图描述了Real-Time BPTT算法在每一个时刻t的存储和处理操作。历史缓存每经过一个时刻t，就会增加一层的数据（包括该t时刻所有的输入和输出值）。实线箭头表明了当前的输出值由和上一时刻的输入输出值确定。虚线表示反向传播，计算直到$t_0+1$的$\delta$。步骤①为injecting error操作，剩下的步骤为每一步的误差计算。

激活函数通常取logistics函数，此时的$f'_k(s_k(\tau))=f_k(s_k(\tau))(1-f_k(s_k(\tau)))$
最后，权值的梯度通过下式计算：
$\frac {\partial J(t)}{\partial w_{ij}}=\sum\limits^t_{\tau=t_0+1}\delta_i(\tau)x_j(\tau-1)$

在每一个时刻t，算法的执行流程如下：
(1)将当前网络的状态和当前的输入值添加到历史缓存2；
(2)注入当前时刻$t$的$e_k(t)$,然后在时间区间$(t_0,t]$上进行反向传播,计算出所有的$\epsilon_k(\tau),\delta_k(\tau)$；
(3)计算所有的$\frac {\partial J(t)}{\partial w_{ij}}$;
(4)根据第(3)步的结果修改权值。

随着时间的增长，算法对历史缓存的需求将是无限的，因此，有时也用BPTT(∞)来表示这个算法，它在理论上的研究价值要远大于实用。接下来，我们将讨论更为实用的近似算法。

4.2 Epochwise BPTT

为了解决Real-Time BPTT对内存的无限制需求，我们采用一种近似的算法，即：Epochwise BPTT。
算法的目标是计算基于$J^{total}(t_0,t_1)$的梯度(即损失函数$F=J^{total}(t_0,t_1)$)，其步骤跟前边类似。同样的，
令$\tau∈(t_0,t_1],k∈U$,
$\epsilon_k(t_1)=e_k(t_1),$
$\delta_k(\tau)=f'_k(s_k(\tau))\epsilon_k(\tau),$
$\epsilon_k(\tau-1)=e_k(\tau-1)+\sum\limits_{l∈U}w_{lk}\delta_l(\tau),$

算法从最后的时刻$t_1$开始，injecting error $e_k(t_1)$，然后运用后边两个等式，迭代计算$\delta_k(\tau),\epsilon_k(\tau-1)$，直到$\tau=t_0+1$。此时权值的梯度按下式计算：
$\frac {\partial J^{total}(t_0,t_1)}{\partial w_{ij}}=\sum\limits^{t_1}_{\tau=t_0+1}\delta_i(\tau)x_j(\tau-1)$

对$[t_0,t_1]$中所有的输入输出以及目标值都被存储在历史缓存中。实线表示输出由上一时刻的输入和输出确定，当一次epoch完成后，执行BP操作（虚线箭头）。奇数索引的步骤表示error injection，偶数索引的步骤表示误差($\delta$)传播。一旦BP操作完成，每个权值的梯度就可以算出来了。

算法的执行流程如下：
(1)执行BP算法，计算所有的$\epsilon_k(\tau),\delta_k(\tau),\tau∈(t_0,t_1]$；
(2)计算所有的$\frac {\partial J^{total}(t_0,t_1)}{\partial w_{ij}}$；
(3)使用(2)的结果更新权值,重复步骤(1)~(3)；

5.RTRL(Real-Time Recurrent Learning)

与反向传播的BPTT算法不同的是，RTRL通过前向传播梯度来进行计算。

对任意的$k∈U,i∈U,j∈U∪I,以及t∈[t_0,t_1]$，定义：
$p^k_{ij}(t)=\frac {\partial y_k(t)}{\partial w_{ij}}$
令$F=J(t)$,有：
$\frac {\partial J(t)}{\partial w_{ij}}=\sum\limits_{k∈U}e_k(t)p^k_{ij}(t)$

根据之前的关系等式：
$s_k(t+1)=\sum\limits_{l∈U}w_{kl}y_l(t)+\sum\limits_{l∈I}w_{kl}x^{net}_l(t)=\sum\limits_{l∈U∪I}w_{kl}x_l(t)......(2)$
$y_k(t+1)=f_k(s_k(t+1))......(3)$
可以推出：
$p^k_{ij}(t+1)=\frac {\partial y_k(t+1)}{\partial w_{ij}}=\frac {\partial y_k(t+1)}{\partial s_k(t+1)}\frac {\partial s_k(t+1)}{\partial w_{ij}}=f'_k(s_k(t+1))[\sum\limits_{l∈U}w_{kl}p^l_{ij}(t)+\delta_{ik}x_j(t)]$3
此外，$t_0$时刻的输出为预设值，与连接权值无关，所以有：
$p^k_{ij}(t_0)=\frac {\partial y_k(t_0)}{\partial w_{ij}}=0$
于是，整个计算过程将从$t=t_0$开始迭代计算，直到$t=t_1$。
对每一个时刻$t$，计算相应的$y_k(t)$以及$\frac {\partial J(t)}{\partial w_{ij}}$

6.Hybrid(FP/BPTT)

$\frac {\partial F}{\partial w_{ij}}=\sum\limits_{\tau=t_0}^{t'-1}\frac {\partial F}{\partial w_{ij}(\tau)} +\sum\limits_{\tau=t'}^{t-1} \frac {\partial F}{\partial w_{ij}(\tau)}$
等式右边的第一部分可写为：
$\sum\limits_{\tau=t_0}^{t'-1}\frac {\partial F}{\partial w_{ij}(\tau)} =\sum\limits_{\tau=t_0}^{t'-1}\sum\limits_{l∈U}\frac {\partial F}{\partial y_l(t')}\frac {\partial y_l(t')}{\partial w_{ij}(\tau)}=\sum\limits_{l∈U}\frac {\partial F}{\partial y_l(t')}\sum\limits_{\tau=t_0}^{t'-1}\frac {\partial y_l(t')}{\partial w_{ij}(\tau)}=\sum\limits_{l∈U}\frac {\partial F}{\partial y_l(t')}\frac {\partial y_l(t')}{\partial w_{ij}}=\sum\limits_{l∈U}\epsilon_l(t';F)p_{ij}^l(t')$
因此，最初的式子可变为：
$\frac {\partial F}{\partial w_{ij}}=\sum\limits_{l∈U}\epsilon_l(t';F)p_{ij}^l(t')+\sum\limits_{\tau=t'}^{t-1} \delta_i(\tau+1;F)x_j(\tau)$
令$F=J^{total}(t',t)$
$\frac {\partial J^{total}(t',t)}{\partial w_{ij}}=\sum\limits_{l∈U}\epsilon_l(t')p_{ij}^l(t')+\sum\limits_{\tau=t'}^{t-1} \delta_i(\tau+1)x_j(\tau)$

首先计算BPTT：

$$\epsilon_k(\tau)=\left\{\begin{aligned}\delta_{kr} \ \ if \ \ \tau=t\\\sum_{l∈U}w_{lk}\delta_l(\tau+1) \ \ if\ \ \tau<t\\\end{aligned}\right.$$

然后，使用上边的计算结果执行：
$p^r_{ij}(t)=\sum\limits_{l∈U}\epsilon_l(t')p^l_{ij}(t')+\sum\limits^{t-1}_{\tau=t'}\delta_{l}(\tau+1)x_j(\tau)$

上图是FP/BPTT(h)算法的简单描述。可以看到，算法包含两个连续的误差计算过程。一个在时刻$t$，另一个在时刻$t+h$.从时刻$t-h$直到时刻$t$的输入、输出和目标值都存储在历史缓存中。

7.参考文献

1.Gradient-Based Learning Algorithms for Recurrent Networks and Their Computational Complexity.Ronald J. Williams,David Zipser