Press "Enter" to skip to content

滴滴ETA论文解读:CompactETA

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

引言

 

paper

 

: A Fast Inference System for Travel Time Prediction

 

读后感

 

核心就是将graph attention network应用到ETA中。

 

核心内容

 

问题

 

对于WDR来说,只要起终点不同,那幺link序列就不同,整个recurrent部分都要重新计算。WDR的recurrent结构复杂,所以,WDR整体耗时非常严重。

 

场景特点

空间聚集性:选派司机时,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更加相似。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注