滴滴研究院

+36

AI影響因子

論文

名稱：KDD

時(shí)間：

企業(yè)：滴滴

活動(dòng)

企業(yè)：滴滴

操作：獨(dú)家約稿

事項(xiàng)：KDD 2018獨(dú)家約稿

更多相關(guān)

國際數(shù)據(jù)挖掘領(lǐng)域的頂級會(huì)議 KDD 2018 在倫敦舉行，今年 KDD 吸引了全球范圍內(nèi)共 1480 篇論文投遞，共收錄 293 篇，錄取率不足 20%。其中滴滴共有四篇論文入選 KDD 2018，涵蓋 ETA 預(yù)測 ( Estimated Time of Arrival, 預(yù)估到達(dá)時(shí)間) 、智能派單、大規(guī)模車流管理等多個(gè)研究領(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》的詳細(xì)解讀，在這篇文章中，滴滴技術(shù)團(tuán)隊(duì)設(shè)計(jì)了一種使用深度神經(jīng)網(wǎng)絡(luò)來預(yù)測預(yù)估到達(dá)時(shí)間（ETA）的方案，通過將 ETA 建模成一個(gè)時(shí)空回歸問題，構(gòu)建了一個(gè)豐富有效的特征體系，進(jìn)一步提出 Wide-deep-recurrent（WDR）模型，能在給定出發(fā)時(shí)間和路線的情況下更加準(zhǔn)確地預(yù)測。這一事件在雷鋒網(wǎng)學(xué)術(shù)頻道 AI 科技評論旗下數(shù)據(jù)庫項(xiàng)目「AI 影響因子」中有相應(yīng)加分。

 從規(guī)則模型到完整的機(jī)器學(xué)習(xí)方案

ETA 是智能交通和位置信息服務(wù)（Location Based Service，LBS）中至關(guān)重要、又極具復(fù)雜性和挑戰(zhàn)性的問題。它不僅需要考慮交通系統(tǒng)的空間特性，比如途徑紅綠燈的個(gè)數(shù)、道路的限速、是否可以繞遠(yuǎn)走快速路；還要考慮交通系統(tǒng)的時(shí)間特性，比如早晚高峰的規(guī)律性擁堵和交通事故導(dǎo)致的偶發(fā)性擁堵等。同時(shí)，因?yàn)榻煌ㄏ到y(tǒng)的運(yùn)行需要人和車作為主體來參與，也少不了外部因素的影響，因此時(shí)間預(yù)估問題還需要引入對個(gè)性化特征和外部特征的建模，比如司機(jī)駕駛習(xí)慣、雨天霧天對行車速度的干擾等。

在滴滴平臺(tái)，ETA 是一項(xiàng)必不可少的基礎(chǔ)服務(wù)。無論是行程前的預(yù)估接駕時(shí)間、預(yù)估價(jià)格顯示，還是派單、調(diào)度、拼車等系統(tǒng)決策，亦或是行程中的預(yù)計(jì)到達(dá)終點(diǎn)的時(shí)間計(jì)算等，離不開高精度 ETA 的輔助。滴滴每天有約 700 億次的 ETA 請求，峰值時(shí)每秒要處理約 400 萬次。

用規(guī)則模型計(jì)算 ETA 是此前地圖行業(yè)通用做法之一。即分別計(jì)算各段路的行駛時(shí)間，全部加起來再根據(jù)紅綠燈時(shí)間做一個(gè)偏移修正。用數(shù)學(xué)來描述，預(yù)估時(shí)間可以表達(dá)為

其中，是第 i 個(gè)路段的預(yù)估行駛時(shí)間，而 是第 j 個(gè)紅綠燈的預(yù)估等待時(shí)間。下圖更為直觀地展示了這種計(jì)算方法：

這是完全根據(jù)物理結(jié)構(gòu)構(gòu)建起來的模型，而其中最關(guān)鍵的部分在于每一路段的時(shí)間和每一個(gè)紅綠燈時(shí)間的獲取?？紤]到路段的通行狀態(tài)每時(shí)每刻都在動(dòng)態(tài)變化，一個(gè)比較實(shí)際的做法是利用最新的歷史數(shù)據(jù)（比如，剛剛過去的 5 分鐘）來估計(jì)路段的實(shí)時(shí)通行時(shí)間，而把歷史平均通行時(shí)間作為默認(rèn)值來填充信息缺失的路段（若一個(gè)路段在最近沒有滴滴車輛經(jīng)過，此時(shí)它的通行狀態(tài)是未知的）。紅綠燈亦可采用類似的做法從數(shù)據(jù)中去挖掘每個(gè)紅綠燈的歷史平均等待時(shí)間，用作.

規(guī)則模型雖然在線服務(wù)計(jì)算量小，易于實(shí)現(xiàn)，但其使用大量基于經(jīng)驗(yàn)和直覺的人為規(guī)則，不僅缺乏科學(xué)的探索方法；局限多、擴(kuò)展差，也容易遺漏了很多重要信息，比如個(gè)性化特征等；此外，簡單的統(tǒng)計(jì)量也不足以分析出復(fù)雜的交通模式，核心指標(biāo)往往容易面臨瓶頸，無法再靠添加新規(guī)則進(jìn)行優(yōu)化。

為了更好地發(fā)揮海量出行數(shù)據(jù)的潛力，滴滴于 2015 年首創(chuàng)了一整套機(jī)器學(xué)習(xí)系統(tǒng)來解決 ETA 問題。從類型上看，ETA 是一個(gè)很典型的回歸問題：給定輸入特征，模型輸出一個(gè)實(shí)數(shù)值，代表了預(yù)測的行程時(shí)間。滴滴探索和構(gòu)建了一套系統(tǒng)的地圖領(lǐng)域的特征和表達(dá)集合，包括空間信息、時(shí)間信息、交通信息、個(gè)性化信息、擴(kuò)展信息等幾個(gè)方面，能充分考慮連通起點(diǎn)和終點(diǎn)的全部路徑、涉及的路段、路口和紅綠燈，以及所經(jīng)過區(qū)域的 POI、行程對應(yīng)的時(shí)間屬性、實(shí)時(shí)路況、司機(jī)的駕車行為以及天氣、交通管制情況等。

考慮到用戶對誤差的敏感程度更多的和相對值有關(guān)，滴滴將 MAPE（mean absolute percentage error）選擇為目標(biāo)函數(shù)，對應(yīng)于 MAPE 的優(yōu)化問題為：

其中，是真實(shí)到達(dá)時(shí)間（Actual Time of Arrival，ATA），而是預(yù)估時(shí)間，代表了回歸模型。為了防止 over-fitting，還可以加上正則項(xiàng)

而在回歸模型上，滴滴先后考慮過兩種在業(yè)界比較流行的模型，Tree Based model 和 Factorization Machine。其中，樹模型的最終輸出是多棵樹的集成結(jié)果，可以寫成：

是模型中樹的數(shù)量。每一棵樹都會(huì)根據(jù)輸入特征進(jìn)行判斷，決定輸入數(shù)據(jù)所屬的葉子節(jié)點(diǎn)，然后將葉子節(jié)點(diǎn)對應(yīng)的分?jǐn)?shù)作為單棵樹的輸出，也就是

代表了第 t 棵樹全部葉節(jié)點(diǎn)構(gòu)成的分?jǐn)?shù)向量，是一個(gè)映射函數(shù)（通過一系列條件判斷），決定了應(yīng)該歸屬的葉子節(jié)點(diǎn)序號。對于模型，其復(fù)雜度是由樹的結(jié)構(gòu)和規(guī)模來控制的，即使用如下正則項(xiàng)

直觀來看，第一項(xiàng)對葉子節(jié)點(diǎn)的數(shù)目進(jìn)行了控制，而第二項(xiàng)通過 L2 范數(shù)來對葉子節(jié)點(diǎn)的輸出 score 進(jìn)行控制。用樹模型做 ETA 任務(wù)的目標(biāo)函數(shù)最終可以寫成

而 FM 模型的核心思路是將特征交互的權(quán)重矩陣進(jìn)行分解，表達(dá)為向量內(nèi)積的形式，以此來減少參數(shù)數(shù)量。二階 FM 的計(jì)算為

其中 d 是特征維度，通常在千萬級別甚至更高。而參數(shù)向量的維度 m 相對很小，通常在幾十的量級便能達(dá)到較好的預(yù)測精度。FM 同樣可以對 ETA 進(jìn)行回歸建模，加上一些正則項(xiàng)，就得到了優(yōu)化目標(biāo)

其中表示 v 向量構(gòu)成的矩陣的 Frobenius 范數(shù)。

Wide-Deep-Recurrent 模型進(jìn)一步提升精度

雖然這一完整的機(jī)器學(xué)習(xí)解決方案，為滴滴帶來了顯著的 ETA 準(zhǔn)確度提升，但由于大部分回歸模型比如 XGBoost，能夠接收的輸入向量必須是固定長度的，而一段行程對應(yīng)的路段（以下稱為 link）數(shù)變動(dòng)范圍很大，因此在實(shí)際使用時(shí)，舍去了 link 級的特征，取而代之使用整體統(tǒng)計(jì)值。所以在細(xì)節(jié)信息層面，這一解決方案還有優(yōu)化的空間。

為了最大化信息的無損，保留模型對 link 序列信息的建模能力，滴滴創(chuàng)新地將深度學(xué)習(xí)應(yīng)用到 ETA 上。這一 ETA 模型的核心思路是 global model + recurrent model。其中 global model 的作用類似于上一代模型，針對行程的全局信息進(jìn)行學(xué)習(xí)；而 recurrent model 則專注于對 link 序列等局部細(xì)節(jié)的學(xué)習(xí)。

在 global model 部分滴滴考慮了近年來在推薦系統(tǒng)領(lǐng)域受到關(guān)注的 Wide & Deep 模型，以保證所有模塊都可以進(jìn)行端到端的訓(xùn)練。其 Wide 分支其實(shí)和 FM 是源出一脈的，對特征進(jìn)行二階交叉，對歷史數(shù)據(jù)擁有一定的記憶功能。而它的 Deep 分支就是傳統(tǒng)的多層感知機(jī)結(jié)構(gòu)，有較好的泛化能力。兩個(gè)分支強(qiáng)強(qiáng)聯(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í)數(shù)特征，比如起終點(diǎn)球面距離、起終點(diǎn) GPS 坐標(biāo)等。

• Sparse feature：行程級別的離散特征，比如時(shí)間片編號、星期幾、天氣類型等。

• Sequential feature：link 級別的特征，實(shí)數(shù)特征直接輸入模型，而離散特征先做 embedding 再輸入模型。注意，這里不再是每個(gè)行程一個(gè)特征向量，而是行程中每條 link 都有一個(gè)特征向量。比如，link 的長度、車道數(shù)、功能等級、實(shí)時(shí)通行速度等。

其中，Wide 和 Deep 模塊對行程的整體信息進(jìn)行建模，而 Recurrent 模塊對行程的軌跡進(jìn)行細(xì)致的建模，可以捕捉到每條 link、每個(gè)路口的信息。在最終匯總時(shí)，Wide 模塊通過仿射變換把輸出變到合適維度，Deep 模塊直接把頂層 hidden state 作為輸出，而 Recurrent 模塊將 LSTM 的最后一個(gè) hidden state 作為輸出。三個(gè)模塊的輸出向量被拼接起來，進(jìn)入最終的 Regressor 進(jìn)行預(yù)測，得到 ETA 值。全部參數(shù)都基于 MAPE loss 做梯度下降來訓(xùn)練。

系統(tǒng)架構(gòu)如下圖所示。最底層為數(shù)據(jù)源，分別是地圖信息、GPS 軌跡、訂單記錄和其它必要的附加信息。然后，原始數(shù)據(jù)經(jīng)過特定的處理，變?yōu)槟Ｐ涂捎玫母袷?，用于?xùn)練模型。注意這里有一個(gè)小分支，表示在訓(xùn)練完成之后還單獨(dú)取出了一小批 up-to-date 數(shù)據(jù)進(jìn)行 finetune，使得模型更傾向于最新收集的數(shù)據(jù)。線下訓(xùn)練好的模型，最后被推送到線上系統(tǒng)，對外服務(wù)。

線下實(shí)驗(yàn)中，滴滴對 2017 年前五月北京滴滴平臺(tái)的數(shù)據(jù)進(jìn)行了適當(dāng)?shù)倪^濾，發(fā)現(xiàn)無論是 pickup（司機(jī)去接乘客）還是 trip（司機(jī)送乘客前往目的地），其 WDR 模型有較大幅度的提升。

滴滴也進(jìn)行了為期一周的線上評估，從曲線可以看到，其模型在線上實(shí)際系統(tǒng)中也有著領(lǐng)先的性能。

滴滴團(tuán)隊(duì)指出，雖然其 WDR 模型能進(jìn)行更準(zhǔn)確的預(yù)測，但仍然有很多問題需要進(jìn)一步地探索，比如怎樣引入路網(wǎng)的拓?fù)鋱D結(jié)構(gòu)，如何與路徑規(guī)劃進(jìn)行融合，如何將路況算法與 ETA 聯(lián)合起來進(jìn)行端到端的學(xué)習(xí)，如何預(yù)測時(shí)間區(qū)間而不是單個(gè)時(shí)間，如何提高線上系統(tǒng)的服務(wù)性能等，然是需要深入研究的課題。

（論文地址：Learning to Estimate the Travel Time

http://www.kdd.org/kdd2018/accepted-papers/view/learning-to-estimate-the-travel-time）

或點(diǎn)擊本鏈接移步AI研習(xí)社社區(qū)下載四篇論文。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。