时空序列

DCRNN (ICLR 2018)

Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting

arxiv:https://arxiv.org/abs/1707.01926

前言前言前言

有一丢丢懒得整理图神经网络的论文，主要下一篇想写的FastGCN里涉及了很多数学推导，书稿里因为篇幅原因写的不是很细，但是又不愿意把这么粗糙的介绍放到博客里，所以还是得等我提起干劲去把公式都推一推再放上来。今天先偷懒看一篇时空序列图神经网络的文章。刚开始在找论文没有按时间排序的后果就是时间线开始疯狂反复横跳（等把文章写全了我再重排一下这个系列的标号叭），这回的文章是2018年ICLR上发表的，在之前介绍很多论文中也都有提到。废话挺久的了，也不多说别的了，还是按着文章结构介绍吧。

这篇文章也是解决交通预测问题的，按照惯例，文章给出了三个交通路网预测的挑战，分别是：1、复杂的路网空间依赖性；2、随着路况变化非线性变化的动态时间依赖性；3、长期预测本身就存在的内在的困难。针对这些问题，论文给出了DCRNN结构，分别使用基于双向随机游走的扩散卷积和编码-解码结构来处理空间、时间依赖性。

在介绍背景时，文章提到了在交通路网结构中，空间结构是非欧几里德空间且定向的，这也很好理解，交通路网本质上就是一张图，而图就是非欧的；而定向是因为道路的上下游对该段道路是会产生不同影响的。此外，同STGCN论文里一样，这篇文章也提到了Knowledge-Driven和Data-Driven两种交通路网预测的方法大类，两篇文章时间点类似，介绍的也大差不差，不具体展开了。

总的来说，DCRNN融合了扩散卷积、seq2seq结构和schedule sample技术，实现了对时间、空间依赖性信息的抽取，具体结构我们下面再看，不过按照惯例，还是先定义一下问题。

问题定义

与之前提到的交通路网问题一样（其实应该是他们和这个一样，因为这个早一些，无所谓啦），模型将路上的传感器定义为节点，两个节点之间的相似性表示边权重（相似性通过路网距离计算，文章没提这个路网距离怎么计算，先按下不表），所以路网结构可以用一个带权有向图G=(V,E,W)\mathcal{G}=(\mathcal{V},\mathcal{E},W)表示，V\mathcal{V}和E\mathcal{E}分别表示顶点集合和边集合，WW表示权重。除此之外，模型还定义了一个图信号X∈RN×PX\in\mathbb{R}^{N\times P}用来表示图上节点的特征，PP表示的特征的个数。整体来说，模型的目标就是通过过去的信息预测未来的节点上的速度，用公式可以表示为：
[X(t−T′+1),...,X(t);G]→h(⋅)[X(t+1),...,X(t+T)] [X^{(t-T^{'}+1)},...,X^{(t)};\mathcal{G}]\overset{h(\cdot)}{\to}[X^{(t+1)},...,X^{(t+T)}]

模型模型模型

先拍图：

DCRNNDCRNN

然后和之前一样，模型按两部分介绍，分别是空间依赖性捕获和时间依赖性捕获。
空间依赖性

扩散操作：

模型通过将交通流与扩散过程相关联来对空间依赖性进行建模。具体来说，模型定义了一个带有α\alpha概率从头开始的随机游走（状态转移矩阵为用Do−1D_o^{-1}标准化的权重矩阵Do−1WD_o^{-1}W表示，这里的DoD_o表示出度矩阵。如同马尔可夫过程一样，这个随机游走在游走了足够长的步数后能得到一个稳定的分布P∈RN×N\mathcal{P}\in\mathbb{R}^{N\times N}，在这个分布中的每一行Pi,:∈RN\mathcal{P}_{i,:}\in\mathbb{R}^{N}表示节点ii与其余节点的相似性。这块内容其实在PPNP&APPNP那篇里介绍过，在jk-net那篇论文里有证明说GCN获得的表征最终会与随机游走获得的稳定分布一致，但传统随机游走由于没考虑restart，使得其在表征起始节点上并不好，所以该模型加入了一个restart的概率来改进。扯回来，这个稳定分布用数学公式表示为：
P=∑k=0∞α(1−α)k(Do−1W)k \mathcal{P}=\sum_{k=0}^{\infin}\alpha(1-\alpha)^{k}(D_o^{-1}W)^k

在实际模型中，还会利用入度矩阵再求一次，以更充分地捕获双向（upstream和downstream）的信息。

扩散卷积：

在定义了扩散操作之后，模型定义了一个扩散卷积的操作。ST-GDN应该是借鉴了这一步的操作，公式定义如下：
X:,p⋆Gfθ=∑k=0K−1(θk,1(Do−1W)k+θk,2(DI−1W⊺)k)X:,pfor  p∈{1,...,P} X_{:,p}\star_{\mathcal{G}}f_\theta=\sum_{k=0}^{K-1}(\theta_{k,1}(D_o^{-1}W)^k+\theta_{k,2}(D_I^{-1}W^{\intercal})^k)X_{:,p}\qquad for\; p\in\{1,...,P\}

这里的Do−1WD_o^{-1}W和DI−1W⊺D_I^{-1}W^{\intercal}分别是由上面的出度、入度扩散操作所得的稳定分布（上面是P\mathcal{P},这里用DD表示），θ∈RK×2\theta\in\mathbb{R}^{K\times 2}是对应的参数。

扩散卷积层：

扩散卷积层包含了上面的扩散卷积操作，并希望输出的向量表征维度能由特征的PP维变为QQ维，这一层的数学表示为：
H:,q=a(∑p=1PX:,q⋆GfΘq,p,:,:)for  q∈{1,...,Q} H_{:,q}=a(\sum_{p=1}^{P}X_{:,q}\star_{\mathcal{G}}f_{\Theta_{q,p,:,:}})\qquad for\;q\in\{1,...,Q\}

这里的Θ∈RQ×P×K×2=[θ]q,p\Theta\in\mathbb{R}^{Q\times P\times K \times 2}=[\theta]_{q,p}，是用来进行维度转化的参数。HH，XX分别是输出输入参数，aa是激活函数。

值得一提的是，文章里提到了扩散卷积层与频域GCN的关系。文中指出，ChebNet实际上是扩散卷积的一种特例。

时间依赖性

DCRNN中采用了GRU模型来对时间依赖性进行建模，改动点时间扩散卷积加入到GRU中，公式如下：
r(t)=σ(Θr⋆G[X(t),H(t−1)]+br)ut=σ(Θu⋆GX(t),H(t−1)]+bu)Ct=tanh(ΘC⋆GX(t),(r(t)⊙H(t−1))]+bc)Ht=u(t)⊙H(t−1)+(1−u(t))⊙C(t) \begin{aligned} r^{(t)}&=\sigma(\Theta_r\star_{\mathcal{G}}[X^{(t)},H^{(t-1)}]+b_r)\\ u^{t}&=\sigma(\Theta_u\star_{\mathcal{G}}X^{(t)},H^{(t-1)}]+b_u)\\ C^{t}&=tanh(\Theta_C\star_{\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{aligned}

其中，⋆G\star_{\mathcal{G}}表示扩散卷积操作，Θ\Theta表示各自的参数，r(t)r^{(t)}和u(t)u^{(t)}表示重置门和更新门。

之后为了进行预测，模型在这一块设计成了Seq2Seq的形式。同时，为了提升Seq2Seq的效果，模型引入了schedule sample，为什么schedule sample能提升效果呢？原因如下：

seq2seq模型在训练和预测的时候实际上存在着差异，在训练过程中，是将已有的正确的序列输入进行预测，而在预测层中，则是根据上一轮生成的结果进行预测，如果上一轮结果错误，那么后续接连错误的概率就会很大。为了解决这个问题，schedule sample设定了一个概率p，使得在训练的过程中，有p的概率使用训练样本，有1-p的概率使用上一轮生成的结果进行预测。在DCRNN的训练策略中，还会随着训练的次数加深不断降低p，直到p为0，这样就使得模型能很好地适应预测阶段的模式。

总结总结总结

总的来说，DCRNN的结构和STGCN、STGNN之类的相差不大，有意思的点在于扩散操作和扩散卷积那块，并没有使用chebnet获取信息而通过随机游走得到的稳定分布代替。由于结构相似性很高，所以暂时没有别的什么创新想法，先这样吧，Over。