1
| 本文作者： 奕欣 | 2018-08-21 19:22 | 專題：KDD 2018 |
國際數據挖掘領域的頂級會議 KDD 2018 在倫敦舉行，今年 KDD 吸引了全球范圍內共 1480 篇論文投遞，共收錄 293 篇，錄取率不足 20%。其中滴滴共有四篇論文入選 KDD 2018，涵蓋 ETA 預測 ( Estimated Time of Arrival, 預估到達時間) 、智能派單、大規模車流管理等多個研究領域。
四篇論文分別是（文末附論文打包下載地址）
Efficient Large-Scale Fleet Management via Multi-Agent Deep Reinforcement Learning
Kaixiang Lin (Michigan State University); Renyu Zhao (AI Labs, Didi Chuxing); Zhe Xu (AI Labs, Didi Chuxing); Jiayu Zhou (Michigan State University)
Multi-task Representation Learning for Travel Time Estimation
Yaguang Li (University of Southern California); Kun Fu (DiDi AI Labs); Zheng Wang (DiDi AI Labs); Cyrus Shahabi (University of Southern California); Jieping Ye (DiDi AI Labs); Yan Liu (University of Southern California)
Large-Scale Order Dispatch in On-Demand Ride-Sharing Platforms: A Learning and Planning Approach
Zhe Xu (AI Labs, Didi Chuxing); Zhixin Li (AI Labs, Didi Chuxing); Qingwen Guan (AI Labs, Didi Chuxing); Dingshui Zhang (AI Labs, Didi Chuxing); Qiang Li (AI Labs, Didi Chuxing); Junxiao Nan (AI Labs, Didi Chuxing); Chunyang Liu (AI Labs, Didi Chuxing); Wei Bian (AI Labs, Didi Chuxing); Jieping Ye (AI Labs, Didi Chuxing)
Learning to Estimate the Travel Time
Zheng Wang (Didi Chuxing); Kun Fu (Didi Chuxing); Jieping Ye (Didi Chuxing)
本文是對滴滴 KDD 2018 Poster 論文《Learning to Estimate the Travel Time》的詳細解讀，在這篇文章中，滴滴技術團隊設計了一種使用深度神經網絡來預測預估到達時間（ETA）的方案，通過將 ETA 建模成一個時空回歸問題，構建了一個豐富有效的特征體系，進一步提出 Wide-deep-recurrent（WDR）模型，能在給定出發時間和路線的情況下更加準確地預測。這一事件在雷鋒網學術頻道 AI 科技評論旗下數據庫項目「AI 影響因子」中有相應加分。
ETA 是智能交通和位置信息服務（Location Based Service，LBS）中至關重要、又極具復雜性和挑戰性的問題。它不僅需要考慮交通系統的空間特性，比如途徑紅綠燈的個數、道路的限速、是否可以繞遠走快速路；還要考慮交通系統的時間特性，比如早晚高峰的規律性擁堵和交通事故導致的偶發性擁堵等。同時，因為交通系統的運行需要人和車作為主體來參與，也少不了外部因素的影響，因此時間預估問題還需要引入對個性化特征和外部特征的建模，比如司機駕駛習慣、雨天霧天對行車速度的干擾等。
在滴滴平臺，ETA 是一項必不可少的基礎服務。無論是行程前的預估接駕時間、預估價格顯示，還是派單、調度、拼車等系統決策，亦或是行程中的預計到達終點的時間計算等，離不開高精度 ETA 的輔助。滴滴每天有約 700 億次的 ETA 請求，峰值時每秒要處理約 400 萬次。
用規則模型計算 ETA 是此前地圖行業通用做法之一。即分別計算各段路的行駛時間，全部加起來再根據紅綠燈時間做一個偏移修正。用數學來描述，預估時間
可以表達為
其中，
是第 i 個路段的預估行駛時間，而 
是第 j 個紅綠燈的預估等待時間。下圖更為直觀地展示了這種計算方法：
這是完全根據物理結構構建起來的模型，而其中最關鍵的部分在于每一路段的時間和每一個紅綠燈時間的獲取。考慮到路段的通行狀態每時每刻都在動態變化，一個比較實際的做法是利用最新的歷史數據（比如，剛剛過去的 5 分鐘）來估計路段的實時通行時間，而把歷史平均通行時間作為默認值來填充信息缺失的路段（若一個路段在最近沒有滴滴車輛經過，此時它的通行狀態是未知的）。紅綠燈亦可采用類似的做法從數據中去挖掘每個紅綠燈的歷史平均等待時間，用作
.
規則模型雖然在線服務計算量小，易于實現，但其使用大量基于經驗和直覺的人為規則，不僅缺乏科學的探索方法；局限多、擴展差，也容易遺漏了很多重要信息，比如個性化特征等；此外，簡單的統計量也不足以分析出復雜的交通模式，核心指標往往容易面臨瓶頸，無法再靠添加新規則進行優化。
為了更好地發揮海量出行數據的潛力，滴滴于 2015 年首創了一整套機器學習系統來解決 ETA 問題。從類型上看，ETA 是一個很典型的回歸問題：給定輸入特征，模型輸出一個實數值，代表了預測的行程時間。滴滴探索和構建了一套系統的地圖領域的特征和表達集合，包括空間信息、時間信息、交通信息、個性化信息、擴展信息等幾個方面，能充分考慮連通起點和終點的全部路徑、涉及的路段、路口和紅綠燈，以及所經過區域的 POI、行程對應的時間屬性、實時路況、司機的駕車行為以及天氣、交通管制情況等。
考慮到用戶對誤差的敏感程度更多的和相對值有關，滴滴將 MAPE（mean absolute percentage error）選擇為目標函數，對應于 MAPE 的優化問題為：
其中，
是真實到達時間（Actual Time of Arrival，ATA），而
是預估時間，
代表了回歸模型。為了防止 over-fitting，還可以加上正則項
而在回歸模型上，滴滴先后考慮過兩種在業界比較流行的模型，Tree Based model 和 Factorization Machine。其中，樹模型的最終輸出是多棵樹的集成結果，可以寫成：
是模型中樹的數量。每一棵樹都會根據輸入特征進行判斷，決定輸入數據所屬的葉子節點，然后將葉子節點對應的分數作為單棵樹的輸出，也就是
代表了第 t 棵樹全部葉節點構成的分數向量，
是一個映射函數（通過一系列條件判斷），決定了
應該歸屬的葉子節點序號。對于模型，其復雜度是由樹的結構和規模來控制的，即使用如下正則項
直觀來看，第一項對葉子節點的數目
進行了控制，而第二項通過 L2 范數來對葉子節點的輸出 score 進行控制。用樹模型做 ETA 任務的目標函數最終可以寫成
而 FM 模型的核心思路是將特征交互的權重矩陣進行分解，表達為向量內積的形式，以此來減少參數數量。二階 FM 的計算為
其中 d 是特征維度，通常在千萬級別甚至更高。而參數向量
的維度 m 相對很小，通常在幾十的量級便能達到較好的預測精度。FM 同樣可以對 ETA 進行回歸建模，加上一些正則項，就得到了優化目標
其中
表示 v 向量構成的矩陣的 Frobenius 范數。
雖然這一完整的機器學習解決方案，為滴滴帶來了顯著的 ETA 準確度提升，但由于大部分回歸模型比如 XGBoost，能夠接收的輸入向量必須是固定長度的，而一段行程對應的路段（以下稱為 link）數變動范圍很大，因此在實際使用時，舍去了 link 級的特征，取而代之使用整體統計值。所以在細節信息層面，這一解決方案還有優化的空間。
為了最大化信息的無損，保留模型對 link 序列信息的建模能力，滴滴創新地將深度學習應用到 ETA 上。這一 ETA 模型的核心思路是 global model + recurrent model。其中 global model 的作用類似于上一代模型，針對行程的全局信息進行學習；而 recurrent model 則專注于對 link 序列等局部細節的學習。
在 global model 部分滴滴考慮了近年來在推薦系統領域受到關注的 Wide & Deep 模型，以保證所有模塊都可以進行端到端的訓練。其 Wide 分支其實和 FM 是源出一脈的，對特征進行二階交叉，對歷史數據擁有一定的記憶功能。而它的 Deep 分支就是傳統的多層感知機結構，有較好的泛化能力。兩個分支強強聯手，能互取所長。
WD 模型的大體結構如下圖所示：
Recurrent model 的選擇則比較豐富，不僅僅限于 RNN（包括變種 GRU、LSTM、SRU 等），還可以是一維卷積 CNN，或者是純粹的 Attention model。以最流行的 LSTM 為例，它通過引入 additive memory 和 gate 來緩解簡單 RNN 的梯度消失問題：
將它和 WD 模型組合之后，就得到了 Wide-Deep-Recurrent model (WDR)。結構見下圖：
可以看到，這一模型總共有三類特征：
Dense feature：行程級別的實數特征，比如起終點球面距離、起終點 GPS 坐標等。
Sparse feature：行程級別的離散特征，比如時間片編號、星期幾、天氣類型等。
Sequential feature：link 級別的特征，實數特征直接輸入模型，而離散特征先做 embedding 再輸入模型。注意，這里不再是每個行程一個特征向量，而是行程中每條 link 都有一個特征向量。比如，link 的長度、車道數、功能等級、實時通行速度等。
其中，Wide 和 Deep 模塊對行程的整體信息進行建模，而 Recurrent 模塊對行程的軌跡進行細致的建模，可以捕捉到每條 link、每個路口的信息。在最終匯總時，Wide 模塊通過仿射變換把輸出變到合適維度，Deep 模塊直接把頂層 hidden state 作為輸出，而 Recurrent 模塊將 LSTM 的最后一個 hidden state 作為輸出。三個模塊的輸出向量被拼接起來，進入最終的 Regressor 進行預測，得到 ETA 值。全部參數都基于 MAPE loss 做梯度下降來訓練。
系統架構如下圖所示。最底層為數據源，分別是地圖信息、GPS 軌跡、訂單記錄和其它必要的附加信息。然后，原始數據經過特定的處理，變為模型可用的格式，用于訓練模型。注意這里有一個小分支，表示在訓練完成之后還單獨取出了一小批 up-to-date 數據進行 finetune，使得模型更傾向于最新收集的數據。線下訓練好的模型，最后被推送到線上系統，對外服務。
線下實驗中，滴滴對 2017 年前五月北京滴滴平臺的數據進行了適當的過濾，發現無論是 pickup（司機去接乘客）還是 trip（司機送乘客前往目的地），其 WDR 模型有較大幅度的提升。
滴滴也進行了為期一周的線上評估，從曲線可以看到，其模型在線上實際系統中也有著領先的性能。
滴滴團隊指出，雖然其 WDR 模型能進行更準確的預測，但仍然有很多問題需要進一步地探索，比如怎樣引入路網的拓撲圖結構，如何與路徑規劃進行融合，如何將路況算法與 ETA 聯合起來進行端到端的學習，如何預測時間區間而不是單個時間，如何提高線上系統的服務性能等，然是需要深入研究的課題。
（論文地址：Learning to Estimate the Travel Time
http://www.kdd.org/kdd2018/accepted-papers/view/learning-to-estimate-the-travel-time）
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
專題
