PYRAFORMER LOW-COMPLEXITY PYRAMIDAL ATTENTION FOR LONG-RANGE TIME SERIES MODELING.pdf

smith0907

446

20页

0次

2023-10-23

50墨值下载

Published as a conference paper at ICLR 2022

PYRAFORMER: LOW-COMPLEXITY PYRAMIDAL AT-

TENTION FOR LONG-RANGE TIME SERIES MODELING

AND FORECASTING

Shizhan Liu

1,2∗

, Hang Yu

1∗

, Cong Liao

, Jianguo Li

1†

, Weiyao Lin

, Alex X. Liu

and Schahram Dustdar

Ant Group,

Shanghai Jiaotong University,

TU Wien, Austria

ABSTRACT

Accurate prediction of the future given the past based on time series data is of

paramount importance, since it opens the door for decision making and risk man-

agement ahead of time. In practice, the challenge is to build a ﬂexible but parsi-

monious model that can capture a wide range of temporal dependencies. In this

paper, we propose Pyraformer by exploring the multi-resolution representation of

the time series. Speciﬁcally, we introduce the pyramidal attention module (PAM)

in which the inter-scale tree structure summarizes features at different resolutions

and the intra-scale neighboring connections model the temporal dependencies of

different ranges. Under mild conditions, the maximum length of the signal travers-

ing path in Pyraformer is a constant (i.e., O(1)) with regard to the sequence length

L, while its time and space complexity scale linearly with L. Extensive experi-

mental results show that Pyraformer typically achieves the highest prediction ac-

curacy in both single-step and long-range multi-step forecasting tasks with the

least amount of time and memory consumption, especially when the sequence is

long

1 INTRODUCTION

Time series forecasting is the cornerstone for downstream tasks such as decision making and risk

management. As an example, reliable prediction of the online trafﬁc for micro-services can yield

early warnings of the potential risk in cloud systems. Furthermore, it also provides guidance for

dynamic resource allocation, in order to minimize the cost without degrading the performance. In

addition to online trafﬁc, time series forecasting has also found vast applications in other ﬁelds,

including disease propagation, energy management, and economics and ﬁnance.

The major challenge of time series forecasting lies in constructing a powerful but parsimonious

model that can compactly capture temporal dependencies of different ranges. Time series often

exhibit both short-term and long-term repeating patterns (Lai et al., 2018), and taking them into

account is the key to accurate prediction. Of particular note is the more difﬁcult task of handling

long-range dependencies, which is characterized by the length of the longest signal traversing path

(see Proposition 2 for the deﬁnition) between any two positions in the time series (Vaswani et al.,

2017). The shorter the path, the better the dependencies are captured. Additionally, to allow the

models to learn these long-term patterns, the historical input to the models should also be long. To

this end, low time and space complexity is a priority.

Unfortunately, the present state-of-the-art methods fail to accomplish these two objectives simul-

taneously. On one end, RNN (Salinas et al., 2020) and CNN (Munir et al., 2018) achieve a low

time complexity that is linear in terms of the time series length L, yet their maximum length of the

signal traversing path is O(L), thus rendering them difﬁcult to learn dependencies between distant

positions. On the other extreme, Transformer dramatically shortens the maximum path to be O(1)

∗

Equal contribution. This work was done when Shizhan Liu was a research intern at Ant Group.

†

Corresponding author

Code is available at: https://github.com/alipay/Pyraformer

Published as a conference paper at ICLR 2022

Connection example

Maximum signal traversing path

(a) Full Attention

Hidden States

Inputs

(e) ETC

(d) Pyraformer

Layer 1

Embeddings

Input

Embeddings

Layer 2

Embeddings

Layer 3

Embeddings

(b) CNN

Layer 1

Embeddings

Input

Embeddings

Layer 2

Embeddings

Layer 3

Embeddings

(f) LogTrans

Figure 1: Graphs of commonly used neural network models for sequence data.

Table 1: Comparison of the complexity and the maximum signal traveling path for different models,

where G is the number of global tokens in ETC. In practice, the G increases with L, and so the

complexity of ETC is super-linear.

Method Complexity per layer Maximum path length

CNN (Munir et al., 2018) O(L) O(L)

RNN (Salinas et al., 2020) O(L) O(L)

Full-Attention (Vaswani et al., 2017) O(L

) O(1)

ETC (Ainslie et al., 2020) O(GL) O(1)

Longformer (Beltagy et al., 2020) O(L) O(L)

LogTrans (Li et al., 2019) O(L log L) O(log L)

Pyraformer O(L) O(1)

at the sacriﬁce of increasing the time complexity to O(L

). As a consequence, it cannot tackle

very long sequences. To ﬁnd a compromise between the model capacity and complexity, variants

of Transformer are proposed, such as Longformer (Beltagy et al., 2020), Reformer (Kitaev et al.,

2019), and Informer (Zhou et al., 2021). However, few of them can achieve a maximum path length

less than O(L) while greatly reducing the time and space complexity.

In this paper, we propose a novel pyramidal attention based Transformer (Pyraformer) to bridge

the gap between capturing the long-range dependencies and achieving a low time and space com-

plexity. Speciﬁcally, we develop the pyramidal attention mechanism by passing messages based on

attention in the pyramidal graph as shown in Figure 1(d). The edges in this graph can be divided

into two groups: the inter-scale and the intra-scale connections. The inter-scale connections build

a multiresolution representation of the original sequence: nodes at the ﬁnest scale correspond to

the time points in the original time series (e.g., hourly observations), while nodes in the coarser

scales represent features with lower resolutions (e.g., daily, weekly, and monthly patterns). Such

latent coarser-scale nodes are initially introduced via a coarser-scale construction module. On the

other hand, the intra-scale edges capture the temporal dependencies at each resolution by connecting

neighboring nodes together. As a result, this model provides a compact representation for long-range

temporal dependencies among far-apart positions by capturing such behavior at coarser resolutions,

leading to a smaller length of the signal traversing path. Moreover, modeling temporal dependencies

of different ranges at different scales with sparse neighboring intra-scale connections signiﬁcantly

reduces the computational cost. In short, our key contributions comprise:

• We propose Pyraformer to simultaneously capture temporal dependencies of different

ranges in a compact multi-resolution fashion. To distinguish Pyraformer from the state-

of-the-art methods, we summarize all models from the perspective of graphs in Figure 1.

• Theoretically, we prove that by choosing parameters appropriately, the maximum path

length of O(1) and the time and space complexity of O(L) can be reached concurrently. To

of 20

50墨值下载

关注

评论