阿里云做视频网站,美食网站的建设,成都洛羽网络科技有限公司,免费外贸电商平台1. 背景 可能很多同学都不知道#xff0c;从打开美团App点一份外卖开始#xff0c;然后在半小时内就可以从骑手小哥手中拿到温热的饭菜#xff0c;这中间涉及的环节有多么复杂。而美团配送技术团队的核心任务#xff0c;就是将每天来自祖国各地的数千万份订单#xff0c;迅… 1. 背景 可能很多同学都不知道从打开美团App点一份外卖开始然后在半小时内就可以从骑手小哥手中拿到温热的饭菜这中间涉及的环节有多么复杂。而美团配送技术团队的核心任务就是将每天来自祖国各地的数千万份订单迅速调度几十万骑手小哥按照最优路线并以最快的速度送到大家手中。 在这种场景下骑手的交付时间即骑手到达用户附近下车后多久能送到用户手中就是一个非常重要的环节。下图是一个订单在整个配送链路的时间构成时间轴最右部分描述了交付环节在整个配送环节中的位置。交付时间衡量的是骑手送餐时的交付难度包括从骑手到达用户楼宇附近到将餐品交付到用户手中的整个时间。 交付时间的衡量是非常有挑战的一件事因为骑手在送餐交付到用户手中时会碰到不同的问题例如骑手一次送餐给楼宇内多个用户骑手对于特定楼宇寻址特别困难骑手在交付楼宇附近只能步行老旧小区没有电梯写字楼无法上楼或者难以等到电梯等等。交付时间预估需要具备刻画交付难度的能力在定价、调度等多个场景中被广泛使用。例如根据交付难度来确定是否调节骑手邮资根据交付难度来确定是否调节配送运单的顺序从而避免超时等等。总的来说交付时间预估是配送业务基础服务的重要一环。 但是交付时间预估存在如下的困难 输入信息较少且多为非数值型数据目前能够被用来预估的仅有如下维度特征交付地址、交付点的经纬度、区域、城市适配常规机器学习模型需要重新整理且容易丢失信息。计算性能要求很高。由于是基础服务会被大量的服务调用需要性能TP99保证在10ms以内整个算法平均响应时间需要控制在5ms内其中包括数据处理及RPC的时间。且该标准为CPU环境下的性能要求而非GPU下的性能要求。 总结起来交付时间预估的问题在于需要使用轻量级的解决方案来处理多种数据形式的非数值型数据并提取有效信息量得到相对准确的结果。在相同效果的前提下我们更倾向于性能更优的方案。 在本文中我们介绍了交付时间预估迭代的三个版本分别为基于地址结构的树模型、向量召回方案以及轻量级的End-to-End的深度学习网络。同时介绍了如何在性能和指标之间取舍以及模型策略迭代的中间历程希望能给从事相关工作的同学们有所启发和帮助。 2. 技术迭代路径 首先在交付时间预估的技术迭代上我们主要经历了三个大版本的改动每一版本在5ms计算性能的约束下追求轻量化的解决方案在兼顾提升效果的基础上不显著增加性能的消耗。 本章节分别叙述了3个模型的迭代路径包括技术选型、关键方案及最终效果。 2.1 树模型 技术选型 最早也是最容易被考虑到的是利用规则核心思路是利用树结构衡量地址相似性尽可能在相似的交付地址上积聚结构化数据然后利用局部的回归策略得到相对充裕的回归逻辑而未能达到回归策略要求的则走兜底的策略。 为了快速聚积局部数据树模型是一个较为合适的解决方案树的规则解析能够有效地聚集数据同时一个层级并不深的树在计算速度上具备足够的优势能够在较短的时间内得到相对不错的解决方案。 观察用户填写地址以及联系实际中地址的层级结构不难发现一个地址可以由四级结构组成地址主干词addr、楼宇号building、单元号unit、楼层floor。其中的地址主干词在实际中可能对应于小区名或者学校名等地标名称。例如望京花园1号楼2单元5楼解析为望京花园1号楼2单元5楼。通过分析实际交付时长与楼层高低呈正相关关系且不同交付地址的交付时长随楼层增加的变化幅度也有所区别所以可以使用线性回归模型拟合楼层信息和交付时长的关系而地址主干词、楼宇号、单元号作为其层级索引。但用户填写的地址中并不一定包含完整的四级结构就会存在一定比例的缺失所以利用这样的层级结构构建成一棵树然后充分利用上一层已知的信息进行预估。预测时只需根据结点的分支找到对应的模型即可如果缺失使用上一层结构进行预测。对于没有达到训练模型要求数据量的地址使用其所在的区域平均交付时长作为交付时长的预估结果这部分也可以看作区域信息作为树结构的根节点。 迭代路径 整体的思路是基于离散特征训练树模型在树的结点上基于楼层训练线性回归模型。树结点训练分裂规则1数据量大于阈值2分裂后MAE平均绝对误差的和小于分裂前。考虑到数据的时效性采用加权线性回归增加近期数据的权重。 2.2 树模型向量召回方案 技术选型 向量召回作为主流的召回方案之一被业界广泛使用在使用LSH、PQ乘积量化等常用开源工具基础上高维向量召回性能通常在毫秒量级。 而从算法上考虑树模型中NLP地址解析结果能够达到模型使用要求的仅为70%剩余20%的地址无法通过训练得到的模型从而只能走降级策略。利用高维向量来表达语义相似性即利用向量来表达地址相似性从而用相似数据对应的模型来替代相似但未被召回数据将地址主干词进行Embedding后摆脱主干词完全匹配的低鲁棒性。 例如在地址上可能会出现【7天酒店晋阳街店】数据量比较充足但【7天连锁酒店太原高新区晋阳街店】数据量不充足从而无法训练模型的案例这可能是同一个交付位置。我们希望尽可能扩大地址解析的成功率。 迭代路径 整个技术路径较为清晰简单即利用Word2Vec将charLevel字符进行Embedding获得该地址的向量表示并且融入GPS位置信息设计相应兜底策略。 最终效果 比较大地提升了整体策略的召回率提升了12.20pp对于未被上一版本树模型召回的地址指标有了显著的提升其中ME下降87.14sMAE下降38.13s1min绝对偏差率减小14.01pp2min绝对偏差率减小18.45pp3min绝对偏差率减小15.90pp。 2.3 End-to-End轻量化深度学习方案 技术选型 在树模型的基础上迭代到向量召回方案整个模型的召回率有了较大幅度的增长但仍然不是100%。分析发现召回率提升的障碍在于NLP对于地址解析的覆盖率。 整个方案的出发点 从模型复杂度考虑同样仅仅使用地址信息的话在提升模型VC维的基础上使用其他的模型方案至少可以持平树模型的效果如果在这基础上还能融入其他信息那么对于原模型的基线还能有进一步的提升。 考虑到不仅仅需要使用地址数据同时需要使用GPS数据、大量ID类的Embedding对于各类非数值类型的处理灵活性考虑采用深度学习的方案来保证多源且多类型特征能在同一个优化体系下优化学习。 工程上需要考虑的点 交付模型作为基础模型被广泛应用在路径构造、定价、ETA等各个业务中频繁调用在树模型版本中对于性能的要求为平均响应时间5msTP99在10ms左右本方案需要考虑沿袭原业务的性能不能显著增加计算耗时。 交付模型的难点在于非数值型特征多信息获取形式的多样化当前的瓶颈并不在于模型的复杂度低。如果可以轻量地获取信息及融合没必要对Fusion后的信息做较重的处理方案。 所以整体的设计思路为利用深度学习融合非数值型特征在简单Fusion的基础上直接得到输出结构对于组件的选择尽可能选用Flops较低的设计。该设计背后意图是在充分使用原始输入信息在尽可能避免信息损失的基础上将非数值型的信息融入进去。并将信息充分融合直接对接所需要的目标。而选用的融合组件结构尽可能保证高性能且具备较高学习效率。这里分别针对地址选用了较为Robust的LSTM针对GPS选用了自定义的双线性Embedding兼顾性能和效果。 迭代路径 开始采用端到端的深度学习模型这里首先需要解决的是覆盖率问题直接采用LSTM读取charLevel的地址数据经过全连接层直接输出交付时间。作为第一版本的数据该版本数据基本持平树模型效果但对于树模型未召回的20%数据有了较大的提升。 在采用charLevel的地址奏效后我们开始采用加入用户地址GPS的信息由于GPS为经纬度信息非数值型数据我们使用一种基于地理位置格点的双线性插值方法进行Embedding。该方案具备一定的扩展性对不同的GPS均能合理得到Embedding向量同时具备平滑特性对于多对偏移较小的GPS点能够很好的进行支持。 最终方案将地址Embedding后以及GPS点的Embedding化后加入下单时间、城市ID、区域ID等特征后再进行特征融合及变换得到交付模型的时间预估输出。整个模型是一个端到端的训练所有参数均为Trainable。 扩展组件 在证实End-to-End路径可行后我们开始进行扩展组件建设包括自定义损失函数、数据采样修正、全国模型统一等操作得到一系列正向效果并开发上线。 特征重要性分析 对于深度学习模型我们有一系列特征重要性评估方案这里采用依次进行Feature Permutation的方式作为评估模型特征重要性的方式。 考虑GPS经纬度和用户地址存在较大程度的信息重叠评估结果如下。Shuffle后用户地址的特征重要性高于GPS经纬度的特征重要性。加入GPS后ME下降不如地址信息明显主要是地址信息包含一定冗余信息下文会分析而其他信息的影响则可以忽略不计。 特征特征重要排名用户地址1GPS经纬度2其他特征……注在配送的其他案例中商户GPS的经纬度重要性用户地址重要性用户GPS的经纬度重要性该特征重要性仅仅为本案例特征重要性排序不同学习目标下可能会有比较明显差别。 最终效果 End-to-End深度学习模型的最终效果较为显著对于树模型及向量召回方案的最痛点覆盖率得到彻底解决覆盖率提升到100%。ME下降4.96sMAE下降8.17s1min绝对偏差率减小2.38pp2min绝对偏差率减小5.08pp3min绝对偏差率减小3.46pp。同时对于之前树模型及向量召回方案未能覆盖到的运单提升则更为明显。 3. 模型相关分析 在整个技术迭代的过程中由于整个解决方案对于性能有着较为苛刻的要求需要单独对方案性能进行分析。本章节对向量召回方案及深度学习方案进行了相应的性能分析以便在线下确认性能指标最终保证上线后性能均达到要求。下文分别着重介绍了向量匹配的工具Faiss以及TensorFlow Operation算子的选取还有对于整体性能的影响。 同时对比End-to-End生成向量与Word2Vec生成向量的质量区别对于相关项目具备一定的借鉴意义。 3.1 向量召回性能 最近邻搜索Nearest Neighbor Search指的是在高维度空间内找到与查询点最近点的问题。在数据样本小的时候通过线性搜索就能满足需求但随着数据量的增加如达到上百万、上亿点时候倾向于将数据结构化表示来更加精确地表达向量信息。 此时近似最近邻搜索ANNApproximate Nearest Neighbor是一个可参考的技术它能在近似召回一部分之后再进行线性搜索平衡效率和精度。目前大体上有以下3类主流方法基于树的方法如K-D树等基于哈希的方法例如LSH基于矢量量化的方法例如PQ乘积量化。在工业检索系统中乘积量化是使用较多的一种索引方法。 针对向量召回的工具存在大量的开源实现在技术选型的过程中我们参照ANN-Benchmarks以及Erikbern/ANN-Benchmarks中的性能评测结果。在众多ANN相关的工具包内考虑到性能、内存、召回精度等因素同时可以支持GPU在向量召回方案的测试中选择以Faiss作为Benchmark。 Faiss是FaceBook在2017年开源的一个用于稠密向量高效相似性搜索和密集向量聚类的库能够在给定内存使用下在速度和精度之间权衡。可以在提供多种检索方式的同时具备C/Python等多个接口也对大部分算法支持GPU实现。 下图为Faiss测评曲线 交付时间模型召回的性能测试如下可以达到性能需求。 召回候选集数量8W条向量【由于采用了GPS距离作为距离限制故召回测试采用8W数量级】测试机器Mac本机CPU【CPU已满足性能故不再测试GPU】 3.2 序列模块性能 在TensorFlow系统中以C API为界限将系统划分为【前端】和【后端】两个子系统前端扮演Client角色完成计算图的构造然后由Protobuf发送给后端启动计算图计算。计算图的基础单元是OP代表的是某种操作的抽象。在TensorFlow中考虑到实现的不同不同OP算子的选择对于计算性能具有较大影响。 为了评测深度学习交付模型的性能瓶颈首先对整个模型进行Profile下图即为Profile后的Timeline其中整个计算大部分消耗在序列模块处理部分即下图中的蓝色部分。故需要对序列模块的计算性能进行OP算子的加速。 考虑到序列处理的需求评估使用了LSTM/GRU/SRU等模块同时在TensorFlow中LSTM也存在多种实现形式包括BasicLSTMCell、LSTMCell、LSTMBlockCell、LSTMBlockFusedCell和CuDNNLSTM等实现由于整个交付模型运行在CPU上故排除CuDNNLSTM同时设置了全连接层FullyConnect加入评估。 从评估中可以发现全连接层速度最快但是对于序列处理会损失2.3pp效果其余的序列模型效果差异不大但不同的OP实现对结果影响较大。原生的BasicLSTM性能较差contrib下的LSTMBlockFusedCell性能最好GRU/SRU在该场景下未取得显著优势。 这是LSTMBlockFusedCell的官方说明其核心实现是将LSTM的Loop合并为一个OP调用时候整个Timeline上更为紧凑同时节约时间和内存 This is an extremely efficient LSTM implementation, that uses a single TF op for the entire LSTM. It should be both faster and more memory-efficient than LSTMBlockCell defined above. 以下是序列模块的性能测试 环境Tensorflow1.10.0CentOS 7。测试方法CPU inference 1000次取最长的地址序列求平均时间。结论LSTMBlockFused实现性能最佳。【FullyConnect性能最快但对性能有损失】注在评估中不仅仅包括了序列模型也包括了其他功能模块故参数量及模型大小按照总体模型而言 lstm结构OP时间(ms)FLOPs可训练参数量模型大小(MB)效果差异Fully Connect1.1827.83M7.00M29.1-2.3ppSRU4.0027.96M7.06M29.4差异不显著GRU Block3.6428.02M7.10M29.6差异不显著GRU4.4428.02M7.10M29.6差异不显著LSTMBlockFused2.4828.09M7.13M29.7差异不显著LSTM Block4.3428.09M7.13M29.7差异不显著LSTM4.8528.09M7.13M29.7差异不显著BasicLSTM4.9228.09M7.13M29.7差异不显著3.3 向量效果分析 将向量召回与深度学习模型进行横向比较二者中间过程均生成了高维向量。不难发现二者具备一定的相似性这里就引发了我们的思考 相较于向量召回深度学习模型带来的提升主要来自于哪里 有监督的lstm学习到的Embedding向量与自监督的Word2Vec得到的向量在地址相似性计算中有多大差别孰优孰劣 首先我们分析第一个问题End-to-End模型提升主要来自哪里 MEMAE1min绝对偏差率2min绝对偏差率3min绝对偏差率End-to-End模型 - Word2Vec模型4.14-0.45-0.31%0.05%我们直接将End-to-End模型得到的char embedding抽取出来直接放入到Word2Vec方案内取代Word2Vec生成的char embedding再进行向量召回的评估。结果如下表所示单独抽取出来的char embedding在向量召回方案中表现与Word2Vec生成的向量基本一致并没有明显的优势。 注 1min绝对偏差率定义|pred-label|60s2min绝对偏差率定义|pred-label|120s3min绝对偏差率定义|pred-label|180s此时的变量有2个方面: a对于charLevel地址的学习结构不同一个为Word2Vec一个为LSTMb输入信息的不同Word2Vec的信息输入仅仅为地址主干词而End-to-End的信息输入则包括了地址主干词、地址附属信息、GPS等其他信息。注 完整地址卓玛护肤造型洞庭湖店 洞庭湖路与天山路交叉路口卓玛护肤造型地址主干词卓玛护肤造型店地址附属信息洞庭湖店洞庭湖路与天山路交叉路口卓玛护肤造型为了排除第二方面的因素即b的因素使用地址主干词作为输入而不用地址附属信息和其他模型结构的输入保持模型输入跟Word2Vec一致。在测试集上模型的效果比完整地址有明显的下降MAE增大约15s。同时将char embedding提取出来取代Word2Vec方案的char embedding效果反而变差了。结合2.3节中的特征重要性可知深度学习模型带来的提升主要来自对地址中冗余信息相较于向量召回的利用其次是多个新特征的加入。另外对比两个End-to-End模型的效果地址附属信息中也包含着对匹配地址有用的信息。 MEMAE1min绝对偏差率2min绝对偏差率3min绝对偏差率End-to-End模型 - Word2Vec模型-1.280.640.90%0.85%针对第二个问题有监督的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更关注结果相似性从而召回一部分语义上完全不相关的向量。两个模型目标上的不同从而导致了结果的差异。 4. 总结与展望 在本篇中依次展示了在配送交付场景下的三次模型策略迭代过程以及在较为苛刻性能要求限制下如何用轻量化的方案不断提高召回率及效果。同时对迭代过程中的性能进行简单的分析及衡量这对相关的项目也具备一定的借鉴意义最后对Word2Vec及End-to-End生成的向量进行了比较。 事实上本文中提及的向量召回及深度学习融合非数值型特征的方案已经在业界被广泛使用。但对于差异化的场景本文仍具备一定的借鉴价值特别是对于订单-骑手匹配、订单-订单匹配等非搜索推荐领域的场景化应用以及TF OP算子的选用及分析、Embedding生成方式带来的差异希望能够给大家提供一些思路和启发。 5. 关联阅读 交付时间预估与ETA预估及配送其他业务关系 交付时间预估是ETA预估中的重要一环关于ETA预估请参见《深度学习在美团配送ETA预估中的探索与实践》。具体ETA在整个配送业务中的位置及配送业务的整体机器学习实践请参看《机器学习在美团配送系统的实践用技术还原真实世界》。6. 作者介绍 基泽美团点评技术专家闫聪美团点评算法工程师7. 招聘信息 美团配送AI团队支撑全球领先的即时配送网络——美团配送并建立了行业领先的美团智能配送系统。美团配送AI团队主要来自一线互联网公司以及知名科研机构研发实力和氛围卓越。目前美团配送业务仍处于快速发展期新的场景、新的技术难题不断涌现成长空间巨大。 美团配送AI团队现诚聘算法策略工程师、机器学习工程师和运筹优化工程师欢迎有兴趣的小伙伴投递简历至techmeituan.com邮件标题注明美团配送AI团队
