ICLR 2022 Oral | 蚂蚁集团用于长程时序建模的开源算法Pyraformer简介
导 言
基于历史的数据预测未来对于风险管理和资源配置具有重要意义，而这样的时序中通常存在着不同尺度的依赖关系，如日周期，周周期和月周期等。目前的时序预测算法面临的主要挑战是在不极大增加模型复杂度的情况下同时捕获时序数据中的多种依赖关系。
针对该挑战，在蚂蚁集团和上海交大合作的一篇论文中，作者们提出了金字塔注意模块(PAM)，通过尺度间连边提取不同分辨率的特征，通过尺度内连边建模不同尺度的依赖关系，从而以线性的复杂度提取出时间序列中的多尺度特征来进行预测。该篇论文已被机器学习顶会ICLR 2022接收为口头报告论文。
相比于现行的SOTA方法，该模型可以处理长时序，并自动从长时序中提取多尺度的特征，在单步和长程预测的任务中表现更好，在预测式扩缩容业务场景中也取得了不错的效果。
简 介
时间序列预测在现代生活中发挥着许多作用，如量化交易、风险控制、事前决策、资源优化等。基于历史的股票数据预测未来趋势并制定策略，能够减少投资者情绪波动的影响，避免非理性的决策；基于历史的异常事件数据预测未来，能够提前识别风险，提升系统的稳定性；基于历史的销售数据预测未来需求，能够提前决定进货量，节约沉没成本。
蚂蚁集团于4月21日加入了低碳专利承诺并开放了7件“绿色计算”相关的专利。时序预测也是“绿色计算”中重要的一环。“绿色计算”的关键在于不影响用户体验的情况下尽量节省资源减少能耗。为了达到这一目的，精准的预测用户的行为（比如流量），可以为后续的资源配置提供可靠的参考。
具体的来说，云原生系统在容器中部署微服务应用或者数据库租户实例等。为了支持大量的用户请求，通常一个微服务/数据库租户要部署多个的容器实例。云原生容量管理的核心问题就是根据需求确定需要部署容器实例的数目。在用户请求超量的时候，要多部署一些实例以应对可能的风险；在用户请求相对较少的时候，可以缩减一些部署实例以节省容量成本。
因此，蚂蚁智能容量管家平台利用机器学习技术在流量发生变化之前自动扩展计算容量，从而提高资源利用率，节省资源开销。为此，我们提出了一种基于金字塔注意力机制的预测模型Pyraformer。该论文被ICLR 2022接收为口头报告(Oral)。
ICLR是机器学习三大顶会之一（另外两个是ICML和NeurIPS），每年都会吸引大量专家、学者和AI领域从业人员参与，在学术界和AI工业界有巨大影响。据悉，今年ICLR共有3391投稿，接收论文1095篇，投稿量和接收量都创了新高，但仅有54篇接收为oral presentation，Oral接收率为1.6%。Oral中第一作者来自中国大陆的论文有6篇，分别为清华大学，上海交通大学，浙江大学，和哈尔滨工业大学。
蚂蚁这篇论文的详细信息如下：
论文：Pyraformer: Low-Complexity Pyramidal Attention for Long-range Time Series Modeling and Forecasting
论文地址：https://openreview.net/pdf?id=0EXmFzUn5I
代码已经开源，github地址：https://github.com/alipay/Pyraformer
时序预测算法的挑战
理想的时序模型应该满足以下两个特性：
1.建模长程依赖的能力强：一般的时序中通常存在着不同尺度的依赖关系（比如日周期，周周期，和月周期）。如何找到一个强力的模型来对这些依赖关系进行建模是时序预测的关键。在不同尺度的依赖关系中，最难被处理的是长程依赖关系。模型对长程依赖的建模能力可以由时序中任意两点在模型里的最大信息传播路径来粗略评判[1]，路径越短，模型对于长程依赖的建模效果越好；
2.时空复杂度低：为了捕捉长程依赖，输入模型的历史数据也需要很长。为了达到这个目的，模型的时空复杂度必须尽可能的小。
不幸的是，目前主流的方法难以同时实现上述两个目标。一方面，CNN [5]、RNN [6]等网络尽管时间复杂度是随时间序列长度$L$线性增长的，但最大信息传播路径是$\mathcal O(L)$的，因此难以学习到长程依赖。Transformer [1] 则是另一个极端，将最大信息传播路径降到了$\mathcal O(1)$，但时间复杂度则增大到了$\mathcal O(L^2)$，因此也难以应用于非常长的序列。
为了在模型能力与复杂度之间找到平衡，近来很多Transformer的变种涌现了出来，例如Longformer [2], Reformer [3] 和Informer [4]. 然而，这些变种也难以同时实现短于$\mathcal O(L)$的最大信息传播路径和极低的时空复杂度。
表1: 不同模型的复杂度和最大信息传播路径比较。其中，$G$是ETC中的全局节点数，实际使用中$G$会随着$L$增长，因此ETC的时空复杂度是超线性的
针对这些挑战，本文提出了Pyraformer，通过提取时间序列中的多尺度特征来进行预测。我们首先引入了金字塔注意模块(PAM)，该模块采用树结构来执行自注意力，通过尺度间连边提取不同分辨率的特征，通过尺度内连边建模不同尺度的依赖关系。
在适当条件下，Pyraformer中的最大信息传播路径相对于序列长度$L$是一个常数(即$\mathcal O(1)$)，而时空复杂度与$L$呈线性关系。大量实验表明，Pyraformer在单步和长程预测任务中都能以最少的时间和内存占用达到最高的预测精度，尤其是在序列较长的情况下。
解决方案
时间序列预测的问题可以描述为：给定历史的$L$个观测值$\bold z_{t - L + 1 : t}$及其对应的协变量$\bold x_{t - L + 1 :t + M}$(比如观测值对应的日期、小时)，预测$M$个未来值$\bold z_{t+1:t+M}$。
为了应对上述挑战，本文提出了一种基于金字塔注意力的 Transformer，来取得捕捉长程依赖和实现低时空复杂度的良好平衡，如图2所示。与Informer [4]相同的是，我们先对观测数据、协变量和位置分别做特征嵌入，然后再将它们相加。接下来，我们使用粗尺度构造模块（CSCM）构建了一棵有$C$个分支的多叉树，其中粗尺度的节点汇总了相应的$C$个细尺度节点的信息。
为了进一步捕获不同范围的时间依赖关系，我们引入了金字塔注意模块（PAM），在金字塔形的图结构中使用注意力机制交换信息。最后，根据下游任务的不同，我们使用不同的网络结构来输出最终的预测。
本文的主要贡献包括:
● 我们提出了 Pyraformer，以多分辨率的方式同时捕捉不同范围的时间依赖关系。为了与目前最先进的方法区分开，我们在图1中以图结构的形式总结了所有对比模型。
● 我们在理论上证明了通过适当选取参数，Pyraformer 可以同时实现$\mathcal O(1)$的最大信息传播路径和$\mathcal O(L)$的时空复杂度。为了突出 Pyraformer 的吸引力，我们进一步在表1中比较了不同模型的最大信息传播路径和复杂度。
● 实验表明，不论是单步预测任务还是长程预测任务，我们提出的 Pyraformer 在多个真实数据集上都取得了比 Transformer 及其变体更好的效果，并且消耗的时间和显存更低。
图2：Pyraformer的结构：CSCM将嵌入序列汇总为不同分辨率的序列，从而构建出一个多分辨率的树结构。然后，PAM被用来在节点之间高效地交换信息
下面我们详细阐述Pyraformer的各个部分：
A 金字塔注意模块（Pyramidal Attention Module, PAM）
由于PAM是本文提出方法的核心，我们首先介绍PAM。如图1(d)所示，我们利用该金字塔形的图结构，以多分辨率的方式表征历史序列中的时间依赖关系。在金字塔图中，我们假设最底层的节点对应了我们观察到的时序。比如，我们观察到的时序是小时粒度，那每个节点对应了一个小时。
上层的节点，可以认为是总结了每天，每周，和每月的信息。为了进行精准的时序预测，我们需要做的就是找到过于和未来的关系，然后基于过去才能预测未来。这里，我们通过连接每一层节点，来建模过于与未来。比如每个小时之间的关系，在底层进行了建模，而每个月之间的关系在顶层进行了建模。
由于，月与月之前的关系在顶层进行了建模，到了周这一层，就不在需要考虑本周与上个月同一周之间了关系了，只需要考虑相邻的一两周之间的关系。因此，每一层里，我们只考虑相邻节点之间的关系。整个图通过attention机制构建，即把Transformer中的全连接图换成金字塔图。
我们比较容易证明如下定理（具体参考论文原文）：
定理：在容易满足的条件下，本文提出的PAM可以同时实现$\mathcal O(L)$的时间和空间复杂度以及$\mathcal O(1)$的最大传播路径长度。
B 粗粒度构造模块(Coarse-Scale Construction Module, CSCM)
CSCM的目的是初始化金字塔图上的粗尺度节点，以便后续的PAM在这些节点之间交换信息。这里通过带bottleneck的卷积网络实现，如下图所示。
图3：粗尺度构造模块: $B$为批大小，$D$为节点特征的维度大小
C 预测模块
这里，我们提出了两种预测模块。第一种直接连接一个线性层，输出结果即为预测值。第二种使用了一个由两层全连接注意力层组成的解码器。具体结构如下图所示。我们发现，由于PAM可以比较好的从时序中提取各种信息，简单线性层已经可以很好的预测未来。
图4：基于attention机制的预测模块
实验
我们在四个真实数据集上验证了Pyraformer的优势，包括Wind, App Flow（蚂蚁应用容量数据）, Electricity和ETT。前三个数据集用于单步预测，后两个数据集用于长程预测。
A 单步预测
我们将Pyraformer与其他5种注意力机制进行了对比，包括原始的Full-attention[1]，LogTrans[8]，Reformer[3]，ETC[7]和Longformer[2]。各方法的结果展示在表2中。
表2：三个数据集上的单步预测结果。"Q-K对"指网络中所有注意力层执行的查询向量和键向量点积的数量，代表了模型的时空复杂度。$N$代表注意力层数，$H$代表注意力头数，$S$代表尺度数，$D$代表每个节点的特征维度。$D_K$表示键向量的特征维度，$D_F$表示前馈层的最大特征维度，而$C$表示CSCM中卷积的步长
实验结果表明，Pyraformer在NRMSE和ND方面优于Transformer及其变种，并且具有最少的计算量。
B 长程预测
我们在三个数据集上评估了Pyraformer的长程预测性能，包括Electricity，ETTh1和ETTm1。我们将解决方案中提出的两个预测模块装配到所有模型上进行了测试，并在表3中列出了最好的结果。
表3: 长程预测结果
可以看到，在所有数据集和所有预测长度上，Pyraformer仍然以最少的Q-K对达到了最好的性能。有趣的是，我们注意到对于Pyraformer，第一个预测模块的效果比第二个预测模块的结果更好。
C 速度和显存占用
为了检验基于TVM实现的PAM专用CUDA核的效率，我们在图4中分别以计算时间和显存占用为纵轴，以序列长度$L$为横轴，画出了二者随序列长度的变化。这里我们只比较了Informer[4]中的prob-sparse注意力机制、全连通注意力机制和PAM。
图5：不同注意力机制的时间和显存消耗比较。包括全连通注意力、Informer的prob-sparse注意力和PAM的TVM实现: (a) 计算时间; (b) 显存占用
图4表明，基于TVM的PAM的计算和存储开销近似为$L$的线性函数，与预期一致，且比全连通注意力机制和prob-sparse注意力机制小几个数量级，特别是对于较长的序列。（更多实验请参考论文原文）
“绿色计算”应用及结果
如前所述，预测式扩缩容需要精准预测所有应用未来不同粒度的流量请求，为提前扩缩容提供参考。准确的预测是容量稳定性和资源节省的重要保障，因此预测性扩缩容是蚂蚁容量管家的核心技术。同时，资源配置的优化可以大大减少能源的损耗，为了“低碳”这一目标做出贡献。时序预测是蚂蚁“绿色计算”技术中重要的一环。
此前，基于Transformer，我们给所有应用建立了一个通用的时序预测模型。目前，基于自动扩缩容的能力，约22%的扩容和53%的缩容工单由系统自动生成，不但可以有效的预防容量风险，还使得应用的CPU利用率水位提升了5%-10%，日均节省资源约3万cores。
另外，由于T+8hour预测效果严重低于T+30min，我们提出了用于长程时序预测的Pyraformer模型，在预测效果提升了近20%。更准确的预测结果，弹性扩缩容能力可以覆盖的应用时序数目也有相应的提升。Pyraformer已经成为预测性扩缩容背后的黑科技核心算法之一。
参考文献
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008, 2017.
[2] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150, 2020.
[3] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2019.
[4] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of AAAI, 2021.
[5] Mohsin Munir, Shoaib Ahmed Siddiqui, Andreas Dengel, and Sheraz Ahmed. Deepant: A deep learning approach for unsupervised anomaly detection in time series. Ieee Access, 7:1991–2005, 2018.
[6] David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. Deepar: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting, 36(3):1181–1191, 2020.
[7] Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. Etc: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 268–284, 2020.
[8] Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, and Xifeng Yan. Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting. Advances in Neural Information Processing Systems, 32:5243–5253, 2019.