新GNN模型應用后 google maps準確率提升50%！

Google Maps是使用最廣泛的地圖app之一，其能預測交通情況的能力使其成為許多司機不可或缺的工具。近日，DeepMind宣布與其合作，幫助Google Maps變得更準確。

你是不是也經歷過這樣的故事?計劃著和女友約會，按照地圖預計的實時路況做準備，可是卻往往不太準時……

眼看著上班就要遲到，明明顯示會在10分鐘后到達的公交車，并沒有如期而至……

如果您是拼車服務的司機，地圖還會獲取接送時間信息，并依據此來估計價格。

全世界都有類似的煩惱。預估到達時間(ETA)準確率低，就是上述煩惱的原因。

ETA為什么低?

谷歌地圖也有一套預測算法。但畢竟世界是動態的，每天的狀況都有可能不同，特別是疫情期間。

例如，盡管上下班高峰時間都會發生在早上、晚上，但具體的確切時間可能每天、每月都有很大差異;一條小巷的擁堵，就會蔓延到下一個大路——這一點，地圖往往無法實時監控;另外，道路質量、限速、事故和封路等因素，都會給預測模型帶來麻煩。

近日，DeepMind宣布幫「兄弟一把」——與谷歌地圖展開合作，利用了一種圖神經網絡(GNN)，成功提升了谷歌地圖在柏林、東京、悉尼等大城市的實時 ETA 準確率，最高提升了50%。

DeepMind此次的研究，就是如何解決這個動態預測問題。

把道路劃片處理

道路網(road network)，指的是在一定區域內，由各種道路組成的相互聯絡、交織成網狀分布的道路系統，類似下圖這樣：

但這樣的數據太龐大了，于是，谷歌地圖將道路網劃分為幾個「超級路段」。超級路段就是指幾個相鄰的路段，因為這些路段的交通流會互相影響。

目前，谷歌Maps交通預測系統由以下部分組成：

(1)路由分析器，以構建超路段

(2)新GNN 模型，利用多個目標函數進行優化，能夠預測每個超級路段的行程時間。

確定最優路線及其出行時間的模型架構

解決架構問題

研究人員要面對一個挑戰：架構問題。

利用現有的交通系統，特別是已有的道路網分割和實時數據 pipeline，全連接神經網絡模型表現良好。但是，每個超級路段都需要單獨訓練神經網絡模型。

要想實現大規模部署，則必須訓練數百萬個這樣的模型，這就對基礎設施構成了巨大的挑戰。

因此，該團隊開始研究能夠處理可變長度序列的模型，例如循環神經網絡(RNN)。但是，向 RNN 添加來自道路網絡的結構也不是容易的事。

最后，研究者決定用圖神經網絡。在對交通情況進行建模時，車輛如何穿過道路網絡是該研究的關注點，而圖神經網絡可以對網絡動態和信息傳播進行建模。

該團隊提出的模型將局部道路網絡視為一個圖，其中每個路段對應一個節點，連接兩個路段(節點)的邊要么在同一條道路上，要么通過交叉點(路口)連接。

在訓練過程中動態調整圖神經網絡的學習速率，以使系統學習自己的最佳學習速率時間表。根據DeepMind的說法，通過在訓練過程中自動調整學習率，該模型不僅表現優異，還學會了自動降低學習率。

實驗表明，似乎范圍越大，預測能力越強。例如，考慮小路上的擁堵狀況對大路交通情況的影響。通過跨越多個交叉路口，該模型能夠預測轉彎處的延誤、并道引起的延誤，以及走走停停交通狀況的通行時間。

但每個超級路段的長度和復雜度可能各有不同(從簡單的兩段路到包含了數百個節點的較長路徑)，但它們都可以使用同一個圖神經網絡模型進行處理。

DeepMind與谷歌地圖團隊的合作，延續了該實驗室與谷歌產品部門的其他合作，包括努力改進谷歌Play Store的發現系統。除了谷歌，DeepMind還貢獻了算法、框架和方法論來支持Waymo的自動駕駛系統。