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

主要核心思想是：

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

把道路切割成超級路段

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

   

   

<<< 左右滑動見更多 >>>

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

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

預(yù)測模型

Deepmind也嘗試了幾個模型：

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

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

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

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

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

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

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

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

DeepMind也嘗試了幾個技術(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 來動態(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)，線性組合多個損失函數(shù)（適當(dāng)加權(quán)）能夠極大地提升了模型的泛化能力，避免過擬合。具體來說，這個多損失目標(biāo)使用了：

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

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

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