閱讀筆記 : DIFFUSION CONVOLUTIONAL RECURRENT NEURAL NETWORK: DATA-DRIVEN TRAFFIC FORECASTING
ICLR 2018
paper link : https://openreview.net/pdf?id=SJiHXGWAZ
概要
本篇針對時空圖的交通預測問題主要貢獻有二,(1) 提出作用於有向圖 (directed graph) 的擴散卷積機制 (diffusion convolution),(2) 改良 RNN 的運算單元,將其結合擴散卷積機制 (diffusion convolution)。
前言
以往的空間聚合通常只考慮,節點間僅有一個權重的圖,可能是無向圖或是單向圖 :
本篇認為應該考慮雙向圖,也就是節點間去回的權重各不相同 :
會這麼做是由於本篇提出的看法,同時也是數據觀察的結果,如下圖所示,路段1的交通狀況與路段2較為相近,卻與它距離較近的路段3交通狀況差異極大,這是由於交通與同向的鄰居關係較大,與對象關係卻不見得顯著。
舉個更生活化的例子,在放假時,南下國道總是塞車,而北上卻相對順暢,這時若是要預測南下的交通資訊,應該主要考慮南下的其他路段,而非北上的路段。
議題描述
輸入T’個歷史交通資訊,預測後T個交通資訊
方法
SPATIAL DEPENDENCY MODELING
本篇採用隨機遊走 (random walk) 的概念來詮釋擴散卷積 (diffusion convolution),用於處理空間資訊。那首先來介紹一下在圖中的隨機遊走 。
隨機遊走 (random walk)
假設現在有一個醉漢,他移動的方式非常隨興,但我們想預測他最終會停在哪。幸好我們現在知道他可能停留的所有位置,也知道他從每個位置移動到鄰近位置的機率為多少,那們我們就可以根據上述,推算他最終停在各點的機率各自為為何,這就是隨機遊走。
而套用在圖上所有位置即是所有節點,而移動的機率,則是節點之間的邊所形成的轉移矩陣。
在進行無窮多次的轉移後,會達到一個靜態平衡 :
α是重置機率,就是醉漢走一走跌回起點的機率,α越小醉漢越有機會走到遠處。W是加權接鄰矩陣,在本篇的交通中,代表的是道路之間距離,而Do^(-1)W則是正規化後的轉移矩陣。
擴散卷積 (diffusion convolution)
擴散卷積其實就是一個節點資訊流動的過程,本篇利用剛提到的隨機遊走來實現。就像是醉漢要拿酒給附近的朋友喝,但每走一步都會灑出來一點,最後剩下的就是要給朋友的量。酒就是傳遞的資訊,灑出來而減少就是隨機遊走的機率。
不過本篇在實際應用的時候,不可能走無限多不來找靜態平衡,所以設置了上限 K 步,而且考慮雙向傳遞的轉移矩陣,也就是醉漢不只分酒給朋友,也考慮朋友分酒給他的部分,所以在公式中,算總和處變為兩項。
TEMPORAL DYNAMICS MODELING
在時間方面本篇採用RNN,RNN常見的運算單元 (unit) 為GRU、LSTM,本篇以GRU為基礎,提出融合擴散卷積的運算單元。
Gated Recurrent Unit (GRU)
RNN的精隨在於會將先前的輸入進行記憶歸納,並將這份記憶用於當前的計算,下圖中的 h 即是記憶。在GRU當中有兩個閘門,分別是(1) reset gate (r) 用於將記憶與當前輸入整合成臨時記憶,(2) update gate (z) 用於將臨時記憶更新進記憶中。更新後的結果既是新的記憶,也是當前輸出。
詳細公式如下,兩個閘門由模型參數、記憶、輸入計算得來。
Diffusion Convolutional Gated Recurrent Unit (DCGRU)
本篇提出的DCGRU,即是將原先線性轉換的部分,都以擴散卷積替換,蠻讓人驚豔的想法。
Sequence to Sequence
基礎RNN中有個嚴重的問題,在GRU的架構圖中即可發現,我們輸入一個值,模型吐出一個結果,但如果我們要預測的長度與輸入的不同該怎麼辦呢?
本篇採用前人的解決方法 : sequence to sequence,有就可以輸入任意長度的輸入,再生成任意長度的輸出。這類型會有 encoder 與 decoder,encoder先將輸入濃縮為一個記憶,將這份記憶傳給 decoder,decoder 必定先吃一個起始符號,再一步步推導預測之後的輸出,直到預測出結束符號為止,或人工設定結束長度。
在訓練階段,decoder每預測一個就會對一次答案,並用修正後的結果去預測下一個,所以通常結果都會很好 : 美中不足 → fly in the ointment
不過在測試階段,因為沒有答案可以對,就將自己的輸出當作正確答案,產生錯誤就會不斷累積下去 : 美中不足 → American Chinese not enough
Scheduled Sampling
為了避免上述問題,本篇一樣採用了前人的智慧 : Scheduled Sampling,在訓練的時候,就有機會讓模型吃到自己預測的結果 ,使其在訓練時就一並處理自己預測可能產生的誤差 :
System Architecture
模型的整體架構由 encoder、decoder 組成,而 encoder、decoder 又由多層的 Diffusion Convolutional Recurrent Layer (含有多個DCGRU) 所組成,為避免預測的錯誤累積,在訓練時有機會使用自己的預測結果當作標準答案。
實驗部分
針對METR-LA、PEMS-BAY兩組資料集的資料,以每五分鐘為單位,預測15、30 、60 分鐘後以內的每個交通狀況。
可以稍微注意一下,這兩組資料算是相當簡單的資料集,多為主幹道且交會點不多。
誤差測量指標為mean absolute error (MAE),、root mean squared error (RMSE)、 mean absolute percentage error (MAPE),總之誤差越低越好。
預測結果
最右側為本篇提出的算法,可以看出吊打其他經典演算法。
EFFECT OF SPATIAL DEPENDENCY MODELING
分為三組比較,討論擴散卷積有多厲害 : (1) DCRNN-NoConv : 不使用擴散卷積,每個節點僅以自己的歷史資料做預測,(2) DCRNN-UniConv : 考慮正向擴散傳遞,圖為單向圖,(3) DCRNN : 考慮雙向擴散傳遞,圖為雙向圖。可見有擴散卷積的效果大勝,而考慮雙向的又再準確一些。
另外再比較有向圖與無向圖對於預測的結果影響,GCRNN為無向圖。
EFFECT OF TEMPORAL DEPENDENCY MODELING
討論如何具和時間最有效,分三組討論 : (1) DCNN : 使用1D卷積層來聚合時間資訊,(2) DCRNN-SEQ : 使用RNN,但不使用scheduled sampling,(3) DCRNN : 使用RNN,也使用scheduled sampling。可見使用RNN效果顯著,有沒有 scheduled sampling 也對預測結果影響很大。
結論
本篇透過對雙向圖中,資料節點關係的觀察,提出新的且更有效的擴散卷積機制,並巧妙的與RNN做結合。