时空序列

STGCN (IJCAI 2018)

Spatio-Temporal Graph Convolutional Networks: A Deep Learning Frameworkfor Traffic Forecasting

arxiv:https://arxiv.org/abs/1709.04875

前言前的碎碎念

这是博客里时间序列介绍的第二篇文章，跨度可能有点大，直接从convLSTM跨到时空图神经网络了，主要也是因为最近一段时间的研究重点会落在时空图上。接下来的几篇博客介绍的也主要会是时空图相关。STGCN其实之前也有看过一边，不过之前是看完20年WWW的那篇STGNN后找过来的（STGNN大概率下一篇文章就会介绍了），当时抱着一种思想上也不过如此的傲慢思想看了STGCN，粗粗阅读之后就放下了，现在重读一遍发现其实当时是有很多没有理解透彻的点的，故在此重新记录阅读笔记。

真滴前言

本文针对的问题是交通预测问题。交通状态预测的重要性不用多言，包括流量控制，路线规划和导航等很多后续功能都十分依赖于交通状态预测。交通流量的基本变量包含有速度，交通容量比(指路网的总交通量与路网容许的总通行能力之比，又称拥挤度或路网适应性。论文里的volume应该是指代这个叭)和密度，这些变量通常被用作流量监控的指标以及预测未来状态的重要参数。基于这些参数，交通预测通常可以按照时间分成两种尺度：短期（5-30分钟），中长期（30分钟以上）。许多统计方法（例如LR）在短期预测上的表现很好，但遇到中长期的问题就欠佳了。

在中长期预测问题上，之前的方法通常可以被分成两派：动态建模(用数学工具和物理方法仿真建模，问题是要想达到一个稳定的状态非常复杂且需要很大的算例)；数据建模（利用大数据建立模型进行预测的方法，例如ARIMA，就是这种方法受限于时间序列的平稳性假设同时无法同时捕捉空间信息。而后，进入机器学习时代，KNN，SVM和NN方法也逐渐被应用于交通预测中。再然后就是深度学习方法了，包括deep belief network（DBN）和stack autoencoder（SAE）等方法也逐渐发展起来了）

括号太长了我跳出来写了，但上述的方法都无法同时提取空间和时间的信息，那咋办呢？有研究者就开始想法子把CNN和RNN弄到一起去了，CNN从空间角度提取信息而RNN从时间角度提取信息。之后，结合了LSTM和一维CNN的CLTFP出现了，这是第一次同时提取空间和时间特征并用以交通预测的尝试。而后，convLSTM出现了（这玩意咱介绍过了前面文章有哈）。嗯，问题又来了，一方面，类RNN模型是出了名的难训练而且算起来很复杂，CNN呢又只能处理图像这种欧式空间数据。

于是呀，STGCN应运而生。它用GCN解决了非欧空间的信息提取，用CNN提取序列信息解决了RNN的难训练和训练复杂问题。

需要的储备知识！

讲模型前我们先看一眼数据啥样叭，先搞张截图:

datadata

这数据其实就是t个时刻的图结构合集，为啥是图结构呢？我们脑补一下地图，如果要按照路上的监视器连线，那结果一定不会是像图像一个像素点一个像素点这样规则排列的，那这种结构的数据最好的表示方法就是Graph了。

这一系列图中的每一个时间步的图VtV_t都表示当前时间段内的交通状态信息，可以用Gt=(Vt,E,W)\mathcal{G}_t=(\mathcal{V}_t,\mathcal{E},W)来表示t时刻的图，其中Vt\mathcal{V}_t表示有限的节点集合，每一个节点表示的就是一个监视器的位置（用来产生速度等变量），E\mathcal{E}表示不同监视器之间的连接关系，WW是图带权重的邻接矩阵。

那么在这个数据上我们的目的是啥呢，总的来说，就是想利用这过去的t个时间步数据预测未来H个时间步的数据。用公式表示大概就是：
v^t+1,...,v^t+H=arg max⁡vt+1,...,vt+H P(vt+1,...,vt+H∣vt−M+1,...,vt) \hat{v}_{t+1},...,\hat{v}_{t+H}={\underset {v_{t+1},...,v_{t+H}}{\operatorname {arg\,max} }}\,P(v_{t+1},...,v_{t+H}|v_{t-M+1},...,v_{t}) 然后康一眼图卷积方法叭，文章内提到了两种方法：1、“Learning Convolutional Neural Networks for Graphs”提出的方法，主要思想是把图结构数据转化为CNN能高效处理的结构，处理过程主要分为两个步骤:a、从图结构中选出具有代表性的nodes序列；b、对于选出的每一个node求出一个卷积的领域。处理完之后再进行卷积操作就行。之后再经过一个图规范化过程和卷积网络即可。2、将图做一个傅里叶变化转入频域，并在频域进行卷积操作。具体不再展开了嗷，展开了讲可长了。

模型模型模型！

再搞张截图！

stgcnstgcn

一点一点来看奥，这图稍微还是有点绕的（至少我第一遍看的时候没有看懂），分到最细，图里的结构主要有Temporal Gated-Conv 和 Spatial Graph-Conv两块，一个一个来~
Temporal Gated-Conv

这个模块由一个1维卷积核（长度为KtK_t）一个gated linear units(GLU)组成。

这个模块里处理的维度是time的那个轴，所以对于1维卷积核的输入，实际上是节点在不同时间步上的数据的拼接，即Y∈RM×CiY\in\mathbb{R}^{M\times{C_i}},这里面的MM是时间序列的长度，CiC_i是每个数据点的输入通道数（可以理解成速度这些变量）。在这个模块里，卷积核被设定维Γ∈RKt×Ci×2Co\Gamma\in\mathbb{R}^{K_t\times{C_i}\times{2C_o}}(KtK_t是长度，CoC_o是输出通道数)，这个卷积核的目标是要将输入映射成[P  Q]∈R(M−Kt+1)×2Co[P \;Q]\in\mathbb{R}^{(M-K_t+1)\times{2C_o}},其中PP和QQ是上面输出通道的对半切分。之后PP,QQ进入GLU中，公式如下：
Γ∗ΓY=P⊙σ(Q)∈R(M−Kt+1)×Co \Gamma*_\Gamma Y = P \odot\sigma{(Q)}\in\mathbb{R}^{(M-K_t+1)\times{C_o}} 其中⊙\odot表示哈达玛积，σ\sigma就是门结构，用来生成系数，Y指的是输入数据。同时，STGCN也引入了残差结构，残差结构是在堆叠的temporal convolutional layers之间实现的。
Spatio Graph-Conv

在上图的三明治结构里，两个Temporal Gated-Conv之间夹着一个Spatio Graph-Conv，这个模块的目的是用图卷积神经网路提取图中的空间信息，在本文中，图卷积神经采用了频域方法，并使用了切比雪夫多项式近似进行参数优化，具体做法使用一阶近似进行优化，具体还是不展开了，有空专门整一篇介绍把。这里我们只需要知道，通过下面的公式进行空间特征提取。
Θ∗Gx=θ(In+D−12WD−12)x=θ(D~−12WD~−12)x \begin{aligned} \Theta*_{\mathcal{G}} x&=\theta{(I_n+D^{-\frac{1}{2}}WD^{-\frac{1}{2}})}x\\ &=\theta(\tilde{D}^{-\frac{1}{2}}W\tilde{D}^{-\frac{1}{2}})x \end{aligned} 同样的，这个公式可以推广到多个channel，推广之后公式就变成了：
yj=∑i=1CiΘi,j(L)xi∈Rn,1≤j≤Co y_j=\sum_{i=1}^{C_i}{\Theta_{i,j}(L)x_i\in\mathbb{R}^n},1\leq j\leq C_o 需要注意的是，这个模块实在空间角度进行的。
ST-Conv Block

介绍完ST-Conv Block中的每一个小结构之后我们来看一下整体的结构，通过结合上述所有的计算步骤，我们可以得知，对于输入vl∈RM×n×Clv^l\in\mathbb{R}^{M\times n\times C^l},输出vl+1∈R(M−2(Kt−1))×n×Cl+1v^{l+1}\in\mathbb{R}^{(M-2(K_t-1))\times n\times C^{l+1}} 可以通过下面的公式进行计算：
vl+1=Γ1l∗ΓRELU(Θl∗G(Γ0l∗Γvl)) v^{l+1}=\Gamma^l_1 *_\Gamma RELU(\Theta^l *_\mathcal{G}(\Gamma^l_0 *_\Gamma v^l)) 最后呢，在ST-Conv Block之后接了一层全连接层用来计算输出，并用L2损失计算模型的性能：
L(v^;Wθ)=∑t∣∣v^(vt−M+1,...,vt,Wθ)−vt=1∣∣2 L(\hat{v};W_\theta)=\sum_t{||\hat{v}(v_{t-M+1},...,v_t,W_\theta)-v_{t=1}||^2}

总结总结！

OK介绍完了，照例不介绍具体的数据集表现了，重读了一边论文之后，其实让我影响深刻的是在一个ST-Conv块里的时间轴，空间轴的转换，包括最开始没看懂也是因为在时间维度的那一块没看懂输入的含义。对了说起来，用CNN代替RNN模型实现训练的加速也是一个很有意思的点，最近也碰到很多这种用CNN处理序列的方法了，也是一个可以借鉴的点。