美團(tuán)技術(shù)解析

簡介：基澤，美團(tuán)點(diǎn)評技術(shù)專家，目前負(fù)責(zé)配送算法策略部機(jī)器學(xué)習(xí)組策略迭代工作。

周越，2017年加入美團(tuán)配送事業(yè)部算法策略組，主要負(fù)責(zé)ETA策略開發(fā)。

顯杰，美團(tuán)點(diǎn)評技術(shù)專家，2018年加入美團(tuán)，目前主要負(fù)責(zé)配送算法數(shù)據(jù)平臺深度學(xué)習(xí)相關(guān)的研發(fā)工作。

1. 背景

ETA（Estimated Time of Arrival，“預(yù)計(jì)送達(dá)時間”），即用戶下單后，配送人員在多長時間內(nèi)將外賣送達(dá)到用戶手中。送達(dá)時間預(yù)測的結(jié)果，將會以"預(yù)計(jì)送達(dá)時間"的形式，展現(xiàn)在用戶的客戶端頁面上，是配送系統(tǒng)中非常重要的參數(shù)，直接影響了用戶的下單意愿、運(yùn)力調(diào)度、騎手考核，進(jìn)而影響配送系統(tǒng)整體成本和用戶體驗(yàn)。

對于整個配送系統(tǒng)而言，ETA既是配送系統(tǒng)的入口和全局約束，又是系統(tǒng)的調(diào)節(jié)中樞。具體體現(xiàn)在：

• ETA在用戶下單時刻就需要被展現(xiàn)，這個預(yù)估時長繼而會貫穿整個訂單生命周期，首先在用戶側(cè)給予準(zhǔn)時性的承諾，接著被調(diào)度系統(tǒng)用作訂單指派的依據(jù)及約束，而騎手則會按照這個ETA時間執(zhí)行訂單的配送，配送是否準(zhǔn)時還會作為騎手的工作考核結(jié)果。

• ETA作為系統(tǒng)的調(diào)節(jié)中樞，需要平衡用戶-騎手-商家-配送效率。從用戶的訴求出發(fā)，盡可能快和準(zhǔn)時，從騎手的角度出發(fā)，太短會給騎手極大壓力。從調(diào)度角度出發(fā)，太長或太短都會影響配送效率。而從商家角度出發(fā)，都希望訂單被盡可能派發(fā)出去，因?yàn)檫@關(guān)系到商家的收入。

在這樣多維度的約束之下，外賣配送的ETA的建模和估計(jì)會變得更加復(fù)雜。與打車場景中的ETA做對比，外賣場景的ETA面臨如下的挑戰(zhàn)：

• 外賣場景中ETA是對客戶履約承諾的重要組成部分，無論是用戶還是騎手，對于ETA準(zhǔn)確性的要求非常高。而在打車場景，用戶更加關(guān)心是否能打到車，ETA僅提供一個參考，司機(jī)端對此也不是特別關(guān)注。

• 外賣場景中ETA包含更多環(huán)節(jié)，騎手全程完成履約過程，其中包括到達(dá)商家、商家出餐、等待取餐、路徑規(guī)劃、不同樓宇交付等較多的環(huán)節(jié)，且較高的合單率使得訂單間的流程互相耦合，不確定性很大，做出合理的估計(jì)也有更高難度。

下圖是騎手履約全過程的時間軸，過程中涉及各種時長參數(shù)，可以看到有十幾個節(jié)點(diǎn)，其中關(guān)鍵時長達(dá)到七個。這些時長涉及多方，比如騎手（接-到-取-送）、商戶（出餐）、用戶（交付），要經(jīng)歷室內(nèi)室外的場景轉(zhuǎn)換，因此挑戰(zhàn)性非常高。對于ETA建模，不光是簡單一個時間的預(yù)估，更需要的是全鏈路的時間預(yù)估，同時更需要兼顧"單量-運(yùn)力-用戶轉(zhuǎn)化率"轉(zhuǎn)化率之間的平衡。配送ETA的演變包括了數(shù)據(jù)、特征層面的持續(xù)改進(jìn)，也包括了模型層面一路從LR-XGB-FM-DeepFM-自定義結(jié)構(gòu)的演變。

具體ETA在整個配送業(yè)務(wù)中的位置及配送業(yè)務(wù)的整體機(jī)器學(xué)習(xí)實(shí)踐，請參看《機(jī)器學(xué)習(xí)在美團(tuán)配送系統(tǒng)的實(shí)踐：用技術(shù)還原真實(shí)世界》。

2. 業(yè)務(wù)流程迭代中的模型改進(jìn)

2.1 基礎(chǔ)模型迭代及選擇

與大部分CTR模型的迭代路徑相似，配送ETA模型的業(yè)務(wù)迭代經(jīng)歷了LR->樹模型->Embedding->DeepFM->針對性結(jié)構(gòu)修改的路徑。特征層面也進(jìn)行不斷迭代和豐富。

• 模型維度從最初考慮特征線性組合，到樹模型做稠密特征的融合，到Embedding考慮ID類特征的融合，以及FM機(jī)制低秩分解后二階特征組合，最終通過業(yè)務(wù)指標(biāo)需求，對模型進(jìn)行針對性調(diào)整。

• 特征維度逐步豐富到用戶畫像/騎手畫像/商家畫像/地址特征/軌跡特征/區(qū)域特征/時間特征/時序特征/訂單特征等維度。

目前版本模型在比較了Wide&Deep、DeepFM、AFM等常用模型后，考慮到計(jì)算性能及效果，最終選擇了DeepFM作為初步的Base模型。整個DeepFM模型特征Embedding化后，在FM（Factorization Machine）基礎(chǔ)上，進(jìn)一步加入deep部分，分別針對稀疏及稠密特征做針對性融合。FM部分通過隱變量內(nèi)積方式考慮一階及二階的特征融合，DNN部分通過Feed-Forward學(xué)習(xí)高階特征融合。模型訓(xùn)練過程中采取了Learning Decay/Clip Gradient/求解器選擇/Dropout/激活函數(shù)選擇等，在此不做贅述。

2.2 損失函數(shù)

在ETA預(yù)估場景下，準(zhǔn)時率及置信度是比較重要的業(yè)務(wù)指標(biāo)。初步嘗試將Square的損失函數(shù)換成Absolute的損失函數(shù)，從直觀上更為切合MAE相比ME更為嚴(yán)苛的約束。在適當(dāng)Learning Decay下，結(jié)果收斂且穩(wěn)定。

同時，在迭代中考慮到相同的ETA承諾時間下，在前后N分鐘限制下，早到1min優(yōu)于晚到1min，損失函數(shù)的設(shè)計(jì)希望整體的預(yù)估結(jié)果能夠盡量前傾。對于提前部分，適當(dāng)降低數(shù)值懲罰。對于遲到部分，適當(dāng)增大數(shù)值懲罰。進(jìn)行多次調(diào)試設(shè)計(jì)后，最終確定以前后N分鐘以及原點(diǎn)作為3個分段點(diǎn)。在原先absolute函數(shù)優(yōu)化的基礎(chǔ)上，在前段設(shè)計(jì)1.2倍斜率absolute函數(shù)，后段設(shè)計(jì)1.8倍斜率absolute函數(shù)，以便讓結(jié)果整體往中心收斂，且預(yù)估結(jié)果更傾向于提前送達(dá)，對于ETA各項(xiàng)指標(biāo)均有較大幅度提升。

2.3 業(yè)務(wù)規(guī)則融入模型

目前的業(yè)務(wù)架構(gòu)是"模型+規(guī)則"，在模型預(yù)估一個ETA值之后，針對特定業(yè)務(wù)場景，會有特定業(yè)務(wù)規(guī)則時間疊加以滿足特定場景需求，各項(xiàng)規(guī)則由業(yè)務(wù)指標(biāo)多次迭代產(chǎn)生。這里產(chǎn)生了模型和規(guī)則整體優(yōu)化的割裂，在模型時間和規(guī)則時間分開優(yōu)化后，即模型訓(xùn)練時并不能考慮到規(guī)則時間的影響，而規(guī)則時間在一年之中不同時間段，會產(chǎn)生不同的浮動，在經(jīng)過一段時間重復(fù)迭代后，會加大割裂程度。

在嘗試了不同方案后，最終將整體規(guī)則寫入到了TF模型中，在TF模型內(nèi)部調(diào)整整體規(guī)則參數(shù)。

• 對于簡單的(ab+c)d等規(guī)則，可以將規(guī)則邏輯直接用TF的OP算子來實(shí)現(xiàn)，比如當(dāng)b、d為定值時，則a、c為可學(xué)習(xí)的參數(shù)。

• 對于過于復(fù)雜的規(guī)則部分，則可以借助一定的模型結(jié)構(gòu)，通過模型的擬合來代替，過多復(fù)雜OP算子嵌套并不容易同時優(yōu)化。

通過調(diào)節(jié)不同的擬合部分及參數(shù)，將多個規(guī)則完全在TF模型中實(shí)現(xiàn)。最終對業(yè)務(wù)指標(biāo)具備很大提升效果，且通過對部分定值參數(shù)的更改，具備部分人工干涉模型能力。

在這里，整體架構(gòu)就簡化為多目標(biāo)預(yù)估的架構(gòu)，這里采用多任務(wù)架構(gòu)中常用的Shared Parameters的結(jié)構(gòu)，訓(xùn)練時按比例采取不同的交替訓(xùn)練策略。結(jié)構(gòu)上從最下面的模型中間融合層出發(fā)，分別在TF內(nèi)實(shí)現(xiàn)常規(guī)預(yù)測結(jié)構(gòu)及多個規(guī)則時間結(jié)構(gòu)，而其對應(yīng)的Label則仍然從常規(guī)的歷史值和規(guī)則時間值中來，這樣考慮了以下幾點(diǎn)：

• 模型預(yù)估時，已充分考慮到規(guī)則對整體結(jié)果的影響（例如多個規(guī)則的疊加效應(yīng)），作為整體一起考慮。

• 規(guī)則時間作為輔助Label傳入模型，對于模型收斂及Regularization，起到進(jìn)一步作用。

• 針對不同的目標(biāo)預(yù)估，采取不同的Loss，方便進(jìn)行針對性優(yōu)化，進(jìn)一步提升效果。

模型結(jié)構(gòu)在進(jìn)行預(yù)估目標(biāo)調(diào)整嘗試中：

• 嘗試過固定共享網(wǎng)絡(luò)部分及不固定共享部分參數(shù)，不固定共享參數(shù)效果明顯。

• 通常情況下激活函數(shù)差異不大，但在共享層到獨(dú)立目標(biāo)層中，不同的激活函數(shù)差異很大。

2.4 缺失值處理

在模型處理中，特征層面不可避免存在一定的缺失值，而對于缺失值的處理，完全借鑒了《美團(tuán)“猜你喜歡”深度學(xué)習(xí)排序模型實(shí)踐》文章中的方法。對于特征x進(jìn)入TF模型，進(jìn)行判斷，如果是缺失值，則設(shè)置w1參數(shù)，如果不是缺失值則進(jìn)入模型數(shù)值為w2*x，這里將w1和w2作為可學(xué)習(xí)參數(shù)，同時放入網(wǎng)絡(luò)進(jìn)行訓(xùn)練。以此方法來代替均值/零值等作為缺失值的方法。

3. 長尾問題優(yōu)化

3.1 模型預(yù)估結(jié)果+長尾規(guī)則補(bǔ)時

基礎(chǔ)模型學(xué)習(xí)的是整體的統(tǒng)計(jì)分布，但對于一些長尾情形的學(xué)習(xí)并不充分，體現(xiàn)在長尾情形下預(yù)估時間偏短（由于ETA擁有考核騎手的功能，預(yù)估偏短對騎手而言意味著很大的傷害）。故將長尾拆解成兩部分來分析：

• 業(yè)務(wù)長尾，即整體樣本分布造成的長尾。主要體現(xiàn)在距離、價格等維度。距離越遠(yuǎn)，價格越高，實(shí)際送達(dá)時間越長，但樣本占比越少，模型在這一部分上的表現(xiàn)整體都偏短。

• 模型長尾，即由于模型自身對預(yù)估值的不確定性造成的長尾。模型學(xué)習(xí)的是整體的統(tǒng)計(jì)分布，但不是對每個樣本的預(yù)估都有“信心”。實(shí)踐中采用RF多棵決策樹輸出的標(biāo)準(zhǔn)差來衡量不確定性。RF模型生成的決策樹是獨(dú)立的，每棵樹都可以看成是一個專家，多個專家共同打分，打分的標(biāo)準(zhǔn)差實(shí)際上就衡量了專家們的“分歧”程度（以及對預(yù)估的“信心”程度）。從下圖也可以看出來，隨著RF標(biāo)準(zhǔn)差的增加，模型的置信度和準(zhǔn)時率均在下降。

在上述拆解下，采用補(bǔ)時規(guī)則來解決長尾預(yù)估偏短的問題：長尾規(guī)則補(bǔ)時為 <業(yè)務(wù)長尾因子 , 模型長尾因子> 組合。其中業(yè)務(wù)長尾因子為距離、價格等業(yè)務(wù)因素，模型長尾因子為RF標(biāo)準(zhǔn)差。最終的ETA策略即為模型預(yù)估結(jié)果+長尾規(guī)則補(bǔ)時。

4. 工程開發(fā)實(shí)踐

4.1 訓(xùn)練部分實(shí)踐

整體訓(xùn)練流程

對于線下訓(xùn)練，采取如下訓(xùn)練流程：

Spark原始數(shù)據(jù)整合 -> Spark生成TFRecord -> 數(shù)據(jù)并行訓(xùn)練 -> TensorFlow Serving線下GPU評估 -> CPU Inference線上預(yù)測

整個例行訓(xùn)練億級數(shù)據(jù)多輪Epoch下流程持續(xù)約4小時，其中TF訓(xùn)練中，考慮到TF實(shí)際計(jì)算效率并不是很高，有很大比例在數(shù)據(jù)IO部分，通過Spark生成TFRecord部分，在此可將速度加速約3.6倍。而在數(shù)據(jù)并行訓(xùn)練部分，16卡內(nèi)的并行度擴(kuò)展基本接近線性，具備良好的擴(kuò)展性。由于PS上參數(shù)量并未達(dá)到單機(jī)無法承受，暫時未對參數(shù)在PS上進(jìn)行切分。Serving線下GPU評估部分，是整個流程中的非必需項(xiàng)，雖然在訓(xùn)練過程中Chief Worker設(shè)置Valid集合可有一定的指標(biāo)，但對全量線下，通過Spark數(shù)據(jù)調(diào)用Serving GPU的評估具備短時間內(nèi)完成全部流程能力，且可以指定大量復(fù)雜自定義指標(biāo)。

數(shù)據(jù)并行訓(xùn)練方式

整個模型的訓(xùn)練在美團(tuán)的AFO平臺上進(jìn)行，先后嘗試分布式方案及單機(jī)多卡方案。考慮到生產(chǎn)及結(jié)果穩(wěn)定性，目前線上模型生產(chǎn)采用單機(jī)多卡方案進(jìn)行例行訓(xùn)練。

• 分布式方案

采用TF自帶的PS-Worker架構(gòu)，異步數(shù)據(jù)并行方式，利用tf.train.MonitoredTrainingSession協(xié)調(diào)整個訓(xùn)練過程。整個模型參數(shù)存儲于PS，每個Step上每個Worker拉取數(shù)據(jù)進(jìn)行數(shù)據(jù)并行計(jì)算，同時將梯度返回，完成一次更新。目前的模型單Worker吞吐1~2W/s，億級數(shù)據(jù)幾輪Epoch耗時在幾小時內(nèi)完成。同時測試該模型在平臺上的加速比，大約在16塊內(nèi)，計(jì)算能力隨著Worker數(shù)目線性增加，16卡后略微出現(xiàn)分離。在目前的業(yè)務(wù)實(shí)踐中，基本上4-6塊卡可以短時間內(nèi)完成例行的訓(xùn)練任務(wù)。

• 單機(jī)多卡方案

采用PS-Worker的方案在平臺上具備不錯的擴(kuò)展性，但是也存在一定的弊端，使用RPC的通訊很容易受到其他任務(wù)的影響，整個的訓(xùn)練過程受到最慢Worker的影響，同時異步更新方式對結(jié)果也存在一定的波動。對此，在線上生產(chǎn)中，最終選取單機(jī)多卡的方案，犧牲一定的擴(kuò)展性，帶來整體訓(xùn)練效果和訓(xùn)練速度的穩(wěn)定性。單機(jī)多卡方案采取多GPU手動指定OP的Device，同時在各個Device內(nèi)完成變量共享，最后綜合Loss與梯度，將Grad更新到模型參數(shù)中。

TF模型集成預(yù)處理

模型訓(xùn)練過程中，ID類特征低頻過濾需要用到Vocab詞表，連續(xù)型特征都需要進(jìn)行歸一化。這里會產(chǎn)生大量的預(yù)處理文件，在線下處理流程中很容易在Spark中處理成Libsvm格式，然后載入到模型中進(jìn)行訓(xùn)練。但是在線上預(yù)測時，需要在工程開發(fā)端載入多個詞表及連續(xù)型特征的歸一化預(yù)處理文件（avg/std值文件等），同時由于模型是按天更新，存在不同日期版本的對齊問題。

為了簡化工程開發(fā)中的難度，在模型訓(xùn)練時，考慮將所有的預(yù)處理文件寫入TF計(jì)算圖之中，每次在線預(yù)測只要輸入最原始的特征，不經(jīng)過工程預(yù)處理，直接可得到結(jié)果：

• 對于ID類特征，需要進(jìn)行低頻過濾，然后制作成詞表，TF模型讀入詞表的list_arr，每次inference通過ph_vals，得到對應(yīng)詞表的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

• 對于連續(xù)型特征，在Spark處理完得到avg/std值后，直接寫入TF模型計(jì)算圖中，作為constant節(jié)點(diǎn)，每個ph_in經(jīng)過兩個節(jié)點(diǎn)，得到相應(yīng)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模型線上預(yù)測

配送機(jī)器學(xué)習(xí)平臺內(nèi)置了模型管理平臺，對算法訓(xùn)練產(chǎn)出的模型進(jìn)行統(tǒng)一管理和調(diào)度，管理線上模型所用的版本，并支持模型版本的切換和回退，同時也支持節(jié)點(diǎn)模型版本狀態(tài)的管理。

ETA使用的DeepFM模型用TensorFlow訓(xùn)練，生成SavedModel格式的模型，需要模型管理平臺支持Tensorflow SavedModel格式。

實(shí)現(xiàn)方案

線上服務(wù)加載TensorFlow SavedModel模型有多種實(shí)現(xiàn)方案：

• 自行搭建TensorFlow Serving CPU服務(wù)，通過gRPC API或RESTful API提供服務(wù)，該方案實(shí)現(xiàn)比較簡單，但無法與現(xiàn)有的基于Thrift的模型管理平臺兼容。

• 使用美團(tuán)AFO GPU平臺提供的TensorFlow Serving服務(wù)。

• 在模型管理平臺中通過JNI調(diào)用TensorFlow提供的Java APITensorFlow Java API，完成模型管理平臺對SavedModel格式的支持。

最終采用TensorFlow Java API加載SavedModel在CPU上做預(yù)測，測試batch=1時預(yù)測時間在1ms以內(nèi)，選擇方案3作為實(shí)現(xiàn)方案。

遠(yuǎn)程計(jì)算模式

TensorFlow Java API的底層C++動態(tài)鏈接庫對libstdc++.so的版本有要求，需要GCC版本不低于4.8.3，而目前線上服務(wù)的CPU機(jī)器大部分系統(tǒng)為CentOS 6, 默認(rèn)自帶GCC版本為4.4.7。如果每臺線上業(yè)務(wù)方服務(wù)器都支持TensorFlow SavedModel本地計(jì)算的話，需要把幾千臺服務(wù)器統(tǒng)一升級GCC版本，工作量比較大而且可能會產(chǎn)生其他風(fēng)險。

因此，我們重新申請了幾十臺遠(yuǎn)程計(jì)算服務(wù)器，業(yè)務(wù)方服務(wù)器只需要把Input數(shù)據(jù)序列化后傳給TensorFlow Remote集群，Remote集群計(jì)算完后再將Output序列化后返回給業(yè)務(wù)方。這樣只需要對幾十臺計(jì)算服務(wù)器升級就可以了。

線上性能

模型上線后，支持了多個業(yè)務(wù)方的算法需求，遠(yuǎn)程集群計(jì)算時間的TP99基本上在5ms以內(nèi)，可以滿足業(yè)務(wù)方的計(jì)算需求。

5. 總結(jié)與展望

模型落地并上線后，對業(yè)務(wù)指標(biāo)帶來較大的提升。后續(xù)將會進(jìn)一步根據(jù)業(yè)務(wù)優(yōu)化模型，進(jìn)一步提升效果：

• 將會進(jìn)一步豐富多目標(biāo)學(xué)習(xí)框架，將取餐、送餐、交付、調(diào)度等整個配送生命周期內(nèi)的過程在模型層面考慮，對訂單生命周期內(nèi)多個目標(biāo)進(jìn)行建模，同時提升模型可解釋性。

• 模型融合特征層面的進(jìn)一步升級，在Embedding以外，通過更多的LSTM/CNN/自設(shè)計(jì)結(jié)構(gòu)對特征進(jìn)行更好的融合。

• 特征層面的進(jìn)一步豐富。

END

也許你還想看

【美團(tuán)技術(shù)解析】機(jī)器學(xué)習(xí)在美團(tuán)配送系統(tǒng)的實(shí)踐：用技術(shù)還原真實(shí)世界

【美團(tuán)技術(shù)解析】模型加速概述與模型裁剪算法技術(shù)解析

【美團(tuán)技術(shù)解析】無人車端到端駕駛模型概述