本文主要關注于工業界的路線時長預估的挑戰！這篇工作可以說兼具前沿力與工業風，論文提出的ConSTGAT模型
同時在準确率和計算速度方面較現有模型獲得了顯著提升。至于這個炫酷模型的線上表現如何，感興趣的小夥伴打開百度地圖試試叭！
關注TechBeat社群(www.techbeat.net)，還有更多幹貨文章、技術Talk與你分享~
無論你是苦逼學生(公交地鐵狗)、職場萌新(打車狗)還是有錢大佬(有車一族)，隻要站在了北上廣深的土地上，就不可避免地每天要跟堵車和出行時間battle。
比如……
- 騎車5分鐘，公交半小時(說的就是後廠村
- 公交半小時，開車一小時(好想去蹭公交專線QAQ
- 開車一小時，打車到天亮(沒車的人别去西二旗瞎逛
大城市的出行時間可以說比薛定貓的谔都要魔幻……
但是！總有黑心老闆要求你務必幾點之前到公司，否則嘿嘿嘿，晚一分鐘罰10塊錢的那種。
當然了，還有比罰錢更殘酷的事情，是以，2020年的地圖類軟體不僅要計算出兩點之間的路線，還要盡可能精準地估計出當下的路線時長，減少出行的不确定性。路線時長預估也成為了當下不僅剛需，且非常有挑戰性的算法命題。
一、背景
工業界的路線時長預估的挑戰主要來源于以下兩方面：
- 路況預估的複雜性：雖然未來路況和曆史路況強相關，但實際情況中，路況往往受突發事件影響。此外，不少現有的方法使用時空圖網絡 (spatial temporal graph neural networks, STGNNs) 分别對時間和空間模組化，卻忽視了其中的關聯性，導緻了資訊有所損失。
- 路線的上下文資訊：路段有多種組合方式，路線中某個路段在不同的上下遊下的通行時長會有差異。比如說，同等距離下，車輛轉彎花費的時間通常比直行長。一些現有的方法使用端到端的方式，預估路線的通行時長。可是這些方法通常都是用序列化的方式模組化，性能效率較難滿足線上超高并發cc要求。
二、工業前沿
今天跟大家分享一下百度在資料挖掘頂級會議 KDD2020 上發表的一篇路線時長預估的工作——《ConSTGAT: Contextual Spatial-Temporal Graph Attention Network for Travel Time Estimation at Baidu Maps》。
論文提出了一種叫做ConSTGAT的模型，實驗表明可以有效提升路線時長預測的準确性，并顯著減小了預測任務所需的計算量。作為工業級的解決方案，ConSTGAT已經部署到百度的通行時長預估服務中，每天成功響應數百億次ETA請求。
圖1 百度地圖路線時長預估示例
總的來說，針對時空曆史路況資訊，ConSTGAT設計了新的三維時空圖注意力網絡(3D Graph Attention Network, 3DGAT)，它能夠在模組化的同時兼顧時間與空間的曆史路況的關聯性；在處理路線上下文資訊的方面，則使用了卷積結構提取路線上所有路段的局部上下文資訊，并使用多任務學習同時學習路線和路段的通行時長。
三、ConSTGAT架構
ConSTGAT模型的輸入包括三個部分：路線 (route)，背景資訊 (background)，和曆史路況 (historical traffic conditions)。其中，路線由多個路段組成，可以用路段的序清單示；背景資訊指代出發時間等資訊；曆史路況則是路網中相關的路段的曆史路況資訊。
網絡由三個核心子產品組成，包括：
- 上下文資訊子產品(Contextual Information)：以路段序列作為輸入，用于提取路段在路線中的上下文資訊；
- 路況預測子產品(Traffic Prediction)：以上下文資訊，背景資訊，和曆史路況資訊作為輸入，使用三維時空圖注意力網絡模組化對曆史路況模組化，預估未來的路況；
- 預估整合子產品(Integration)：使用多目标同時學習路段時長與路線時長。
圖2 ConSTGAT架構
其中，路況預測子產品用于路況預測，而上下文資訊子產品和預估整合子產品用于路線上下文模組化。
路況預測 (Traffic Prediction)
現有的許多工作利用時空圖網絡來解決路況預測問題。時空圖網絡可以看作圖網絡的一種特例，直接模組化曆史路況的時空資訊。然而，現有的時空圖網絡通常将時間資訊和空間資訊分開獨立看待，如先通過普通圖網絡模組化空間資訊，再通過序列結構模組化時間資訊，導緻時空之間關聯性有所損失。新的時空圖網絡3DGAT，可以同時模組化時間和空間的聯合關系。
圖3 3DGAT和傳統時空圖網絡比較(紅圈為目标路段，黑圈為鄰居路段。每一清單示某個曆史時刻目标路段和鄰居路段的路況)
假設有目标路段和它的鄰居路段-，這些路段在不同時刻的曆史路況、路段自身的特征資訊、路段的曆史時間資訊可以分别用三個矩陣表示，其中矩陣的每一行對應一個路段的資訊，最終這三個矩陣合并成一個矩陣，并重塑成一個三階的時空張量。
圖4 3DGAT對曆史路況的時空模組化過程
(為出發時刻，為曆史時刻數)
和經典的注意力機制類似，ConSTGAT将時空張量中的向量同時作為注意力機制中的keys 和values ，将上下文資訊和背景資訊作為query 。特别地，文中提出了一種新的注意力機制3D-attention，捕捉query和keys/values之間的關系。公式如下：
上下文資訊 (Contextual Information)
上下文資訊子產品和預估整合子產品負責利用路線的上下文資訊，結構如圖5所示。
圖5 上下文資訊模組化
- 上下文資訊子產品：通過使用卷積層抽取路段 (link) 在路線中的局部的上下文資訊。某個路段和它的上遊路段、下遊路段看作一個整體，也就是一條子路 (sub-path) 編碼。通過這樣的方式，路段之間的夾角以及主路和輔路之間的關聯等上下文關系可以被利用，作為其他子產品的輸入。
- 整合預測子產品：使用多任務學習同時預估路段通行時長 (link travel time) 與路線通行時長 (route travel time)。預估的路段通行時長相加為預估的路線通行時長。其中，使用Huber Loss作為路段的損失函數；使用相對誤差作為路線的損失函數。
相比傳統的端到端的方法，ConSTGAT将實時運算的任務轉成預運算任務+檢索任務，極大地減輕了總體運算量，是以更容易規模化。由于ConSTGAT沒有使用序列化的網絡結構，可以提前并行地計算并用表存儲每個路段的通行時長。當有路線時長預估請求到達時，隻需在表中檢索對應路段的時長并加和即可。是以，這個方案可以輕松地部署在大規模真實的導航服務中。
四、實驗
實驗設定
ConSTGAT使用了通過百度地圖收集的三個城市(太原，合肥和惠州)從19年07月21日到19年08月31日的路線資料。其中，前面4周資料用于模型訓練，最後1周資料用于評估。評估名額采用了目前通行時長預估領域最為常用的标準：平均絕對值相對誤差(MAPE)，平均誤差(MAE)和均方根誤差(RMSE)。
整體表現
ConSTGAT與五個基線方法進行了比較：AVG是均值曆史路段速度；DeepTravel是一個端到端的路線通行時間預測方法；STANN, DCRNN和 GAT+Attention都基于時空圖網絡，但它們都将時間和空間分開考慮。如下表所示，ConSTGAT在三個資料集的MAPE，MAE和RMSE都低于其他通行時長預估方法，表現最佳。
表1 ConSTGAT和基線方法的比較
模型分析
為了觀察3DGAT機制是否能有效捕捉路況的時空關聯行，文中分析和對比了不同場景下的注意力機制權重的熱度圖和曆史通行流量數和通行時間的關系。圖6中，顔色越深表示注意力機制權重越大，曆史記錄越多，或是通行速度越慢。
圖6a 3DGAT注意力機制權重的熱度圖
圖6b 曆史通行流量數
圖6c 曆史通行時間中位數
可以看出，3DGAT注意力機制捕捉到了一些規律，如：
- 下遊的路段相比起其他鄰居路段更重要；
- 曆史通行記錄越多的鄰居路段越重要；
- 通行速度越慢的鄰居路段越重要。
五、總結
這篇工作可以說兼具前沿力與工業風，論文提出的ConSTGAT模型同時在準确率和計算速度方面較現有模型獲得了顯著提升。其最大的創新點在于建立了時間模組化與空間模組化的關聯性，并且有效地利用了路線的上下文資訊。至于這個炫酷模型的線上表現如何，感興趣的小夥伴打開百度地圖試試叭！
-The End-
文章在哪兒？
www.techbeat.net進入社群，
選擇【文章】，即可檢視所有幹貨内容啦！
關于TechBeat社群
▼
TechBeat(www.techbeat.net)是一個荟聚全球華人AI精英的成長社群。
我們希望為AI人才打造更專業的服務和體驗，加速并陪伴其學習成長。
期待這裡可以成為你學習AI前沿知識的高地，分享自己最新工作的沃土，在AI進階之路上的更新打怪的根據地！
點選“❀在看”，讓更多朋友們看到吧~