導讀：在本文中，我們介紹了交付時間預估迭代的三個版本，分別為基于地址結構的樹模型、向量召回方案以及輕量級的End-to-End的深度學習網絡。同時介紹了如何在性能和指標之間取舍，以及模型策略迭代的中間歷程，希望能給從事相關工作的同學們有所啟發和幫助。

1. 背景

可能很多同學都不知道，從打開美團App點一份外賣開始，然后在半小時內就可以從騎手小哥手中拿到溫熱的飯菜，這中間涉及的環節有多么復雜。而美團配送技術團隊的核心任務，就是將每天來自祖國各地的數千萬份訂單，迅速調度幾十萬騎手小哥按照最優路線，并以最快的速度送到大家手中。

在這種場景下，騎手的交付時間，即騎手到達用戶附近下車后多久能送到用戶手中，就是一個非常重要的環節。下圖是一個訂單在整個配送鏈路的時間構成，時間軸最右部分描述了交付環節在整個配送環節中的位置。交付時間衡量的是騎手送餐時的交付難度，包括從騎手到達用戶樓宇附近，到將餐品交付到用戶手中的整個時間。

交付時間的衡量是非常有挑戰的一件事，因為騎手在送餐交付到用戶手中時會碰到不同的問題，例如：騎手一次送餐給樓宇內多個用戶，騎手對于特定樓宇尋址特別困難，騎手在交付樓宇附近只能步行，老舊小區沒有電梯，寫字樓無法上樓，或者難以等到電梯等等。交付時間預估需要具備刻畫交付難度的能力，在定價、調度等多個場景中被廣泛使用。例如根據交付難度來確定是否調節騎手郵資，根據交付難度來確定是否調節配送運單的順序，從而避免超時等等。總的來說，交付時間預估是配送業務基礎服務的重要一環。

但是，交付時間預估存在如下的困難：

• 輸入信息較少，且多為非數值型數據，目前能夠被用來預估的僅有如下維度特征：交付地址、交付點的經緯度、區域、城市，適配常規機器學習模型需要重新整理且容易丟失信息。

• 計算性能要求很高。由于是基礎服務，會被大量的服務調用，需要性能TP99保證在10ms以內，整個算法平均響應時間需要控制在5ms內，其中包括數據處理及RPC的時間。且該標準為CPU環境下的性能要求，而非GPU下的性能要求。

上圖為部分版本所對應的性能，平響時間均在5ms內，TP99基本在10ms內

總結起來，交付時間預估的問題，在于需要使用輕量級的解決方案來處理多種數據形式的非數值型數據，并提取有效信息量，得到相對準確的結果。在相同效果的前提下，我們更傾向于性能更優的方案。

在本文中，我們介紹了交付時間預估迭代的三個版本，分別為基于地址結構的樹模型、向量召回方案以及輕量級的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.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，TP99在10ms左右，本方案需要考慮沿襲原業務的性能，不能顯著增加計算耗時。

交付模型的難點在于非數值型特征多，信息獲取形式的多樣化，當前的瓶頸并不在于模型的復雜度低。如果可以輕量地獲取信息及融合，沒必要對Fusion后的信息做較重的處理方案。

所以整體的設計思路為：利用深度學習融合非數值型特征，在簡單Fusion的基礎上，直接得到輸出結構，對于組件的選擇，盡可能選用Flops較低的設計。該設計背后意圖是，在充分使用原始輸入信息，在盡可能避免信息損失的基礎上，將非數值型的信息融入進去。并將信息充分融合，直接對接所需要的目標。而選用的融合組件結構盡可能保證高性能，且具備較高學習效率。這里分別針對地址選用了較為Robust的LSTM，針對GPS選用了自定義的雙線性Embedding，兼顧性能和效果。

迭代路徑

開始采用端到端的深度學習模型，這里首先需要解決的是覆蓋率問題，直接采用LSTM讀取charLevel的地址數據，經過全連接層直接輸出交付時間。作為第一版本的數據，該版本數據基本持平樹模型效果，但對于樹模型未召回的20%數據，有了較大的提升。

地址信息輸入charLevel模型

在采用charLevel的地址奏效后，我們開始采用加入用戶地址GPS的信息，由于GPS為經緯度信息，非數值型數據，我們使用一種基于地理位置格點的雙線性插值方法進行Embedding。該方案具備一定的擴展性，對不同的GPS均能合理得到Embedding向量，同時具備平滑特性，對于多對偏移較小的GPS點能夠很好的進行支持。

最終方案將地址Embedding后，以及GPS點的Embedding化后，加入下單時間、城市ID、區域ID等特征后，再進行特征融合及變換，得到交付模型的時間預估輸出。整個模型是一個端到端的訓練，所有參數均為Trainable。

模型結構示意圖

擴展組件

在證實End-to-End路徑可行后，我們開始進行擴展組件建設，包括自定義損失函數、數據采樣修正、全國模型統一等操作，得到一系列正向效果，并開發上線。

特征重要性分析

對于深度學習模型，我們有一系列特征重要性評估方案，這里采用依次進行Feature Permutation的方式，作為評估模型特征重要性的方式。

考慮GPS經緯度和用戶地址存在較大程度的信息重疊，評估結果如下。Shuffle后，用戶地址的特征重要性高于GPS經緯度的特征重要性。加入GPS后ME下降不如地址信息明顯，主要是地址信息包含一定冗余信息（下文會分析），而其他信息的影響則可以忽略不計。

注：在配送的其他案例中，商戶GPS的經緯度重要性>>用戶地址重要性>>用戶GPS的經緯度重要性，該特征重要性僅僅為本案例特征重要性排序，不同學習目標下可能會有比較明顯差別。

最終效果

End-to-End深度學習模型的最終效果較為顯著：對于樹模型及向量召回方案的最痛點，覆蓋率得到徹底解決，覆蓋率提升到100%。ME下降4.96s，MAE下降8.17s，1min絕對偏差率減小2.38pp，2min絕對偏差率減小5.08pp，3min絕對偏差率減小3.46pp。同時，對于之前樹模型及向量召回方案未能覆蓋到的運單，提升則更為明顯。

3. 模型相關分析

在整個技術迭代的過程中，由于整個解決方案對于性能有著較為苛刻的要求，需要單獨對方案性能進行分析。本章節對向量召回方案及深度學習方案進行了相應的性能分析，以便在線下確認性能指標，最終保證上線后性能均達到要求。下文分別著重介紹了向量匹配的工具Faiss以及TensorFlow Operation算子的選取，還有對于整體性能的影響。

同時對比End-to-End生成向量與Word2Vec生成向量的質量區別，對于相關項目具備一定的借鑒意義。

3.1 向量召回性能

最近鄰搜索（Nearest Neighbor Search）指的是在高維度空間內找到與查詢點最近點的問題。在數據樣本小的時候，通過線性搜索就能滿足需求，但隨著數據量的增加，如達到上百萬、上億點時候，傾向于將數據結構化表示來更加精確地表達向量信息。

此時近似最近鄰搜索ANN（Approximate 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.0，CentOS 7。

• 測試方法：CPU inference 1000次，取最長的地址序列，求平均時間。

• 結論：LSTMBlockFused實現性能最佳。【FullyConnect性能最快，但對性能有損失】

注：在評估中，不僅僅包括了序列模型，也包括了其他功能模塊，故參數量及模型大小按照總體模型而言

3.3 向量效果分析

將向量召回與深度學習模型進行橫向比較，二者中間過程均生成了高維向量。不難發現，二者具備一定的相似性，這里就引發了我們的思考：

• 相較于向量召回，深度學習模型帶來的提升主要來自于哪里？

• 有監督的lstm學習到的Embedding向量與自監督的Word2Vec得到的向量在地址相似性計算中有多大差別，孰優孰劣？

首先，我們分析第一個問題，End-to-End模型提升主要來自哪里？

我們直接將End-to-End模型得到的char embedding抽取出來，直接放入到Word2Vec方案內，取代Word2Vec生成的char embedding，再進行向量召回的評估。結果如下表所示，單獨抽取出來的char embedding在向量召回方案中，表現與Word2Vec生成的向量基本一致，并沒有明顯的優勢。

注：

• 1min絕對偏差率定義：|pred-label|<=60s

• 2min絕對偏差率定義：|pred-label|<=120s

• 3min絕對偏差率定義：|pred-label|<=180s

此時的變量有2個方面:

1. 對于charLevel地址的學習結構不同，一個為Word2Vec，一個為LSTM。

2. 輸入信息的不同，Word2Vec的信息輸入僅僅為地址主干詞，而End-to-End的信息輸入則包括了地址主干詞、地址附屬信息、GPS等其他信息。

注：

• 完整地址：卓瑪護膚造型（洞庭湖店） （洞庭湖路與天山路交叉路口卓瑪護膚造型）

• 地址主干詞：卓瑪護膚造型店

• 地址附屬信息：（洞庭湖店）（洞庭湖路與天山路交叉路口卓瑪護膚造型）

為了排除第二方面的因素，即b的因素，使用地址主干詞作為輸入，而不用地址附屬信息和其他模型結構的輸入，保持模型輸入跟Word2Vec一致。在測試集上，模型的效果比完整地址有明顯的下降，MAE增大約15s。同時將char embedding提取出來，取代Word2Vec方案的char embedding，效果反而變差了。結合2.3節中的特征重要性，可知，深度學習模型帶來的提升主要來自對地址中冗余信息（相較于向量召回）的利用，其次是多個新特征的加入。另外，對比兩個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更關注結果相似性，從而召回一部分語義上完全不相關的向量。兩個模型目標上的不同，從而導致了結果的差異。

4. 總結與展望

在本篇中，依次展示了在配送交付場景下的三次模型策略迭代過程，以及在較為苛刻性能要求限制下，如何用輕量化的方案不斷提高召回率及效果。同時，對迭代過程中的性能進行簡單的分析及衡量，這對相關的項目也具備一定的借鑒意義，最后對Word2Vec及End-to-End生成的向量進行了比較。

事實上，本文中提及的向量召回及深度學習融合非數值型特征的方案，已經在業界被廣泛使用。但對于差異化的場景，本文仍具備一定的借鑒價值，特別是對于訂單-騎手匹配、訂單-訂單匹配等非搜索推薦領域的場景化應用，以及TF OP算子的選用及分析、Embedding生成方式帶來的差異，希望能夠給大家提供一些思路和啟發。

5. 關聯閱讀

交付時間預估與ETA預估及配送其他業務關系：

• 交付時間預估是ETA預估中的重要一環，關于ETA預估，請參見《深度學習在美團配送ETA預估中的探索與實踐》。

• 具體ETA在整個配送業務中的位置及配送業務的整體機器學習實踐，請參看《機器學習在美團配送系統的實踐：用技術還原真實世界》。