DCRNN 模型是南加州大学的 Li 等人发表在 $ICLR2018$ 会议上一个用于交通预测的时空预测模型，论文题目为: 《DIFFUSION CONVOLUTIONAL RECURRENT NEURAL NETWORK: DATA-DRIVEN TRAFFIC FORECASTING》，文章地址为: https://arxiv.org/abs/1707.01926。

引言

文章首先指出了交通预测问题的难点是如何处理复杂的时空依赖关系，一方面，交通序列在时间上具有强烈的时间动态性，反复发生的事件(如高峰时段或交通事故)会导致时序表现出非平稳定性，从而难以进行长期预测。同时，道路网络上的传感器包含复杂而独特的空间相关性。如下图所示:

路段1和路段2相关，路段1和路段3不相关，尽管两者在欧式空间中很接近，但它们的交通行为却截然不同。同时，未来车速受下游车流的影响大于上游车流，说明交通流的空间结构是非欧几里得且是一个有向图。

文章指出，当前时序预测算法主要分为2大阵营: 知识驱动和数据驱动，知识驱动主要通过应用排队论来模拟交通中的车辆行为进而实现预测。数据驱动类方法，如自回归综合移动平均(ARIMA) 模型和卡尔曼滤波等传统机器学习算法仍然很流行。而深度学习方面，用于序列分析的 LSTM 和 GRU 等 RNN 类算法也大量应用于时间序列的预测。但上述算法均未考虑交通路网的空间特性，虽然也出现了将 CNN 用于空间特征的挖掘，但其是将交通路网作为欧几里得空间(二维图像)来进行处理的，后续出现的谱域图卷积(ChebNet，GCN等)虽然实现了非欧几里得空间的卷积操作，但其只能应用于无向图，无法处理有向图。

在此基础上，给出了 DCRNN 模型优势:

• 将交通流量的空间依赖性建模为有向图上的扩散过程，在此基础上提出了扩散图卷积，其具有直观的解释且计算高效。

• 提出的 DCRNN 模型将扩散图卷积和Seq2Seq结构有机结合起来，并通过策略采样技术完成训练，实现了时序预测空间依赖和时间依赖的共同学习，且该模型不仅仅局限于交通预测领域，也可以迁移到其他领域。

• 在2个大规模的真实数据集上进行了性能测试，比最先进的基线方法有了显著改进。

模型

交通预测问题定义

交通预测的目标是，根据路网上 $N$ 个传感器观测到的交通流特征，来预测未来的交通速度。可以将传感器网络表示为一个有权有向图 $\mathcal{G}=(v,\epsilon ,W)$，其中 $v$ 代表节点集合，节点数量为 $N$。$\epsilon$ 是边的集合，而 $W\in {\mathbb{R}}^{N\times N}$ 是一个有权的邻接矩阵，表示节点之间的邻近程度(例如: 节点间的路网距离函数)。将 $\mathcal{G}$ 上观测到的交通流特征表示为图上的信号 $X\in {\mathbb{R}}^{N\times P}$，$P$ 表示每个节点的特征维度(如速度、流量等)。$X^{(t)}$ 表示在 t 时刻的图信号，而交通预测的目标就是学习一个 $h(\cdot )$ 函数，建立历史 $T^{{}^{\prime }}$ 个图信号到未来 $T$ 个图信号的映射关系。

$$[X^{(t-T^{{}^{\prime }}+1)},...,X^{(t)};\mathcal{G}]\stackrel{h(\cdot )}{⟶}[X^{(t+1)},...,X^{(t+T)}$$

空间依赖建模

扩散卷积

本文通过将交通流与扩散过程联系起来来模拟空间依赖性，扩散过程是在图 $\mathcal{G}$ 上的随机行走，重启概率为 $\alpha \in [0,1]$，状态转移矩阵为 $D_o^{-1}W$。

其中，$D_o=diag(W1)$ 为出度的对角矩阵，$1\in {\mathbb{R}}^N$ 表示一个全为1的 $N$ 维向量。

经过很多时间步后，这样的马尔科夫过程会收敛到一个稳态分布 $\mathcal{P}\in {\mathbb{R}}^{N\times N}$，其第 $i$ 行 ${\mathcal{P}}_{i,:}\in {\mathbb{R}}^N$ 表示从节点 $v_i\in \mathcal{V}$ 向外扩散的可能性，下述定理给出了稳态分布的闭合解:

$$\mathcal{P}=\sum _{k=0}^{\infty }\alpha (1-\alpha {)}^k(D_o^{-1}W{)}^k$$

即扩散过程的稳态分布可以表示作为图上无限随机游走的加权组合，并以闭合形式计算。

其中 $k$ 是扩散步骤。在实践中，使用扩散过程的有限 $K$ 步截断，并为每个步骤分配一个可训练的权重。同时，扩散过程还包括反向扩散过程，这样，双向扩散为模型提供了更大的灵活性，以同时捕获来自上游和下游的流量。

综上，图信号 $X\in {\mathbb{R}}^{N\times P}$ 和卷积核 $f_{\theta }$ 的图卷积过程可以定义为:

X : , p ∗ G f θ = ∑ k = 0 K − 1 ( θ k , 1 ( D o − 1 W ) k + θ k , 2 ( D i − 1 W T ) k ) X : , p    f o r   p ∈ { 1 , . . . , P } X_{:,p}* _\mathcal{G}f_{\theta}=\sum_{k=0}^{K-1}(\theta_{k,1}(D_{o}^{-1}W)^{k}+\theta_{k,2}(D_{i}^{-1}W^{T})^{k})X_{:,p} \space \space for \space p \in \{1,...,P\} X:,p​∗G​fθ​=k=0∑K−1​(θk,1​(Do−1​W)k+θk,2​(Di−1​WT)k)X:,p​  for p∈{1,...,P}

其中，$\theta \in {\mathbb{R}}^{K\times 2}$ 为卷积核 $D_o^{-1}W,D_i^{-1}{W}^T$ 的参数。一般来讲，当图比较大时，上述卷积计算可能比较昂贵，但如果 $\mathcal{G}$ 是稀疏连接的话，上述等式可以使用递归稀疏-密集矩阵乘法，总复杂度降为 $\mathcal{O}(K|\epsilon |)\ll \mathcal{O}(N^2)$。

扩散卷积层

基于扩散卷积，很容易构建将 $P$ 维输入特征映射为 $Q$ 维输出特征的扩散卷积层:

H : , q = a ( ∑ p = 1 P X : , p ∗ G f θ q , p , : , : )    f o r   q ∈ { 1 , . . . , Q } H_{:,q}=a(\sum_{p=1}^{P}X_{:,p}* _{\mathcal{G}}f_{\theta_{q,p,:,:}}) \space \space for \space q \in \{1,...,Q\} H:,q​=a(p=1∑P​X:,p​∗G​fθq,p,:,:​​)  for q∈{1,...,Q}

此时，输入为 $X\in {\mathbb{R}}^{N\times P}$，输出为 $H\in {\mathbb{R}}^{N\times Q}$，$a$ 为激活函数(例如: Sigmoid 或者 ReLU)。

整个扩散卷积层的参数集合 $\Theta \in {\mathbb{R}}^{Q\times P\times K\times 2}=[\theta {]}_{p,q}$，其中 ${\Theta }_{p,q,:,:}\in {\mathbb{R}}^{K\times 2}$ 代表输入的第 $i$ 维变量到输出的第 $j$ 维变量的卷积核。

和谱域图卷积的关系

论文指出，扩散图卷积不但适用无向图，还适用有向图。而无向图上比较经典的谱域图卷积算法，例如: ChebNet(Defferrard等，2016)，可以当做是扩散图卷积的一个特例。

谱域图卷积的定义为：

$$X_{:,p}{\ast }_{\mathcal{G}}{f}_{\theta }=\Phi F(\theta ){\Phi }^T{X}_{:,p}$$

其中，$L=\Phi \Lambda {\Phi }^T$，$F(\theta )={\sum }_0^{K-1}{\theta }_k{\Lambda }^k$。

故上式也可以转化为:

$$\begin{array}{c}\begin{array}{rl}{X}_{:,p}{\ast }_{\mathcal{G}}{f}_{\theta }& =\Phi F(\theta ){\Phi }^T{X}_{:,p}\\ & =\Phi (\sum _0^{K-1}{\theta }_k{\Lambda }^k){\Phi }^T{X}_{:,p}\\ & =\sum _0^{K-1}{\theta }_k(\Phi \Lambda {\Phi }^T{)}^k{X}_{:,p}\\ & =\sum _0^{K-1}{\theta }_k{L}^k{X}_{:,p}\end{array}\end{array}$$

谱域图卷积中 $L=\Phi \Lambda {\Phi }^T$ 成立的前提是图为无向图，无向图的出度矩阵和入度矩阵是一样的，且无向图为对称矩阵，所以 $W=W^T$。

则扩散卷积公式可以转化为:

X : , p ∗ G f θ = ∑ k = 0 K − 1 ( θ k , 1 ( D o − 1 W ) k + θ k , 2 ( D i − 1 W T ) k ) X : , p    f o r   p ∈ { 1 , . . . , P } = ∑ k = 0 K − 1 ( θ k , 1 ( D − 1 W ) k + θ k , 2 ( D − 1 W ) k ) X : , p = ∑ k = 0 K − 1 ( θ k , 1 + θ k , 2 ) ( D − 1 W ) k X : , p = ∑ k = 0 K − 1 θ k ( D − 1 W ) k X : , p \begin{equation} \begin{split} X_{:,p}* _\mathcal{G}f_{\theta} &= \sum_{k=0}^{K-1}(\theta_{k,1}(D_{o}^{-1}W)^{k}+\theta_{k,2}(D_{i}^{-1}W^{T})^{k})X_{:,p} \space \space for \space p \in \{1,...,P\} \\ &= \sum_{k=0}^{K-1}(\theta_{k,1}(D^{-1}W)^{k}+\theta_{k,2}(D^{-1}W)^{k})X_{:,p} \\ &= \sum_{k=0}^{K-1}(\theta_{k,1}+\theta_{k,2})(D^{-1}W)^{k}X_{:,p} \\ &= \sum_{k=0}^{K-1}\theta_k(D^{-1}W)^{k}X_{:,p} \end{split} \end{equation} X:,p​∗G​fθ​​=k=0∑K−1​(θk,1​(Do−1​W)k+θk,2​(Di−1​WT)k)X:,p​  for p∈{1,...,P}=k=0∑K−1​(θk,1​(D−1W)k+θk,2​(D−1W)k)X:,p​=k=0∑K−1​(θk,1​+θk,2​)(D−1W)kX:,p​=k=0∑K−1​θk​(D−1W)kX:,p​​​​

可以发现，谱域图卷积其实就是相当于将扩散卷积公式里的 $D_o^{-1}W$ 替换为了 $L$ 而已。

时间依赖建模

本文选取 GRU 这个 RNN 类模型来进行时间依赖的学习和挖掘，并将其中的矩阵乘法替换为了上述的扩散图卷积，并将此结构命名为 DCGRU。

具体过程如下:

$$\begin{array}{c}\begin{array}{r}{r}^{(t)}=\sigma ({\Theta }_r{\ast }_{\mathcal{G}}[X^{(t)},H^{(t-1)}]+b_r)\\ u^{(t)}=\sigma ({\Theta }_u{\ast }_{\mathcal{G}}[X^{(t)},H^{(t-1)}]+b_u)\\ C^{(t)}=tanh({\Theta }_C{\ast }_{\mathcal{G}}[X^{(t)},(r^{(t)}\odot H^{(t-1))}]+b_c)\\ H^{(t)}=u^{(t)}\odot H^{(t-1))}+(1-u^{(t)})\odot C^{(t))}\end{array}\end{array}$$

这里有些人会有疑问: GRU 的结构好像 (1-) 的位置有问题吧，他们可能看到的是下图:

按照上图所示，上述公式的最后一行应该调整为:

$$H^{(t)}=u^{(t)}\odot C^{(t))}+(1-u^{(t)})\odot H^{(t-1))}$$

到底哪一个对呢？我们可以查看一下 GRU 的原始论文: Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling

可以看到，原始论文的 (1-) 的位置确实和上图一致，而和本文中的不一致。

但 GRU 作者的另外一篇文章，Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation。

哈哈哈，这篇论文里 (1-) 的位置又和本文中的一致了！

而 Pytorch 的 GRU 官方实现如下:

到底哪个对呢，其实我理解下来，(1-) 的位置上述两种情况是等效的，因为 $u^{(t)}$ 本身就是 $\sigma$ 激活以后，通过将范围压到 $[0,1]$ 起到门控的作用。

假如第1种情况下(本文)，训练得到的 $u^{(t)}$ 为0.7，则同样的一批数据在第2种情况下(GRU原文)执行训练，得到的 $u^{(t)}$ 将为 0.3。而两者其实都相当于70%的 $H^{(t-1)}$ 和30%的 $C^{(t)}$ 流向下游。

多步预测

多步预测场景下，DCRNN 采用的架构是 Encoder-Decoder。

其中，Encoder 和 Decoder 均是由前面定义的 DCGRU 组成，在训练过程中，将历史时间序列输入Encoder，并使用其最终状态来初始化 Decoder，Decoder 将根据历史观测真值来生成预测结果。在测试阶段，模型上一步迭代生成的预测结果将取代上一步的真值来进行下一步的预测。此时，训练和测试输入分布之间的差异会导致性能下降，为了缓解这一问题，本文采用了计划采样策略(scheduled sampling)，即在第 $i$ 步迭代时，以 ${ϵ}_i$ 的概率喂给模型观测真值，而以 $1-{ϵ}_i$ 的概率喂给模型前一步的预测值。在训练阶段，${ϵ}_i$ 的值将逐渐下降为0来使得模型能够学习到测试分布。

实验

基础实验

DCRNN 在两个真实世界的大规模数据集上进行了实验：

• METR-LA

包含从洛杉矶高速公路上的线圈检测器收集的交通信息（Jagadish 等，2014），选择了207个传感器，并收集了2012年3月1日以到2012年6月30日的数据进行实验。

• PEMS-BAY

此流量数据集由加利福尼亚州交通局基于 PeMS 系统收集，本文选择了325个湾区的传感器，并收集从 2017年1月1日到2017年5月31日的数据进行实验。

在这两个数据集中，将交通速度指标聚合到5分钟窗口中，并应用 $Z-Score$ 归一化。70%的数据用于训练，20%用于测试，其余10%用于验证。邻接矩阵的构建方式如下:

$$W_{i,j}=\{\begin{array}{ll}exp(-\frac{dist(v_i,v_j{)}^2}{{\sigma }^2})& \text{ if }i\ne j\text{and}dist(v_i,v_j)\le \kappa \\ 0& \text{ otherwise }\end{array}$$

性能对比测试结果如下:

消融实验

设计了两个消融模型来说明扩散图卷积的作用。

• DCRNN-NoConv

将扩散卷积的扩散概率矩阵替换为单位阵，相当于节点预测仅能依赖节点自身的历史特征，而无法获取周边邻接节点的信息。

• DCRNN-UniConv

仅保留扩散图卷积公式中的前向随机行走。

可以看出，DCRNN-NoConv相比DCRNN的实验结果说明周边邻接节点的信息还是非常重要的，DCRNN-UniConv相比DCRNN的实验结果，则说明了双向随机游走的有效性。

同时，论文还通过 ${\hat{W}}_{i,j}={\hat{W}}_{j,i}=max(W_{i,j},W_{j,i})$ 操作强行构建了1个无向图的对称矩阵 $\hat{W}$，然后将 DCRNN 中的扩散图卷积部分替换为 ChebNet 图卷积，并将新模型命名为 GCRNN，并进行了性能对比。

可以看出，DCRNN 模型优于 GCRNN 模型，直觉是有向图更好地捕捉了交通传感器之间的不对称相关性。

文章还对超参数 $K$ 和 $Units$ 进行了探索:

为了评估时间建模的效果，文章设计了3种变体:

• DCNN

将历史观测结果连接为固定长度的向量，并将其输入到堆叠的扩散卷积层来预测未来的时间序列，仅训练1个单步预测模型，多步预测通过迭代预测来实现。

• DCRNN-SEQ

采用 Encoder-Decoder 结构进行预测。

• DCRNN

与DCRNN-SEQ相似，但增加了计划采样策略(scheduled sampling)。

可以发现，预测步长越大，DCRNN 相比于 DCNN 的优势越明显。

模型评价

主要创新点就是将双向扩散图卷积引入到了交通时空预测领域，解决了谱域图卷积仅能应用在无向图上的限制。

至于和GRU的结合，在之前就有很多类似的工作了，比如2015年的Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting。

整体来看是篇不错的论文，实验部分设计得也比较扎实，值得精读。

最后说一句，该论文的附录里有个小的错误:

应该为:

$$T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$$