创新点（Graph Multi-Attention）

关注时空因素，并提出了一个图多注意力网络（GMAN）来预测道路网络图上不同位置的前一时间步长的交通状况。

GMAN：

​ GMAN采用编码器和解码器结构，编码器和解码器都由多个时空注意力块组成。

​ 编码器编码特征输入，解码器预测输出序列。

​ 编码器和解码器之间，有一个transform attention layer 转换编码器特征去生成解码器未来时间步长的序列表示。这个transform attention机制对历史和未来的时间步长的直接关系进行建模，这有助于缓解误差传播问题。

引言

​ 轨迹预测旨在基于历史信息去预测未来的交通条件。

​ 附近地区的交通条件会相互之间产生影响，CNN被广泛使用与捕捉空间上的相关性。

​ 同时交通状况也与历史信息相关，RNN用来对时间相关性进行建模。

​ 最近的研究将交通预测公式化为一个图建模问题，因为交通条件限制在道路网络图上。使用图卷积网络可在短期的预测中取得较好的结果，但长期交通网络的研究进展依旧不尽人意。

​ 长期预测有如下挑战：

1. 复杂的时空相关性
   • 动态的空间相关性：道路网络中传感器之间交通状况的相关性随时间显著变化，如何动态选择相关传感器的数据来预测目标传感器的长期交通状况是一个具有挑战性的问题
   • 非线性的时间相关性：传感器处的交通状况可能会急剧波动，影响不同时间步长之间的相关性。如何对非线性时间相关性进行自适应建模仍然是一个挑战。
2. 对误差传播的敏感性：从长远来看，当对未来进行进一步预测时，每个时间步长中的小错误可能会放大（一个错误在节点之间传播会越累越大）。这种错误传播使得对遥远未来的预测极具挑战性

模型：

1. GMAN采用编码器译码器架构
2. 编码器和译码器由ST-Attention blocks堆叠而成，每个 ST-Attention 块由用于建模动态空间相关性的空间注意机制、用于建模非线性时间相关性的时间注意机制以及用于自适应融合空间和时间表示的门控融合机制形成。
3. 编码器和译码器中间的 转换注意力机制 对历史时间的步长和未来时间的步长之间的直接关系进行建模，缓解对错误传播的影响。

贡献：

1. 提出了空间和时间注意机制，分别对动态空间和非线性时间相关性进行建模。此外，我们设计了一种门控融合，以自适应地融合由空间和时间注意力机制提取的信息。
2. 提出了一种转换注意力机制，将历史交通特征转换为未来的表示。这种注意力机制对历史和未来时间步长之间的直接关系进行建模，以缓解错误传播的问题。
3. 在两个真实世界的交通数据集上评估了我们的图多注意力网络（GMAN），并在1小时前的预测中观察到与最先进的基线方法相比有4%的改进和卓越的容错能力。

相关工作

1. 在交通预测任务上，深度学习方法在捕获交通环境中的时间关系上比传统的时间序列方法、机器学习方法和K-近邻方法有更好的表现。
2. 为了建模空间相关性，使用CNN来得到欧几里得空间中的依赖关系
3. 最新的研究中将交通预测归结为图问题，并且使用图卷积网络来对道路网络中的非欧几里得关系进行建模。但是基于图的模型，精确度容易受到不同预测步骤之间误差传播的影响。

预备芝士

​ 将道路网络看作一个加权有向图 G =(V, E, A)， V 是点集（N个点）；E 是边集，表示点与点的连通性；A 是权重邻接矩阵，$A_{V_i,V_j}$ 表示 V_i 到 V_j 之间的权重。

时间步长为 t 时的交通条件被表示为一个图信号 $X_t\in R^{N\times C}$ ，此处 C 是感兴趣的交通条件的状态数量（如交通量、交通速度等）。

​ 研究问题：给定 P 个时间步长的 N 个历史观察值 $X=(X_{t1},X_{t2},\cdots ,X_{tp})\in R^{P\times N\times C}$ ，$X_{t_i}$ 就是 i 时间 N个传感器每个传感器C个的交通图信号。

​ 目标是预测下面 Q 个时间步长的所有顶点的值，表示为 $\hat{Y}=({\hat{X}}_{t_{P+1}},{\hat{X}}_{t_{P+2}},\cdots ,{\hat{X}}_{t_{P+Q}})$

图多注意力网络

​ 编码器和译码器都包含了 L 个带有残差连接的 STAtt Block，每个ST注意块由具有门控融合的空间和时间注意机制组成。在编码器和解码器之间，向网络添加了一个转换注意力层，以将编码的流量特征转换到解码器。还通过时空嵌入（STE）将图结构和时间信息整合到多注意力机制中，此外，为了便于残差连接，所有层都产生D维的输出。下面将详细介绍这些模块。

---

STE（Spatio-Temporal Embedding）

空间嵌入：

1. 基础道路结构很重要，所以提出了空间嵌入，将顶点信息编码为带有能够保存图结构信息的向量。用 node2vec来学习顶点表示，为了与整个模型共同训练与学习的向量，将这些向量输入到两个FCN中，就可得到空间嵌入表示 $e_{v_i}^S\in R^D$。
2. 空间嵌入仅仅是交通传感器在道路网络中相关关系的静态表示，并非表示动态关系。

时间嵌入：

1. 因此，又提出了时间嵌入，将每个时间步编码为向量。
2. 将每个周的时间和每天的具体时间编码为向量 R⁷ 和 R^T ，用one-hot 编码表示。拼接他们就可用 R^7+T 表示一周里的具体时间。
3. 用两层FCN将时间特征转换为向量，在模型中嵌入了 P 个历史时间步长，Q 个未来时间步长的时间特征，表示为 $e_{t_j}^T\in R^D$ 此处 $t_j=t_j，\cdots ，t_P，\cdots ，t_{P+Q}$

融合：

​ 为得到变化时间的顶点表示，融合时间嵌入和空间嵌入为时空嵌入（STE），如Figure2-b。时间步长 $t_j$ 出的顶点$v_i$，STE 定义为 $e_{v_i,t_j}=e_{v_i}^S+e_{t_j}^T$ ，所以STE表示 N 个顶点 P+Q个时间步长的状态为 $E\in R^{(P+Q)\times N\times D}$ ，此时STE就包含了图结构和时间的信息，用于时空注意力转换。

总结：

1. 将时间信息进行编码定位，然后输入到两个全连接层，得到输出为 D 维向量。
2. 将道路信息喂入两层FNC，得到 D 维输出向量。
3. 将两个 D 维向量 直接相加 而非concatenate
4. 所以 Spatial Embedding 和 Temporal Embedding 都是两层 FCN

---

ST-Attention Block

包括了一个空间注意力、一个时间注意力和一个门控融合单元。

1. 表示第 l 个STAtt Block 的输入为 $H^{l-1}$ ，即第 l-1 个STAtt Block 的输出。其中时间步 $t_j$ 时，顶点 $v_i$ 的隐藏状态为 $h_{v_i,t_j}^{l-1}$
2. 第 l 个STAtt块中的时间和空间注意力输出表示为 $H_T^l,H_S^l$
3. 顶点 $v_i$ 在时间步 $t_j$ 的隐藏状态表示为 $h_{S_{v_i,t_j}}^{(l)}$ ，$h_{T_{v_i,t_j}}^{(l)}$
4. 将空间注意力机制和时间注意力机制的输出通过门控融合单元进行融合得到该 STAtt Block 的输出
5. 将非线性变换表示为 $f(x)=ReLU(xW+b)$

Spatial Attention 空间注意力机制

道路状态随着时间高度动态改变，为了获取传感器之间的相关关系，使用空间注意力机制。

关键思想是在不同的时间步长为不同的顶点（例如传感器）动态分配不同的权重

顶点 $v_i$ 在时间步 $t_j$ 的空间隐藏状态计算为上一层所有顶点隐藏状态的加权和（α 是表示所有顶点 V 对 v_i 的重要性注意力分数，且所有的注意力分数和为1）：
$$h_{S_{v_i,t_j}}^{(l)}=\sum _{v\in V}{\alpha }_{v_i,v}\cdot h_{v,t_j}^{(l-1)}$$
此外，某一时刻的交通状况也受相关传感器的影响。用如下公式计算某一点与整个网络图的相关性：
$$s_{v_i,v}=\frac{⟨h_{v_i,t_j}^{(l-1)}\Vert e_{v_i,t_j},h_{v,t_j}^{l-1}\Vert e_{v,t_j}⟩}{\sqrt{2D}}$$
然后利用计算来的相关性通过softmax得到注意力分数 attention score：
$${\alpha }_{v_i,v}=\frac{\exp (s_{v_i},v)}{{\sum }_{v_r\in V}\exp (s_{v_i,v_r})}$$
为了使得它更稳定，采用了多头的空间注意力机制，k是头的个数，将k个平行的不同学习策略的注意力机制连接起来：

$f$ 是不同的非线性操作，输出维度 $d=D/K$。

分组操作降低了计算量，将所有的顶点分为 M 组，用 567 计算组内的参数并在组内用最大池化的方法生成一个唯一表示。

Temporal Attention时间注意力

时间注意力机制和空间注意力机制在计算过程中大同小异，一个是固定传感器，一个是固定时间。时间注意力机制没有对节点进行分组，$N_{t_j}$表示 $t_j$ 之前的一组时间步长，因为在训练过程中不能看见后面时刻的交通状况。

Gate Fusion 门控单元

当前交通状况与先前的值和其他道路的值都相关。门控单元用于融合时间和空间的表示

$l^{th}$ 个STAtt Block 时间和空间注意力机制的输出表示为 $H_T^{(l)}和H_S^{(l)}$ ，他们在编码器中的 shape 为 $R^{P\times N\times D}$ ，解码器中的 shape为 $R^{Q\times N\times D}$

$H_T^{(l)}和H_S^{(l)}$ 融合得到 $H^{(l)}$ 方式如下：
$$\begin{gathered} z=\sigma (H_S^{(l)}{W}_{z,1}+H_T^{(l)}{W}_{z,2}+b_z) \\ {H}^{(l)}=z\odot H_S^{(l)}+(1-z)\odot H_T^{(l)} \end{gathered}$$

1. $W_{z,1}和W_{z,2}\in R^{D\times D}$，$b_z\in R^D$，均为可学习参数。
2. $⨀$ 为元素点乘，$\large \sigma(\cdot) $ 表示 sigmoid 激活函数。
3. $z$ 是门。

门控机制自适应地控制每个顶点和时间步长的空间和时间依赖性的流动

---

Transform Attention注意力转换

用于缓解误差在节点图中传播的影响，他对每个未来时间步长和每个历史时间步长之间的直接关系进行建模，转换被编码的交通特征以生成作为解码器输入的未来表示。

对于顶点$v_i$，预测时间步长 $t_j(t_j=t_{P+1},\dots ,t_{P+Q})$ 和历史时间步长 $t(t=t_1,\dots ,t_P)$之间 的相关性是通过时空嵌入来测量的：
λtj,t(k)=⟨ftr,1(k)(evi,tj),ftr,2(k)(evi,t)d相关性γtj,t(k)=exp⁡(λtj,t(k))∑tr=t1tPexp⁡(λtj,tr(k))注意力分数hvi,tj(l)=∥k=1K{∑t=t1tpγtj,t(k)⋅ftr,3(k)(h(vi,t)(l−1))} \large \lambda^{(k)}_{t_j,t}=\frac{\langle f^{(k)}_{tr,1}(e_{v_i,t_j}),f^{(k)}_{tr,2}(e_{v_i,t})}{\sqrt{d}} \quad 相关性\\ \large \gamma^{(k)}_{t_j,t}=\frac{\exp(\lambda^{(k)}_{t_j,t})}{\sum^{t_P}_{t_r=t_1}\exp(\lambda^{(k)}_{t_j,t_r})} \quad 注意力分数\\ \large h^{(l)}_{v_i,t_j} = \|^K_{k=1}\{\sum^{t_p}_{t=t_1} \gamma^{(k)}_{t_j,t} \cdot f^{(k)}_{tr,3}(h^{(l-1)}_{(v_i,t)}) \} λtj​,t(k)​=d ​⟨ftr,1(k)​(evi​,tj​​),ftr,2(k)​(evi​,t​)​相关性γtj​,t(k)​=∑tr​=t1​tP​​exp(λtj​,tr​(k)​)exp(λtj​,t(k)​)​注意力分数hvi​,tj​(l)​=∥k=1K​{t=t1​∑tp​​γtj​,t(k)​⋅ftr,3(k)​(h(vi​,t)(l−1)​)}
利用注意力得分${\gamma }_{t_j,t}^{(k)}$，通过在所有历史 P 时间步长上自适应地选择相关特征，将编码的交通特征转换到解码器。

上述方程可以在所有顶点和时间步长上并行计算，共享可学习参数。

---

编码器译码器架构

1. GMAN 是encoder - decoder 架构
2. 在输入到 encoder 之前，历史观测数据 $X\in R^{P\times N\times C}$ 通过 FCNs 转换为 $H^{(0)}\in R^{P\times N\times D}$
3. $H^{(0)}$ 被喂入带有 L 个 ST-Attetion Block 的 encoder ，输出 $H^{(L)}\in R^{P\times N\times D}$
4. 然后一个注意力转换层 transform attention layer 将被编码的特征 $H^{(L)}$ 转换以生成未来序列表示 $H^{(L+1)}\in R^{Q\times N\times D}$
5. 译码器将 L 个 ST-Attention Block堆叠在 $H^{(L+1)}$ 上，生成输出 $H^{(2L+1)}\in R^{Q\times N\times D}$
6. 最后 FCNs 生成 Q 个时间步长的预测 $\hat{Y}\in R^{Q\times N\times C}$

GMAN可以通过反向传播进行端到端的训练，使得预测值和真实值的平均误差 (MEA) 最小化
$$\zeta (\Theta )=\frac{1}{Q}\sum _{t=t_{P+1}}^{t_{P+Q}}|Y_t-{\hat{Y}}_t|\Theta 表示所有可学习的参数$$