Informer：用于长序列时间序列预测的新型Transform

作者: 酷酷的群 | 来源:发表于2021-04-16 09:33 被阅读0次

论文标题：Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting
论文链接：https://arxiv.org/abs/2012.07436
代码链接：https://github.com/zhouhaoyi/Informer2020
论文来源：AAAI 2021

一、概述

长序列时间序列预测问题

长序列时间序列预测（Long sequence time-series forecasting，LSTF）问题在现实世界中经常遇到，比如电力消耗规划。LSTF期待模型能够拥有较高的预测容量（capacity），以便于能够捕捉输入与输出之间的长程依赖关系。Transformer模型相较于其他模型提高了预测的容量，然而其本身也受到诸多限制以致于难以直接应用于LSTF，比如二次时间复杂度、高内存占用以及encoder-decoder架构所固有的一些限制。

LSTF存在于多个领域，比如网络监控、能源管理、经济与金融以及疾病传播分析等，在这些场景下需要依据过去的大量数据来对未来做出长期预测。现有模型在长序列预测问题上能力不足，举例来说，使用LSTM来进行时间序列预测时，模型预测短序列（比如12 points, 0.5 days）时能够取得较高的精度，而预测长序列（比如480 points, 20 days）时会出现预测速度的下降和MSE损失的上升，尤其是48 points这个分界线上，模型的预测速度急剧下降，损失急剧上升，LSTM对长序列预测任务来说是失败的：

example for LSTM

上述模型的失败表明需要提高模型对长序列的容量以应对LSTM问题，具体来说需要模型具备以下能力：
①良好的长程对齐（long-range alignment）能力；
②对长序列的输入和输出的有效处理。

Transfomer模型的优势与局限之处

Transfomer模型相较于RNN结构模型表现出了更强的捕获长程依赖关系的能力，其中很重要的一个原因是Transformer应用 self-attention机制将信号传播的最大路径长度降低到了最短的 $O(1)$ 并且避免了循环架构（recurrent structure），也就是说Transfomer模型具备能力①，因此Transfomer对于解决LSTF问题表现出巨大的潜力。

然而不幸的是Transfomer模型对于长度为 $L$ 的序列来说需要 $L^2$ 的二次计算复杂度和内存使用，也就是说它不具备能力②。虽然在一些NLP任务上取得了较好的成效但是也消耗了大量的资源，尤其对于现实世界中的LSTF问题来说，Transfomer模型所需的资源（比如训练时需要多GPU以及部署时昂贵的花费）是难以承受的，这是将Transfomer应用于LSTF的瓶颈所在。

Transformer在应用于LSTF时具体会有以下3种限制：
① self-attention的二次计算复杂度。self-attention的原子操作——规范点积（canonical dot-product）导致每层的时间复杂度和内存使用是 $O(L^2)$ 。
②层的堆叠在输入长序列时受到内存限制。encoder/decoder的 $J$ 层堆叠架构会导致在输入长序列时内存使用为 $O(J\cdot L^{2})$ ，这一点限制了模型输入长序列时的可拓展性（scalability）。
③对长序列输出进行预测时的速度骤降。Transformer的动态解码（dynamic decoding）过程导致在对长序列输出进行推断时速度缓慢，实际效果可能和前面例子里的基于RNN的模型一样差。

基于上述事实，本文试图回答以下问题：在保持对长序列预测容量的同时，Transfomer能不能在计算复杂度、内存使用和架构上同样是高效的？

相关工作

为了提高self-attention的效率，已有一些前人的工作，提出了一些改进Transformer的模型。Sparse Transformer，LogSparse Transformer，Longformer使用启发式的方法试图解决限制①，将每层复杂度降到了 $O(Llog L)$ ，不过这些模型效果的增益是有限的；Reformer使用locally sensitive hashing self-attention同样达到了 $O(Llog L)$ 的复杂度，不过其只对非常长的序列才能起到效果； Linformer达到了线性复杂度 $O(L)$ ，不过对于真实世界的长序列数据不能固定映射矩阵，因而有退化到 $O(L^2)$ 的风险；Transformer-XL和Compressive Transformer使用辅助隐状态来捕获长程依赖关系，因而有可能放大限制①，不利于打破效率瓶颈。

本文的贡献

上述前人的相关工作只关注解决限制①，而没有着手解决限制②和③。为了增强Transformer模型对长序列的容量，本文研究了self-attention机制的稀疏性，将会针对所有的3个限制来提出各自的解决方案。具体来说，本文的贡献如下：
①Informer模型增强了对LSTF问题的预测容量，这一点验证了Transformer-like的模型的潜在价值，即其能够捕获长序列时间序列输入与输出之间的长程依赖关系；
②提出了ProbSparse Self-attention机制，能够替换规范self-attention，并且达到了 $O(LlogL)$ 的时间复杂度和内存使用量；
③提出了self-attention蒸馏（ Self-attention Distilling）操作，能够在堆叠的 $J$ 层中提炼主要的注意力得分，大幅降低了总的空间复杂度，达到 $O((2-\epsilon )Llog L)$ ；
④提出了生成式的decoder（Generative Style Decoder）来获取长序列输出，只需要一个前向的步骤即可输出整个解码序列，同时避免了推断期间的累积误差传播（cumulative error spreading）。

本文的②，③，④3个贡献分别针对前面提出的Transformer的3个限制。

二、ProbSparse Self-attention

表示

首先定义我们要讨论的问题。时间序列（time-series）简单的说就是各时间点上形成的数值序列，时间序列分析就是通过观察历史数据预测未来的值。时间序列分析并不是关于时间的回归，它主要是研究自身的变化规律的。在进行一个固定窗口的滚动预测（rolling forecast）时，我们的每个时刻的输入为 $\mathrm{X}^{t}=\left \{x_{1}^{t},\cdots ,x_{L_{x}}^{t}|x_{i}^{t}\in \mathbb{R}^{d_{x}}\right \}$ ，输出为需要预测的序列 $\mathrm{Y}^{t}=\left \{y_{1}^{t},\cdots ,y_{L_{y}}^{t}|y_{i}^{t}\in \mathbb{R}^{d_{y}}\right \}$ 。相较于之前的工作，LSTF要求预测一个 $L_{y}$ 更大的序列，并且这里并不限定仅预测单变量，即 $d_{y}\geq 1$ 。

在传统的encoder-decoder架构中，encoder会将输入 $\mathrm{X}^{t}$ 编码成隐状态序列 $\mathrm{H}^{t}=\left \{h_{1}^{t},\cdots ,h_{L_{h}}^{t}\right \}$ ，然后decoder利用 $\mathrm{H}^{t}$ 解码成 $\mathrm{Y}^{t}$ 。在解码过程中，包括一个step-by-step的过程，也就是动态解码，在第 $k$ 步中，decoder会利用前一个时刻的隐状态 $h_{k-1}^{t}$ 以及其他必要的前一时刻的输出来计算一个新的隐状态 $h_{k}^{t}$ ，然后来预测当前时刻的输出 $y_{k}^{t}$ 。在Transformer中也沿用了类似的动态解码的过程（在预测时需要动态解码，在训练时不需要，因为在训练时直接使用ground truth即可），而在本文提出的Informer中同样沿用了encoder-decoder架构，但舍弃了动态解码过程，而采用一种生成式的解码过程一次性解码出整个序列 $\mathrm{Y}^{t}$ 。

基于RNN的模型依靠其本身的循环结构来学习时间序列，而很少依赖时间戳。在Transformer中，时间戳作为局部的位置信息。然而在LSTF中，为了捕获长程依赖关系需要提供全局的时间信息，比如hierarchical time stamps（周、月、年等）以及agnostic time stamps（假期、时间）。为了能够输入这些信息，本文提出了一种统一的输入表示，如下图所示：

输入表示

我们有第 $t$ 个序列输入 $\mathrm{X}^{t}$ 和 $p$ 个类型的全局时间戳，并且模型的输入维度为 $d_{model}$ ，首先使用固定的位置编码 $PE$ 来表示局部的位置信息，即：

$PE_{(pos,2j)}=sin(pos/(2L_{x})^{2j/d_{model}})\\ PE_{(pos,2j+1)}=cos(pos/(2L_{x})^{2j/d_{model}})\\ where\; j\in \left \{1,\cdots ,\left \lfloor d_{model}/2\right \rfloor\right \}$

每种类型的全局时间戳都被分配了一个可学习的时间戳embedding $SE_{(pos)}$ ，每种embedding都有一个固定的vocab size（最大是60，也就是以分钟作为最细的粒度）。另外为了对齐维度，我们使用一维卷积（卷积核宽度为3，步长为1）将 $x_i^t$ 映射到 $d_{model}$ 维的 $u_i^t$ 。最终输入到模型中的序列为：

$X_{feed[i]}^{t}=\alpha u_{i}^{t}+PE_{(L_{x}\times (t-1)+i,)}+\sum _{p}[SE_{(L_{x}\times (t-1)+i)}]_{p}\\ where\; i\in \left \{1,\cdots ,L_{x}\right \}$

$\alpha$ 是一个超参数，用来平衡 $u_{i}^{t}$ 和位置编码以及时间戳embedding，如果输入已经被标准化，那么建议 $\alpha=1$ 。

self-attention机制

Transformer中定义的self-attention接收3个输入query、key和value，然后计算它们的scale dot-product，即：

$A(Q,K,V)=softmax\left (\frac{QK^{T}}{\sqrt{d}}\right )V\\ where\; Q\in \mathbb{R}^{L_{Q}\times d},K\in \mathbb{R}^{L_{K}\times d},V\in \mathbb{R}^{L_{V}\times d}$

这里的 $d$ 指输入的维度。这里使用 $q_i,k_i,v_i$ 分别表示 $Q,K,V$ 的第 $i$ 行，那么第 $i$ 个query的attention就被定义为一个概率形式的核平滑方法（kernel smoother）:

$A(q_{i},K,V)=\sum _{j}\frac{k(q_{i},k_{j})}{\sum _{l}k(q_{i},k_{l})}v_{j}=E_{p(k_{j}|q_{i})}[v_{j}]\\ where\; p(k_{j}|q_{i})=\frac{k(q_{i},k_{j})}{\sum _{l}k(q_{i},k_{l})}\; and\; k(q_{i},k_{j})\; select\; asymmetric\; exponential\; kernel\; exp\left (\frac{q_{i}k_{j}^{T}}{\sqrt{d}}\right )$

self-attention通过计算 $p(k_{j}|q_{i})$ 来将所有的value进行加权求和，这个过程需要 $O(L_{Q}L_{K})$ 的时间复杂度和内存使用，这是增强Transformer对LSTF问题的容量的主要障碍。

ProbSparse Self-attention

一些之前的研究表明self-attention的权重具有潜在的稀疏性（sparsity），并且已经研究了一些选择性的方法来不影响性能地过滤稀疏权重，这一方面的研究包括Sparse Transformer、 LogSparse Transformer、Longformer等。

本文对self-attention的稀疏性进行了调查。self-attention的权重构成了一个长尾分布（long tail distribution），也就是很少的权重贡献了主要的attention，而其他的可以被忽略：

长尾分布

问题在于对于可忽略的权重，如何识别出它们。第 $i$ 个query对所有的key的attention权重可以看做一个概率分布 $p(k_{j}|q_{i})$ ，一些起显著作用的attention权重会使得 $p(k_{j}|q_{i})$ 偏离均匀分布。如果 $p(k_{j}|q_{i})$ 接近一个均匀分布 $q(k_{j}|q_{i})=\frac{1}{L_{K}}$ ，那么self-attention就成了对value的平均，也就是冗余的，也就表明第 $i$ 个query是lazy的。下图展示了active和lazy的query的attention权重分布：

权重的分布

一个query的分布 $p(k_{j}|q_{i})$ 与均匀分布的 $q(k_{j}|q_{i})$ 之间的差异可以用KL散度来度量：

$KL(q||p)=-\sum _{j=1}^{L_{K}}q(k_{j}|q_{i})ln\left (\frac{p(k_{j}|q_{i})}{q(k_{j}|q_{i})}\right )\\ =\sum _{j=1}^{L_{K}}q(k_{j}|q_{i})ln\, q(k_{j}|q_{i})-\sum _{j=1}^{L_{K}}p(k_{j}|q_{i})ln\, p(k_{j}|q_{i})\\ =\sum _{j=1}^{L_{K}}\frac{1}{L_{K}}ln\frac{1}{L_{K}}-\sum _{j=1}^{L_{K}}\frac{1}{L_{K}}ln\frac{k(q_{i},k_{j})}{\sum _{l}k(q_{i},k_{l})}\\ =\sum _{j=1}^{L_{K}}\frac{1}{L_{K}}ln\frac{1}{L_{K}}-\sum _{j=1}^{L_{K}}\frac{1}{L_{K}}ln\frac{exp\left (q_{i}k_{j}^{T}/\sqrt{d}\right )}{\sum _{l=1}^{L_{K}}exp\left (q_{i}k_{l}^{T}/\sqrt{d}\right )}\\ =ln\sum _{l=1}^{L_{K}}exp\left (\frac{q_{i}k_{l}^{T}}{\sqrt{d}}\right )-\frac{1}{L_{K}}\sum _{j=1}^{L_{K}}\frac{q_{i}k_{j}^{T}}{\sqrt{d}}-lnL_{K}$

去掉常数，就可以定义第 $i$ 个query的稀疏性度量为：

$M(q_{i},K)=ln\sum _{j=1}^{L_{K}}exp\left (\frac{q_{i}k_{j}^{T}}{\sqrt{d}}\right )-\frac{1}{L_{K}}\sum _{j=1}^{L_{K}}\frac{q_{i}k_{j}^{T}}{\sqrt{d}}$

这里的第一项为一个Log-Sum-Exp（LSE）运算，第二项为一个算术平均值，如果第 $i$ 个query获得了一个较大的 $M(q_{i},K)$ ，这表明它的attention权重分布 $p$ 是更加的多样化，很可能包含长尾分布中的主要注意力。因此对于所有的query来说，我们选取 $M(q_{i},K)$ 排名前 $u$ 的若干query作为 $\hat{Q}$ ，这里的 $u=c\,lnL_Q$ ， $c$ 是一个常数采样因子，那么ProbSparse Self-attention的过程就表示为：

$A(Q,K,V)=softmax\left (\frac{\hat{Q}K^{T}}{\sqrt{d}}\right )V$

这里的ProbSparse Self-attention对于每个key就只需要计算 $O(lnL_{Q})$ 次点积，并且内存使用量为 $O(L_{K}lnL_{Q})$ 。然而，在计算所有的 $M(q_{i},K)$ 时我们需要计算每个点积，也就是 $O(L_{Q}L_{K})$ 的复杂度，并且LSE操作有潜在的数值稳定性问题。对于这个问题，本文提出了一种近似计算稀疏性度量的方法。

对于近似的稀疏性度量，我们采用以下的度量方法：

$\hat{M}(q_{i},K)=\underset{j}{max}\left \{\frac{q_{i}k_{j}^{T}}{\sqrt{d}}\right \}-\frac{1}{L_{K}}\sum _{j=1}^{L_{K}}\frac{q_{i}k_{j}^{T}}{\sqrt{d}}$

在实际操作中，我们只需要采样 $U=L_QlnL_K$ 个点积来近似计算所有的 $\hat{M}(q_{i},K)$ ，对于其他的点积赋值为 $0$ 。根据计算的稀疏性度量 $\hat{M}(q_{i},K)$ ，挑选排名前 $u$ 的query作为 $\hat{Q}$ ，然后进行ProbSparse Self-attention。在 $\hat{M}(q_{i},K)$ 没有LSE操作，其中的最大值操作对 $0$ 不敏感并且数值稳定。最终ProbSparse Self-attention的复杂度为 $O(LlnL)$ （通常 $L_Q$ 和 $L_K$ 是相等的）。

上面之所以可以用 $\hat{M}(q_{i},K)$ 来代替 $M(q_{i},K)$ 来作为稀疏性度量，是因为有以下Lemma 1和Proposition 1做支撑：

Lemma 1
对于所有的query $q_{i}\in \mathbb{R}^{d}$ 以及集合 $K$ 中所有的key $k_{j}\in \mathbb{R}^{d}$ ，我们有 $M(q_{i},K)$ 的上下界：
$lnL_{K}\leq M(q_{i},K)\leq \underset{j}{max}\left \{\frac{q_{i}k_{j}^{T}}{\sqrt{d}}\right \}-\frac{1}{L_{K}}\sum _{j=1}^{L_{K}}\frac{q_{i}k_{j}^{T}}{\sqrt{d}}+lnL_{K}$
当 $q_{i}\in K$ 时同样满足。

Proposition 1
假设 $k_{j}\sim N(\mu ,\Sigma )$ ，同时定义集合 $qk_{i}=\left \{(q_{i}k_{j}^{T})/\sqrt{d}|j=1,\cdots ,L_{K}\right \}$ ，对于 $\forall M_{m}=max_{i}M(q_{i},K)$ ，存在一个 $\kappa$ 满足： $\forall q_{1},q_{2}\in \left \{q|M(q,K)\in [M_{m},M_{m}-\kappa )\right \}$ ，如果 $\hat{M}(q_{1},K)>\hat{M}(q_{2},K)$ ，同时 $Var(qk_{1})>Var(qk_{2})$ ，那么大概率 $M(q_{1},K)>M(q_{2},K)$ 。

$\hat{M}(q_{i},K)$ 也就是 $M(q_{i},K)$ 的上界，上述命题保证了使用 $\hat{M}(q_{i},K)$ 来做稀疏性度量和使用 $M(q_{i},K)$ 的效果是差不多的。关于Lemma 1和Proposition 1的证明可以参照论文附录里的证明。

ProbSparse Self-attention的算法如下：

输入：Tensor $Q\in \mathbb{R}^{m\times d},K\in \mathbb{R}^{n\times d},V\in \mathbb{R}^{n\times d}$
①初始化：设置超参数 $c,u=c\, lnm,U=m\, lnn$ ；
②从 $K$ 中随机采样 $U$ 个点积对 $\hat{K}$ ；
③计算采样的得分 $\hat{S}=Q\hat{K}^{T}$ ；
④按行计算稀疏性得分 $\hat{M}=max(\hat{S})-mean(\hat{S})$ ；
⑤按照 $\hat{M}$ 选择排名最前的 $u$ 个query组成 $\hat{Q}$ ；
⑥ $S_{1}=softmax\left (\frac {Q\hat{K}^{T}}{\sqrt{d}}\right )V$ ；
⑦ $S_{0}=mean(V)$ ；
⑧ $S=\left \{S_{1},S_{0}\right \}$ ，并且调整为原来的行顺序；
输出：ProbSparse Self-attention的feature map $S$ 。

三、Informer的encoder（Self-attention Distilling）

按照上一节中介绍的输入表示方法， $t$ 时刻输入的序列 $\mathrm{X}^{t}$ 会被表示成 $X_{feed\_en}^{t}\in \mathbb{R}^{L_{x}\times d_{model}}$ 。

按照上面的算法介绍的ProbSparse Self-attention过程，attention的结果必然会产生冗余（由于存在 $S_{0}$ ），因此本文又提出了self-attention蒸馏操作来提炼出主要的attention，这大大地缩短了输入的时间维度。具体的，从第 $j$ 层到 $j+1$ 的蒸馏操作为：

$X_{j+1}^{t}=MaxPool(ELU(Conv1d([X_{j}^{t}]_{AB})))$

式子中 $[\cdot ]_{AB}$ 表示Multi-head ProbSparse Self-attention以及其他必要的操作（包括Add、LayerNorm、FFN等）， $Conv1d$ 表示在时间维度上执行一维卷积（卷积核宽度为3）并且后面跟随 $ELU$ 激活函数，然后经过 $MaxPool$ 进行最大池化下采样（池化窗口宽度为2），将输入的长度变为原来的一半。self-attention蒸馏操作将总共的内存占用量变为了 $O((2-\epsilon )LlogL)$ ，这里的 $\epsilon$ 是一个很小的数字。

为了增强蒸馏操作的鲁棒性，本文的encoder架构还建立了多个encoder的stack，每个stack都是一个独立的小的encoder，只是随着stack的增加，逐步每次减少一个蒸馏操作层和输入长度的一半，最终将所有的stack输出拼接起来。Informer的encoder架构如下图所示：

encoder

举例来说，如果encoder存在3个stack，那么第一个stack就会有3个Multi-head ProbSparse Self-attention层和2个Self-attention Distilling层（输入为 $L$ ，输出为 $L/4$ ），第二个stack就会有2个Multi-head ProbSparse Self-attention层和1个Self-attention Distilling层（输入为 $L/2$ ，输出为 $L/4$ ），第三个stack就会有1个Multi-head ProbSparse Self-attention层而没有Self-attention Distilling层（输入为 $L/4$ ，输出为 $L/4$ ）。这里的stack输入如果为 $L/2$ ，则使用的是原输入的后半部分， $L/4$ 类似。

四、Informer的decoder（Generative Style Decoder）

Informer的decoder由一个Multi-head Masked ProbSparse Self-attention层和一个Multi-head Self-attention层组成。这里的Multi-head ProbSparse Self-attention要进行mask，也是为了避免左向信息流，防止自回归。同时最后要有一个全连接层，全连接层输出的维度取决于要预测的变量维度 $d_y$ 。本文提出了一种生成式的推理过程来提高推理的速度，具体的，decoder的输入为：

$X_{feed\_de}^{t}=Concat(X_{token}^{t},X_{0}^{t})\in \mathbb{R}^{(L_{token}+L_{y})\times d_{model}}$

这里的 $X_{token}^{t}\in \mathbb{R}^{L_{token}\times d_{model}}$ 是start token， $X_{0}^{t}\in \mathbb{R}^{L_{y}\times d_{model}}$ 是一个为预测序列保留的placehood（设置scalar值为0）。start token是自然语言处理的动态解码过程中一项有效的技术，通常start token设置为一个特殊的flag，而在Informer里的start token是一个序列，从encoder的输入中截取得到，举例来说，要预测7天的序列，那么可以截取输入序列中的最后5天作为start token。 $X_{0}^{t}$ 包含预测序列的时间戳embedding。整个decoder的解码过程舍弃了动态解码过程，而采用一次前向过程即可解码得到整个输出序列。训练时选用MSE作为损失函数。