最近听说上交提了一个SRNN，相比普通RNN的效率提升100+倍，这让想起了去年的QRNN[1]和SRU[2]，借这篇文章说一下关于RNN的长期依赖和计算效率的问题。
RNN的效率瓶颈在于时间轴上state的传递依赖，借鉴现在大部分DL框架api的设计，可以用下式表示：
$\mathcal{C}$可以用于表示LSTM，GRU这类cell逻辑。如果具体展开的话，和$x$相关的计算，在每个时间步上没有依赖，因此可以一次计算完毕（即form成矩阵的形式），涉及到$h$相关的计算时，因为$h_{t}$需要等待$h_{t-1}$，因此，整个序列上的$h$推断过程需要串行进行（step by step）。QRNN这类方案的出发点都是对$h$的计算进行局部的依赖解除（但是不能完全解除，否则就不是传统意义上的循环结构了，因此必然存在recurrent逻辑），从而加速inference过程。
LSTM结构中，每一个门状态的计算都需要依赖$h_{t - 1}$，导致门状态计算时$h_{t - 1}$相关的矩阵运算必须串行进行。QRNN将门状态的计算化简为仅仅对当前输入依赖，即$x_{[t - k + 1 \cdots t]}$，$k$是可配置参数，论文中称为filter width，理解为门输入的context就行，在QRNN的开源实现（pytorch-qrnn）中，$k$只支持1和2，用$\mathbf{g}_t$表示门$g$（$g = {z, f, o}$）在$t$时刻的状态值，$\sigma$表示对应的激活函数，那么门状态的计算统一可以用下式表示：
不像LSTM那样存在对$h$的依赖，因此，可以一次计算出所有时刻的门状态值$\mathbf{G}$：
$\mathbf{X}_s$表示根据$k$拼帧的结果。需要注意的是，实现的时候，$*$用一个线性层就行了，并没有像论文中所说的卷积操作。
以上是QRNN的parallel部分，不可缺少的recurrent部分，QRNN中称为“dynamic average pooling”，描述cell之间的依赖关系，这部分和LSTM & GRU很像，以fo-pooling为例：
这部分的计算量集中在Hadamard Product（逐元素相乘）上，相比原始RNN/LSTM中的矩阵乘法，加上在CUDA上的优化，recurrent部分的计算效率得到了极大的提升。
总结一下QRNN的设计思路，将门状态的计算独立到循环逻辑之外，仅仅保留cell的循环依赖，宏观上就是高计算量的部分parallel进行，小计算量的部分串行计算。这时候再看论文中的QRNN的Block diagrams就很容易体会其中的思想了：
红色区域表示$(2)$式的计算，一次将门状态计算完毕，之后用”dynamic average pooling“层计算recurrent依赖。
SRU和QRNN中$k = 1$的结构十分相似，思路上也都是解除门状态的依赖关系。不添加highway的情况下只设置一个forget门，网络结构写成：
可以看出$\mathbf{f}_t$的计算逻辑也是基于当前输入的一个线性层激活层。
SRNN（Spliced Recurrent Neural Networks）的逻辑是把长序列划分成若干的等长的子序列，再将每个子序列的最后一个状态视为新的序列进行划分，直到新形成的序列长度不能被继续划分为子序列为止。循环过程在每个子序列中进行，并用每个子序列的最后一个状态值初始化父序列的state。由于同一层的每个子序列之间被强制分割，断开了时间上的依赖性，因此可以并行计算状态值。
根据论文中的结论，如果处理的序列足够长，SRNN的效率提升是惊人的。 当然是否所有任务都满足训练序列越长越好，还需要具体的实验对比。在ASR任务中，我本人并不倾向于选择过长的序列进行训练。
最后我再说一下TDNN[4]和FSMN[5]，这是很早以前我就想写一点的东西。这两种结构在ASR中被广泛应用，对识别率的提升做出了巨大的贡献。由于本质上他们是前馈结构，因此，在训练和推断的效率上相比RNN具有巨大的优势，对于ASR这种在实际应用中对实时要求较高的任务上，这一点就显得尤为重要。
TDNN(Time Delay)的历史十分久远[1]，近年来JHU那边主推，并在kaldi的nnet2/3上做了实现，得到了大规模的尝试和应用。它的思想用四个词来表述就行，即层间拼帧。一般的DNN结构，如果要增加输入信息量，只在输入层做拼帧，但是通常不会拼帧过多，否则会导致输入层参数量过大，因此限制了网络的输入信息量。如果同时允许隐层拼帧，那么在多层叠加的情况下，网络输入的context就可以得到扩展，同时也可以保证每一层的参数量不会十分巨大，如果画出整个TDNN的依赖关系图，会得到一种类似金字塔的结构，如下：
以上图为例，输出$t$时刻的后验，输入的context为$[-13, +9]$。
实际熟悉kaldi的人也知道，tdnn层实际配置的时候当成对线性层的一种扩展，添加了拼帧选项而已，可以放在任意网络结构中间，CNN和LSTM等。同时拼帧允许sub-sampling，以上图的layer 2为例子，context为$[-1, +2]$，相比$[-1,0,+1,+2]$，减少了隐层的参数量的同时保证了网络的context。
FSMN的思想来源于信号处理中，一个无限冲击响应可以用高阶的有限冲击响应来近似。它的隐层输入来源于两部分，一部分来自上层的输入，另一部分来自一个称为memory block的结构，写为：
其中$ \mathbf{\tilde{h}}_t^\ell$表示$\ell$层的memory block，有两种计算方式：
被称为sFSMN（scalar encoding FSMN）以及
称为vFSMN（vector encoding FSMN）。$N > 0$时，类似于双向RNN的逻辑。从$(3,4)$式可以看出，memory block强制存储下了若干时刻的记忆块，并用于当前时刻的输入，记忆长度以当前时刻为参考为$M + N$。由于最终的输入是记忆块加权和的形式，因此，FSMN的隐层维度同样不会过大。用信号流图来表示因果系统下memory block的计算如下：
FSMN后续还有相关实验，包括deep FSMN和compact FSMN等等，有兴趣的读者可以参阅一下下面的参考文献。
[1]. Zhang S, Jiang H, Xiong S, et al. Compact Feedforward Sequential Memory Networks for Large Vocabulary Continuous Speech Recognition[C]//INTERSPEECH. 2016: 3389-3393.
[2]. Zhang S, Lei M, Yan Z, et al. Deep-FSMN for Large Vocabulary Continuous Speech Recognition[J]. arXiv preprint arXiv:1803.05030, 2018.
最后总结一下，RNN的耗时来自时间轴上的展开过程，原始的LSTM和GRU，门状态的计算存在时间上的依赖，矩阵乘法无法并行。QRNN和SRU的思路都是将门状态的依赖关系解除，放到循环外解决，只保留cell state的时间依赖。FSMN和TDNN虽然是前馈结构，但是通过结构上的设计，强制网络获得额外的context信息，相比RNN在效率上具有很大优势，相比传统的DNN/CNN更加适用于long context建模，在ASR任务上均取得了巨大的成功，其中阿里的线上模型已经由LC-BLSTM替换为FSMN，充分体现了其在ASR和工业界的价值。
参考文献：
[1]. Bradbury J, Merity S, Xiong C, et al. Quasi-recurrent neural networks[J]. arXiv preprint arXiv:1611.01576, 2016.
[2]. Lei T, Zhang Y. Training rnns as fast as cnns[J]. arXiv preprint arXiv:1709.02755, 2017.
[3]. Waibel A, Hanazawa T, Hinton G, et al. Phoneme recognition using time-delay neural networks[M]//Readings in speech recognition. 1990: 393-404.
[4]. Peddinti V, Povey D, Khudanpur S. A time delay neural network architecture for efficient modeling of long temporal contexts[C]//Sixteenth Annual Conference of the International Speech Communication Association. 2015.
[5]. Zhang S, Liu C, Jiang H, et al. Feedforward sequential memory networks: A new structure to learn long-term dependency[J]. arXiv preprint arXiv:1512.08301, 2015.