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