利用圖神經(jīng)網(wǎng)絡(luò)讓谷歌地圖實現(xiàn)新突破

公交車、出租車等交通工具的到達(dá)時間是影響公眾出行的一大因素。所以，預(yù)估到達(dá)時間（ETA）準(zhǔn)確率成為非常實際的研究課題。近日，DeepMind 與谷歌地圖展開合作，利用圖神經(jīng)網(wǎng)絡(luò)等 ML 技術(shù)，極大了提升了柏林、東京、悉尼等大城市的實時 ETA 準(zhǔn)確率。

很多人使用谷歌地圖（Google Maps）獲取精確的交通預(yù)測和預(yù)估到達(dá)時間（Estimated Time of Arrival，ETA）。這是很重要的工具，尤其是當(dāng)你將途經(jīng)交通擁堵路段或者需要按時參加重要的會議。 此外，對于拼車服務(wù)公司等企業(yè)而言，這些功能也很有用。它們使用 Google Maps 平臺獲取接送時間信息并基于乘車時間估計價格。 DeepMind 研究者與 Google Maps 團(tuán)隊展開合作，嘗試通過圖神經(jīng)網(wǎng)絡(luò)等高級機(jī)器學(xué)習(xí)技術(shù)，提升柏林、雅加達(dá)、圣保羅、悉尼、東京和華盛頓哥倫比亞特區(qū)等地的實時 ETA 準(zhǔn)確率，最高提升了 50%。下圖為這些城市的 ETA 提升率：

Google Maps 如何預(yù)測 ETA 為了計算 ETA，Google Maps 分析了世界各地不同路段的實時交通數(shù)據(jù)。這些數(shù)據(jù)為 Google Maps 提供了目前交通狀況的精確圖景，但是它卻無法幫助司機(jī)預(yù)計車程時間是 10 分鐘、20 分鐘，還是 50 分鐘。 所以，為了精確地預(yù)測未來交通狀況，Google Maps 使用機(jī)器學(xué)習(xí)將全球道路的實時交通狀況和歷史交通模式結(jié)合起來。這一過程非常復(fù)雜，原因很多。例如，早晚高峰每天都會有，但每一天、每一月的高峰期確切時間有很大不同。道路質(zhì)量、限速、交通事故等因素也增加了交通預(yù)測模型的復(fù)雜度。 DeepMind 團(tuán)隊與 Google Maps 合作嘗試提升 ETA 準(zhǔn)確率。Google Maps 對超過 97% 的行程有著精確的 ETA 預(yù)測，DeepMind 與 Google Maps 的合作目的是將剩下那些預(yù)測不準(zhǔn)確的情況最小化，例如臺中（Taichung）的 ETA 預(yù)測準(zhǔn)確率提升了 50% 多。 為了在全球范圍內(nèi)實現(xiàn)這一目的，DeepMind 利用了一種通用機(jī)器學(xué)習(xí)架構(gòu)——圖神經(jīng)網(wǎng)絡(luò)（GNN），通過向模型添加關(guān)系學(xué)習(xí)偏置來進(jìn)行時空推理，進(jìn)而建?，F(xiàn)實世界道路網(wǎng)絡(luò)的連通性。具體步驟如下： 將世界上的道路分割為超級路段（Supersegment） 該團(tuán)隊將道路網(wǎng)絡(luò)分割為包含多個鄰近路段的「超級路段」，超級路段都具有極大的交通流量。目前，Google Maps 交通預(yù)測系統(tǒng)包括以下組件：

路線分析器：具備數(shù) TB 的交通信息，可用于構(gòu)建超級路段；

新型 GNN 模型：使用多個目標(biāo)函數(shù)進(jìn)行優(yōu)化，能夠預(yù)測每個超級路段的行程時間。

Google Maps 確定最優(yōu)路線和行程時間的模型架構(gòu)圖示。 用新型機(jī)器學(xué)習(xí)架構(gòu)進(jìn)行交通預(yù)測 利用超級路段創(chuàng)建估計行程時間的機(jī)器學(xué)習(xí)系統(tǒng)，所面臨的最大挑戰(zhàn)是架構(gòu)問題。如何以任意準(zhǔn)確率表示連接路段的規(guī)?？勺儤颖?，進(jìn)而保證單個模型也能預(yù)測成功？ DeepMind 團(tuán)隊最初的概念證明始于一種簡單明了的方法，該方法盡可能地利用現(xiàn)有的交通系統(tǒng)，特別是已有的路網(wǎng)分割和相關(guān)的實時數(shù)據(jù) pipeline。這意味著超級路段覆蓋了一組路段，其中每個路段都有特定的長度和相應(yīng)的速度特征。 首先，該團(tuán)隊為每個超級路段訓(xùn)練了一個全連接神經(jīng)網(wǎng)絡(luò)模型。初步結(jié)果良好，表明神經(jīng)網(wǎng)絡(luò)在預(yù)測行程時間方面是很有潛力的。但是，鑒于超級路段的可變規(guī)模，該團(tuán)隊需要為每個超級路段單獨訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型。要想實現(xiàn)大規(guī)模部署，則必須訓(xùn)練數(shù)百萬個這樣的模型，這就對基礎(chǔ)設(shè)施構(gòu)成了巨大的挑戰(zhàn)。 因此，該團(tuán)隊開始研究能夠處理可變長度序列的模型，例如循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）。但是，向 RNN 添加來自道路網(wǎng)絡(luò)的結(jié)構(gòu)是很難的。于是，研究者決定使用圖神經(jīng)網(wǎng)絡(luò)。在對交通情況進(jìn)行建模時，車輛如何穿過道路網(wǎng)絡(luò)是該研究的關(guān)注點，而圖神經(jīng)網(wǎng)絡(luò)可以對網(wǎng)絡(luò)動態(tài)和信息傳播進(jìn)行建模。 該團(tuán)隊提出的模型將局部道路網(wǎng)絡(luò)視為一個圖，其中每個路段對應(yīng)一個節(jié)點，連接兩個路段（節(jié)點）的邊要么在同一條道路上，要么通過交叉點（路口）連接。在圖神經(jīng)網(wǎng)絡(luò)中執(zhí)行消息傳遞算法時，其傳遞的消息及其對邊和節(jié)點狀態(tài)的影響均由神經(jīng)網(wǎng)絡(luò)學(xué)得。從這個角度看，超級路段是根據(jù)交通密度隨機(jī)采樣的道路子圖。因此，使用這些采樣的子圖能夠訓(xùn)練單個模型，且單個模型可以進(jìn)行大規(guī)模部署。

圖神經(jīng)網(wǎng)絡(luò)通過泛化「相似度（proximity）」概念，擴(kuò)展了卷積神經(jīng)網(wǎng)絡(luò)和循環(huán)神經(jīng)網(wǎng)絡(luò)所施加的學(xué)習(xí)偏置（learning bias），進(jìn)而具備任意復(fù)雜度的連接，不僅可以處理道路前后方的交通情況，還可以處理相鄰和相交道路的情況。在圖神經(jīng)網(wǎng)絡(luò)中，相鄰節(jié)點之間互相傳遞消息。在保持這種結(jié)構(gòu)的情況下，研究者施加了局部偏置，節(jié)點將更容易依賴于相鄰節(jié)點（這僅需要一個消息傳遞步）。這些機(jī)制使圖神經(jīng)網(wǎng)絡(luò)可以更高效地利用道路網(wǎng)絡(luò)的連通性結(jié)構(gòu)。 實驗表明，將考慮范圍擴(kuò)展到不屬于主要道路的相鄰道路能夠提高預(yù)測能力。例如，考慮小路上的擁堵狀況對大路交通情況的影響。通過跨越多個交叉路口，該模型能夠預(yù)測轉(zhuǎn)彎處的延誤、并道引起的延誤，以及走走停停交通狀況的通行時間。圖神經(jīng)網(wǎng)絡(luò)在組合空間上的泛化能力使得該研究的建模技術(shù)具備強(qiáng)大能力。 每個超級路段的長度和復(fù)雜度可能各有不同（從簡單的兩段路到包含了數(shù)百個節(jié)點的較長路徑），但它們都可以使用同一個圖神經(jīng)網(wǎng)絡(luò)模型進(jìn)行處理。 從?基礎(chǔ)研究到生產(chǎn)級機(jī)器學(xué)習(xí)模型 在學(xué)術(shù)研究中，生產(chǎn)級機(jī)器學(xué)習(xí)系統(tǒng)存在一個常常被忽視的巨大挑戰(zhàn)，即同一模型在多次訓(xùn)練運行中會出現(xiàn)巨大的差異。雖然在很多學(xué)術(shù)研究中，細(xì)微的訓(xùn)練質(zhì)量差別可以簡單地作為 poor 初始化被丟棄，但數(shù)百萬用戶的細(xì)微不一致累加在一起就會產(chǎn)生極大的影響。 因此，在將該模型投入生產(chǎn)時，圖神經(jīng)網(wǎng)絡(luò)對訓(xùn)練中這種變化的魯棒性就成為了重中之重。研究者發(fā)現(xiàn)，圖神經(jīng)網(wǎng)絡(luò)對訓(xùn)練過程中的變化特別敏感，造成這種不穩(wěn)定性的原因是訓(xùn)練中使用的圖結(jié)構(gòu)之間存在巨大差異。單批次圖可以涵蓋從兩節(jié)點小圖到 100 節(jié)點以上的大圖。 然而，在反復(fù)試錯之后，研究者在有監(jiān)督設(shè)置下采用了一種新型強(qiáng)化學(xué)習(xí)技術(shù)，解決了以上問題。 在訓(xùn)練機(jī)器學(xué)習(xí)系統(tǒng)的過程中，系統(tǒng)的學(xué)習(xí)率決定了自身對新信息的「可塑性」。隨著時間推移，研究人員常常會降低模型的學(xué)習(xí)率，這是因為學(xué)習(xí)新東西和忘記已經(jīng)學(xué)得的重要特征之間存在著權(quán)衡，就像人類從兒童到成人的成長歷程一樣。 所以，在預(yù)定義訓(xùn)練階段之后，研究者首先采用一種指數(shù)衰減學(xué)習(xí)率計劃來穩(wěn)定參數(shù)。此外，研究者還探究和分析了以往研究中被證明有效的模型集成技術(shù)，從而觀察是否可以減少訓(xùn)練運行中的模型差異。 最后，研究者發(fā)現(xiàn)，最成功的解決方案是使用 MetaGradient 來動態(tài)調(diào)整訓(xùn)練期間的學(xué)習(xí)率，從而可以有效地使系統(tǒng)學(xué)得自身最優(yōu)的學(xué)習(xí)率計劃。通過在訓(xùn)練期間自動地調(diào)整學(xué)習(xí)率，該模型不僅實現(xiàn)了較以往更高的質(zhì)量，而且還學(xué)會了自動降低學(xué)習(xí)率。最終實現(xiàn)了更穩(wěn)定的結(jié)果，使得該新型架構(gòu)能夠應(yīng)用于生產(chǎn)。 通過自定義損失函數(shù)實現(xiàn)模型泛化 雖然建模系統(tǒng)的最終目標(biāo)是減少行程預(yù)估中的誤差，但是研究者發(fā)現(xiàn)，利用多個損失函數(shù)（適當(dāng)加權(quán)）的線性組合極大地提升了模型的泛化能力。具體而言，研究者利用模型權(quán)重的正則化因子、全局遍歷時間上的 L_2 和 L_1 損失、以及圖中每個節(jié)點的 Huber 和負(fù)對數(shù)似然（negative-log likelihood, NLL）損失，制定了一個多損失目標(biāo)。 通過結(jié)合這些損失，研究者能夠指導(dǎo)模型并避免訓(xùn)練數(shù)據(jù)集的過擬合。雖然對訓(xùn)練過程的質(zhì)量衡量標(biāo)準(zhǔn)并沒有變化，但是訓(xùn)練中出現(xiàn)的提升更直接地轉(zhuǎn)化到留出（held-out）測試集和端到端實驗中。 目前，研究者正在探究，在以減少行程估計誤差為指導(dǎo)指標(biāo)的情況下，MetaGradient 技術(shù)是否也可以用來改變訓(xùn)練過程中多成分損失函數(shù)的構(gòu)成。這項研究受到先前在強(qiáng)化學(xué)習(xí)中取得成功的 MetaGradient 的啟發(fā)，并且早期實驗也顯示出了不錯的結(jié)果。