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