到达时间预测两则: Uber 和美团

| ~ |

Uber: DeepETA (Transformer)

参考

预测到达时间 (ETA, estimated time of arrival) 显然对 Uber 很重要 (最高 QPS 的服务). 传统方法把道路网分割为小路段, 每个路段表示为图中的带权边, 找出图中最短路径即得 ETA. 为考虑别的因素, 用机器学习预测 “真实到达时间和传统方法得到的 ETA” 的差值 (residual).

之前用 XGB ensemble. Eventually, we reached a point where increasing the dataset and model size using XGBoost became untenable. (为啥不行?) We decided to explore deep learning because of the relative ease of scaling to large datasets using data-parallel SGD. (树模型应该也有并行算法?)

目标有三个

  • 时延: 毫秒级
  • 准确度: MAE 要胜过 XGB
  • 通用性: 用于 Uber 所有业务线

模型

在表格数据上用 Transformer, 其中 attention 可以学到特征之间的交互. Uber 实践中将连续变量按照分位数分桶效果更好.

其中地理位置有很多粒度, embedding 用下述第三种方式处理

  • Exact indexing, which maps each grid cell to a dedicated embedding. This takes up the most space.
  • Feature hashing, which maps each grid cell into a compact range of bins using a hash function. The number of bins is much smaller than with exact indexing.
  • Multiple feature hashing, which extends feature hashing by mapping each grid cell to multiple compact ranges of bins using independent hash functions. See Figure 5:

加速

用了 linear transformer. 对于 $K$ 个 $d$ 维输入, 原始 transformer 时间复杂度为 $O(K^2d)$, 而 linear transformer 为 $O(Kd^2)$, 只要 $K > d$ 就能加速 (不严谨, 要看它们差的数量级和 big o 前面的常数).

模型层数少, 参数主要在 embedding 层. 把连续输入离散化也便于直接找 embedding 从而加速.

通用化

模型的总体架构如下

The decoder is a fully connected neural network with a segment bias adjustment layer. This approach performs better than simply adding segment features to the model. The reason we implemented a bias adjustment layer instead of a multi-task decoder is due to latency constraints.

Further reading

美团: GBDT 到 DeepFM

参考

外卖场景比打车更复杂.

  • 外卖场景 ETA 对用户和骑手都很重要; 而打车场景用户更关心能否打到车, 司机也不会特别 care 这个.
  • 外卖场景环节更多: 骑手 (接-到-取-送), 商户 (出餐), 用户 (交付), 还要经历室内室外的场景转换 (上下楼).

17 年的时候美团还是 GBDT 构造特征 + 线性回归. 迭代路径类似 CTR, 转向用 DeepFM 以及自定义的网络.

推荐阅读业务全景描述, 非常 informative

特征

  • 离线特征
    • 商户画像: 商户平均送达时长, 到店时长, 取餐时长, 出餐状况, 单量, 种类偏好, 客单价, 平均配送距离
    • 配送区域画像: 区域运力平均水平, 骑手规模, 单量规模, 平均配送距离
  • 在线特征
    • 商家实时特征: 商家订单挤压状况, 过去 N 分钟出单量, 过去 N 分钟进单量
    • 区域实时特征: 在岗骑手实时规模, 区域挤压 (未取餐) 单量, 运力负载状况
    • 订单特征: 配送距离, 价格, 种类, 时段
    • 天气数据: 温度, 气压, 降水量

在实际配送中, 我们都会要求骑手在完成交付后进行签到, 这样就会积累大量的上报数据, 对于后续进行精细化挖掘非常有帮助.

其他

智能配送运筹优化相关