Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting

1 Introduction

Long sequence multivariate time series forecasting plays an essential role in planning and managing complex systems across diverse domains [Liu et al., 2018; Guo et al., 2020; Pedersen et al., 2020a; Pedersen et al., 2020b; Yang et al., 2020]. In such settings, multiple sensors are often deployed to collect diverse information related to a complex system, thus giving rise to multivariate time series [Cirstea et al., 2019]. Figure 1 shows an example of a 3-variate time series indicating the power consumption of three clients from a power grid system, where each variable has its own time series.

∗Corresponding Author

While extensive studies on short term forecasting exist, e.g., dozens steps ahead forecasting [Hochreiter and Schmidhuber, 1997; Qin et al., 2017; Wu et al., 2019; Wu et al., 2020], a limited number of studies focus on long term forecasting, e.g., hundreds steps ahead. Recent studies show that attentions [Vaswani et al., 2017; Wu et al., 2021b] are able to capture better long term dependencies, comparing to Recurrent Neural Networks RNNs [Li et al., 2018; Hu et al., 2020; Kieu et al., 2022a] or Temporal Convolutional Networks TCNs [Wu et al., 2019; Campos et al., 2022; Kieu et al., 2022b]. However, two main limitations still exist.

High complexity. For a time series of H timestamps, canonical self-attention has a quadratic complexity of O(H2 ). Recent studies on long-term forecasting propose different "sparse" versions of self-attentions [Zhou et al., 2021; Kitaev et al., 2020], aiming at reducing the high complexity. We propose Triformer with linear complexity O(H). We first break the time series into small patches. For each patch, we define a novel Patch Attention (PA) with linear complexity (cf. the small white triangles in Figure 2). Specifically, we introduce a pseudo timestamp for a patch and we compute attentions of the timestamps in the patch only to the single Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

2 RelatedWork

We categorize multivariate time series forecasting methods in Table 1 along two dimensions-short vs. long term forecasting and variable-agnostic vs. variable-specific modeling.

For long term forecasting, self-attention based models achieve superior accuracy, but they suffer from quadratic memory and runtime overhead w.r.t. the input time series length H. To reduce the complexity, recent long term forecasting studies propose sparse attentions: LogTrans [Li et al., 2019] is with O(H(logH)2 ), and Informer [Zhou et al., 2021] further reduces the complexity to O(H logH). There also exist other efficient versions of attentions [Beltagy et al., 2020; Wang et al., 2020; Katharopoulos et al., 2020], but they are not designed and verified for time series forecasting. When stacking multiple layers of attentions, an additional pooling layer is often used after each attention layer. This helps shrink the input size to the next attention layer, thus reducing overall complexity [Dai et al., 2020; Zhou et al., 2021]. We propose a novel efficient patch attention with linear complexity, which is able to shrink the layer size by itself without using additional pooling, making a multi-layer patch attention structure also linear.

Variable-agnostic vs. variable-specific modeling. Most studies are variable agnostic, meaning that, although different variables' time series may exhibit distinct temporal patterns, they share the same sets of model parameters, e.g., the same weight matrices in RNNs, the same convolution kernels in TCNs, or the same projection matrices in attentions. Some studies propose variable-specific modeling for RNNs. [Pan et al., 2019] generates variable-specific weight matrices using additional meta-information, e.g., categories of points of interest around the deployed sensor locations. However,

Variable-agnostic parameters. Existing forecasting models often use variable-agnostic parameters, although different variables may exhibit distinct temporal patterns [Wu et al., 2019; Li et al., 2018; Wu et al., 2021b]. For example, as shown in Figure 1, although variable 1 has a unique temporal pattern, which is different from the patterns of variables 2 and 3, the same model parameters, e.g., the projection matrices WQ,WK, and WV used in self-attentions (cf. the black matrices in Figure 1), are applied to all three variables. This forces the learned parameters to capture an "average" pattern among all the variables, thus failing to capture distinct temporal pattern of each variable and hurting accuracy.

We propose a light-weight method to enable variable specific parameters, e.g., a distinct set of matrices W(i) Q ,W(i) K , and W(i) V for the i-th variable (cf. the colorful matrices in Figure 1), such that it is possible to capture distinct temporal patterns for different variables. Specifically, we factorize the projection matrices into variable-agnostic and variablespecific matrices, where the former is shared among all variables and the latter is specific to different variables. We make the variable-specific matrices very compact, thus avoiding increasing the parameter space and computation overhead.

We summarize the main contributions as follows: (i) We propose a novel, efficient attention mechanism, namely Patch Attention, along with its triangular, multi-layer structure. This ensures an overall linear complexity, thus achieving high efficiency. (ii) We propose a light-weight approach to enable variable-specific model parameters, making it possible to capture distinct temporal patterns from different variables, thus enhancing accuracy. (iii) We conduct extensive experiments on four public, commonly used multivariate time series data sets from different domains, justifying our design choices and demonstrating that the proposal outperforms state-of-the-art methods.

such additional meta-information may not be always available. [Bai et al., 2020] learns variable-specific weight matrices using a purely data-driven manner without additional information. We empirically compare with it in the experiments. [Cirstea et al., 2022b; Cirstea et al., 2021] consider variable-specific modeling for networks other than RNNs, but not focusing on long term forecasting. {M (i) } i = 1 N {M (i) } i = 1 N

block. Second, we propose a triangular structure when stacking multiple layers of patch attentions, such that the layer sizes shrink exponentially. This ensures linear complexity for multi-layer patch attentions and also enables extracting multiscale features. Third, we propose a light-weight method to enable variable specific modeling, thus being able to capture distinct temporal patterns from different variables, without TP+1 TP TP+1 TP

x(p -1)s+1

where ϕ denotes the learnable parameters of the forecasting model and ˆxj is the predicted values at timestamp j.

Self-attention. Self-attention is a core operation in attention based models. Given a sequence, e.g., a time series, each timestamp attends to all timestamps in the time series, thus deriving a representation of the entire time series by capturing both long- and short-term dependencies. Consider a time series with H timestamps, e.g., time series x(i) ∈ RH from the i-th variable. Canonical self-attention [Vaswani et al., 2017] first transforms the time series into a query matrix Q(i) = x(i)WQ ∈ RH×d , a key matrix K(i) = x(i)WK ∈ RH×d and a value matrix V(i) = x(i)WV ∈ RH×d , where d represents the hidden representation andWQ,WK, WV ∈ Rd×d are projection matrices, which are learnable. Next, the output is represented as a weighted sum of the values in the value matrix V(i) , where the weights, a.k.a., attention scores, are computed based on the query matrix Q(i) and the key matrix K(i) , as shown in Equation 2.

where φ represents the softmax activation function. Computing the attention scores requires quadratic O(H2 ) time complexity and memory usage, which is a major drawback. Sparse versions of self-attentions exist, [Li et al., 2019; Kitaev et al., 2020; Zhou et al., 2021], reducing the complexity to O(Hlog(H)2 ) and O(H· logH). We strive for linear complexity. In addition, in related attention based works, the same projection matrices WQ, WK and WV are applied to all variables x(i) for 1 ≤ i ≤ N. In contrast, we strive for variable-specific projection matrices.

4 Triformer

We propose Triformer for learning long-term and multiscale dependencies in multivariate time series. An overview of the Triformer is shown in Figure 2. The design choices of Triformer are three-fold. First, we propose an efficient Patch Attention with linear complexity as the basic building Based on the patches, we compute attention scores per patch. If we naively use self-attention in a patch, we still have quadratic complexity (cf. Figure 3a). To reduce the complexity to linear, for each patch p, we introduce a learnable, pseudo timestamp Tp ∈ RN×d (cf. Figure 3b). The pseudo timestamp acts as a data placeholder where all the timestamps from the patch can write useful information which is then passed to the next layers. In Triformer, we choose to use the attention mechanism to update the pseudo timestamp, where the pseudo timestamp works as the Query in self-attentions. The pseudo timestamp queries all the "real" timestamps in the patch, thus only computing a single attention score for each real timestamp, giving rise to linear complexity. We call this Patch Attention (PA). TP+1 TP θ1,b1 θ2,b2 gσ PA PA TP+1 TP θ1,b1 θ2,b2 gσ PA PA

Equation 3 elaborates the computations of PA for pseudo timestamp Tp. Note that Tp = {T(i) p }Ni=1 and each variable has specific pseudo timestamp T(i) p , thus being variablespecific.

The reduced complexity of PA comes with a price that the temporal receptive filed of each timestamp is reduced to the patch size S. In contrast, in the canonical attention, it is H

of the l-th layer. This leads to Lemma 1.

Lemma 1. An L-layer Triformer has a linear time complexity O(H) if patch size Sl ≥ 2 where 1 ≤ l ≤ L.

Proof. Presented in the technical report [Cirstea et al., 2022a].

In a multi-layer Triformer, each layer consists of different numbers of patches and thus having different number of outputs, i.e., pseudo timestamps. Instead of only using the last pseudo timestamp per layer, we aggregate all pseudo timestamps per layer into an aggregated output. More specifically, the aggregate output Ol at the l-th layer is defined as

where θl is a neural network, Tlp denotes the pseudo timestamp for patch p ∈ [1, P] at the l-th layer.

Finally, the aggregate outputs from all layers are connected to the predictor. This brings two benefits than just using the aggregate output of the last layer. First, the aggregate outputs represent features from different temporal scales, contributing to different temporal views. Second, it provides multiple gradient feedback short-paths, thus easing the learning processes. In the ablation study, we empirically justify this design choice (cf. Table 3 in Experiments).

Predictor. We use a fully connected neural network as the predictor due to its high efficiency w.r.t. longer term forecasting.

Variable-specific modeling can be achieved in a naive way by introducing different projection matrices for each variable, which leads to a very large parameter space. Figure 4 (a) shows that the naive approach needs to learn N·d2 parameters for each projection matrix. This may lead to over-fitting, incurs high memory usage, and does not scale well w.r.t. the number of variables N.

To contend with the above challenges, we propose a lightweight method to generate variable specific parameters. In addition, the method is purely data-driven that only relies on the time series themselves and does not require any additional prior knowledge. The overall process is illustrated in Figure 4 (b). First, we introduce a m-dimensional memory vector M(i) ∈ Rm for each variable with i ∈ [1,N]. The memory is randomly initialized and learnable. This makes the method purely data-driven and can learn the most prominent characteristics of each variable.

Next, we propose to factorize a projection matrix, e.g., a Key matrix W(i) K ∈ Rd×d into three matrices-a left variableagnostic matrix LK ∈ Rd×a , a middle variable-specific matrix B(i) ∈ Ra×a , and a right variable-agnostic matrix RK ∈ Ra×d . We intend to make the middle matrix compact, i.e., a ≪ d, thus making the method light-weight.

The left and right matrices are variable-agnostic, thus being shared with all variables. Different variables have their own middle matrices {B(i) }Ni=1 , thus making the middle matrices variable-specific. More specifically, the i-th variable's middle matrix B(i) is generated from its memory M(i) using a generator G(·), e.g., a 1-layer neural network. This step is also essential to reduce the number of parameters to be learned. Learning a full matrix B={B(i) }Ni=1 directly requires N·a2 parameters. In contrast, when using a generator, it requires N·m for the memories, and an additional overhead of m·a2 for the generator.

In addition to the reduced parameter sizes, the factorization also contributes to improved accuracy (cf. Table 3

in Experiments). Since all variables' time series share the variable-agnostic matrices L and R, they act as an implicit regularizer-the amount of combinations that can be produced using them is limited. It also facilitates implicit knowledge sharing among variables.

Equation 6 summarizes the generation of variable-specific Key and Value matrices W(i) K and W(i) V , which replace WK and WV in Equation 3 to make Patch Attention variablespecific. We do not need the Query matrix as PA does not need it and employs the pseudo timestamp instead.

5 Experiments

We report on a comprehensive empirical study on four realworld, commonly used time series long term forecasting data sets to justify our design choices and demonstrate that Triformer outperforms the state-of-the-art methods.

5.1 Experimental Setup

Datasets. We consider four data sets and follow the setup from the-state-of-the-art method for long term forecasting [Zhou et al., 2021].

ETTh1 , ETTm1 . (Electricity Transformer Temperature) 1 : ETTh1 and ETTm1 has observations every 15 minutes. Each observation consists of 6 power load features, making them 6variate time series. To ensure fair comparisons with existing studies, following [Zhou et al., 2021], the train/validation/test data cover 12/4/4 months.

1 https://github.com/zhouhaoyi/ETDataset

ECL. (Electricity Consumption Load) 2 is a 321-variate time series, which records the hourly electricity consumption (Kwh) of 321 clients. Following [Zhou et al., 2021], the train/validation/test data cover 15/3/4 months.

Weather. 3 is a 12-variate time series which record 12 different climate features, e.g., temperature, humidity, etc, from 1,600 U.S. locations. The data is collected hourly. Following [Zhou et al., 2021], the train/validation/test data cover 28/10/10 months.

Forecasting Setups. We use historical H timestamps to forecast the future F timestamps. We vary H and F for different data sets, by following a commonly used long term forecasting setup [Zhou et al., 2021]. We vary F progressively in {24, 48, 168, 336, 720, 960} for the hourly data sets ETTh1 , ECL, and Weather, corresponding to 1, 2, 7, 14, 30, and 40 days ahead; and we vary F in {24, 48, 96, 288, 672} for ETTm1 corresponding to 6, 12, 24, 72 and 168 hours ahead. We also vary the input historical timestamps H. For ETTh1 , Weather and ECL, we vary H from {24, 48, 96, 168, 336, 720}, and from {24, 48, 96, 192, 288, 672} for ETTm1 . Following [Zhou et al., 2021], for each F value, we iterate all possible H values and report the best values in Table 2. A more detailed description of the setup can be found in the technical report [Cirstea et al., 2022a].

Baselines. We select six recent and strong baselines from different categories shown in Table 1, including StemGNN [Cao et al., 2020], AGCRN [Bai et al., 2020], Informer [Zhou et al., 2021], Reformer [Kitaev et al., 2020], LogTrans [Li et al., 2019], and Autoformer [Wu et al., 2021a].

2 https://archive.ics.uci.edu/ml/datasets/ ElectricityLoadDiagrams20112014

3 https://ncei.noaa.gov/data/local-climatological-data

Implementation Details. Due to space limitation the implementation details are listed in the technical report [Cirstea et al., 2022a].

5.2 Experimental Results

Table 2 shows the overall accuracy. The results of Informer, Reformer and LogTrans are collected from [Zhou et al., 2021]. For AGCRN, StemGNN, and Autoformer we have used their original implementations which are publicly available. Triformer outperforms all baselines on all datasets. In most settings, AGCRN achieves better results when compared to the three attention based methods that are variable-agnostic Reformer, LogTrans and Informer. This highlights the needs of variable-specific modeling. Autoformer achieves the second best accuracy which highlights the importance of auto-correlation. Finally our proposed method, Triformer, achieves the best accuracy in all settings.

Ablation Study. We perform an ablation study on the ECL dataset, as shown in Table 3. First, we remove the variablespecific modeling (VSM), where the same projection matrices are shared across all variables. We observe a significant loss of accuracy, which well justifies our design considerations to capture distinct temporal patterns of different variables. A shared parameter space for all variables fails to do so. Second, we replace the light-weight variable specific modeling by the naive way (cf. Figure 4(a)). We observe that the naive method is less accurate and incurs significant more parameters to be learned, which are well aligned with our design considerations. The generator G in Triformer takes very limited additional time to generate matrix B. Third, we do not stack multiple layers patch attentions but use only 1 layer of patch attentions. We observe a significant drop in accuracy, suggesting that the proposed multi-layer, triangular structure, is very effective. Fourth, we remove the multiscale modeling such that only the top most layer's output, rather than the outputs from all layers, is fed into the predictor. The accuracy drops significantly, which justifies our design choices of using multi-scale representations in the predictor. Finally, we remove the recurrent connections that connect two consecutive pseudo timestamps within PAs. The temporal information flow is thus broken, meaning that each patch is computed independently of the others. This results in sub-optimal accuracy. However, we note that the accuracy loss is much smaller than removing other components. One of the benefit of this variant is that this makes the computations of all PAs per layer fully parallelizable thus improving the running time.

Impact of m. To study the impact of m, i.e., the memory size of M(i) (cf. the section "Variable-Specific Modeling" and Figure 5 in the main paper), we ran multiple experiments in which we vary m among {3, 5, 16, 32}. The results are shown in Table 4. We observe insignificant variations in terms of accuracy, which indicates the proposed method is insensitive w.r.t. the memory size.

Impact of a. We study the impact of a, i.e., the size of the middle matrix B(i) (cf. the section "Variable-SpecificModeling" and Figure 4b). We vary a among the following values {3, 5, 16, 32} and the results are shown in Table 5. We observe that when a is too small, e.g., a = 3, the accuracy drops significantly, which is understandable as the variable-specific matrix B(i) has a shape of a × a, which may be too compact to capture sufficient variable-specific temporal patterns. In addition, we observe that a = 5 is sufficient and increasing further a to 32 does not contribute to improved accuracy.

Efficiency. Figure 5 shows the training runtime (seconds/epoch) of Triformer against other four baselines that show the second best accuracy in some data sets, i.e., Informer, AGCRN, StemGNN and Autoformer, as shown in Table 2. When varying H: (i) Triformer is faster than Informer and Autoformer, which is in accordance with the complexities of the two methods and also due to the efficient fully connected neural network based predictor. (ii) StemGNN increases faster as H increases, while Triformer almost keeps steady. (iii) we observe that the recurrent based method AGCRN falls behind when compared with attention based methods, especially when the input time series is long, i.e., large H. When varying F , Triformer is the fastest in all settings. In addition, for inference time, all methods are less than 13.3 ms per inference, which are sufficiently efficient to support real-time forecasting.

Visualization of Learned Memories. We visualize the learned memories M(i) to investigate whether they may capture distinct and the most prominent patterns of different variable's time series. We select 8 time series from the ECL data sets, as shown in Figure 6. We use t-SNE [Maaten and Hinton, 2008] to compress each variable memory M(i) to a 2D point, which is also shown in Figure 6. We observe that the points are spread over the space, indicating that different time series have their own unique patterns. In addition, we observe that when the variables have similar temporal patterns, their learned memories are close by. For example, the time series of variables 6, 7, and 8 are similar, and their corresponding memories are also clustered together, i.e., in the right, top corner.

Additional experiments for very long sequence forecasting, hyper-parameter sensitivity analysis for number of layers and different patches sizes, and empirical evidence that the proposed VSM can generalize to existing methods are presented in the technical report [Cirstea et al., 2022a].

6 Conclusion and Outlook

We propose Triformer, a triangular structure that employs novel patch attentions, which ensures linear complexity. Furthermore, we propose a light-weight method to generate variable-specific projection matrices which are tailored to capture distinct temporal patterns for each variable's time series. Extensive experiments on four data sets show that our proposal outperforms other state-of-the-art methods for long sequence multivariate time series forecasting. In future work, it is of interest to explore different ways of supporting dynamic input lengths and to enhance model training using curriculum learning [Yang et al., 2021; Yang et al., 2022].

Acknowledgements

This work was supported in part by Independent Research Fund Denmark under agreements 8022-00246B and 8048-

00038B, VILLUM FONDEN under agreements 34328 and 40567, and Innovation Fund Denmark centre, DIREC.