如何用GNN提高ETAs準(zhǔn)確率

主要核心思想是：

1. 把道路切割成一個(gè)個(gè)的路段，每個(gè)路段視為一個(gè)節(jié)點(diǎn)，路段的相對(duì)位置構(gòu)成節(jié)點(diǎn)間的邊，形成路網(wǎng)的一個(gè)子圖（文章稱作Supersegments，超級(jí)路段）
2. 然后使用GNN模型來對(duì)超級(jí)路段的行程時(shí)間進(jìn)行預(yù)估。

把道路切割成超級(jí)路段

DeepMind把路網(wǎng)切割成一個(gè)個(gè)的路段，超級(jí)路段由多個(gè)相鄰路段組成。也就是說，超級(jí)路段包含了幾個(gè)路段，且每個(gè)路段都有特定的長(zhǎng)度和相應(yīng)的速度特征。每一個(gè)路段對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，一條路上的連續(xù)路段存在邊，或者通過路口進(jìn)行連接

   

   

<<< 左右滑動(dòng)見更多 >>>

該系統(tǒng)專門有一個(gè)模塊（route analyser，路由分析器）來專門處理大量的道路信息并構(gòu)建超級(jí)路段。

而構(gòu)建的模型則是用來預(yù)測(cè)每個(gè)超級(jí)路段的行程時(shí)間（travel time）。

預(yù)測(cè)模型

Deepmind也嘗試了幾個(gè)模型：

1. 為每一個(gè)超級(jí)路段配上一個(gè)全連接網(wǎng)絡(luò)，效果也不錯(cuò)；但超級(jí)路段的長(zhǎng)度是動(dòng)態(tài)的，所以需要單獨(dú)為每個(gè)超級(jí)路段都訓(xùn)練一個(gè)模型，大規(guī)模下這顯然不現(xiàn)實(shí)。
2. RNN模型能夠處理變長(zhǎng)序列；但是公路結(jié)構(gòu)是復(fù)雜的，這一類模型難以處理；

所以最終選擇了圖神經(jīng)網(wǎng)絡(luò)，把局部路網(wǎng)視為一個(gè)圖。也就是說，超級(jí)路段其實(shí)就是一個(gè)根據(jù)交通密度來隨機(jī)采樣形成的道路子圖。

GNN不僅可以處理前后兩段道路，還可以處理各種復(fù)雜的道路，比如交叉口。通過這種特性，DeepMind實(shí)驗(yàn)發(fā)現(xiàn)，通過把超級(jí)路段范圍擴(kuò)展到相鄰道路，而不僅僅是只包含主道路，能夠獲得性能上的提升（比如說某條小巷的擁堵、甚至堵到了主干道）。

通過考慮多個(gè)路口的情況，模型可以考慮到轉(zhuǎn)彎處、并道時(shí)的延誤和走走停停情況下的總時(shí)間。

無論多長(zhǎng)的超級(jí)路段（兩個(gè)路段或者數(shù)百個(gè)路段組成的），都能用同一個(gè)GNN模型來處理。

從研究到生產(chǎn)力

DeepMind發(fā)現(xiàn)GNN對(duì)訓(xùn)練過程（training curriculum）的變化非常敏感，主要原因是訓(xùn)練過程中使用的圖結(jié)構(gòu)的差異太大。一個(gè)batch中每張圖的節(jié)點(diǎn)數(shù)量從兩個(gè)到一百多個(gè)都有。

在這里我有個(gè)疑惑，難道不是每個(gè)超級(jí)路網(wǎng)采樣相同的節(jié)點(diǎn)，估計(jì)出每個(gè)路段的通行時(shí)間，然后再根據(jù)用戶的起點(diǎn)終點(diǎn)來拼接出總時(shí)間？就算說全球路網(wǎng)巨大，難以為每一個(gè)路段都計(jì)算，但還是能根據(jù)歷史記錄來找出特定的“常用”路段。所以還是得等他們出論文再看看怎么處理的。

DeepMind也嘗試了幾個(gè)技術(shù)：

1. 在監(jiān)督條件下的新型強(qiáng)化學(xué)習(xí)技術(shù)。
2. 在預(yù)定義訓(xùn)練階段之后，DeepMind使用指數(shù)衰減學(xué)習(xí)率計(jì)劃來穩(wěn)定模型的參數(shù)。
3. 還嘗試了集成技術(shù)，從而觀察是否可以減少訓(xùn)練過程中的模型差異。

這里原文寫得挺亂的，所以我姑且把涉及到技術(shù)列出來，到底是組合使用還是依次嘗試，還得琢磨琢磨。

最后，最成功的解決方案是使用 MetaGradient 來動(dòng)態(tài)調(diào)整訓(xùn)練期間的學(xué)習(xí)率，從而可以有效地使系統(tǒng)學(xué)得自身最優(yōu)的學(xué)習(xí)率計(jì)劃。最終實(shí)現(xiàn)了更穩(wěn)定的結(jié)果，使得該新型架構(gòu)能夠應(yīng)用于生產(chǎn)。

自定義損失函數(shù)實(shí)現(xiàn)模型泛化

DeepMind發(fā)現(xiàn)，線性組合多個(gè)損失函數(shù)（適當(dāng)加權(quán)）能夠極大地提升了模型的泛化能力，避免過擬合。具體來說，這個(gè)多損失目標(biāo)使用了：

1. 模型權(quán)重的正則化因子；
2. 全局遍歷時(shí)間上的 L2 和 L1 損失；
3. 圖中每個(gè)節(jié)點(diǎn)的 Huber 和負(fù)對(duì)數(shù)似然（negative-log likelihood, NLL）損失。

雖然沒有提高訓(xùn)練的指標(biāo)，但是能夠更泛化地應(yīng)用在測(cè)試集和端對(duì)端實(shí)驗(yàn)上。

目前，DeepMind 還在探索，在減少行程估計(jì)誤差（travel estimate errors）為指導(dǎo)下， MetaGradient 技術(shù)是否可以改變訓(xùn)練過程中的損失函數(shù)的組合成分。這項(xiàng)研究受 MetaGradient 的啟發(fā)，并且早期實(shí)驗(yàn)得到不錯(cuò)的結(jié)果。