【论文笔记】用于数据驱动交通预测的扩散卷积循环神经网络（DCRNN）

2019 年 10 月 28 日 专知

导读

本文发表于ICLR 2018，用于时空图预测的扩散卷积循环神经网络（DCRNN），DCRNN通过在图上使用双向随机游走（bidirectional random walks）捕获空间依赖性，使用具有预采样（scheduled sampling）的编码解码（encoder and decoder）结构捕获时间依赖性。

动机

交通预测的目标是在历史车速以及路网的基础上预测未来传感器检测到的车辆速度。但是交通预测具有复杂的时空依赖性以及在长期预测上的固有困难；同时，下游的交通对未来的交通速度的影响更大，因此交通预测的空间结构是非欧几里得的和有向的。目前，可用于交通预测的方法具有如下两个缺点：

1）传统的交通预测方法中简单的时间序列模型经常依赖稳态假设（stationarity assumption,），这个假设在交通数据中不成立。

2）近期基于图卷积的方法仅仅考虑无向图。

基于交通预测的复杂性以及以上方法的不足，作者提出了扩散卷积循环神经网络（DCRNN），将交通流的动态性建模为一个扩散过程。

核心思想

扩散卷积循环神经网络（DCRNN），将交通流的动态性建模为一个扩散过程，并且使用扩散卷积操作去捕获空间依赖性，使用具有预采样（scheduled sampling）的编码解码（encoder and decoder）结构捕获时间依赖性。扩散卷积递归神经网络（DCRNN）的框架如下图所示：

问题建模

交通预测的目标是从道路网络上的n个相关传感器中预测未来的交通速度，即致力于学习一个函数h(.)它将T‘时段内的历史图信号映射到未来的T时段的图信号，给出一个图g：

其中：

G=（V,E,W）表示路网中的传感器网络
V是节点丨V丨=N的集合
E是边的集合
W∈R^(N*N)是表示节点邻近性（proximity）的加权邻接矩阵。
X∈R^(N×p)是图信号，其中P是每一个节点的特征数量。
X^（t）表示时间t时刻观察到的图信号

扩散卷积

文中在对空间依赖性建模时引入了扩散卷积，并且构建了扩散卷积层，与普通的GCN不同的是，扩散卷积考虑了正向传播与反向传播，更好的对交通网络这种有向图建模。

扩散过程的特征是在图g上具有重新启动概率（restart probability）α∈[0.1]以及状态转移矩阵D^(-1)W的随机游动。在许多时间步之后，这样的马尔可夫过程可以收敛到一个静态分布P∈R^(N×N)，其第i行Pi∈R^(N)表示从节点vi∈V扩散的可能性，也就是节点vi的邻近性（proximity）。

定理：扩散卷积的静态分布可以被表示为图上无数随机游走的加权组合，并以封闭形式计算：

在图信号X∈R^(N×P)和卷积核f_Θ上的扩散卷积操作结果被表示为：

其中：

θ∈R^(K×2) 表示卷积核参数，
D^(−1)_O W表示扩散过程的转移矩阵
D^(−1)__I W 表示反向扩散的转移矩阵。

根据定义的卷积操作，可以构建一个扩散卷积层，将 P 维特征映射到 Q 维输出上。扩散卷积层为：

其中;

X∈R^(N×P) 是输入
H∈R^(N×Q) 是输出
{f_Θ__{q,p,:,:} 是卷积核
a是激活函数。

Θ_{q,p,:,:}∈R^(K×2) 是第 p 个输入和 q 个输出的参数

时间动态模型

文中利用 RNN 对时间依赖建模，将 GRU （图2）中的矩阵乘法换成了扩散卷积，得到了扩散卷积门控循环单元（Diffusion Convolutional Gated Recurrent Unit(DCGRU))

其中：

X^(t),H^(t) 表示时间 t 的输入和输出，
r(t),u(t) 表示时间 t 的重置门（reset gate）和更新门（update gate）的输出。
⋆G 表示混合卷积，
Θ_r,Θ_u,Θ_C表示对应的滤波器的参数。

图2 GRU结构图（图片来源于网络）

在多步预测中，文中使用 Sequence to Sequence 架构。编码解码器都是 DCGRU。训练时，把历史的时间序列放到编码器，使用最终状态初始化解码器。解码器生成预测结果。测试时，ground truth 替换成模型本身生成的预测结果。

训练和测试输入的分布的差异会导致性能的下降。为了减轻这个问题的影响，文中使用了 scheduled sampling ，在训练的第 i轮时，模型的输入要么是概率为 ϵi 的 ground truth，要么是概率为 1−ϵi的预测结果。在训练阶段，ϵi 逐渐的减小为0，使得模型可以学习到测试集的分布。

实验

数据集

文中使用两个公共交通网络数据集Metr-la和Pems-Bay。

Metr-la：记录了洛杉矶县高速公路上207个传感器上从2012年3月1日到2012年6月30日4个月的交通速度统计数据。
Pems-Bay：包含在湾区325个传感器上2017年1月1日到2017年5月31日6个月的交通速度信息。

实验设置

邻接矩阵W：使用阈值高斯核（thresholded Gaussian kernel）来构建：

其中：

W_ij表示了检测器 v_i和 v_j之间的权重
dist(v_i,v_j)表示检测器 v_i到 v_j之间的距离
σ 表示距离的标准差
κ 表示阈值。

Baselines

HA：历史均值，将交通流建模成周期性过程，使用之前的周期的加权平均作为预测。
ARIMA_kal：具有卡尔曼滤波的自回归综合移动平均模型(Auto-Regressive Integrated Moving
Average)
VAR: 向量自回归模型（Vector Auto-Regression ，1994）
SVR：支持向量回归(Support Vector Regression)，使用线性支持向量机用于回归任务。
FNN：前向传播神经网络(Feed forward Neural network)，两个隐藏层，L2正则化。
FC-LSTM:具有全连通LSTM隐单元的递归神经网络(Recurrent Neural Network with fully connected LSTM hidden units)