3.6.循环神经网络

    网络输出不仅和当前时刻输入相关，也和过去一段时间的输出相关，如有限自动状态机。

    循环神经网络（Recurrent Neural Network, RNN）是具有短期记忆的神经网络，它的参数学习可使用随时间反向传播算法来学习，如果序列比较长，也会出现梯度爆炸和消失问题，称为长程依赖问题，可使用门控机制（Gating Mechanism）来解决。

• 递归神经网络

• 图网络

1.给网络增加记忆力

    由于前馈网络不具备记忆能力，所以采用三种方式来增加网络记忆能力。

1.1.延时神经网络

    一种最简单的利用历史信息的方法是创建一个额外延时单元，来存储网络的历史信息（输入、输出、隐状态），比较有代表性的模型是延时神经网络。延时神经网络是在前馈网络中的非输出层都添加一个延时器，记录神经元最近几次活性值，在$t$个时刻，第$l$层神经元的活性值依赖$l-1$层神经元最近$K$个时刻的活性值：

$h_t^{(l)} = f(h_t^{(l-1)},h_{t-1}^{(l-1)},...,h_{t-K}^{(l-1)})$

1.2.自回归模型

    自回归模型（AutoRegressive Model,AR）是统计学上常用的一类时间序列模型，用一个变量$y_t$的历史信息来预测自己

$y_t = w_0 + \sum\limits_{k=1}^K w_k y_{t-k} + \epsilon_t$

    有外部输入的非线性自回归模型（Nonlinear AutoRegressive with Exogenous Inputs Model,NARX），在每个时刻$t$都有一个外部输入$x_t$，它会产生一个输出$y_t$，NARX通过一个延时器记录最近$K_x$次的外部输入和最近$K_y$次的输出：

$y_t = f(x_t, x_{t-1},..., x_{t-K_x}, y_{t-1}, y_{t-2},...,y_{t-K_y})$

1.3.循环神经网络

    循环神经网络（Recurrent Neural Network,RNN）通过使用带自反馈的神经元，能够处理任意长度的时序数据。给定一个输入序列$x_{1:T} = (x_1,x_2,...,x_t,...,x_T)$，循环神经网络通过表达式更新带反馈边的隐藏层活性值$h_t$：

$h_t = f(h_{t-1},x_t)$

    上述公式是一个动力系统，隐藏层的活性值$h_t$在很多文献中称为状态（State）或隐状态（Hidden State）。

2.简单循环网络

    简单循环网络（Simple Recurrent Network,SRN）是一个很简单的循环神经网络，只有一个隐藏层，在一个两层的前馈神经网络中，连接存在相邻的层与层之间，隐藏层的节点之间是无连接的，而简单循环网络增加了从隐藏层到隐藏层的反馈连接。它的公式如：

$z_t = U h_{t-1} + W x_t + b$

$h(t) = f(z_t)$

• $z_t$为隐藏层的净输入

• $U \in R^{D \times D}$为状态-状态权重矩阵

• $W \in R^{D \times M}$为状态-输入权重矩阵

• $b \in R^D$为偏置向量

• $f(\cdot)$是非线性激活函数，通常为Logistic或Tanh

    循环神经网络可看做：时间维度上权值共享的神经网络。

2.1.计算能力

    先定义一个完全连接的神经网络，输入$x_t$，输出$y_t$：

$h_t = f(U h_{t-1} + W x_t + b)$ $y_t = V h_t$

2.1.1.通用近似定理

定理6.1——循环神经网络的通用近似定理：如果一个完全连接的循环神经网络有足够数量的sigmoid型隐藏神经元，它可以以任意的准确率去近似任何一个非线性动力系统 $s_t = g(s_{t-1},x_t)$ $y_t = o(s_t)$ 之中$s_t$为每个时刻的隐状态，$x_t$是外部输入，$g(\cdot)$是可测的状态转移函数，$o(\cdot)$是连续输出函数，并且对状态空间的紧致性没有限制。

2.1.2.图灵完备

    图灵完备（Turing Completeness）是一种操作规则，如某种计算机语言，可实现图灵机（Turing Machine）。

定理6.2——图灵完备：所有的图灵机都可以被一个由使用Sigmoid型激活函数的神经元构成的全连接循环网络进行模拟。

3.机器学习应用

    循环神经网络模式：

• 序列到类别模式

• 同步的序列到序列模式

• 异步的序列到序列模式

3.1.序列到类别

    序列到类别模式主要用于序列数据的分类，输入为序列，输出为类别。

$\hat{y}=g(h_T)$

• $g(\cdot)$可以是简单线性分类器或复杂的分类器

    最终转换成

$\hat{y} = g(\frac{1}{T} \sum\limits_{t=1}^T h_t)$

3.2.同步序列到序列

    同步序列到序列主要用于序列标注（Sequence Labeling）任务，即每一个时刻有输入和输出，输入序列和输出序列长度相同，如词性标注（Part-of-Speech Tagging）。

3.3.异步序列到序列

    异步序列到序列也称为编码器-解码器（Encoder-Decoder）模型，即输入序列和输出序列不需要有严格对应关系，也不需要保持相同长度。先将样本$x$按不同时刻输入到一个循环神经网络（编码器）中，并得到其编码$h_T$，然后再使用另一个循环神经网络（解码器），得到最终输出序列$\hat{y}_{1:M}$。

4.参数学习

    循环神经网络依旧使用梯度下降法来学习。

    在时刻$t$的损失函数为：

$L_t = L(y_t,g(h_t))$

• $g(h_t)$为$t$时刻的输出

• $L$为可微分的损失函数，如交叉熵

    整个序列的损失函数为：

$L = \sum\limits_{t-1}^T L_t$

    整个序列损失函数L关于参数U的梯度为

$\frac{\partial L}{\partial U} = \sum\limits_{t=1}^T \frac{\partial L_t}{\partial U_t}$

    循环神经网络中存在一个递归调用函数$f(\cdot)$，因此计算梯度方式有两种：

• 随时间反向传播：BPTT

• 实时循环学习：RTRL

4.1.BPTT

    随时间反向传播（BackPropagation Through Timer, BPTT）算法的主要思想是通过类似前馈神经网络的错误反向来计算梯度。BPTT算法将循环神经网络看做一个多层前馈网络，每一层对应循环网络中的“每个时刻”，如此循环神经网络就可以按照前馈网络中的反向传播算法计算参数梯度。

    计算偏导数$\frac{\partial L_t}{\partial U}$，参数$U$和隐藏层在每个时刻$k(1 \le k \le t)$的净输入$z_k = U h_{k-1} + W x_k + b$，所以：$t$时刻损失函数$L_t$关于参数$u_{ij}$的梯度为：

$\frac{\partial L_t}{\partial u_{ij}} = \sum\limits_{k = 1}^t \frac{\partial^+ z_k}{\partial u_{ij}}\frac{\partial L_t}{\partial z_k}$

    $\frac{\partial^+ z_k}{\partial u_{ij}}$表示直接偏导数，即表达式$z_k = U h_{k-1} + W x_k + b$中保持$h_{k-1}$不变，对$u_{ij}$求偏导。

$\frac{\partial L_t}{\partial U} = \sum\limits_{k-1}^t \delta_{t,k}h_{k-1}^T$

    所以整个序列的损失函数$L$关于参数$U$的梯度为

$\frac{\partial L}{\partial U} = \sum\limits_{t=1}^T \sum\limits_{k=1}^t \delta_{t,k}h_{k-1}^T$

    计算复杂度：在BPTT算法中，参数梯度需要在一个完整的前向计算和反向计算后才能得到并进行参数更新。

4.2.RTRL

    实时循环学习（Real-Time Recurrent Learning, RTRL）是通过前向传播的方式来计算梯度。

    两种算法比较，RTRL算法和BPTT算法都是基于梯度下降的算法，分别通过前向模式和反向模式应用链式法则来计算梯度，在循环神经网络中，一般网络输出维度低于输入维度，因此BPTT算法计算量更小，但空间复杂度更高，RTRL算法比较适合在线学习和无限序列任务。

5.长程依赖问题

    循环神经网络在学习过程中主要问题是梯度消失或爆炸问题，很难建立长时间间隔（Long Range）的状态依赖关系。展开表达式：

$\delta_{t,k} \cong \gamma^{t-k}\delta_{t,t}$

• 如果$\gamma > 1$，如果$t - k \rightarrow \infty, \gamma^{t-k} \rightarrow \infty$，如果时间间隔很大，梯度也会很大，造成不稳定，称梯度爆炸问题（Gradient Exploding Problem）。

• 如果$\gamma < 1$，如果$t - k \rightarrow \infty, \gamma^{t-k} \rightarrow 0$，当间隔很大，梯度也会消失，会出现和深层前馈神经网络类似的梯度消失问题（Vanishing Gradient Problem）。

    循环神经网络经常使用Logistic和Tanh函数，导数都小于1，权重矩阵也不会太大，经常出现梯度消失问题，由于简单循环网络学习的是短期的依赖关系，所以时间间隔比较大时，它无法对长距离的依赖关系建模，这就是长程依赖问题（Long-Term Dependencies）。

5.1.改进方案

    最简单避免爆炸和消失的问题，是使用合适的参数，同时使用非饱和的激活函数。

    梯度爆炸，一般而言，循环网络的梯度爆炸问题比较容易解决，一般通过权重衰减或梯度截断避免。

• 权重衰减是通过给参数增加$l_1$或$l_2$范数的正则化项来限制参数取值范围，从而使得$\gamma \le 1$。

• 梯度截断是另一种有效的启发式方法，当梯度的模大于一定阈值，就将它截断成一个较小的数。

    梯度消失，梯度消失是循环网络的主要问题，除了使用一些优化技巧，更有效的方式是改变模型，模型改进中可能会遇到如下问题：

• 梯度爆炸问题

• 记忆容量（Memory Capacity）问题

最好的方式是引入门控机制。

6.基于门控的RNN

    为改善循环神经网络的长程依赖问题，一种比较好的方法是引入门控机制来控制信息的积累速度，有选择地让信息加入，并且有选择性遗忘某些信息，这一类网络称为基于门控的循环神经网络（Gated RNN）。

• 长短期记忆网络

• 门控循环单元网络

6.1.长短期记忆网络

    长短期记忆网络（Long Short-Term Memory Network, LSTM）是循环神经网络的一个变体，可以有效解决简单循环神经网络中梯度爆炸或消失的问题。

    新的内部状态：LSTM网络引入了一个新的内部状态（Internal State）$c_t \in R^D$专程进行线性的循环信息传递，同时输出信息给隐藏层的外部状态$h_t \in R^D$，计算公式如：

$c_t = f_t \odot c_{t-1} + i_t \cdot \bar{c_t}$

$h_t = o_t \odot \tanh(c_t)$

    $f_t, i_t, o_t$为三个门（gate）来控制信息传递路径，$\odot$为向量元素乘积，$\bar{c_t}$是通过非线性函数得到的候选状态：

$\bar{c_t} = \tanh(W_c x_t + U_c h_{t - 1} + b_c)$

    在每个时刻$t$，LSTM网络内部状态$c_t$记录了到当前时刻为止的历史信息。

    门控机制：LSTM网络引入了门控机制（Gating Mechanism）来控制信息传递路径，LSTM中的门是一种“软”门，取值在(0,1)之间，表示以一定的比例允许通过：

• 遗忘门$f_t$：控制上一个时刻的内部状态$c_{t-1}$需要遗忘多少信息。

  $f_t = \sigma(W_fx_t + U_fh_{t-1} + b_f)$

• 输入门$i_t$：控制当前时刻的候选状态$\bar{c_t}$有多少信息需要保存。

  $i_t = \sigma(W_ix_t + U_ih_{t-1} + b_i)$

• 输出门$o_t$：控制当前时刻的内部状态$c_t$有多少信息需要输出给外部状态$h_t$。

  $o_t = \sigma(W_ox_t + U_oh_{t-1} + b_o)$

上述公式中，$\sigma(\cdot)$为Logistic函数，输出区间为(0,1)，$x_t$为当前时刻输入，$h_{t-1}$为上一时刻的外部状态。

1. 首先利用上一时刻的外部状态$h_{t-1}$和当前时刻的输入$x_t$计算出三个门以及候选状态$\bar{c_t}$

2. 结合遗忘门$f_t$和输入门$i_t$来更新记忆单元$c_t$

3. 结合输出门$o_t$，将内部状态的信息传递给外部状态$h_t$

    最终的公式如：

$$\begin{bmatrix} \bar{c_t} \\ o_t \\ i_t \\ f_t \end{bmatrix} = \begin{bmatrix} \tanh \\ \sigma \\ \sigma \\ \sigma \end{bmatrix}(W \begin{bmatrix} x_t \\ h_{t-1} \\ \end{bmatrix} + b )$$

$c_t = f_t \odot c_{t-1} + i_t \odot \bar{c_t}$

$h_t = o_t \odot \tanh(c_t)$

    记忆：循环神经网络中的隐状态$h$存储了历史信息，可以看做一种记忆（Memory），简单循环网络中，该状态每个时刻都会被重写，因此是短期记忆（Short-Term Memory），神经网络中，长期记忆（Long-Term Memory）可以看做网络参数，隐含了从迅联数据中学习卡的经验，更新周期慢于短期记忆。

    在LSTM中，记忆单元$c$可以在某个时刻捕捉关键信息，并有能力将该信息保留一定时间间隔，$c$中保存信息周期长于短期记忆$h$，又短于长期记忆，所以称为长短期记忆（Long Short-Term Memory）。

6.2.LSTM各种变体

    目前主流的LSTM使用三个门来动态控制内部状态应该：遗忘多少信息，输入多少信息，输出多少信息。

    无遗忘门的LSTM网络：假设内部更新状态（如果记忆单元$c$不断增加，输入序列长度很大时，记忆单元容量会趋于饱和，大大降低LSTM的性能）：

$c_t = c_{t-1} + i_t \odot \bar{c_t}$

    peephole连接：另一种变体是三个门不但依赖输入$x_t$和上一时刻的隐状态$h_{t-1}$，也依赖上一个时刻记忆单元$c_{t-1}$：

$i_t = \sigma(W_ix_t + U_ih_{t-1} + V_ic_{t-1}+ b_i)$

$f_t = \sigma(W_fx_t + U_fh_{t-1} + V_fc_{t-1} + b_f)$

$o_t = \sigma(W_ox_t + U_oh_{t-1} + V_oc_{t} + b_o)$

    耦合输入门和遗忘门：由于LSTM中输入和遗忘门互补，因此同时使用两个门有些冗余，为了减少复杂度，可合并成一个门：$f_t = 1 - i_t$，内部状态更新方式为：

$c_t = (1 - i_t) \odot c_{t-1} + i_i \odot \bar{c_t}$

6.3.门控循环单元

    门控循环单元（Gated Recurrent Unit, GRU）网络是一种比LSTM网络更简单的循环神经网络，GRU网络引入门控制来控制更新方式，和LSTM不同的是，它不引入额外的记忆单元，它引入了一个更新门（Update Gate）来控制当前状态需要从历史状态中保存多少信息：

$h_t = z_t \odot h_{t - 1} + (1 - z_t) \odot g(x_t, h_{t-1};\theta)$

    更新门

$z_t = \sigma(W_z x_t + U_z h_{t-1} + b_z)$

借助LSTM网络中输入门和遗忘门的互补性，GRU来控制二者之间的平衡。

• $z_t = 0$，当前状态$h_t$和前一时刻状态$h_{t-1}$为非线性函数关系

• $z_t = 1$，$h_t$和$h_{t-1}$为线性函数关系

    GRU网络函数定义：

$\tilde{h_t} = \tanh(W_h x_t + U_t(r_t \odot h_{t-1}) + b_h)$

    其中$r_t \in [0,1]^D$为重置门（Reset Gate）:

$r_t = \sigma(W_t x_t + U_r h_{t-1} + b_r)$

它用来控制候选状态$\tilde{h_t}$的计算是否依赖上一时刻的状态$h_{t-1}$。

• $r_t = 0$，候选状态只和当前输入$x_t$相关，和历史状态无关

• $r_t = 1$，候选状态和当前输入$x_t$以及历史状态$h_{t-1}$相关（简单循环网络）

    GRU网络的状态更新方式如：

$h_t = z_t \odot h_{t-1} + (1 - z_t) \odot \tilde{h_t}$

    GRU网络结构：

7.深层循环神经网络

7.1.堆叠循环神经网络

    常见的深层网络是将多个循环网络堆叠起来，称为堆叠循环神经网络（Stacked Recurrent Neural Network, SRNN），一个堆叠的简单循环网络（Stacked SRN）也称为循环多层感知机（Recurrent Multi-Layer Perceptron, RMLP）。

7.2.双向循环神经网络

    某些任务中，一个时刻的输出不但和过去时间有关，还和后续时间信息有关，因此可以增加我一个逆向层来增强网络能力。双向循环神经网络（Bidirectional Recurrent Neural Network, Bi-RNN）。

8.扩展到图结构

    如果将循环神经网络按时间展开，每个时刻的隐状态$h_t$看做一个节点，那这些节点可以构造一个链式结构，每个节点$t$都收到其父节点消息，更新状态并传递给子节点。链式传递很容易将这种消息传递（Message Passing）扩散到整个图。

8.1.递归神经网络

    递归神经网络（Recursive Nerual Network, RecNN）是循环神经网络在有向无循环图上的扩展。当递归神经网络结构退化成线性序列结构，递归神经网络等价于简单循环网络，使用门控机制改进递归神经网络中的长距离依赖问题，比如树结构的长短期记忆模型（Tree-Structured LSTM）。

8.2.图神经网络

    图神经网络（Graph Neural Network, GNN）是将消息传递思想扩展到图结构数据上的神经网络。

• 图卷积网络（Graph Convolutional Network, GCN）, 2016

• 图注意力网络（Graph Attention Network, GAT），2017

• 消息传递神经网络（Message Passing Neural Network, MPNN），2017