DIFFUSION CONVOLUTIONAL RECURRENT NEURAL NETWORK: DATA-DRIVEN TRAFFIC FORECASTING

针对问题：交通预测。

提出模型：扩散卷积递归神经网络（DCRNN）。DCRNN在图形上使用双向随机步捕获空间依赖性，并使用计划采样的编码器-解码器结构捕获时间依赖性。

代码 GitHub - liyaguang/DCRNN: Implementation of Diffusion Convolutional Recurrent Neural Network in Tensorflow

方法

传感器--节点，边的权重-两节点接近度（衡量距离）。

有向权重图G=(V,E,W),V-节点集，|V|=N, E-边，W∈R[N*N]-节点接近度（如其路网距离的函数）的加权邻接矩阵。将流量表示为G的一个图信号 $X∈R^{N*P}$ ，P为每个节点特征数，则 $X^t$ -时间t观察到的图信号。那么流量预测目的就是：给定G下，学得一个函数 $h$ 将T'个历史图信号映射到未来T时刻的图信号：

$h[X^{t-\dot{T}+1},...,X^t;G]\rightarrow[X^{t+1},...,X^{t+T}]$

空间相关建模

将流量与扩散过程diffusion相关联来对空间依赖性进行建模，该过程捕获了交通动态的随机性。

扩散过程是用重启概率α∈[0,1]随机游走在G，和一个状态转移矩阵 $D_{O}^{-1}W$ 。 $D_O=diag(W1)$ 为斜对角矩阵。在许多步之后，这种马尔科夫过程会收敛于一个平稳分布 $P∈R^{N*N}$ ,第i行 $P_i∈R^N$ 表示从节点 $v_i$ 扩散的可能性。

引理：扩散过程的平稳分布可以表示为图上无限随机游动的加权组合，并以封闭形式计算：

$P=\sum\nolimits_{k=0}^\infty \alpha(1-\alpha )^k( D_{O}^{-1}W)^k$

k为扩散步数，使用扩散过程的有限K步截断并为每个步骤分配可训练的权重。还包括反向扩散，这样双向扩散为模型提供了更大的灵活性，可以捕获上游和下游流量的影响。

扩散卷积：在图信号 $X∈R^{N*P}$ 上产生的扩散卷积运算和滤波器 $f_\theta$ 定义为：

$X:,_{p\star G}f_\theta=\sum\nolimits_{k}^{K-1}(\theta_{k,1}( D_{O}^{-1}W)^k+(\theta_{k,2}( D_{I}^{-1}W^T)^k)X:,_p,$ p∈{1,...,P}

$θ ∈ R^{K×2 }$ 为滤波器参数， $D_{O}^{-1}W, D_{I}^{-1}W^T$ 为扩散过程的转换矩阵和反向扩散的转换矩阵。

时间相关建模

用扩散卷积替换GRU的矩阵相乘：

\star G

表示扩散卷积（上面公式）

在多部预测，本文使用sequence2sequence结构，解码编码器都为RNN，将历史数据输入到encoder得到最终的状态向量去初始化decoder。

在测试时使用decoder生成的预测值，训练和测试的输入分布之间的差异会导致性能下降。为了缓解这个问题，将 计划采样scheduled sampling 集成到模型中：在第i次迭代中，给模型feed概率为 $ε_i$ 的真实值或概率为 $1-ε_i$ 的模型预测值。在训练过程中， $ε_i$ 逐渐减小到0，以使模型学习测试的分布。

整体框架。通过最大程度地使用反向传播来生成目标未来时间序列的可能性来训练整个网络。

实验

baselines: HA,ARIMA,VAR: Vector Auto-Regression, SVR, 前馈NN，LSTM

度量指标：RMSE,MAPE,MAE

预测：15分钟，30分钟和1小时。

结果：（1）基于RNN的方法（FC-LSTM和DCRNN），通常胜过其他baseline，表明对时间依赖性建模的重要性。（2）DCRNN在所有预测范围的均达到最佳性能，表明时空依赖建模的有效性。（3）神经网络（FNN，FC-LSTM和DCRNN），对于线性预测（例如提前1小时）的性能往往优于线性baseline。这是因为时间依赖性随着horizon增长而变得越来越非线性。

空间依赖性建模的评估

将DCRNN与以下变体进行了比较：（1）DCRNN-NoConv，它通过将扩散卷积中的转换矩阵（扩散卷积公式）替换为恒等矩阵而忽略了空间依赖性。使得只能根据传感器的历史读数来推断传感器的预测。（2）DCRNN-UniConv，仅使用前向随机游走过渡矩阵进行扩散卷积。

三个模型的学习曲线，DCRNN实现了最低的验证误差，这表明了使用双向随机游走的有效性。

时间建模评估

进一步设计了DCRNN的三个变体：（1）DCNN：将历史观测值连接为固定长度的向量，并将其输入堆叠的扩散卷积层来预测未来的时间序列。我们训练一个模型进行提前一步的预测，然后将先前的预测作为输入提供给模型，以执行提前进行多步预测。（2）DCRNN-SEQ：使用编码器-解码器序列对序列学习框架进行提前预测的多个步骤。（3）DCRNN：类似于DCRNN-SEQ，只是增加了调度采样。

四种方法于不同预测水平的MAE比较。

观察结果：（1）DCRNN-SEQ优于DCNN，符合建模时间依赖性的重要性。（2）DCRNN效果最好，其优越性随着预测范围的增加而更加明显。原因：模型经过训练以在提前进行多步预测的过程中处理其误差，因此较少遭受错误传播问题的困扰。此外还训练了一个将预测输出作为输入进行多步预测的模型。该模型性能最差，三个变体都强调了计划抽样的重要性。

模型可解释性

预测1h的可视化图

观察结果：（1）当speed中存在小振荡时，DCRNN生成均值平滑预测[图6(a)]。这反映了模型的鲁棒性。（2）与baseline（如FC-LSTM）相比，DCRNN更准确地预测speed的突变[图6(b)]，DCRNN可以预测高峰时段的开始和结束。原因：DCRNN捕获了空间依赖性，并能够利用邻域传感器（邻节点）的速度变化进行更准确的预测。

以不同节点为中心的学习过滤器的可视化示例。星号-中心，颜色-权重。

观察结果：（1）权重准确定位在中心周围，（2）权重根据路网距离而扩散。

总结

1. diffusionDCRNN可以捕获时空依赖：双向图随机步 bidirectional graph random walk -捕获空间依赖，RNN-捕获时间依赖。

2. 利用encoder-decoder和scheduled sampling 技术改善long-term预测性能。

科普：

计划采样：Scheduled Sampling：RNN的训练trick_Deep Learning and NLP Farm-CSDN博客_scheduled sampling