(WDR) Learning to Estimate the Travel Time

严重申明:本篇文章所有信息从论文、网络等公开渠道中获得,不会透露滴滴地图 ETA 任何实现方法。

这篇论文是滴滴时空数据组 2018 年在 KDD 上发表的关于在 ETA 领域应用深度学习的文章,里面提到模型和技巧大家都应该耳熟能详,最大亮点是工业界的创新。

说点题外话 你为什么从滴滴出行离职? - 知乎 中提到一点:

8.同年大跃进,在滴滴中高层的眼里,没有BAT。滴滴单量超淘宝指日可待,GAFA才是滴滴要赶超的对象。百度系,LinkedIn系,学院派,uber帮,联想系,MBB就算了,据说连藤校都混成了一个小圈子。。一个项目A team ,B team。一个ETA,投入了多少人力自相残杀?MAPE做到0%又如何?用户体验就爆表了吗?长期留存就高枕无忧了吗?风流总被雨打风吹去,滴滴是二龙山,三虫聚首?是不是正确的事情不知道,反正跟着公司大势所趋,升D10保平安。

简单介绍一下背景:ETA 是 Estimate Travel Time 的缩写,中文大概能翻译成到达时间估计。这个问题描述是:在某一个时刻,估计从 A 点到 B 点需要的时间。对于滴滴,关注的是司机开车把乘客从起点送到终点需要的时间。抽象出来 ETA 就是一个时间空间信息相关的回归问题。CTR 中常用的方法都可以在这里面尝试。

对于这个问题:文章首先提到一个最通用的方法 Route ETA:即在获得 A 点到 B 点路线的情况下,计算路线中每一段路的行驶时间,并且预估路口的等待时间。最终 ETA 由全部时间相加得到。这种方法实现起来很简单,也能拿到一些收益。但是仔细思考一下,没有考虑未来道路的通行状态变化情况以及路线的拓扑关系。针对这些问题,文章中提到滴滴内部也有利用 GBDT 或 FM 的方法解决 ETA 问题,不过没有仔细写实现的方法,我也不好继续分析下去。

评价指标

对于 ETA 问题来说,工业界和学术界常用的指标是 MAPE(mean absolute percentage error),\({y_i}\) 是司机实际从 A 点到 B 点花费的时间,\({f(x_i)}\) 是 ETA 模型估计出来的时间。得到计算公式如下:

\[{min_f \sum_{i=1}^{N}\frac{|y_i - f(x_i)|}{y_i}}\]

多说一句,如果使用 GBDT 模型实现 ETA 时,这个损失函数的推导有点困难,全网也没有看见几个人推导过。

这个公式主要考虑预估时间偏差大小对用户感知体验的影响,目前我们更加关心极端 badcase 对用户的影响。

特征

  • 特征:
    • 空间特征:路线序列、道路等级、POI等
    • 时间特征:月份、星期、时间片等
    • 路况特征:道路的通行速度、拥堵程度
    • 个性化信息:司机特征、乘客特征(有「杀熟」风险)、车辆特征
    • 附近特征:天气、交通管制

模型

模型包含 3 个部分:

  • Wide Learning Models:Wide & Deep 这一部分使用的是 LR + 特征工程,希望模型能记忆一部分的模型。这篇论文中直接利用交叉积学习,减少手动特征工程。
  • Deep Neural Networks:对 sparse feature 做一次 Embedding,使用 3 层 MLP 和 ReLU 的网络。
  • Long-Short Term Memory:前两部分模块没用使用路线序列特征,所以这部分采用 LSTM 抽取路线特征。由于路线序列是不定长的,论文中的模型是使用最后一个隐藏状态,我们也可以把全部的隐藏状态 reduce_sum 输入到最后的模块。
  • Regressor: 将 3 个模型的输出综合起来,作为最后的 ETA 预估。MAPE 作为损失函数,利用 BP 训练模型。
WDR
WDR

上面模型中使用的特征分类:

  • Dense feature:行程级别的实数特征,比如起终点球面距离、起终点 GPS 坐标等。
  • Sparse feature:行程级别的离散特征,比如时间片编号、星期几、天气类型等。
  • Sequential feature:link 级别的特征,实数特征直接输入模型,而离散特征先做 embedding 再输入模型。注意,这里不再是每个行程一个特征向量,而是行程中每条 link 都有一个特征向量。比如,link 的长度、车道数、功能等级、实时通行速度等。

评估

包括两部分:离线评估和在线评估。

离线评估中取滴滴 2017 年北京前6个月的订单数据,分成两类 pickup (平台给司机分单后,司机开车去接乘客的过程)和 trip (司机接到乘客并前往目的地的过程)。具体数据集划分如下。

离线效果
离线效果

离线使用 MAPE 来评价模型。在线评估时,为了更好的与用户体验挂钩,采用多个指标来衡量 ETA 的效果。包括:

  • APE20: absolute percentage error 小于 20% 的订单占比。(越大越好)
  • Badcase率:APE 大于 50% 或者 AE 大于 180s 的订单占比,定义为对用户造成巨大影响的情况。(越小越好)
  • 低估率:低估订单的比例。(越小越好)

离线结果如下图所示,说来汗颜 PTTE 和 TEMP 是什么算法我都不知道…… WD-MLP 指的是将 WDR 中的 R 部分换成 MLP 。最终 WDR 较 route-ETA 有巨大提升,而且 LSTM 引入的序列信息也在 pikcup 上提升了 0.75%。文章的最后还提出来,LSTM 也可以换成是 Attention,这样替换有什么优点和缺点留给大家思考。

pickup 和 trip 效果
pickup 和 trip 效果

在线实验结果如下图所示,滴滴 ETA MAPE 明显小于 com1、com2、com3 ,这三家地图公司具体是哪三家,大家也能猜到吧。

线上实验效果
线上实验效果

ETA 服务工程架构

工程架构
工程架构

从上面的图中可以看出 ETA 服务工程架构主要包括三个部分:

  • Data Aggregation:包括利用 Map Matching 将司机上传到平台的 GPS 对应到滴滴的 Map Info 中得到司机真实行驶过的路线信息,Order Context 指的是订单相关的信息,augmented Data 额外数据比如上文说的交通情况相关信息。
  • Offline Training:利用上一步得到的历史数据训练模型。这里可以值得一提的是,ETA 模型是和时间强相关的(节假日和工作日的数据分布明显不同),所以在文章中作者指出将拿出最新的一部分数据用来 fine-tune 训练出来的 WDR 模型。
  • Online Service:这里需要一个完整的模型服务系统,其他公司也有很多分享,所以原文没有多提。

FMA-ETA: Estimating Travel Time Entirely Based on FFN With Attention

模型架构
模型架构
  • 大学实验报告级别的论文 简单记录一下,不详细评价
  • WDR 模型中 RNN 耗时长,探索基于 Attention 机制的模型
  • 将特征分组(multi-factor)去做 Attention 效果比多头要好
  • 实验结果给出的理由有点牵强。 > The deep modules with attention achieve better results than WDR on MAE and RMSE metrics, which means attention mechanism can help to extract features and sole the long-range dependencies in long sequence.
  • 说预测时延减少,也没有提供线上数据。
  • 最后,不公开代码、不公开数据、SOTA 是 WDR,图一乐。

总结

从上面简单的介绍来看,ETA 可以使用 CTR 和 NLP 领域的很多技术,大有可为。最后,滴滴 ETA 团队持续招人中(社招、校招、日常实习等),感兴趣者快快和我联系。

参考