一、简介

这篇论文提出了一种新的方法来预测交通流量。论文由厦门大学的福建省智慧城市感知与计算重点实验室（Fujian Key Laboratory of Sensing and Computing for Smart Cities）出品。目前的交通流量预测在短期（5-15分钟）效果还行，但是长期的流量预测效果一直不会太好，主要存在以下几个问题。

1.复杂的时空相关性（Complex Spatio-temporal correlations）

图1 时空复杂度

大家看图1，左侧的红点Traffic sensor就是交通传感器。右侧是其在时间维度上，该拓扑结果的变化。然后有Spatial correlation（空间相关）, Temporal correlation（时间相关）。这个其实很好理解，只要道路1，跟道路2有路口相交，那么道路1的车流存在流入道路2的情况。那么1与2的车流量关系在时间上肯定是相关的。

作者对时间和空间的复杂相关性进行了一个细化：一是动态的空间相关性（Dynamic spatial correlations），这里的动态是指传感器之间的空间相关性是变化的，而非静态的。这点这样理解：每个时段一个路口左拐跟右拐的比例肯定是动态变化的，从而导致空间相关性上的动态变化。图1的Spatial correlation 也就是那些实线的颜色实际上是随着时间变化而变化的。.二是时间相关性的非线性（Non-linear temporal correlations），比如某个路口突然发生车祸，那么这个路口的拥堵情况就会突然上升。（我感觉这里有点牵强，但是从写作上来看，整体机构很美，空间与时间对应，复杂与非线性对应）

2.误差传播灵敏度（Sensitivity to error propagation）

简单来说就是蝴蝶效应，因为整个交通是一个网络，某个节点的错误会被其他节点放大，从而影响最终的预测结果。

为了解决上述问题，论文提出了一种图多注意神经网络（GMAN, Graph Multi-Attention Network）来解决上述问题。这个模型可以被用在很多交通数据的预测，但是这个论文仅用来预测交通流量跟交通速度。
GMAN（图1)是一个Encoder-decoder的架构(H大神的架构还是很有用的)。encoder 用来提取特征，decoder来预测，这个中间有一个transform attention来把encoder的历史特征转化为特征表示。这里的Encoder跟Docoder都是由ST-attention block组成的。然后作者用一个STE模块，把空间与时间的信息结合在一起，然后输入进ST-ATTENTION块，来解决时间空间复杂相关性的问题。具体的在第三章会谈到。

图1

GMAN在两个显示交通流数据库上做了实验，在1小时左右的预测上获得了4%提升。

二、相关工作

Traffic Prediction(交通情况预测):有用LSTM的， KNN，CNN，GCN的。这些方法进行长时间步长的预测都是通过不断预测段时间不长叠加得到的。这种办法其实会导致error propagation很高，一开始的一点小错误很容易在后期被放大。
Deep Learning on Graphs: 图的深度学习。图类型的数据最近很火，比如图卷积网络。一部分人通过用CNN尝试对图形数据分别映射成频谱与空间特征。另外一拨人，专注在搞图的特征化（graph embedding）。（Wu et al. 2019b）把WaveNet 集成到了GCN中，用来处理时空数据。但是这个学习得到的矩阵是静态的。
Attention 机制。Velikovi et al. 2018 这篇用注意力机制来解决空间信息的图分类问题。这篇文章用来解决空间信息的数据预测问题。

其实读到这里，作者的思路就很明朗了，主要创新就是这个动态的STE模块。把时间信息集成进去了。

三、方法。

1. 建模（让我们定义几个概念）

我们定义一个网络道路 $G=(V,E,A)$ 三元组。是由 $N$ 个节点 $V$ ，与边 $E$ ，以及 $A∈R^{N*N}$ 这个 $N*N$ 维矩阵组成。 $A$ 是邻接矩阵。 $A_{v_i,v_j}$ 就表示节点 $v_i$ 和 $v_j$ 的距离。 $t$ 时间点的交通情况，用 $X_{t}∈R^{N\times C}$ 来表示， $C$ 是你关心的交通情况兴趣点，本篇论文只关注交通流量和速度。

那么待解决的问题就可以定义为：给定一个 $N$ 个节点， $P$ 个时间节点 $\chi=(X_{t_1},X_{t_2},...,X_{t_p})∈R^{P*N*C}$ , 我们的目标是预测 $Q$ 个时间节点 $\hat{Y}=(\hat{X}_{t_{P+1}},\hat{X}_{t_{P+2}},...,\hat{X}_{t_{P+Q}})∈R^{Q*N*C}$

这个其实说跟没说一个样，就是用数学的语言表示了一下。也便于后续论文的书写。

2.Graph Multi-Attention Network（GMAN）

这是这篇论文的核心部分。大家还是看图1. encoder和decoder的结构，借鉴了 Hekaiming的 residual connections, 就是那个add&nor。正是因为如此，所以每一层的输出都被调整到了 $D$ 维

我们从输入层讲起，这个输入包括两个部分。 $\chi$ 这个是输入给全连接层（FCs）,网络拓扑G跟时间是输入到STE中。这个就是图2中的（b）Spatio-Temporal Embedding

(1) Spatio-Temporal Embedding

这个时间空间embedding自然分为空间跟时间两个部分，空间部分就是拿 $G$ 去embedding, 时间部分是拿时间向量。空间embedding表示为 $e_{v_i}^S\in R^D$ , 这里 $v_i\in V$ 空间上的关系是静态的，因为道路是不可能一直变的，论文要刻画交通网络动态变化情况，就必须引入时间embedding，把时间序列编码进特征向量。让一天有 $T$ 个时间片段，这样一周七天，跟每天时间片段就可以表示为 $R^7$ 和 $R^T$ , 然后concate在一起，就是一个 $R^{T+7}$ 的向量。（吐槽一下：这么简单的一个做法，用这么装逼的方式说出来，也是醉了）
然后为了要跟左边的Spatial embedding 相加，维度必须一样，所以作者就弄了两个全连接层，把输入的时间向量转化为了 $e_{v_i}^T\in R^D$ 大小的特征值。
好了STE的输出，就是这两个东西的相加： $e_{v_i,t_j}=e_{v_i}^T + e_{v_i}^T$ 。由于训练的时候，其实整个输入的时间矩阵包含了历史的时间节点以及未来（预测时间点）的时间片段。所以总的输出是一个大小为 $E\in R^{(P+Q)\times N\times D}$ 的矩阵。

(2) ST-Attention Block

这部分是作者总体的核心设计，总体思路是让二个ATTENTION机制（空间和时间）动态的去影响输出。ST-attention block包括三个部分空间注意力机制（spatial attention）， 时间注意力机制( temporal attention)，以及一个融合机制（gate fusion）。定义 $l^{th}$ 个ST-block的输入为 $H^{l-1}$ ，然后点 $v_i$ 在时间点 $t_j$ 的隐藏状态表示为 $h^{l-1}_{v_i,t_j}$ 。第 $l^{th}$ ST-block输出的时间与空间注意力机制用 $H^{(l)}_S$ , $H^{(l)}_T$ 表示。定义两个attention模块在点 $v_i$ 与时间点 $t_j$ 的隐藏状态为 $hs^{l-1}_{v_i,t_j}$ 和 $ht^{l-1}_{v_i,t_j}$ 。 $H^{(l)}_S$ , $H^{(l)}_T$ 这两个其实就是gate fusion的输入，gate fusion的输出是 $H^{(l)}$

Spatial Attention, 也就是 $hs^{l-1}_{v_i,t_j}$ ,如下面的公式所示。

这个V是节点 $v$ 的集合， $\alpha_{v_i,v}$ 这里就是attention score，也就是注意力机制的系数，代表了节点 $v$ 对节点 $v_i$ 的重要程度，且满足 $\sum_{v\in V}\alpha _{v_i,v}=1$ (个人觉得这个假设有问题，这个假设有一个前提，就是整个网络里面车流总量是不变的，也就是说车子不会进停车场，才会满足这个假设)直观一点表现就是下图。

图3

接下来作者谈了一下这个 $\alpha _{v_i,v}$ 是怎么得到的。主要是两个公式。

公式 1

|| 是concate, 表示矩阵A与矩阵B的点乘。那么，其实就没什么好说的，就是block的输入跟STE做concate然后再相乘。除个跟Bert某步很像，就是为了防止爆炸。

公式 2

上面这个就是取个指数（保证都是正数），然后求百分比。好了，上面说的是单个attentions机制，这个论文作者就引入了多attentions机制，下面的公式是上面的延伸。

公式 3

Temporal Attention, 这个思路基本上也是concate + 点乘。从下面的公式可以看出来，跟上面的attention基本上一模一样。

Temporal Attention

直观的去看的话，就是如下图Fig.6 。与上面的Fig.3对比的话，大家可以发现，一个是纵向的节点间关系建模，另外一个是横着看的在时间关系的对同一个点进行建模。

image.png

最后的形式是下面的这个公式，把 $K$ 个Attention concate在一起了。

image.png
Gated Fusion 这个个人感觉比较关键，因为这个东西把两个 $H^{(l)}_S$ 和 $H^{(l)}_T$ 融合在了一起：

$H^{(l)}=z\odot H^{(l)}_S+(1-z)\odot H^{(l)}_T$

好了，这个 $z$ 其实就是一个系数。这个思路非常常见。然后我们继续看

$z=\sigma(H^{(l)}_S W_{z,1}+H^{(l)}_TW_{z,2}+b_z)$ .

这里 $W_{z,1}\in R^{D\times D}$ , $W_{z,2}\in R^{D\times D}$ , 然后 $b_z\in R^D$

这里的 $z$ 其实就是一个sigmoid激活函数的输出。这个输入也是一个矩阵W训练得到的。

(3) Transform Attention

四、实验部分。

作者搞了两个数据库，一个是厦门的他自己之前搞出来的，另外一个是PeMS。厦门数据集中包含95个交通传感器从2015年8月1日至2015年12月31日在中国厦门记录的5个月数据; PeMS数据集包含325个交通传感器在2017年1月1日至2017年6月30日在湾区记录的6个月数据。传感器的分布如下图，个人感觉两个额数据库都有意避开了非关键道路。特别是PeMS几乎就是只选了几条主要公路，复杂性根本就不太高。

传感器探头位置

实验的评估部分，论文做的问题实质上是一个regression问题，所以用MAE, RMSE, MAPE来做评估。情况如下表：

image.png

在1小时左右的时间上，比其他一些方法好，做到了state of art。