機器之心報導
編輯：魔王、杜偉、小舟
公交車、計程車等交通工具的到達時間是影響公眾出行的一大因素。所以，預估到達時間（ETA）準確率成為非常實際的研究課題。近日，DeepMind 與谷歌地圖展開合作，利用圖神經網絡等 ML 技術，極大了提升了柏林、東京、雪梨等大城市的實時 ETA 準確率。
很多人使用谷歌地圖（Google Maps）獲取精確的交通預測和預估到達時間（Estimated Time of Arrival，ETA）。這是很重要的工具，尤其是當你將途經交通擁堵路段或者需要按時參加重要的會議。
此外，對於拼車服務公司等企業而言，這些功能也很有用。它們使用 Google Maps 平臺獲取接送時間信息並基於乘車時間估計價格。
DeepMind 研究者與 Google Maps 團隊展開合作，嘗試通過圖神經網絡等高級機器學習技術，提升柏林、雅加達、聖保羅、雪梨、東京和華盛頓哥倫比亞特區等地的實時 ETA 準確率，最高提升了 50%。下圖為這些城市的 ETA 提升率：
Google Maps 如何預測 ETA
為了計算 ETA，Google Maps 分析了世界各地不同路段的實時交通數據。這些數據為 Google Maps 提供了目前交通狀況的精確圖景，但是它卻無法幫助司機預計車程時間是 10 分鐘、20 分鐘，還是 50 分鐘。
所以，為了精確地預測未來交通狀況，Google Maps 使用機器學習將全球道路的實時交通狀況和歷史交通模式結合起來。這一過程非常複雜，原因很多。例如，早晚高峰每天都會有，但每一天、每一月的高峰期確切時間有很大不同。道路質量、限速、交通事故等因素也增加了交通預測模型的複雜度。
DeepMind 團隊與 Google Maps 合作嘗試提升 ETA 準確率。Google Maps 對超過 97% 的行程有著精確的 ETA 預測，DeepMind 與 Google Maps 的合作目的是將剩下那些預測不準確的情況最小化，例如臺中（Taichung）的 ETA 預測準確率提升了 50% 多。
為了在全球範圍內實現這一目的，DeepMind 利用了一種通用機器學習架構——圖神經網絡（GNN），通過向模型添加關係學習偏置來進行時空推理，進而建模現實世界道路網絡的連通性。具體步驟如下：
將世界上的道路分割為超級路段（Supersegment）
該團隊將道路網絡分割為包含多個鄰近路段的「超級路段」，超級路段都具有極大的交通流量。目前，Google Maps 交通預測系統包括以下組件：
路線分析器：具備數 TB 的交通信息，可用於構建超級路段；
新型 GNN 模型：使用多個目標函數進行優化，能夠預測每個超級路段的行程時間。
Google Maps 確定最優路線和行程時間的模型架構圖示。
用新型機器學習架構進行交通預測
利用超級路段創建估計行程時間的機器學習系統，所面臨的最大挑戰是架構問題。如何以任意準確率表示連接路段的規模可變樣本，進而保證單個模型也能預測成功？
DeepMind 團隊最初的概念證明始於一種簡單明了的方法，該方法儘可能地利用現有的交通系統，特別是已有的路網分割和相關的實時數據 pipeline。這意味著超級路段覆蓋了一組路段，其中每個路段都有特定的長度和相應的速度特徵。
首先，該團隊為每個超級路段訓練了一個全連接神經網絡模型。初步結果良好，表明神經網絡在預測行程時間方面是很有潛力的。但是，鑑於超級路段的可變規模，該團隊需要為每個超級路段單獨訓練神經網絡模型。要想實現大規模部署，則必須訓練數百萬個這樣的模型，這就對基礎設施構成了巨大的挑戰。
因此，該團隊開始研究能夠處理可變長度序列的模型，例如循環神經網絡（RNN）。但是，向 RNN 添加來自道路網絡的結構是很難的。於是，研究者決定使用圖神經網絡。在對交通情況進行建模時，車輛如何穿過道路網絡是該研究的關注點，而圖神經網絡可以對網絡動態和信息傳播進行建模。
該團隊提出的模型將局部道路網絡視為一個圖，其中每個路段對應一個節點，連接兩個路段（節點）的邊要麼在同一條道路上，要麼通過交叉點（路口）連接。在圖神經網絡中執行消息傳遞算法時，其傳遞的消息及其對邊和節點狀態的影響均由神經網絡學得。從這個角度看，超級路段是根據交通密度隨機採樣的道路子圖。因此，使用這些採樣的子圖能夠訓練單個模型，且單個模型可以進行大規模部署。
圖神經網絡通過泛化「相似度（proximity）」概念，擴展了卷積神經網絡和循環神經網絡所施加的學習偏置（learning bias），進而具備任意複雜度的連接，不僅可以處理道路前後方的交通情況，還可以處理相鄰和相交道路的情況。在圖神經網絡中，相鄰節點之間互相傳遞消息。在保持這種結構的情況下，研究者施加了局部偏置，節點將更容易依賴於相鄰節點（這僅需要一個消息傳遞步）。這些機制使圖神經網絡可以更高效地利用道路網絡的連通性結構。
實驗表明，將考慮範圍擴展到不屬於主要道路的相鄰道路能夠提高預測能力。例如，考慮小路上的擁堵狀況對大路交通情況的影響。通過跨越多個交叉路口，該模型能夠預測轉彎處的延誤、並道引起的延誤，以及走走停停交通狀況的通行時間。圖神經網絡在組合空間上的泛化能力使得該研究的建模技術具備強大能力。
每個超級路段的長度和複雜度可能各有不同（從簡單的兩段路到包含了數百個節點的較長路徑），但它們都可以使用同一個圖神經網絡模型進行處理。
從基礎研究到生產級機器學習模型
在學術研究中，生產級機器學習系統存在一個常常被忽視的巨大挑戰，即同一模型在多次訓練運行中會出現巨大的差異。雖然在很多學術研究中，細微的訓練質量差別可以簡單地作為 poor 初始化被丟棄，但數百萬用戶的細微不一致累加在一起就會產生極大的影響。
因此，在將該模型投入生產時，圖神經網絡對訓練中這種變化的魯棒性就成為了重中之重。研究者發現，圖神經網絡對訓練過程中的變化特別敏感，造成這種不穩定性的原因是訓練中使用的圖結構之間存在巨大差異。單批次圖可以涵蓋從兩節點小圖到 100 節點以上的大圖。
然而，在反覆試錯之後，研究者在有監督設置下採用了一種新型強化學習技術，解決了以上問題。
在訓練機器學習系統的過程中，系統的學習率決定了自身對新信息的「可塑性」。隨著時間推移，研究人員常常會降低模型的學習率，這是因為學習新東西和忘記已經學得的重要特徵之間存在著權衡，就像人類從兒童到成人的成長曆程一樣。
所以，在預定義訓練階段之後，研究者首先採用一種指數衰減學習率計劃來穩定參數。此外，研究者還探究和分析了以往研究中被證明有效的模型集成技術，從而觀察是否可以減少訓練運行中的模型差異。
最後，研究者發現，最成功的解決方案是使用 MetaGradient 來動態調整訓練期間的學習率，從而可以有效地使系統學得自身最優的學習率計劃。通過在訓練期間自動地調整學習率，該模型不僅實現了較以往更高的質量，而且還學會了自動降低學習率。最終實現了更穩定的結果，使得該新型架構能夠應用於生產。
通過自定義損失函數實現模型泛化
雖然建模系統的最終目標是減少行程預估中的誤差，但是研究者發現，利用多個損失函數（適當加權）的線性組合極大地提升了模型的泛化能力。具體而言，研究者利用模型權重的正則化因子、全局遍歷時間上的 L_2 和 L_1 損失、以及圖中每個節點的 Huber 和負對數似然（negative-log likelihood, NLL）損失，制定了一個多損失目標。
通過結合這些損失，研究者能夠指導模型並避免訓練數據集的過擬合。雖然對訓練過程的質量衡量標準並沒有變化，但是訓練中出現的提升更直接地轉化到留出（held-out）測試集和端到端實驗中。
目前，研究者正在探究，在以減少行程估計誤差為指導指標的情況下，MetaGradient 技術是否也可以用來改變訓練過程中多成分損失函數的構成。這項研究受到先前在強化學習中取得成功的 MetaGradient 的啟發，並且早期實驗也顯示出了不錯的結果。
參考內容：https://deepmind.com/blog/article/traffic-prediction-with-advanced-graph-neural-networks