文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
本文为美团文章学习的笔记整理。
1. 背景
在点外卖的过程中，骑手的交付时间，即骑手到达用户附近下车后多久能送到用户手中，是一个非常重要的环节。下图是一个订单在整个配送链路的时间构成，时间轴最右部分描述了交付环节在整个配送环节中的位置。交付时间衡量的是骑手送餐时的交付难度，包括从骑手到达用户楼宇附近，到将餐品交付到用户手中的整个时间。
交付时间的衡量是非常有挑战的一件事，因为骑手在送餐交付到用户手中时会碰到不同的问题，例如：骑手一次送餐给楼宇内多个用户，骑手对于特定楼宇寻址特别困难，骑手在交付楼宇附近只能步行，老旧小区没有电梯，写字楼无法上楼，或者难以等到电梯等等。交付时间预估需要具备刻画交付难度的能力，在定价、调度等多个场景中被广泛使用。例如根据交付难度来确定是否调节骑手邮资，根据交付难度来确定是否调节配送运单的顺序，从而避免超时等等。总的来说，交付时间预估是配送业务基础服务的重要一环。
Note:
预估订单交付难度，根据难度调节骑手工资，对交付难度预估模型的准确度有很高要求，因为直接涉及骑手的收入，也涉及到公司的运营成本。
交付时间预估存在如下的困难：
- 输入信息较少，且多为非数值型数据，目前能够被用来预估的仅有如下维度特征：交付地址、交付点的经纬度、区域、城市，适配常规机器学习模型需要重新整理且容易丢失信息。
- 计算性能要求很高。由于是基础服务，会被大量的服务调用，要求很高的性能，其中包括数据处理及RPC的时间。且该标准为CPU环境下的性能要求，而非GPU下的性能要求。
总结起来，交付时间预估的问题，在于需要使用轻量级的解决方案来处理多种数据形式的非数值型数据，并提取有效信息量，得到相对准确的结果。在相同效果的前提下，更倾向于性能更优的方案。
Note:
时间预测要求性能高，更更倾向于性能更优的方案。
交付时间预估迭代了三个版本，分别为基于地址结构的树模型、向量召回方案以及轻量级的End-to-End的深度学习网络。同时介绍了如何在性能和指标之间取舍，以及模型策略迭代的中间历程。
2. 技术迭代路径
2.1 树模型
技术选型
最早也是最容易被考虑到的是利用规则，核心思路是利用树结构衡量地址相似性，尽可能在相似的交付地址上积聚结构化数据，然后利用局部的回归策略，得到相对充裕的回归逻辑，而未能达到回归策略要求的则走兜底的策略。
观察用户填写地址以及联系实际中地址的层级结构，不难发现，一个地址可以由四级结构组成：地址主干词（addr）、楼宇号（building）、单元号（unit）、楼层（floor）。其中的地址主干词在实际中可能对应于小区名或者学校名等地标名称。通过分析，实际交付时长与楼层高低呈正相关关系，且不同交付地址的交付时长随楼层增加的变化幅度也有所区别，所以可以使用线性回归模型拟合楼层信息和交付时长的关系，而地址主干词、楼宇号、单元号作为其层级索引。但用户填写的地址中并不一定包含完整的四级结构，就会存在一定比例的缺失，所以利用这样的层级结构构建成一棵树，然后充分利用上一层已知的信息进行预估。预测时，只需根据结点的分支找到对应的模型即可，如果缺失，使用上一层结构进行预测。对于没有达到训练模型要求数据量的地址，使用其所在的区域平均交付时长作为交付时长的预估结果，这部分也可以看作区域信息，作为树结构的根节点。
Note:
从用户的角度来预估交付时间，聚类地址相似用户。
迭代路径
整体的思路是基于离散特征训练树模型，在树的结点上基于楼层训练线性回归模型。树结点训练分裂规则：（1）数据量大于阈值；（2）分裂后MAE（平均绝对误差）的和小于分裂前。考虑到数据的时效性，采用加权线性回归增加近期数据的权重。
2.2 树模型+向量召回方案
技术选型
向量召回作为主流的召回方案之一，被业界广泛使用，在使用LSH、PQ乘积量化等常用开源工具基础上，高维向量召回性能通常在毫秒量级。
而从算法上考虑，树模型中NLP地址解析结果能够达到模型使用要求的仅为70%+，剩余20%+的地址无法通过训练得到的模型从而只能走降级策略。利用高维向量来表达语义相似性，即利用向量来表达地址相似性，从而用相似数据对应的模型来替代相似但未被召回数据，将地址主干词进行Embedding后，摆脱主干词完全匹配的低鲁棒性。
迭代路径
整个技术路径较为清晰简单，即利用Word2Vec将charLevel字符进行Embedding，获得该地址的向量表示，并且融入GPS位置信息，设计相应兜底策略。
最终效果
比较大地提升了整体策略的召回率，提升了12.20pp，对于未被上一版本树模型召回的地址，指标有了显著的提升，其中ME下降87.14s，MAE下降38.13s，1min绝对偏差率减小14.01pp，2min绝对偏差率减小18.45pp，3min绝对偏差率减小15.90pp。
2.3 End-to-End轻量化深度学习方案
技术选型
在树模型的基础上，迭代到向量召回方案，整个模型的召回率有了较大幅度的增长，但仍然不是100%。分析发现，召回率提升的障碍在于NLP对于地址解析的覆盖率。
整个方案的出发点：
从模型复杂度考虑，同样仅仅使用地址信息的话，在提升模型VC维的基础上，使用其他的模型方案至少可以持平树模型的效果，如果在这基础上还能融入其他信息，那么对于原模型的基线，还能有进一步的提升。
考虑到不仅仅需要使用地址数据，同时需要使用GPS数据、大量ID类的Embedding，对于各类非数值类型的处理灵活性考虑，采用深度学习的方案，来保证多源且多类型特征能在同一个优化体系下优化学习。
工程上需要考虑的点：
交付模型作为基础模型，被广泛应用在路径构造、定价、ETA等各个业务中频繁调用，在树模型版本中，对于性能的要求为平均响应时间5ms，本方案需要考虑沿袭原业务的性能，不能显著增加计算耗时。
交付模型的难点在于非数值型特征多，信息获取形式的多样化，当前的瓶颈并不在于模型的复杂度低。如果可以轻量地获取信息及融合，没必要对Fusion后的信息做较重的处理方案。
所以整体的设计思路为：利用深度学习融合非数值型特征，在简单Fusion的基础上，直接得到输出结构，对于组件的选择，尽可能选用Flops较低的设计。该设计背后意图是，在充分使用原始输入信息，在尽可能避免信息损失的基础上，将非数值型的信息融入进去。并将信息充分融合，直接对接所需要的目标。而选用的融合组件结构尽可能保证高性能，且具备较高学习效率。这里分别针对地址选用了较为Robust的LSTM，针对GPS选用了自定义的双线性Embedding，兼顾性能和效果。
迭代路径
开始采用端到端的深度学习模型，这里首先需要解决的是覆盖率问题，直接采用LSTM读取charLevel的地址数据，经过全连接层直接输出交付时间。作为第一版本的数据，该版本数据基本持平树模型效果，但对于树模型未召回的20%数据，有了较大的提升。
在采用charLevel的地址奏效后，开始采用加入用户地址GPS的信息，由于GPS为经纬度信息，非数值型数据，我们使用一种基于地理位置格点的双线性插值方法进行Embedding。该方案具备一定的扩展性，对不同的GPS均能合理得到Embedding向量，同时具备平滑特性，对于多对偏移较小的GPS点能够很好的进行支持。
最终方案将地址Embedding后，以及GPS点的Embedding化后，加入下单时间、城市ID、区域ID等特征后，再进行特征融合及变换，得到交付模型的时间预估输出。整个模型是一个端到端的训练，所有参数均为Trainable。
Note:
这个方案相对复杂很多，适合规模较大时使用，初期不太适合。
扩展组件
在证实End-to-End路径可行后，我们开始进行扩展组件建设，包括自定义损失函数、数据采样修正、全国模型统一等操作，得到一系列正向效果，并开发上线。
特征重要性分析
对于深度学习模型，我们有一系列特征重要性评估方案，这里采用依次进行Feature Permutation的方式，作为评估模型特征重要性的方式。
本方案的特征重要性：用户地址>GPS经纬度>其它特征。
注：在配送的其他案例中，商户GPS的经纬度重要性>用户地址重要性>用户GPS的经纬度重要性，不同学习目标下可能会有比较明显差别。
最终效果
End-to-End深度学习模型的最终效果较为显著：对于树模型及向量召回方案的最痛点，覆盖率得到彻底解决，覆盖率提升到100%。ME下降4.96s，MAE下降8.17s，1min绝对偏差率减小2.38pp，2min绝对偏差率减小5.08pp，3min绝对偏差率减小3.46pp。同时，对于之前树模型及向量召回方案未能覆盖到的运单，提升则更为明显。
3. 模型相关分析
主要是对向量召回方案及深度学习方案进行了相应的性能分析，以便在线下确认性能指标，最终保证上线后性能均达到要求。
3.1 向量召回性能
最近邻搜索（Nearest Neighbor Search）指的是在高维度空间内找到与查询点最近点的问题。在数据样本小的时候，通过线性搜索就能满足需求，但随着数据量的增加，如达到上百万、上亿点时候，倾向于将数据结构化表示来更加精确地表达向量信息。
此时近似最近邻搜索ANN（Approximate Nearest Neighbor）是一个可参考的技术，它能在近似召回一部分之后，再进行线性搜索，平衡效率和精度。目前大体上有以下3类主流方法：基于树的方法，如K-D树等；基于哈希的方法，例如LSH；基于矢量量化的方法，例如PQ乘积量化。在工业检索系统中，乘积量化是使用较多的一种索引方法。
针对向量召回的工具，存在大量的开源实现，在技术选型的过程中，可以参照ANN-Benchmarks以及Erikbern/ANN-Benchmarks中的性能评测结果。
3.2 序列模块性能
为了评测深度学习交付模型的性能瓶颈，首先对整个模型进行Profile，其中整个计算大部分消耗在序列模块处理部分。需要对序列模块的计算性能进行OP算子的加速。
3.3 向量效果分析
将向量召回与深度学习模型进行横向比较，二者中间过程均生成了高维向量。相较于向量召回，深度学习模型带来的提升主要来自于哪里？有监督的lstm学习到的Embedding向量与自监督的Word2Vec得到的向量在地址相似性计算中有多大差别，孰优孰劣？
首先，我们分析第一个问题，End-to-End模型提升主要来自哪里？
经过测试可知，深度学习模型带来的提升主要来自对地址中冗余信息（相较于向量召回）的利用，其次是多个新特征的加入。另外，对比两个End-to-End模型的效果，地址附属信息中也包含着对匹配地址有用的信息。
针对第二个问题，有监督的End-to-End学习到的Embedding向量，与自监督的Word2Vec得到的向量在地址相似性计算中有多大差别，孰优孰劣？
采用地址主干词代替完整地址，作为End-to-End模型的输入进行训练，其他信息均保持不变。使用地址主干词训练得到的Embedding向量，套用到向量召回方案中。
从评估结果来看，对于不同的阈值，End-to-End的表现差异相对Word2Vec较小。相同阈值下，End-to-End召回率更高，但是效果不如Word2Vec。
从相似计算结果看，End-to-End模型会把一些语义不相关但是交付时间相近的地址，映射到同一个向量空间，而Word2Vec则是学习一个更通用的文本向量表示。
如果想要针对更为复杂的目标和引入更多信息，可以使用End-to-End框架；只是计算文本相似性，从实验结果看，Word2Vec更好一些。同时，通过查看Case也可以发现，End-to-End更关注结果相似性，从而召回一部分语义上完全不相关的向量。两个模型目标上的不同，从而导致了结果的差异。
