TESTAM: A Time-Enhanced Spatio-Temporal Attention Model with Mixture of Experts
睾丸：与专家混合的时间增强时空注意模型

Let us define a road network as $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})$, where $\mathcal{V}$ is a set of all roads in road networks with $|\mathcal{V}|=N$, $\mathcal{E}$ is a set of edges representing the connectivity between roads, and $\mathcal{A}\in\mathbb{R}^{N\times N}$ is a matrix representing the topology of $\mathcal{G}$. Given road networks, we formulate our problem as a special version of multivariate time series forecasting that predicts future $T$ graph signals based on $T^{\prime}$ historical input graph signals:
我们将道路网络定义为 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})$ ，其中 $\mathcal{V}$ 是道路网络中所有道路的集合， $|\mathcal{V}|=N$ ， $\mathcal{E}$ 是一组表示道路之间连通性的边， $\mathcal{A}\in\mathbb{R}^{N\times N}$ 是代表 {​​5} 拓扑的矩阵。给定道路网络，我们将问题表述为多元时间序列预测的一个特殊版本，该版本基于 $T^{\prime}$ 历史输入图信号预测未来 $T$ 图信号：

where $X_{\mathcal{G}}^{(i)}\in\mathbb{R}^{N\times C}$, $C$ is the number of input features. We aim to train the mapping function $f(\cdot):\mathbb{R}^{T^{\prime}\times N\times C}\rightarrow\mathbb{R}^{T\times N\times C}$, which predicts the next $T$ steps based on the given $T^{\prime}$ observations. For the sake of simplicity, we omit $\mathcal{G}$ from $X_{\mathcal{G}}$ hereinafter.
其中 $X_{\mathcal{G}}^{(i)}\in\mathbb{R}^{N\times C}$ 、 $C$ 是输入特征的数量。我们的目标是训练映射函数 $f(\cdot):\mathbb{R}^{T^{\prime}\times N\times C}\rightarrow\mathbb{R}^{T\times N\times C}$ ，该函数根据给定的 $T^{\prime}$ 观察结果预测接下来的 $T$ 步。为简单起见，下文中我们将 $X_{\mathcal{G}}$ 中的 $\mathcal{G}$ 省略。

To effectively forecast the traffic signals, we first discuss spatial modeling, which is one of the necessities for traffic data modeling. In traffic forecasting, we can classify spatial modeling methods into four categories: 1) with identity matrix (i.e., multivariate time-series forecasting), 2) with a pre-defined adjacency matrix, 3) with a trainable adjacency matrix, and 4) with attention (i.e., dynamic spatial modeling without prior knowledge). Conventionally, a graph topology $\mathcal{A}$ is constructed via an empirical law, including inverse distance (Li et al., 2018; Yu et al., 2018) and cosine similarity (Geng et al., 2019). However, these empirically built graph structures are not necessarily optimal, thus often resulting in poor spatial modeling quality. To address this challenge, a line of research (Wu et al., 2019; Bai et al., 2020; Jiang et al., 2023) is proposed to capture the hidden spatial information. Specifically, a trainable function $g(\cdot,\theta)$ is used to derive the optimal topological representation $\tilde{\mathcal{A}}$ as:
为了有效地预测交通信号，我们首先讨论空间建模，这是交通数据建模的必要条件之一。 在交通预测中，我们可以将空间建模方法分为四类：1）使用单位矩阵（即多元时间序列预测），2）使用预定义邻接矩阵，3）使用可训练邻接矩阵，以及 4）使用注意力机制（即无需先验知识的动态空间建模）。 传统上，图拓扑 $\mathcal{A}$ 是通过经验定律构建的，包括反距离 (Li et al., 2018 ; Yu et al., 2018 ) 和余弦相似度 (Geng et al., 2019 ) 。然而，这些经验构建的图结构不一定是最优的，因此常常导致空间建模质量不佳。为了应对这一挑战，提出了一系列研究 (Wu et al., 2019 ; Bai et al., 2020 ; Jiang et al., 2023 ) 来捕获隐藏的空间信息。具体而言，使用可训练函数 $g(\cdot,\theta)$ 来推导出最优拓扑表示 $\tilde{\mathcal{A}}$ ，如下所示：

where $g(X^{(t)},\theta)\in\mathbb{R}^{N\times e}$, and $e$ is the embedding size. Spatial modeling based on Eq. 1 can be classified into two subcategories according to whether $g(\cdot,\theta)$ depends on $X^{(t)}$. Wu et al. (2019) define $g(\cdot,\theta)=E\in\mathbb{R}^{N\times e}$, which is time-independent and less noise-sensitive but less in-situ modeling. Cao et al. (2020); Zhang et al. (2020) propose time-varying graph structure modeling with $g(H^{(t)},\theta)=H^{(t)}W$, where $W\in\mathbb{R}^{d\times e}$, projecting hidden states to another embedding space. Ideally, this method models dynamic changes in graph topology, but it is noise-sensitive.
其中 $g(X^{(t)},\theta)\in\mathbb{R}^{N\times e}$ ， $e$ 是嵌入大小。基于公式 1 的空间建模可以根据 $g(\cdot,\theta)$ 是否依赖于 $X^{(t)}$ 分为两个子类别。 Wu 等人（ 2019 ） 定义 $g(\cdot,\theta)=E\in\mathbb{R}^{N\times e}$ ，它与时间无关、对噪声不太敏感，但现场建模能力较弱。 Cao 等人（ 2020 年 ）；Zhang 等人（ 2020 年 ） 提出了一种时变图结构建模方法，其中 $g(H^{(t)},\theta)=H^{(t)}W$ （其中 $W\in\mathbb{R}^{d\times e}$ ）将隐藏状态投影到另一个嵌入空间。理想情况下，该方法可以模拟图拓扑的动态变化，但它对噪声敏感。

To reduce noise-sensitivity and obtain a time-varying graph structure, Zheng et al. (2020) adopt a spatial attention mechanism for traffic forecasting. Given input $H_{i}$ of node $i$ and its spatial neighbor $\mathcal{N}_{i}$, they compute spatial attention using multi-head attention as follows:
为了降低噪声敏感性并获得随时间变化的图结构， Zheng 等人（ 2020 年）采用了空间注意力机制进行交通预测。给定节点 $i$ 及其空间邻居 $\mathcal{N}_{i}$ 的输入 $H_{i}$ ，他们使用多头注意力计算空间注意力，如下所示：

where $W^{O}$ is a projection layer, $d_{k}$ is a dimension of key vector, and $f^{(k)}_{q}(\cdot),f^{(k)}_{k}(\cdot),$ and $f^{(k)}_{v}(\cdot)$ are query, key, and value projections of the $k$-th head, respectively. Although effective, these attention-based approaches still suffer from irregular spatial modeling, such as less accurate self-attention (i.e., from node $i$ to $i$) (Park et al., 2020) and uniformly distributed uninformative attention, regardless of its spatial relationships (Jin et al., 2023).
其中 $W^{O}$ 是投影层， $d_{k}$ 是键向量的维度， $f^{(k)}_{q}(\cdot),f^{(k)}_{k}(\cdot),$ 和 $f^{(k)}_{v}(\cdot)$ 分别是第 $k$ 个头的查询、键和值投影。这些基于注意力机制的方法虽然有效，但仍然存在空间建模不规则的问题，例如自注意力机制准确性较低（即从节点 $i$ 到 $i$ ） （Park 等人， 2020 年 ） 以及均匀分布的无信息量注意力机制，无论其空间关系如何 （Jin 等人， 2023 年 ） 。

Since temporal features (e.g., time of day) work as a global position with a specific periodicity, we omit position embedding in the original transformer architecture. Furthermore, instead of normalized temporal features, we utilize Time2Vec embedding (Kazemi et al., 2019) for periodicity and linearity modeling. Specifically, for the temporal feature $\tau\in\mathbb{N}$, we represent $\tau$ with $h$-dimensional embedding vector $v(\tau)$ and the learnable parameters $w_{i},\phi_{i}$ for each embedding dimension $i$ as below:
由于时间特征（例如，一天中的时间）作为具有特定周期性的全局位置，我们省略了原始 Transformer 架构中的位置嵌入。 此外，我们利用 Time2Vec 嵌入 （Kazemi 等人， 2019 ） 进行周期性和线性建模，而非归一化的时间特征。具体来说，对于时间特征 $\tau\in\mathbb{N}$ ，我们用 $h$ 维嵌入向量 $v(\tau)$ 表示 $\tau$ ，并为每个嵌入维度 $i$ 指定可学习的参数 $w_{i},\phi_{i}$ ，如下所示：

where $\mathcal{F}$ is a periodic activation function. Using Time2Vec embedding, we enable the model to utilize the temporal information of labels. Here, temporal information embedding of an input sequence is concatenated with other input features and then projected onto the hidden size $h$.
其中 $\mathcal{F}$ 是周期性激活函数。使用 Time2Vec 嵌入，我们使模型能够利用标签的时间信息。在这里，输入序列的时间信息嵌入与其他输入特征连接，然后投影到隐藏大小 $h$ 上。

As temporal attention in TESTAM is the same as that of transformers, we describe the benefits of temporal attention. Recent studies (Li et al., 2018; Bai et al., 2020) have shown that attention is an appealing solution for temporal modeling because, unlike recurrent unit-based or convolution-based temporal modeling, it can be used to directly attend to features across time steps with no restrictions. Temporal attention allows parallel computation and is beneficial for long-term sequence modeling. Moreover, it has less inductive bias in terms of locality and sequentiality. Although strong inductive bias can help the training, less inductive bias enables better generalization. Furthermore, for the traffic forecasting problem, causality among roads is an unavoidable factor (Jin et al., 2023) that cannot be easily modeled in the presence of strong inductive bias, such as sequentiality or locality.
由于 TESTAM 中的时间注意力机制与 Transformer 中的时间注意力机制相同，我们描述了时间注意力机制的优势。最近的研究 （Li et al., 2018 ; Bai et al., 2020 ） 表明，注意力机制是时间建模的一个有吸引力的解决方案，因为与基于循环单元或基于卷积的时间建模不同，它可以用来直接关注跨时间步长的特征而不受任何限制。时间注意力机制允许并行计算，有利于长期序列建模。此外，它在局部性和顺序性方面的归纳偏差较小。虽然强归纳偏差有助于训练，但较小的归纳偏差可以实现更好的泛化。此外，对于交通预测问题，道路之间的因果关系是一个不可避免的因素 （Jin et al., 2023 ）， 在存在强归纳偏差（如顺序性或局部性）的情况下，很难对其进行建模。

In this work, we leverage three spatial modeling layers for each expert, as shown in the middle of Fig. 1: spatial modeling with an identity matrix (i.e., no spatial modeling), spatial modeling with a learnable adjacency matrix (Eq. 1), and spatial modeling with attention (Eq. 2 and Eq. 3). We calculate spatial attention using Eqs. 2 and 3. Specifically, we compute attention with $\forall_{i\in\mathcal{V}},\mathcal{N}_{i}=\mathcal{V}$, which means attention with no spatial restrictions. This setting enables similarity-based attention, resulting in better generalization.
在本研究中，我们为每位专家构建了三个空间建模层，如图 1 中间所示：使用单位矩阵的空间建模（即无空间建模）、使用可学习邻接矩阵的空间建模（公式 1 ）以及使用注意力机制的空间建模（公式 2 和公式 3 ）。我们使用公式 2 和公式 3 计算空间注意力机制。具体来说，我们使用 $\forall_{i\in\mathcal{V}},\mathcal{N}_{i}=\mathcal{V}$ 计算注意力机制，这意味着注意力机制不受空间限制。此设置支持基于相似性的注意力机制，从而实现更好的泛化效果。

Inspired by the success of memory-augmented graph structure learning (Jiang et al., 2023; Lee et al., 2022), we propose a modified meta-graph learner that learns prototypes from both spatial graph modeling and gating networks. Our meta-graph learner consists of two individual neural networks with a meta-node bank $\mathbf{M}\in\mathbb{R}^{m\times e}$, where $m$ and $e$ denote total memory items and a dimension of each memory, respectively, a hyper-network (Ha et al., 2017) for generating node embedding conditioned on $\mathbf{M}$, and gating networks to calculate the similarities between experts’ hidden states and queried memory items. In this section, we mainly focus on the hyper-network. We construct a graph structure with a meta-node bank $\mathbf{M}$ and a projection $W_{E}\in\mathbb{R}^{e\times d}$ as follows:
受到记忆增强图结构学习成功的启发 (Jiang et al., 2023 ; Lee et al., 2022 ) ，我们提出了一种改进的元图学习器，它可以从空间图建模和门控网络中学习原型。我们的元图学习器由两个独立的神经网络组成，一个元节点库 $\mathbf{M}\in\mathbb{R}^{m\times e}$ ，其中 $m$ 和 $e$ 分别表示总记忆项和每个记忆的维度，一个超网络 (Ha et al., 2017 ) 用于生成以 $\mathbf{M}$ 为条件的节点嵌入，以及门控网络用于计算专家隐藏状态和查询记忆项之间的相似性。在本节中，我们主要关注超网络。我们构建一个具有元节点库 $\mathbf{M}$ 和投影 $W_{E}\in\mathbb{R}^{e\times d}$ 的图结构，如下所示：

By constructing a memory-augmented graph, the model achieves better context-aware spatial modeling than that achieved using other learnable static graphs (e.g., graph modeling with $E\in\mathbb{R}^{N\times d}$). Detailed explanations for end-to-end training and meta-node bank queries are provided in Sec. 3.3.
通过构建记忆增强图，该模型实现了比使用其他可学习静态图（例如，使用 $E\in\mathbb{R}^{N\times d}$ 的图建模）更好的情境感知空间建模。端到端训练和元节点库查询的详细说明请参见第 3.3 节。

To eliminate the error propagation effects caused by auto-regressive characteristics, we propose a time-enhanced attention layer that helps the model transfer its domain from historical $T^{\prime}$ time steps (i.e., source domain) to next $T$ time steps (i.e., target domain). Let $\mathbf{\tau}^{(t)}_{label}=[\tau^{(t+1)},\dots,\tau^{(t+T)}]$ be a temporal feature vector of the label. We calculate the attention score from the source time step $i$ to the target time step $j$ as:
为了消除自回归特性引起的误差传播效应，我们提出了一个时间增强注意层，帮助模型将其域从历史 $T^{\prime}$ 时间步（即源域）转移到下一个 $T$ 时间步（即目标域）。令 $\mathbf{\tau}^{(t)}_{label}=[\tau^{(t+1)},\dots,\tau^{(t+T)}]$ 为标签的时间特征向量。我们计算从源时间步 $i$ 到目标时间步 $j$ 的注意力得分，如下所示：

where $d_{k}=d/K$, $K$ is the number of heads, and $W_{q}^{(k)},W_{k}^{(k)}$ are linear transformation matrices. We can calculate the attention output using the same process as in Eq. 2, except that time-enhanced attention attends to the time steps of each node, whereas Eq. 2 attends to the important nodes at each time step.
其中 $d_{k}=d/K$ 、 $K$ 是头的数量， $W_{q}^{(k)},W_{k}^{(k)}$ 是线性变换矩阵。我们可以使用与公式 2 相同的过程来计算注意力输出，不同之处在于时间增强注意力关注的是每个节点的时间步长，而公式 2 关注的是每个时间步长上的重要节点。

To enable fine-grained routing that fits the regression problem, we adopt two classification losses: a classification loss to avoid the worst routing and another loss function to find the best routing. Inspired by SMoEs, we define the worst routing avoidance loss as the cross entropy loss with pseudo label $l_{e}$ as shown below:
为了实现适合回归问题的细粒度路由，我们采用了两种分类损失：一种分类损失用于避免最差路由，另一种损失函数用于找到最佳路由。受 SMoE 的启发，我们将最差路由避免损失定义为具有伪标签 $l_{e}$ 的交叉熵损失，如下所示：

where $\hat{y}$ is the output of the selected expert, and $q$ is an error quantile. If an expert is incorrectly selected, its label becomes zero and the unselected experts have the pseudo label $1/(E-1)$, which means that there are equal chances of choosing unselected experts.
其中 $\hat{y}$ 是所选专家的输出， $q$ 是错误分位数。如果错误地选择了专家，则其标签变为零，而未选择的专家则具有伪标签 $1/(E-1)$ ，这意味着选择未选择的专家的机会均等。

We also propose the best-route selection loss for more precise routing. However, as traffic data are noisy and contain many nonstationary characteristics, the best-route selection is not an easy task. Therefore, instead of choosing the best routing for every time step and every node, we calculate node-wise routing. Our best-route selection loss is similar to that in Eq. 6, except that it calculates node-wise pseudo labels and the routing probability, and the condition for pseudo labels is changed from “$L(y,\hat{y})$ is greater/smaller than $q$-th quantile” to “$L(y,\hat{y})$ is greater/smaller than $(1-q)$-th quantile.” Detailed explanations are provided in Appendix A.
我们还提出了最佳路线选择损失，以实现更精确的路线选择。 然而，由于交通数据嘈杂且包含许多非平稳特性，最佳路线选择并非易事。 因此，我们不是为每个时间步和每个节点选择最佳路由，而是计算节点路由。 我们的最佳路线选择损失与公式 6 中的类似，不同之处在于它计算了节点伪标签和路由概率，并且伪标签的条件从“ $L(y,\hat{y})$ 大于/小于 $q$ 分位数”更改为“ $L(y,\hat{y})$ 大于/小于 $(1-q)$ 分位数”。详细解释见附录 A。

It uses only the output of the attention experts without ensembles or any other gating mechanism. Memory items are not trained because there are no gradient flows for the adaptive expert or gating networks. This setting results in an architecture similar to that of GMAN.
它仅使用没有集合或任何其他门控机制的注意专家的输出。由于没有适用于自适应专家或门控网络的梯度流，因此没有训练内存项。此设置导致与Gman类似的架构。

Instead of using MoEs, the final output is calculated with the weighted summation of the gating networks and each expert’s output. This setting allows the use of all spatial modeling methods but no in-situ modeling.
最终输出不是使用门控网络和每个专家的输出来计算的，而不是使用MOE。此设置允许使用所有空间建模方法，但没有原位建模。

It excludes the loss for guiding best route selection. The exclusion of this relatively coarse-grained loss function is based on the fact that coarse-grained routing tends not to change its decisions after initialization (Dryden & Hoefler, 2022).
它不包括指导最佳路线选择的损失。这种相对粗粒的损失函数的排除是基于以下事实：粗粒式路由倾向于在初始化后不改变其决策（Dryden＆Hoefler， 2022 ） 。

It does not exclude any components. Instead, it replaces identity expert with a GCN-based adaptive expert, reducing spatial modeling diversity. The purpose of this setting is to test the hypothesis that in-situ modeling with diverse graph structures is helpful for traffic forecasting.
它不排除任何组件。取而代之的是，它用基于GCN的自适应专家取代了身份专家，从而降低了空间建模的多样性。这种设置的目的是检验以下假设：具有不同图形结构的原位建模有助于流量预测。

It replaces temporal information embedding (TIM) with simple embedding vectors without periodic activation functions.
它用无定期激活功能的简单嵌入向量替代了嵌入时间信息（TIM）。

It replaces time-enhanced attention with basic temporal attention as we described in Sec. 3.2.
正如我们在SEC中所述，它取代了时间增强的注意力。 3.2 。

The experimental results shown in Table 2 connote that our hypotheses are supported and that TESTAM is a complete and indivisible set. The results of “w/o gating” and “ensemble” suggest that in-situ modeling greatly improves the traffic forecasting quality. The “w/o gating” results indicate that the performance improvement is not due to our model but due to in-situ modeling itself since this setting lead to performance comparable to that of GMAN (Zheng et al., 2020). “worst-route avoidance only” results indicate that our hypothesis that both of our routing classification losses are crucial for proper routing is valid. Finally, the results of “replaced,” which indicate significantly worse performance even than “worst route avoidance only,” confirm the hypothesis that diverse graph structures is helpful for in-situ modeling. Additional qualitative results with examples are provided in Appendix C.
表 2 中的实验结果表明我们的假设得到了支持，并且 TESTAM 是一个完整且不可分割的集合。“w/o gating”和“ensemble”的结果表明现场建模极大地提高了流量预测质量。“w/o gating”的结果表明性能的提升不是由于我们的模型，而是由于现场建模本身，因为这种设置导致的性能与 GMAN (Zheng et al., 2020 ) 相当。“仅避免最差路线”的结果表明我们的两种路线分类损失对于正确路线都至关重要的假设是正确的。最后，“replaced”的结果甚至比“仅避免最差路线”的结果性能差得多，证实了多样化的图结构有助于现场建模的假设。附录 C 中提供了其他定性结果和示例。