引言
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 优化成果显著。