(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等
    • 时间特征:月份、星期、时间片等
    • 路况特征:道路的通行速度、拥堵程度
    • 个性化信息:司机特征、乘客特征、车辆特征
    • 附近特征:天气、交通管制

模型

WDR 模型,包含 3 个部分: - Wide Learning Models:利用交叉积学习信息,泛化能力。 - Deep Neural networks:对 sparse feature 做一次 Embedding,使用 3 层 MLP 和 ReLU 的网络。 - Long-Short Term Memory:解决 Wide & Deep 没用使用路线的顺序特征,利用 LSTM 学习 link 信息以及序列信息,最后一个单元的隐藏状态作为输出。 - Regressor: 将 3 个模型的输出综合起来,作为最后的 ETA 预估。MAPE 作为损失函数,利用 BP 训练模型。

-w962
-w962

上面模型中使用的特征分类: - 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,这样替换有什么优点和缺点留给大家思考。

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

ETA 服务工程架构:

-w486
-w486

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

总结

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

参考