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

2019 年 10 月 28 日 专知

导读

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



动机

01


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


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


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


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


核心思想

02


扩散卷积循环神经网络(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,使得模型可以学习到测试集的分布。


实验

03



数据集


文中使用两个公共交通网络数据集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)


实验结果


为了证明DRCNN能够很好地捕获空间与时间依赖性,作者对比了以上不同的方法在15分钟,30分钟,1小时在两个数据集上预测的对比,表1为实验结果:

为了验证空间依赖建模的影响,文中还对比了 DCRNN 和以下变体:


1). DCRNN-NoConv,使用单位阵替换扩散卷积中的转移矩阵,忽略空间依赖。


2). DCRNN-UniConv,扩散卷积中只使用前向随机游走


图3展示了这三个模型使用大体相同数量的参数时的学习曲线

同样地,为了衡量 Sequence to Sequence框架以及 scheduled sampling 技术对时间建模的影响,文中设计 DCRNN 的三种变体:


1). DCNN:拼接历史的观测值为一个固定长度的向量,将它放到堆叠的扩散卷积层中,预测未来的时间序列。


2). DCRNN-SEQ:使用编码解码序列到序列学习框架做多步预测。


3). DCRNN:在 DCRNN-SEQ 的基础上增加了 scheduled sampling。


图5展示了这四种方法针的 MAE 结果对比

除此之外,文中还对比了有向图(DCRNN)与无向图(GCRNN)的结果来证明有向图在交通预测中的有效性,如表2所示:


通过不同参数k的对比试验(图4),我们可以看到越大的 K 越能使模型捕获更宽的空间依赖,代价是增加了学习的复杂度。


-END-
专 · 知


专知,专业可信的人工智能知识分发,让认知协作更快更好!欢迎注册登录专知www.zhuanzhi.ai,获取更多AI知识资料!
欢迎微信扫一扫加入专知人工智能知识星球群,获取最新AI专业干货知识教程视频资料和与专家交流咨询
请加专知小助手微信(扫一扫如下二维码添加), 获取专知VIP会员码 ,加入专知人工智能主题群,咨询技术商务合作~
点击“阅读原文”,了解注册成为 专知VIP会员 
登录查看更多
42

相关内容

循环神经网络(RNN)是一类人工神经网络,其中节点之间的连接沿时间序列形成有向图。 这使其表现出时间动态行为。 RNN源自前馈神经网络,可以使用其内部状态(内存)来处理可变长度的输入序列。这使得它们适用于诸如未分段的,连接的手写识别或语音识别之类的任务。
【CMU】基于图神经网络的联合检测与多目标跟踪
专知会员服务
54+阅读 · 2020年6月24日
【斯坦福大学博士论文】自监督场景表示学习, 97页pdf
专知会员服务
92+阅读 · 2020年6月19日
【KDD2020】多源深度域自适应的时序传感数据
专知会员服务
59+阅读 · 2020年5月25日
【CVPR2020-百度】用于视觉识别的门控信道变换
专知会员服务
12+阅读 · 2020年3月30日
【斯坦福大学-论文】实体上下文关系路径的知识图谱补全
【MIT深度学习课程】深度序列建模,Deep Sequence Modeling
专知会员服务
75+阅读 · 2020年2月3日
必读的7篇IJCAI 2019【图神经网络(GNN)】相关论文-Part2
专知会员服务
58+阅读 · 2020年1月10日
赛尔笔记 | 自然语言处理中的迁移学习(下)
AI科技评论
11+阅读 · 2019年10月21日
论文浅尝 | 面向时序知识图谱推理的循环事件网络
开放知识图谱
76+阅读 · 2019年9月22日
【泡泡图灵智库】用于单目深度估计的深度有序回归网络
论文 | 基于RNN的在线多目标跟踪
七月在线实验室
30+阅读 · 2017年12月27日
Deep Anomaly Detection with Outlier Exposure
Arxiv
17+阅读 · 2018年12月21日
Arxiv
22+阅读 · 2018年8月3日
Two Stream 3D Semantic Scene Completion
Arxiv
4+阅读 · 2018年7月16日
Arxiv
8+阅读 · 2018年4月12日
Arxiv
28+阅读 · 2018年4月6日
VIP会员
相关资讯
赛尔笔记 | 自然语言处理中的迁移学习(下)
AI科技评论
11+阅读 · 2019年10月21日
论文浅尝 | 面向时序知识图谱推理的循环事件网络
开放知识图谱
76+阅读 · 2019年9月22日
【泡泡图灵智库】用于单目深度估计的深度有序回归网络
论文 | 基于RNN的在线多目标跟踪
七月在线实验室
30+阅读 · 2017年12月27日
Top
微信扫码咨询专知VIP会员