全文共 7263 个字，阅读大概需要 10 分钟
来源：AI科技评论
ID: aitechtalk
某个周末晚上，小陈约好了和女朋友去商场吃饭看电影。
小陈平时喜爱打游戏，此时正在专心打农药。
“啊！ZZ队友送人头，白瞎我最强亚索！伤心～”
而小陈的女朋友这个时候打来了电话：“你收拾好了吗？我已经到口红啦……”
小陈内心：“这次竟然这么快？我还以为刚到眉毛呢，可是我还想再开一局逆风翻盘拿五杀呢！但是又不能迟到啊……
小陈想到先点开打车软件计算一下双方的时间吧：
首先设置好出发地为女朋友家，目的地为要去的商场，呼叫快车，显示要30分钟。
再来设置一下自己的出发地，呼叫快车，哇！只要15分钟。
小陈于是决定再开一局，一套“行云流水”的操作下来之后，成功“助力”自己一方被五杀，望着被推倒的水晶塔，小陈内心“开心无比”，心想这局胜利的关键果然在自己身上啊！
后来小陈准时赶到女朋友之前赴约......
小陈心想这软件预估到达的时间真是准啊，多亏了它，农药也打了，约会也没迟到。
相信以上类似场景大家多少都有遇到过，大家近些年逐渐习惯用网约车，而以滴滴为代表的网约车软件背后必须要提供各方面精准的服务。
这其中就涉及到一个至关重要的基础问题：预估到达时间（Estimated Time of Arrival, ETA）。
在滴滴、Uber、Lyft等共享出行平台，时间预测的精度会直接关系到路径选择的合理性、订单分配的精确性和交通系统的整体效率，从而影响乘客的出行体验，以及司机的效率和收入；而且，海量的日均调用量也会对ETA模型的线上推理速度提出非常高的要求。
ETA的复杂性和挑战性，使其成为颇具学术研究价值的问题。它要考虑交通要素的空间关系和交通系统的时间特性，也要引入个性化特征和外部特征的建模。这些特点使得机器学习成为很好的ETA解决方案，能够利用海量交通数据来建模行程时间分布。
在今年的KDD2020大会上，滴滴发表了一篇题为《CompactETA: A Fast Inference System for Travel Time Prediction》的论文，详细介绍了如何在线上部署中实现微秒级的ETA机器学习解决方案。
这种名为CompactETA的新算法是滴滴在此前论文《Learning to Estimate the Travel Time》（KDD2018）的算法框架的基础上提出的，它能基于图注意力网络（Graph Attention Network）将高阶的时空依赖关系编码到特征表示中，并进一步使用了位置编码技术（Positional Encoding）来保留行驶路径的序列信息。相比前一代方案，CompactETA实现了超过100倍的线上加速，平均响应时间低于50us。
01
ETA可建模成机器学习问题
直观来看，ETA系统要预测从地图上一点移动到另外一点所花费的时间。这是一个广泛存在的概念，航班、火车、汽车、单车骑行、快递和外卖都有对应的ETA预测任务。
下面是一个示意图，假设用户从左上方的起点出发，想要前往右下角的终点，ETA系统将结合路网状态和用户信息对这段行程花费的时间做一个预估（图中示例的25分钟）。
ETA的应用在滴滴平台上无处不在。
例如以下场景：
1、选定目的地之后，乘客首先看到就是预估接驾时间和预计到达终点的时间。前者告诉乘客大约多久之后司机可以到达他指定的出发点，后者给了乘客关于旅途时长的一个预测。如果这两个时间足够准确，乘客便会对行程有合理的心理预期，便于高效安排自己的事务。
2、除了显示时间之外，其实还有一个数字隐藏了ETA的贡献，那就是预估价格。滴滴平台综合了行程距离和ETA等信息，按照计价规则提前估计一个金额供乘客参考。这些都是用户直观可感受的。
3、在用户看不到的后台，ETA当然也是滴滴的派单引擎和调度引擎的重要决策信息之一。在滴滴，ETA服务的日均调用量已经达到百亿级别，想要提升网约车双边交易的效率，精准的ETA是重要基础之一。
当人们想要预估一次行程时间时，至少有三个信息是必要的：谁、何时出发，以及走哪条路。放在网约车平台，这三个信息对应着：司机ID、出发时刻和行驶路径。这三个必要信息构成了ETA的query，即：
其中司机ID和出发时刻都是标量，而行驶路径是一个向量，由一系列的路段ID组成。把路段称作Link。那么路径可以表示为：
其中的各个L代表了Link的ID。根据query中的三项输入，可以在特征库中查询并构造出丰富的特征，车型、车龄、驾龄等画像信息，这些都可能对行车速度有影响。利用出发时刻，可以得到当前的天气信息、道路限行信息、交通管制信息等。
出发时刻本身输入到模型中也帮助了对周期性交通规律的建模。利用行驶路径就可以查询到该行程经过了哪些路，这些路的静态物理属性是怎样的（封闭快速路/乡镇村道，车道数，限速，红绿灯情况等）；同时还能知道这些路的动态属性，通常指的是路况，描述了路网当前的通行拥堵情况。
所有特征会分为两类：
第一类是全局特征，描述了行程级别的基本信息。对于每个样本来说，它记录成一个向量。
第二类是道路特征，描述了行程的link序列细节，对于每个样本来说，它记录成一个矩阵。每一列描述了一个link的特征向量。例如，在下图中，左边的天气类型构成了全局特征的一维；而右边的link特征，每个link都有对应维度记录自己的长度和通行速度值。
在输入模型之前，不同类型的特征会进行变换。离散特征先通过各自对应的embedding层，然后与连续特征拼接起来。全局特征和道路特征都采用这种做法。
基于query构造完特征之后，就可以设计模型学习出从特征到行程时间预估的一个映射，这是一个典型的回归问题：
。
02
ETA机器学习方案的一些探索性工作
在滴滴团队于2018年发表的《Learning to Estimate the Travel Time》一文中，首次提出了系统性的ETA机器学习解决方案。
其中，Wide-Deep-Recurrent（WDR）深度神经网络模型取得了很好的精度。WDR的细节可参考之前的解读文章，接下来简要介绍一下团队在WDR之后的一些思考和探索。
首先是数据稀疏性问题。尽管滴滴有着庞大的轨迹数据，但在时间、空间和人这三个维度的组合面前，却还没有达到充足。在WDR（以及大部分深度学习模型）中，link ID都以embedding的方式处理。
一旦某个link的历史数据太少，那么它的embedding vector就容易处于欠拟合状态，影响了整体ETA预测的准确性，我们把这称之为空间稀疏性问题。
为了解决这个问题，团队做了一个工作：基于路况分布来度量不同link的相似性，并利用metric learning来对link的embedding vector进行训练。这个思路类似于迁移学习，把热门link的知识迁移到缺少数据但是通行模式相似的冷门link上。
除了空间稀疏性问题，对应的还有时间稀疏性和司机稀疏性的问题，它们是数据在不同时段和司机上的分布不均导致的。我们同样用了metric learning的方法来处理司机稀疏性，用他们的驾驶习惯来度量相似性。
而对于时间稀疏性，我们尝试了给相邻时段的embedding vector设置共享参数，使得相邻时段的embedding vector更加相似。
除了稀疏性问题，我们也关心当规划路线不存在的场景下如何进行ETA预测。本质上看，这需要把起终点之间多种可能的路线都学习到模型中。
团队针对性地提出用图相关的算法来隐式地对路线进行建模，同时采用了multi-task learning的框架，不光预测行程时间，也预测行程距离，通过多任务的相互协同来加强ETA的准确性。这个工作已经发表在KDD 2018上（Multi-task Representation Learning for Travel Time Prediction）。
此外，考虑到路网天然是一个拓扑图，我们也关注把图卷积方法应用在ETA和路况预测任务上。这方面可以关注同样在KDD 2020上的《HerETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival》。
当然，作为工业级应用，WDR最大的瓶颈还是在于线上推理速度。
模型中recurrent结构消耗了相当大的计算资源。一次典型的ETA计算耗时长达几毫秒，如果服务器负载较高，响应时间甚至会到几十毫秒。这样的服务效率，在传统互联网应用中算是非常高的，但在共享出行领域，却还是重要的系统瓶颈之一，也产生了较大的机器成本。
因此，在提出了ETA的机器学习解决方案后团队就把主要精力放在提升ETA推理速度上。同时，也希望精度不要有所降低。这就是本文要介绍的CompactETA的产生背景。
03
既准又快的ETA
对出行平台降本提效有重要意义
ETA在网约车后台服务中发挥着重要作用，比如分单引擎、拼车引擎和运力调度等。为了实现整体交通系统的最优调度，分单引擎需要计算每个司机去接每个乘客的ETA，由此来综合统筹片区内的情况，尽最大可能保证司机和乘客的有效分配。
再比如，既要提升交通效率，又要满足个性化出行需求，拼车是很有潜力的解决方案。以路径规划、ETA为代表的地图算法在拼车中扮演着重要的角色。拼车的顺路程度不仅由距离决定，时间也是重要参考。过长的绕行时间同样会给乘客体验和司机效率带来严重伤害。
作为一项重要的工业级应用，ETA仅仅是精度高还远远不够。以拼车ETA调用量为例，如下图所示，假设仅考虑10名司机和20名乘客，引擎想要计算出最佳的双拼方案，那么就需要知道每一种组合的预估接驾时间。这里，总共有10x20x19=3800种司机和乘客的组合。
假如有一天，乘客愿意接受短距离调度，比如走几十米到更佳的上车点（乘客走几十米，比如过天桥或出园区，有可能让司机少绕路几百米甚至几公里），那么我们要为每个乘客考虑附近的多个上车点，并且寻找最优的整体路线。假如候选上车点为5个，接驾路径的组合数迅速爆炸为3800x5x5=95000。为了求解10名司机和20名乘客的最佳拼车接驾方案（哪个司机接哪两个乘客，顺序如何），我们可能面临至少95000次ETA调用。在全国范围内，类似的计算还要重复成千上万遍。
我们当然可以采用各种组合优化的近似算法来降低ETA的调用量，或者调用更快但相对不准的降级ETA服务，但这都会损害解的最优性。在共享出行平台，为了支持庞大的业务，ETA计算占据的服务器资源非常大。一个既准又快的ETA服务方案不仅能支持更复杂的业务策略，而且还能明显降低成本。
04
CompactETA设计思路
提到神经网络加速，首先让人想到的是近年来流行的模型压缩方法，又或者是采用GPU的整型计算来降低浮点数精度进行推理。如果优化得当，这些手段确实能取得几倍的性能提升，但这还远远不够。我们希望实现更可观的加速，因此分析了业务和模型更深层次的特点，尝试站在一个更全面的角度来设计快速推理的ETA。
经典的线上机器学习系统，比如图像分类，处理各个query的流程是解耦的。一张图片的推理计算与其它图片无关。但是ETA的query分布有自身的特点，具有明显的聚集现象，总的来说可以分为两个方面：
（1）空间聚集性。
派单场景的ETA query来源于邻近区域内的司机乘客产生的接送组合。这一批路线虽然起终点各不相同，但其中重叠的link非常多。比如下图，我们想知道某个乘客被周围各个司机接驾的ETA，最后那一段路线很大概率是重复的。
（2）时间聚集性。
ETA query不仅在空间上聚集，时间上也呈现聚集现象。大部分乘客在呼叫车辆时，都可能在短时间内经过好几轮的派单尝试，由此产生的ETA query在时间上非常接近。比如下图，第二轮派单时相比第一轮派单，司机又移动了几十米，两条路线有很多重复的地方。但与多个司机同时产生路线的情形不同，这是一个司机在多个时间产生的路线，我们要确保这段时间内道路特征没有发生变化，才能认为这两次计算有冗余的地方。
事实上，道路特征确实不是实时变化的，而是有一定的更新周期。更新最快的是路况信息，工业界更新频率较高的平台一般采用2分钟发布一版路况的做法。对于其它特征，比如车道等属性来说，更新周期为地图测绘的间隔，通常是天级别的。因此，在两次间隔不长的ETA query中，重合路线的特征是完全不变的（只要不横跨多个路况更新周期）。
对于WDR来说，只要起终点不同，那么link序列就不同，整个recurrent部分都要重新计算。有没有办法让这些聚集的query共享计算结果呢？我们首先尝试了一个思路：把端到端整体预测的方式改为对每个link单独预测时间然后求和的方式。但在滴滴的实践中发现，大量link过短过碎导致时间误差较大，求和之后误差可能进一步积累放大。另外，link时间求和的方式也阻碍了个性化信息在模型中的充分表达，影响了整体的准确性。
最终，我们决定对每个link抽取高层级的表示（high level representation），然后对表示向量求和而不是直接对时间求和。在最后阶段，保留了一个精简的MLP模型，将个性化信息和link表示之和进行融合。各个link的表示向量可以独立于query定期更新。当两个query的路线有大量重复时，它们可以充分复用这些重合link的表示向量。在这样的思路指导下，我们设计了CompactETA模型，相比WDR它有几个根本性的改进：
（1）Graph Attention Network取代了LSTM的位置。在WDR中，邻近link的依赖关系通过LSTM的序列学习能力来建立；而在CompactETA中，link之间的依赖关系通过学习路网的拓扑结构来建立。
（2）移除了wide和deep部分。为了把query到达之后的计算量压缩到极致，我们选择了直接把全局特征输入到最终的MLP中，而不再经过wide和deep部分，这在一些情况下会对精度有少许影响。
（3）增加了位置编码。这一操作是为了尽可能地保留link的序列信息。在求和操作中，link的顺序完全不影响结果，这与我们的直觉相违背——先走哪条路再走哪条路对整体行程时间是有影响的。这个问题同样存在于NLP任务中，当模型从RNN演化为Attention结构时，单词的顺序信息也被丢失了。我们借鉴了Transformer的解决方案，用三角函数生成了一系列关于位置的编码。但与Transformer不同的是，直接把PE加到表示向量上对于求和操作依然没有任何作用，所以我们采用了更加激进的乘法方式来使用位置编码。
最终，CompactETA的设计结构如下图所示。在线上部署中，Graph Attention Network构成了updater模块，每当感知到新版路况时，就为地图中每一个link计算它的表示向量。这些表示向量被存在一个内存表中，并及时推送到predictor模块。真正的实时计算发生在predictor中。当一个ETA query到来时，服务仅仅执行了查表、求和等简单操作，加上一个128维隐层的MLP计算。这些计算是非常快的，即便CPU机器也能在若干微秒内完成。
CompactETA的优势有两方面。
第一，它响应速度非常快。只有发生在predictor上的计算会影响query响应时间，而updater的计算与此是完全隔离的。
第二，它节约了非常多的计算量。如前所述，空间聚集和时间聚集的query大量共享了同一批link表示向量，整体计算量有了大幅下降。
05
实验表明CompactETA推理速度大幅提升
模型的准确性经过了离线和在线评估，而服务性能指标由实际压测给出。结果可以总结为：CompactETA推理速度比state-of-the-art模型快了超过100倍，同时准确性非常接近。以下详述。
在北京、苏州和沈阳的离线评测中，相比于WDR模型，CompactETA的MAPE指标最多变差了0.21%（北京接驾场景）。对于大多数业务来说，这个精度差异已经很难被感知了。比如，20分钟的行程，平均预测误差仅变大了2.52秒（0.21%）。
在线上实验中，考虑到网约车双边市场不适宜做简单的随机分配流量，实验分别进行了A/A阶段和A/B阶段。在A/A阶段中，对照组（WDR）和实验组（WDR）天然有2%左右的噪声波动。而在A/B阶段中，我们观察到对照组（WDR）和实验组（CompactETA）的差异水平也在2%左右。服务指标方面，测试服务器配备了Intel Xeon E5-2670 2.3GHz的48核CPU，机器内存是128GB。
不同并发量下的压力测试表明，CompactETA的单机峰值QPS高达93.4万，平均响应时间在中低负载下可以稳定控制到50us以内。作为对比，WDR模型的单机峰值QPS仅为0.7万，且无论何种负载水平下，平均响应时间都超过了CompactETA的100倍。
06
总结
ETA服务是共享出行的基础设施之一,本文介绍了CompactETA这种能够高速进行线上推理的模型，也梳理了本团队在ETA方向上的系统性工作以及相关思考。
高效率的ETA服务一方面可以突破新业务形态的计算瓶颈，另一方面也能显著降低现有业务的成本。低成本且高精度的ETA，是出行企业进行运力智能调度和精细化运营的基础。除了出行之外，也有潜力服务于电子地图、外卖、物流以及无人车调度等领域。ETA还有不少有价值的问题值得探讨，期待感兴趣的同行和我们交流,一同进步！
滴滴KDD2020论文解析系列
滴滴KDD2020论文(一) | 实时事件嵌入学习的动态异质图神经网络
滴滴KDD2020论文(二) | 一种新奇且通用的面向在线推荐的异构图信息融合框架
滴滴KDD2020论文(三) | 为客服构建更加智能的对话机器人
滴滴KDD2020论文(四) | 更精确地预估到达时间，新提出异质时空图卷积网络