Pyraformer: 低复杂度金字塔注意力在长序列时间序列建模和预测中的应用

时间序列数据的分析和预测在许多领域中具有重要意义，如决策制定和风险管理。本文将介绍一种名为Pyraformer的新模型，该模型通过探索时间序列的多分辨率表示，提出了一种低复杂度的金字塔注意力机制用于长序列时间序列的建模和预测。

引言

时间序列预测是许多下游任务的基础，例如决策制定和风险管理。例如，在线流量的可靠预测可以为云系统中潜在风险提供早期预警，同时也为动态资源分配提供指导，以最小化成本而不降低性能。除了在线流量，时间序列预测在疾病传播、能源管理以及经济和金融等领域也有广泛应用。

时间序列预测的主要挑战在于构建一个强大但简洁的模型，能够紧凑地捕捉不同范围的时间依赖性。时间序列通常表现出短期和长期重复模式，考虑这些模式是精确预测的关键。特别是处理长范围依赖的任务更加困难，这通常通过信号传递路径的长度来衡量。路径越短，依赖关系捕捉得越好。同时，为了让模型学习这些长期模式，输入的历史数据也应该足够长。因此，低时间和空间复杂度是优先考虑的。

现有的最先进的方法难以同时实现这两个目标。RNN和CNN在时间复杂度方面表现良好，但它们的信号传递路径长度较长，难以学习远距离的位置依赖。另一方面，Transformer虽然缩短了信号传递路径，但增加了时间复杂度。为了在模型能力和复杂度之间找到平衡，出现了一些Transformer的变种，如Longformer、Reformer和Informer。然而，很少有方法能够在大幅降低时间和空间复杂度的同时实现短的最大路径长度。

Pyraformer模型概述

为了解决上述问题，本文提出了一种新型的基于金字塔注意力的Transformer模型（Pyraformer）。具体来说，开发了一种金字塔注意力机制，通过在金字塔图上基于注意力的消息传递来描述时间序列的时间依赖性。该图中的边可分为两组：跨尺度和同尺度连接。跨尺度连接构建了原始序列的多分辨率表示，而同尺度连接捕捉了各分辨率下的时间依赖性。这样，该模型通过在较粗的分辨率下捕捉长范围的行为，提供了对远距离位置之间长期时间依赖性的紧凑表示，从而缩短了信号传递路径的长度。此外，在不同尺度上通过稀疏的邻接同尺度连接建模不同范围的时间依赖性显著降低了计算成本。

金字塔注意力模块（PAM）

金字塔注意力模块（PAM）是Pyraformer的核心。通过金字塔图以多分辨率的方式描述观察到的时间序列的时间依赖性。金字塔图可以分解为两部分：跨尺度和同尺度连接。跨尺度连接形成了一棵C叉树，其中每个父节点有C个子节点。例如，如果将金字塔图的最细尺度与原始时间序列的小时观察值相关联，则较粗尺度的节点可以看作是时间序列的每日、每周甚至每月模式。因此，金字塔图提供了原始时间序列的多分辨率表示。此外，通过简单地连接邻近节点来捕捉各分辨率下的时间依赖性，可以在较粗尺度上更容易地捕捉长范围依赖性。

粗尺度构建模块（CSCM）

CSCM的目标是初始化金字塔图在较粗尺度上的节点，从而促进后续的PAM在这些节点之间交换信息。具体来说，通过在对应的子节点上执行卷积操作，逐层引入粗尺度节点。卷积层的步长和核大小均为C，经过多层卷积操作后，得到不同尺度上的序列，形成一棵C叉树。为了减少参数和计算量，在输入嵌入序列到卷积层之前，通过全连接层减少每个节点的维度，并在所有卷积操作完成后恢复原始维度。

预测模块

对于单步预测，在输入嵌入层之前，向历史序列的末尾添加一个结束标记。在PAM编码序列后，收集金字塔图中所有尺度上的最后一个节点的特征，进行串联后通过全连接层进行预测。

对于多步预测，提出了两种预测模块。第一种与单步预测模块相同，但将所有尺度上的最后一个节点映射到所有未来时间步。第二种则采用具有两个全注意力层的解码器。具体来说，类似于原始Transformer，将未来时间步的观测值替换为0，嵌入它们并将观测值、协变量和位置嵌入的和称为“预测标记”。第一个注意力层将预测标记作为查询，PAM的输出作为键和值，生成解码器输出。第二层将解码器输出作为查询，解码器输出和PAM的输出作为键和值。历史信息直接输入到两个注意力层中，因为这些信息对精确的长范围预测至关重要。

实验结果与分析

在四个真实世界数据集上进行了广泛的实验，包括Wind、App Flow、Electricity和ETT。结果显示，Pyraformer在单步和长范围多步预测任务中表现出色，且时间和内存消耗较低。

单步预测

在Electricity、Wind和App Flow数据集上进行了单步预测实验。结果表明，Pyraformer在NRMSE和ND指标上优于其他Transformer变种，且具有最少的查询-键点积数量。

长范围多步预测

在Electricity、ETTh1和ETTm1数据集上进行了长范围多步预测实验。结果显示，无论预测长度如何，Pyraformer在所有数据集上的表现均优于其他模型，并且具有最少的查询-键点积数量。

计算时间和内存消耗

通过实验验证了基于TVM实现的定制CUDA内核的效率。结果表明，Pyraformer的时间和内存消耗与序列长度近似呈线性关系，且显著低于全注意力和概率稀疏注意力机制，特别是对于较长的时间序列。

结论与展望

本文提出了Pyraformer，一种基于金字塔注意力的新型模型，能够在低时间和空间复杂度下有效描述短期和长期时间依赖性。实验结果表明，Pyraformer在单步和长范围多步预测任务中均优于现有最先进模型，且计算时间和内存消耗较低。未来的工作将探索如何从数据中自适应地学习超参数，并将Pyraformer扩展到自然语言处理和计算机视觉等其他领域。

参考文献

Shizhan Liu, Hang Yu, Cong Liao, Jianguo Li, Weiyao Lin, Alex X. Liu, Schahram Dustdar. "Pyraformer: Low-Complexity Pyramidal Attention for Long-Range Time Series Modeling and Forecasting." ICLR 2022. PDF
Vaswani, Ashish, et al. "Attention is all you need." Advances in neural information processing systems. 2017.
Zhou, Haoyi, et al. "Informer: Beyond efficient transformer for long sequence time-series forecasting." AAAI. 2021.
Beltagy, Iz, Matthew E. Peters, and Arman Cohan. "Longformer: The long-document transformer." arXiv preprint arXiv:2004.05150 (2020).
Kitaev, Nikita, Łukasz Kaiser, and Anselm Levskaya. "Reformer: The efficient transformer." International Conference on Learning Representations. 2019.

Summary of "Pyraformer: Low-Complexity Pyramidal Attention for Long-Range Time Series Modeling and Forecasting"

This paper proposes Pyraformer, a novel Transformer-based model designed to address the challenges of long-range time series forecasting. The key innovation lies in its pyramidal attention module (PAM), which efficiently captures both short-term and long-term dependencies in time series data.

Here's a breakdown of the paper's key aspects:

Problem: Existing time series forecasting methods struggle to balance computational efficiency with the ability to capture long-range dependencies. RNNs and CNNs are efficient but struggle with long sequences, while Transformers, while good at capturing long-range dependencies, suffer from quadratic complexity.

Proposed Solution: Pyraformer

Pyramidal Attention Module (PAM):
- Employs a multi-resolution pyramidal graph to represent the time series.
- Inter-scale connections: Form a C-ary tree where each level summarizes information at a different resolution (e.g., hourly, daily, weekly).
- Intra-scale connections: Capture temporal dependencies within each resolution by connecting neighboring nodes.
- This structure allows for efficient modeling of long-range dependencies by capturing them at coarser resolutions.
Coarser-Scale Construction Module (CSCM): Initializes the nodes at coarser scales using convolutions applied to finer-scale representations.
Prediction Module:
- Single-step forecasting: Gathers features from all scales and uses a fully connected layer for prediction.
- Multi-step forecasting: Offers two options:
  - Similar to single-step but maps to multiple future time steps.
  - Utilizes a decoder with two full attention layers for incorporating historical information.

Advantages:

Low Complexity: Achieves linear time and space complexity (O(L)) thanks to the sparse connections in the pyramidal graph.
Long-Range Dependency Capture: Maintains a constant maximum signal traversing path length (O(1)), enabling efficient modeling of long-range dependencies.
Improved Accuracy: Outperforms existing methods in both single-step and long-range multi-step forecasting tasks.

Key Results:

Pyraformer consistently achieves higher prediction accuracy compared to other Transformer variants and traditional methods on various real-world datasets.
It achieves this while maintaining significantly lower time and memory consumption, especially for long sequences.

Overall, Pyraformer presents a promising solution for long-range time series forecasting by effectively balancing model complexity and the ability to capture long-term dependencies.