引言

paper
CompactETA: A Fast Inference System for Travel Time Prediction
读后感
外围就是将graph attention network利用到ETA中。

核心内容

问题

对于WDR来说，只有起起点不同，那么link序列就不同，整个recurrent局部都要从新计算。WDR的recurrent结构复杂，所以，WDR整体耗时十分重大。本文要解决的问题是：如何进步ETA计算的响应速度。

场景特点

  • 空间汇集性：选派司机时，link重合度十分高
  • 工夫汇集性：短时间内通过多轮派单尝试，对应ETA query在工夫上十分靠近。

初始思路

把端到端整体预测的形式改为对每个link独自预测工夫而后求和的形式。
缺点：link误差累积，导致误差较大

改良思路
对每个link抽取高层级的示意（high level representation），而后对示意向量求和而不是间接对工夫求和。

相比WDR它有几个根本性的改良：

（1）移除了wide和deep局部。

间接把全局特色输出到最终的MLP（3-layer）中，这在一些状况下会对精度有少许影响。

其中$r_{l_t}$示意link $l_t$的向量示意，$g$为转换后的全局特色。$l_t$的取值通过查问table b表来获取。table b表的更新与query无关，只与路况更新周期无关。（通常是5分钟）

（2）Graph Attention Network取代了LSTM的地位。

在WDR中，邻近link的依赖关系通过LSTM的序列学习能力来建设；而在CompactETA中，link之间的依赖关系通过学习路网的拓扑构造来建设。

用一个one-hot向量表征节点i与节点j之间的连贯关系：

并且定义$_{ii}=[0,0,1]$。


We build our graph attention network by stacking 3 graph attention blocks. Let ???? = 1, 2, 3 be the block index。$????????????^{(????)}$示意单隐层MLP，$u^{(????-1)}_i$、$u^{(????-1)}_j$别离示意节点i和j的在第k-1个block的输入。


应用softmax函数将向量依照neighbors维度计算散布，其中，$N_i$指代节点i及其街坊节点。

针对$N_i$加权求和，更新$l_i$的状态。

在first attention block之前，咱们采纳仿射变换(Affine Transformation)为残差链接（residual connection）对立 input 和 output的size大小。

其中，$x_{l_i}$为link $l_i$的特色，$W_{af}$、$b_{af}$为转换参数。
针对第k个block，$u_{i}^{(k)}$能够取得k-hop街坊的信息。k值越大，对应层级的神经元能够看到更多的信息（有点相似于CNN的部分感触野）。感触野越大，通常预测准确性越高，计算耗时也越大。折中起见，这里将k取值为3。

（3）减少了地位编码。

LSTM耗时重大，曾经采纳Graph Attention Network替换掉，所以这里通过减少地位编码尽可能地保留link的序列信息。借鉴了Transformer的解决方案，用三角函数生成了一系列对于地位的编码。但与Transformer不同的是，间接把PE加到示意向量上对于求和操作仍然没有任何作用，所以这里采纳了更加激进的乘法形式来应用地位编码。

其中，pos为link在行走门路中的地位，取值从1到T；$dim$为link表征的dimension index，$d_{rep}$为link表征的维度大小。

（4）架构降级。


在线上部署中，Graph Attention Network形成了updater模块，每当感知到新版路况时，就为地图中每一个link计算它的示意向量。这些示意向量被存在一个内存表中，并及时推送到predictor模块。真正的实时计算产生在predictor中。当一个ETA query到来时，服务仅仅执行了查表、求和等简略操作，加上一个128维隐层的MLP计算。这些计算是十分快的，即使CPU机器也能在若干微秒内实现。

（5）trick（这几个改良与本文主线无关，但也是蛮实用的trick）

  • 空间稠密性问题：link ID以embedding的形式解决，某个link的历史数据太少，embedding vector会欠拟合。基于路况散布来度量不同link的相似性，并利用metric learning来对link的embedding vector进行训练。
  • 司机稠密性问题：同样采纳metric learning解决
  • 工夫稠密性问题：咱们尝试了给相邻时段的embedding vector设置共享参数，使得相邻时段的embedding vector更加类似。

成果

从MAPE来看，CompactETA略差于WDR。

从响应时长来看，CompactETA优化成果显著。