Question

2.1 BPTT 算法

1. 以 多输出&隐-隐RNN为例，设：输入到隐状态的权重为 $ \mathbf U $ ，隐状态到输出的权重为 $ \mathbf V $ ，隐状态到隐状态的权重为 $ \mathbf W $ ， $ \mathbf{\vec b},\mathbf{\vec c} $ 为输入偏置向量和输出偏置向量；激活函数为双曲正切激活函数 $ \tanh $ 。

   设网络从特定的初始状态 $ \mathbf{\vec h}^{(0)} $ 开始前向传播，从 $ t=1 $ 到 $ t=\tau $ 的每个时间步，则有更新方程：

   $ \mathbf{\vec a}^{(t)}=\mathbf{\vec b}+\mathbf W\mathbf{\vec h}^{(t-1)}+\mathbf U\mathbf{\vec x}^{(t)}\\ \mathbf{\vec h}^{(t)}=\tanh(\mathbf{\vec a}^{(t)})\\ \mathbf{\vec o}^{(t)}=\text{softmax}\left(\mathbf{\vec c}+\mathbf V\mathbf{\vec h}^{(t)}\right) $

   多输出&隐-隐RNN 的单个样本损失函数为： $ L = - \sum_{t=1}^{\tau}\sum_{k=1}^K \mathbb I_\left({k = y^{(t)}}\right) \log o_{k}^{(t)} $ 。该损失函数的梯度计算代价较高：

   • 因为每个时间步只能一前一后的计算无法并行化，因此时间复杂度为 $ O(\tau) $ 。
   • 前向传播中各个状态必须保存直到它们反向传播中被再次使用，因此空间复杂度也是 $ O(\tau) $ 。
   • 采用 tanh 激活函数而不是 ReLU 激活函数的原因是为了缓解长期依赖。

2. back-propagation through time:BPTT：通过时间反向传播算法，其算法复杂度为 $ O(\tau) $ 。

   由 BPTT 计算得到梯度，再结合任何通用的、基于梯度的技术就可以训练 RNN 。

3. 计算图的节点包括参数 $ \mathbf U,\mathbf V,\mathbf W,\mathbf{\vec b},\mathbf{\vec c} $ ，以及以 $ t $ 为索引的节点序列 $ \mathbf{\vec x}^{(t)}, y^{(t)}, \mathbf{\vec h}^{(t)},\mathbf{\vec o}^{(t)} $ 以及 $ L^{(t)} $ 。

   • 根据 $ L=\sum_{t=1}^{\tau} L^{(t)} $ ，则有： $ \frac{\partial L}{\partial L^{(t)}}=1 $ 。

   • 令节点 $ \mathbf{\vec s}^{(t)} = \mathbf{\vec c}+\mathbf V\mathbf{\vec h}^{(t)} $ ，则有： $ \mathbf{\vec o}^{(t)}=\text{softmax}(\mathbf{\vec s}^{(t)}) $ 。则有：

     $ L^{(t)} = - \sum_{k=1}^K \mathbb I_\left({k = y^{(t)}}\right) \log o_{k}^{(t)} = -s^{(t)}_{y^{(t)}} + \log \sum_{k=1}^K \exp(s_k^{(t)}) $

     其中 $ s_k^{(t) } $ 表示 $ \mathbf{\vec s}^{(t)} $ 的第 $ k $ 个分量。

     则有：

     $ \left(\nabla_{\mathbf{\vec s}^{(t)}}L\right)_k=\frac{\partial L}{\partial s_k^{(t)}}=\frac{\partial L}{\partial L^{(t)}}\times \frac{\partial L^{(t)}}{\partial s_k^{(t)}}=1\times \frac{\partial L^{(t)}}{\partial s_k^{(t)}}\\ =-\mathbb{ I}_{k= y^{(t)}}+\frac{\exp(s^{(t)}_k)}{\sum_{k^\prime=1}^{K}\exp(s^{(t)}_{k^\prime})} =o^{(t)}_k-\mathbb{ I}_{k= y^{(t)}} $

     $ \left(\nabla_{\mathbf{\vec s}^{(t)}}L\right)_k $ 表示梯度 $ \left(\nabla_{\mathbf{\vec s}^{(t)}}L\right) $ 的第 $ k $ 个分量， $ \mathbb I(\cdot ) $ 为示性函数。写成向量形式为：

     $ \nabla_{\mathbf{\vec s}^{(t)}}L = \mathbf{\vec o}^{(t)} - \mathbf{\vec y}^{(t)} $

     其中 $ \mathbf{\vec y}^{(t)}=(0,\cdots,0,1,0,\cdots,0) $ 为真实标签 $ y^{(t)} $ 扩充得到的概率分布，其真实的类别 $ y_i^{(t)} $ 位置上的分量为 1，而其它位置上的分量为 0。

   • 根据定义 $ \mathbf{\vec h}^{(t+1)}=\tanh(\mathbf{\vec b}+\mathbf W\mathbf{\vec h}^{(t)}+\mathbf U\mathbf{\vec x}^{(t+1)}) $ ，得到：

     $ h^{(t+1)}_i=\tanh\left(b_i+\sum_{j}W_{i,j}h^{(t)}_j+\sum_{j}U_{i,j}x_j^{(t+1)}\right) $

     根据导数： $ d\frac{\tanh(x)}{d x}=1-\tanh^2(x) $ ，则有：

     $ \frac{\partial h_i^{(t+1)}}{\partial h_j^{(t)}}=\left(1-(h_i^{(t+1)})^2\right)W_{i,j} $

     设隐向量长度为 $ n $ ，定义：

     $ \frac{\partial\mathbf{\vec h}^{(t+1)}}{\partial\mathbf{\vec h}^{(t)} }=\begin{bmatrix} \frac{\partial h_1^{(t+1)}}{\partial h_1^{(t)}}&\cdots &\frac{\partial h_n^{(t+1)}}{\partial h_1^{(t)}}\\ \vdots&\ddots&\vdots\\ \frac{\partial h_1^{(t+1)}}{\partial h_N^{(t)}}&\cdots &\frac{\partial h_n^{(t+1)}}{\partial h_1^{(t)}} \end{bmatrix}\\ \quad\\ \text{diag}\left(1-(\mathbf{\vec h}^{(t+1)})^{2}\right)=\begin{bmatrix} 1-(h_1^{(t+1)})^2&0&\cdots&0\\ 0&1-(h_2^{(t+1)})^2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1-(h_n^{(t+1)})^2 \end{bmatrix} $

     则有： $ \frac{\partial\mathbf{\vec h}^{(t+1)}}{\partial\mathbf{\vec h}^{(t)} } =\text{diag}\left(1-(\mathbf{\vec h}^{(t+1)})^{2}\right) \mathbf W $ 。

     根据定义 $ \mathbf{\vec s}^{(t)} = \mathbf{\vec c}+\mathbf V\mathbf{\vec h}^{(t)} $ ，即 $ s^{(t)}_i=c_i+\sum_{j}V_{i,j}h^{(t)}_j $ ，则有： $ \frac{\partial s^{(t)}_i}{\partial h_j^{(t)}}=V_{i,j} $ ，记作：

     $ \frac{\mathbf{\partial \vec s}^{(t)}}{\partial\mathbf{\vec h}^{(t)} } =\mathbf V $

     因此得到隐单元的梯度：

     • 当 $ t=\tau $ 时， $ \mathbf {\vec h}^{(\tau)} $ 只有一个后续结点 $ \mathbf{\vec o}^{(\tau)} $ （从而只有一个后继节点 $ \mathbf{\vec s}^{(\tau)} $ ） ，因此有：

       $ \nabla_{\mathbf{\vec h}^{(\tau)}}L=\left(\frac{\mathbf{\partial \vec s}^{(t)}}{\partial\mathbf{\vec h}^{(t)} }\right)^{T}\nabla_{\mathbf{\vec s}^{(t)}}L=\mathbf V^{T}\nabla_{\mathbf{\vec s}^{(\tau)}}L $

     • 当 $ t\lt \tau $ 时， $ \mathbf {\vec h}^{(t)} $ 同时具有 $ \mathbf {\vec o}^{(t)},\mathbf {\vec h}^{(t+1)} $ 两个后续节点，因此有：

       $ \nabla_{\mathbf{\vec h}^{(t)}}L=\left(\frac{\partial\mathbf{\vec h}^{(t+1)}}{\partial\mathbf{\vec h}^{(t)} }\right)^{T}\nabla_{\mathbf{\vec h}^{(t+1)}}L+\left(\frac{\partial \mathbf{\vec s}^{(t)}}{\partial\mathbf{\vec h}^{(t)} }\right)^{T}\nabla_{\mathbf{\vec s}^{(t)}}L\\ =\mathbf W^{T}(\nabla_{\mathbf{\vec h}^{(t+1)}}L)\text{diag}\left(1-(\mathbf{\vec h}^{(t+1)})^{2}\right)+\mathbf V^{T}\nabla_{\mathbf{\vec s}^{(t)}}L $

       由于 $ \nabla_{\mathbf{\vec h}^{(t)}}L $ 依赖于 $ \nabla_{\mathbf{\vec h}^{(t+1)}}L $ ，因此求解隐单元的梯度时，从末尾开始反向计算。

4. 一旦获得了隐单元及输出单元的梯度，则可以获取参数节点的梯度。

   注意：由于参数在多个时间步共享，因此在参数节点的微分操作时必须谨慎对待。

   微分中的算子 $ \nabla _{\mathbf A}f $ 在计算 $ \mathbf A $ 对于 $ f $ 的贡献时，将计算图的所有边都考虑进去了。但是事实上：有一条边是 $ t $ 时间步的 $ \mathbf A $ ，还有一条边是 $ t+1 $ 时间步的 $ \mathbf A $ ，.... 。

   为了消除歧义，使用虚拟变量 $ \mathbf A^{(t)} $ 作为 $ \mathbf A $ 的副本。用 $ \nabla _{\mathbf A^{(t)}} f $ 表示参数 $ \mathbf A $ 在时间步 $ t $ 对于梯度的贡献。将所有时间步上的梯度相加，即可得到 $ \nabla _{\mathbf A}f $ 。

5. 根据定义 $ \mathbf{\vec s}^{(t)}=\mathbf{\vec c}^{(t)}+\mathbf V\mathbf{\vec h}^{(t)} $ ，即 $ s^{(t)}_i=c_i+\sum_{j}V_{i,j}^{(t)}h^{(t)}_j $ 。则有：

   $ \frac{\partial \mathbf{\vec s}^{(t)}}{\partial \mathbf{\vec c}^{(t)}}=\mathbf I,\quad \frac{\partial s^{(t)}_i}{\partial V_{i,j}^{(t)}}=h_j^{(t)} $

   • 考虑到 $ \mathbf{\vec c} $ 对于每个输出 $ \mathbf{\vec o}^{(1)},\cdots,\mathbf{\vec o}^{(\tau)} $ 都有贡献，因此有：

     $ \nabla _{\mathbf{\vec c}}L=\sum_{t=1}^{t=\tau}\left(\frac{\partial \mathbf{\vec s}^{(t)}}{\partial \mathbf{\vec c}^{(t)}}\right)^{T}\nabla_{\mathbf{\vec s}^{(t)}}L=\sum_{t=1}^{t=\tau}\nabla_{\mathbf{\vec s}^{(t)}}L $

   • 记：

     $ \nabla_{V_{k,:}^{(t)}}s_i^{(t)}=\begin{cases}\mathbf{\vec h}^{(t)},&i=k\\ \mathbf{\vec 0},&i\ne k \end{cases} $

     考虑到 $ \mathbf V $ 对于每个输出 $ \mathbf{\vec o}^{(1)},\cdots,\mathbf{\vec o}^{(\tau)} $ 都有贡献，因此有：

     $ \nabla_{V_{i,:}}L=\sum_{t=1}^{t=\tau}\left(\frac{\partial L}{\partial s_i^{(t)}}\right)\nabla_{V_{i,:}^{(t)}} s_i^{(t)}=\sum_{t=1}^{t=\tau}(\nabla_{\mathbf{\vec s}^{(t)}}L)_i\mathbf{\vec h}^{(t)} $

     其中 $ (\nabla_{\mathbf{\vec s}^{(t)}}L)_i $ 表示 $ \nabla_{\mathbf{\vec s}^{(t)}}L $ 的第 $ i $ 个分量。

6. 根据定义 $ \mathbf{\vec h}^{(t)}=\tanh(\mathbf{\vec b}^{(t)}+\mathbf W\mathbf{\vec h}^{(t-1)}+\mathbf U\mathbf{\vec x}^{(t)}) $ ，即：

   $ h^{(t)}_i=\tanh\left(b_i+\sum_{j}W_{i,j}^{(t)}h^{(t-1)}_j+\sum_{j}U_{i,j}x_j^{(t)}\right) $

   则有：

   $ \frac{\partial \mathbf{\vec h}^{(t)}}{\partial \mathbf{\vec b}^{(t)}}=\text{diag}\left(1-(\mathbf{\vec h}^{(t)})^{2}\right),\quad \frac{\partial h_i^{(t)}}{\partial W^{(t)}_{i,j}}=(1-h_i^{(t)2})h_j^{(t-1)},\quad \frac{\partial h_i^{(t)}}{\partial U_{i,j}^{(t)}}=(1-h_i^{(t)2})x_j^{(t)} $

   • 考虑到 $ \mathbf{\vec b} $ 对于每个隐向量 $ \mathbf{\vec h}^{(1)},\cdots,\mathbf{\vec h}^{(\tau)} $ 都有贡献，因此有：

     $ \nabla _{\mathbf{\vec b}}L=\sum_{t=1}^{t=\tau}\left(\frac{\partial \mathbf{\vec h}^{(t)}}{\partial \mathbf{\vec b}^{(t)}}\right)^{T}\nabla_{\mathbf{\vec h}^{(t)}}L=\sum_{t=1}^{t=\tau}\text{diag}\left(1-(\mathbf{\vec h}^{(t)})^{2}\right)\nabla_{\mathbf{\vec h}^{(t)}}L $

   • 记：

     $ \nabla_{W^{(t)}_{k,:}}h_i^{(t)}=\begin{cases}(1-h_i^{(t)2})\mathbf{\vec h}^{(t-1)},&i=k\\ \mathbf{\vec 0},&i\ne k \end{cases} $

     考虑到每个 $ \mathbf W^{(t)} $ 都对 $ L $ 有贡献，则：

     $ \nabla_{W_{i,:}} L=\sum_{t=1}^{t=\tau}\left(\frac{\partial L}{\partial h_i^{(t)}}\right) \nabla_{W^{(t)}_{i,:}} h_i^{(t)} =\sum_{t=1}^{t=\tau} (\nabla_{\mathbf{\vec h}^{(t)}}L)_i \left(1-h_i^{(t)2}\right)\mathbf{\vec h}^{(t-1)} $

     其中 $ (\nabla_{\mathbf{\vec h}^{(t)}}L)_i $ 表示 $ \nabla_{\mathbf{\vec h}^{(t)}}L $ 的第 $ i $ 个分量。

   • 记：

     $ \nabla_{U_{k,:}^{(t)}}h_i^{(t)}=\begin{cases}(1-h_i^{(t)2})\mathbf{\vec x}^{(t)},&i=k\\ \mathbf{\vec 0},&i\ne k \end{cases} $

     考虑到每个 $ \mathbf U^{(t)} $ 都对 $ L $ 有贡献，则：

     $ \nabla_{U_{i,:}} L=\sum_{t=1}^{t=\tau}\left(\frac{\partial L}{\partial h_i^{(t)}}\right) \nabla_{U_{i,:}^{(t)}} h_i^{(t)} =\sum_{t=1}^{t=\tau} (\nabla_{\mathbf{\vec h}^{(t)}}L)_i \left(1-h_i^{(t)2}\right)\mathbf{\vec x}^{(t)} $

     其中 $ (\nabla_{\mathbf{\vec h}^{(t)}}L)_i $ 表示 $ \nabla_{\mathbf{\vec h}^{(t)}}L $ 的第 $ i $ 个分量。

7. 因为任何参数都不是训练数据 $ \mathbf{\vec x}^{(t)} $ 的父节点，因此不需要计算 $ \nabla _{\mathbf{\vec x}^{(t)}} L $ 。

2.2 Teacher forcing 算法

1. 多输出&输出-隐连接RNN模型可以使用 teacher forcing 算法进行训练。

   • 模型的数学表示： $ o^{(t)}_k=p(y^{(t)} = k \mid y^{(t-1)},\mathbf{\vec x}^{(t)}),\quad k = 1,2,\cdots,K $
   • 单个样本的损失： $ L = - \sum_{t=1}^{\tau}\sum_{k=1}^K \mathbb I_\left({k = y^{(t)}}\right) \log o_{k}^{(t)} $
   • 训练时：在时刻 $ t+1 $ 接受真实类别分布 $ \mathbf{\vec y}^{(t)} $ 作为输入，而不必等待 $ t $ 时刻的模型输出分布 $ \mathbf{\vec o}^{(t)} $ 。
   • 推断时：真实的标记通常是未知的，因此必须用模型的输出分布 $ \mathbf{\vec o}^ {(t)} $ 。

   

2. teacher forcing训练的本质原因是：当前隐状态与早期隐状态没有直接连接。虽然有间接连接，但是由于 $ y^{(t)} $ 已知，因此这种连接被切断。

   • 如果模型的隐状态依赖于早期时间步的隐状态，则需要采用 BPTT算法。
   • 某些模型训练时，需要同时使用teacher forcing和BPTT算法。