深度学习在美团配送ETA预估中的探索与实践
1.背景
ETA（Estimated Time of Arrival，“预计送达时间”），即用户下单后，配送人员在多长时间内将外卖送达到用户手中。送达时间预测的结果，将会以"预计送达时间"的形式，展现在用户的客户端页面上，是配送系统中非常重要的参数，直接影响了用户的下单意愿、运力调度、骑手考核，进而影响配送系统整体成本和用户体验。
对于整个配送系统而言，ETA既是配送系统的入口和全局约束，又是系统的调节中枢。具体体现在：
- ETA在用户下单时刻就需要被展现，这个预估时长继而会贯穿整个订单生命周期，首先在用户侧给予准时性的承诺，接着被调度系统用作订单指派的依据及约束，而骑手则会按照这个ETA时间执行订单的配送，配送是否准时还会作为骑手的工作考核结果。
- ETA作为系统的调节中枢，需要平衡用户-骑手-商家-配送效率。从用户的诉求出发，尽可能快和准时，从骑手的角度出发，太短会给骑手极大压力。从调度角度出发，太长或太短都会影响配送效率。而从商家角度出发，都希望订单被尽可能派发出去，因为这关系到商家的收入。
在这样多维度的约束之下，外卖配送的ETA的建模和估计会变得更加复杂。与打车场景中的ETA做对比，外卖场景的ETA面临如下的挑战：
- 外卖场景中ETA是对客户履约承诺的重要组成部分，无论是用户还是骑手，对于ETA准确性的要求非常高。而在打车场景，用户更加关心是否能打到车，ETA仅提供一个参考，司机端对其准确性也不是特别在意。
- 由于外卖ETA承担着承诺履约的责任，因此是否能够按照ETA准时送达，也是外卖骑手考核的指标、配送系统整体的重要指标；承诺一旦给出，系统调度和骑手都要尽力保证准时送达。因此过短的ETA会给骑手带来极大的压力，并降低调度合单能力、增加配送成本；过长的ETA又会很大程度影响用户体验。
- 外卖场景中ETA包含更多环节，骑手全程完成履约过程，其中包括到达商家、商家出餐、等待取餐、路径规划、不同楼宇交付等较多的环节，且较高的合单率使得订单间的流程互相耦合，不确定性很大，做出合理的估计也有更高难度。
下图是骑手履约全过程的时间轴，过程中涉及各种时长参数，可以看到有十几个节点，其中关键时长达到七个。这些时长涉及多方，比如骑手（接-到-取-送）、商户（出餐）、用户（交付），要经历室内室外的场景转换，因此挑战性非常高。对于ETA建模，不光是简单一个时间的预估，更需要的是全链路的时间预估，同时更需要兼顾"单量-运力-用户转化率"转化率之间的平衡。配送ETA的演变包括了数据、特征层面的持续改进，也包括了模型层面一路从LR-XGB-FM-DeepFM-自定义结构的演变。
具体ETA在整个配送业务中的位置及配送业务的整体机器学习实践，请参看《机器学习在美团配送系统的实践：用技术还原真实世界》。
2.业务流程迭代中的模型改进
2.1 基础模型迭代及选择
与大部分CTR模型的迭代路径相似，配送ETA模型的业务迭代经历了LR->树模型->Embedding->DeepFM->针对性结构修改的路径。特征层面也进行不断迭代和丰富。
- 模型维度从最初考虑特征线性组合，到树模型做稠密特征的融合，到Embedding考虑ID类特征的融合，以及FM机制低秩分解后二阶特征组合，最终通过业务指标需求，对模型进行针对性调整。
- 特征维度逐步丰富到用户画像/骑手画像/商家画像/地址特征/轨迹特征/区域特征/时间特征/时序特征/订单特征等维度。
目前版本模型在比较了Wide&Deep、DeepFM、AFM等常用模型后，考虑到计算性能及效果，最终选择了DeepFM作为初步的Base模型。整个DeepFM模型特征Embedding化后，在FM（Factorization Machine）基础上，进一步加入deep部分，分别针对稀疏及稠密特征做针对性融合。FM部分通过隐变量内积方式考虑一阶及二阶的特征融合，DNN部分通过Feed-Forward学习高阶特征融合。模型训练过程中采取了Learning Decay/Clip Gradient/求解器选择/Dropout/激活函数选择等，在此不做赘述。
2.2 损失函数
在ETA预估场景下，准时率及置信度是比较重要的业务指标。初步尝试将Square的损失函数换成Absolute的损失函数，从直观上更为切合MAE相比ME更为严苛的约束。在适当Learning Decay下，结果收敛且稳定。
同时，在迭代中考虑到相同的ETA承诺时间下，在前后N分钟限制下，早到1min优于晚到1min，损失函数的设计希望整体的预估结果能够尽量前倾。对于提前部分，适当降低数值惩罚。对于迟到部分，适当增大数值惩罚。进行多次调试设计后，最终确定以前后N分钟以及原点作为3个分段点。在原先absolute函数优化的基础上，在前段设计1.2倍斜率absolute函数，后段设计1.8倍斜率absolute函数，以便让结果整体往中心收敛，且预估结果更倾向于提前送达，对于ETA各项指标均有较大幅度提升。
2.3 业务规则融入模型
目前的业务架构是"模型+规则"，在模型预估一个ETA值之后，针对特定业务场景，会有特定业务规则时间叠加以满足特定场景需求，各项规则由业务指标多次迭代产生。这里产生了模型和规则整体优化的割裂，在模型时间和规则时间分开优化后，即模型训练时并不能考虑到规则时间的影响，而规则时间在一年之中不同时间段，会产生不同的浮动，在经过一段时间重复迭代后，会加大割裂程度。
在尝试了不同方案后，最终将整体规则写入到了TF模型中，在TF模型内部调整整体规则参数。
- 对于简单的(a*b+c)*d等规则，可以将规则逻辑直接用TF的OP算子来实现，比如当b、d为定值时，则a、c为可学习的参数。
- 对于过于复杂的规则部分，则可以借助一定的模型结构，通过模型的拟合来代替，过多复杂OP算子嵌套并不容易同时优化。
通过调节不同的拟合部分及参数，将多个规则完全在TF模型中实现。最终对业务指标具备很大提升效果，且通过对部分定值参数的更改，具备部分人工干涉模型能力。
在这里，整体架构就简化为多目标预估的架构，这里采用多任务架构中常用的Shared Parameters的结构，训练时按比例采取不同的交替训练策略。结构上从最下面的模型中间融合层出发，分别在TF内实现常规预测结构及多个规则时间结构，而其对应的Label则仍然从常规的历史值和规则时间值中来，这样考虑了以下几点：
- 模型预估时，已充分考虑到规则对整体结果的影响（例如多个规则的叠加效应），作为整体一起考虑。
- 规则时间作为辅助Label传入模型，对于模型收敛及Regularization，起到进一步作用。
- 针对不同的目标预估，采取不同的Loss，方便进行针对性优化，进一步提升效果。
模型结构在进行预估目标调整尝试中：
- 尝试过固定共享网络部分及不固定共享部分参数，不固定共享参数效果明显。
- 通常情况下激活函数差异不大，但在共享层到独立目标层中，不同的激活函数差异很大。
2.4 缺失值处理
在模型处理中，特征层面不可避免存在一定的缺失值，而对于缺失值的处理，完全借鉴了《美团“猜你喜欢”深度学习排序模型实践》文章中的方法。对于特征x进入TF模型，进行判断，如果是缺失值，则设置w1参数，如果不是缺失值则进入模型数值为w2*x，这里将w1和w2作为可学习参数，同时放入网络进行训练。以此方法来代替均值/零值等作为缺失值的方法。
3.长尾问题优化
3.1 模型预估结果+长尾规则补时
基础模型学习的是整体的统计分布，但对于一些长尾情形的学习并不充分，体现在长尾情形下预估时间偏短（由于ETA拥有考核骑手的功能，预估偏短对骑手而言意味着很大的伤害）。故将长尾拆解成两部分来分析：
- 业务长尾，即整体样本分布造成的长尾。主要体现在距离、价格等维度。距离越远，价格越高，实际送达时间越长，但样本占比越少，模型在这一部分上的表现整体都偏短。
- 模型长尾，即由于模型自身对预估值的不确定性造成的长尾。模型学习的是整体的统计分布，但不是对每个样本的预估都有“信心”。实践中采用RF多棵决策树输出的标准差来衡量不确定性。RF模型生成的决策树是独立的，每棵树都可以看成是一个专家，多个专家共同打分，打分的标准差实际上就衡量了专家们的“分歧”程度（以及对预估的“信心”程度）。从下图也可以看出来，随着RF标准差的增加，模型的置信度和准时率均在下降。
在上述拆解下，采用补时规则来解决长尾预估偏短的问题：长尾规则补时为 <业务长尾因子 , 模型长尾因子> 组合。其中业务长尾因子为距离、价格等业务因素，模型长尾因子为RF标准差。最终的ETA策略即为模型预估结果+长尾规则补时。
4.工程开发实践
4.1 训练部分实践
整体训练流程
对于线下训练，采取如下训练流程：
Spark原始数据整合 -> Spark生成TFRecord -> 数据并行训练 -> TensorFlow Serving线下GPU评估 -> CPU Inference线上预测
整个例行训练亿级数据多轮Epoch下流程持续约4小时，其中TF训练中，考虑到TF实际计算效率并不是很高，有很大比例在数据IO部分，通过Spark生成TFRecord部分，在此可将速度加速约3.6倍。而在数据并行训练部分，16卡内的并行度扩展基本接近线性，具备良好的扩展性。由于PS上参数量并未达到单机无法承受，暂时未对参数在PS上进行切分。Serving线下GPU评估部分，是整个流程中的非必需项，虽然在训练过程中Chief Worker设置Valid集合可有一定的指标，但对全量线下，通过Spark数据调用Serving GPU的评估具备短时间内完成全部流程能力，且可以指定大量复杂自定义指标。
数据并行训练方式
整个模型的训练在美团的AFO平台上进行，先后尝试分布式方案及单机多卡方案。考虑到生产及结果稳定性，目前线上模型生产采用单机多卡方案进行例行训练。
- 分布式方案：
采用TF自带的PS-Worker架构，异步数据并行方式，利用tf.train.MonitoredTrainingSession协调整个训练过程。整个模型参数存储于PS，每个Step上每个Worker拉取数据进行数据并行计算，同时将梯度返回，完成一次更新。目前的模型单Worker吞吐1~2W/s，亿级数据几轮Epoch耗时在几小时内完成。同时测试该模型在平台上的加速比，大约在16块内，计算能力随着Worker数目线性增加，16卡后略微出现分离。在目前的业务实践中，基本上4-6块卡可以短时间内完成例行的训练任务。
- 单机多卡方案：
采用PS-Worker的方案在平台上具备不错的扩展性，但是也存在一定的弊端，使用RPC的通讯很容易受到其他任务的影响，整个的训练过程受到最慢Worker的影响，同时异步更新方式对结果也存在一定的波动。对此，在线上生产中，最终选取单机多卡的方案，牺牲一定的扩展性，带来整体训练效果和训练速度的稳定性。单机多卡方案采取多GPU手动指定OP的Device，同时在各个Device内完成变量共享，最后综合Loss与梯度，将Grad更新到模型参数中。
TF模型集成预处理
模型训练过程中，ID类特征低频过滤需要用到Vocab词表，连续型特征都需要进行归一化。这里会产生大量的预处理文件，在线下处理流程中很容易在Spark中处理成Libsvm格式，然后载入到模型中进行训练。但是在线上预测时，需要在工程开发端载入多个词表及连续型特征的归一化预处理文件（avg/std值文件等），同时由于模型是按天更新，存在不同日期版本的对齐问题。
为了简化工程开发中的难度，在模型训练时，考虑将所有的预处理文件写入TF计算图之中，每次在线预测只要输入最原始的特征，不经过工程预处理，直接可得到结果：
- 对于ID类特征，需要进行低频过滤，然后制作成词表，TF模型读入词表的list_arr，每次inference通过ph_vals，得到对应词表的ph_idx。
tf_look_up = tf.constant(list_arr, dtype=tf.int64) table = tf.contrib.lookup.HashTable(tf.contrib.lookup.KeyValueTensorInitializer(tf_look_up, idx_range), 0) ph_idx = table.lookup(ph_vals) + idx_bias
- 对于连续型特征，在Spark处理完得到avg/std值后，直接写入TF模型计算图中，作为constant节点，每个ph_in经过两个节点，得到相应ph_out。
constant_avg = tf.constant(feat_avg, dtype=tf.float32, shape=[feat_dim], name="avg") constant_std = tf.constant(feat_std, dtype=tf.float32, shape=[feat_dim], name="std") ph_out = (ph_in - constant_avg) / constant_std
4.2 TF模型线上预测
配送机器学习平台内置了模型管理平台，对算法训练产出的模型进行统一管理和调度，管理线上模型所用的版本，并支持模型版本的切换和回退，同时也支持节点模型版本状态的管理。
ETA使用的DeepFM模型用TensorFlow训练，生成SavedModel格式的模型，需要模型管理平台支持Tensorflow SavedModel格式。
实现方案
S
线上服务加载TensorFlow SavedModel模型有多种实现方案：
- 自行搭建TensorFlow Serving CPU服务，通过gRPC API或RESTful API提供服务，该方案实现比较简单，但无法与现有的基于Thrift的模型管理平台兼容。
- 使用美团AFO GPU平台提供的TensorFlow Serving服务。
- 在模型管理平台中通过JNI调用TensorFlow提供的Java API TensorFlow Java API，完成模型管理平台对SavedModel格式的支持。
最终采用TensorFlow Java API加载SavedModel在CPU上做预测，测试batch=1时预测时间在1ms以内，选择方案3作为实现方案。
远程计算模式
TensorFlow Java API的底层C++动态链接库对libstdc++.so的版本有要求，需要GCC版本不低于4.8.3，而目前线上服务的CPU机器大部分系统为CentOS 6, 默认自带GCC版本为4.4.7。如果每台线上业务方服务器都支持TensorFlow SavedModel本地计算的话，需要把几千台服务器统一升级GCC版本，工作量比较大而且可能会产生其他风险。
因此，我们重新申请了几十台远程计算服务器，业务方服务器只需要把Input数据序列化后传给TensorFlow Remote集群，Remote集群计算完后再将Output序列化后返回给业务方。这样只需要对几十台计算服务器升级就可以了。
线上性能
模型上线后，支持了多个业务方的算法需求，远程集群计算时间的TP99基本上在5ms以内，可以满足业务方的计算需求。
总结与展望
模型落地并上线后，对业务指标带来较大的提升。后续将会进一步根据业务优化模型，进一步提升效果：
- 将会进一步丰富多目标学习框架，将取餐、送餐、交付、调度等整个配送生命周期内的过程在模型层面考虑，对订单生命周期内多个目标进行建模，同时提升模型可解释性。
- 模型融合特征层面的进一步升级，在Embedding以外，通过更多的LSTM/CNN/自设计结构对特征进行更好的融合。
- 特征层面的进一步丰富。
作者简介
- 基泽，美团点评技术专家，目前负责配送算法策略部机器学习组策略迭代工作。
- 周越，2017年加入美团配送事业部算法策略组，主要负责ETA策略开发。
- 显杰，美团点评技术专家，2018年加入美团，目前主要负责配送算法数据平台深度学习相关的研发工作。
背景 工程师主要面对的是技术挑战，更关注技术层面的目标。研发团队的管理者则会把实现项目成果和业务需求作为核心目标。实际项目中，研发团队所需资源（比如物理机器、内存、硬盘、网络带宽等）的成本，很容易被忽略，或者在很晚 ...