閱讀筆記 : 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個交通資訊

X是圖訊號(也就是圖中各點在時間的特徵資訊)，G是圖結構資訊，h(.)表示本篇模型

方法

SPATIAL DEPENDENCY MODELING

本篇採用隨機遊走 (random walk) 的概念來詮釋擴散卷積 (diffusion convolution)，用於處理空間資訊。那首先來介紹一下在圖中的隨機遊走 。

隨機遊走 (random walk)

假設現在有一個醉漢，他移動的方式非常隨興，但我們想預測他最終會停在哪。幸好我們現在知道他可能停留的所有位置，也知道他從每個位置移動到鄰近位置的機率為多少，那們我們就可以根據上述，推算他最終停在各點的機率各自為為何，這就是隨機遊走。

而套用在圖上所有位置即是所有節點，而移動的機率，則是節點之間的邊所形成的轉移矩陣。

在進行無窮多次的轉移後，會達到一個靜態平衡 :

k 指的是當前步數，Do^(-1)W是轉移矩陣

α是重置機率，就是醉漢走一走跌回起點的機率，α越小醉漢越有機會走到遠處。W是加權接鄰矩陣，在本篇的交通中，代表的是道路之間距離，而Do^(-1)W則是正規化後的轉移矩陣。

擴散卷積 (diffusion convolution)

擴散卷積其實就是一個節點資訊流動的過程，本篇利用剛提到的隨機遊走來實現。就像是醉漢要拿酒給附近的朋友喝，但每走一步都會灑出來一點，最後剩下的就是要給朋友的量。酒就是傳遞的資訊，灑出來而減少就是隨機遊走的機率。
不過本篇在實際應用的時候，不可能走無限多不來找靜態平衡，所以設置了上限 K 步，而且考慮雙向傳遞的轉移矩陣，也就是醉漢不只分酒給朋友，也考慮朋友分酒給他的部分，所以在公式中，算總和處變為兩項。

X是圖訊號，p是訊號編號(訊號可能不只一種)，θ為模型參數

TEMPORAL DYNAMICS MODELING

在時間方面本篇採用RNN，RNN常見的運算單元 (unit) 為GRU、LSTM，本篇以GRU為基礎，提出融合擴散卷積的運算單元。

Gated Recurrent Unit (GRU)

RNN的精隨在於會將先前的輸入進行記憶歸納，並將這份記憶用於當前的計算，下圖中的 h 即是記憶。在GRU當中有兩個閘門，分別是(1) reset gate (r) 用於將記憶與當前輸入整合成臨時記憶，(2) update gate (z) 用於將臨時記憶更新進記憶中。更新後的結果既是新的記憶，也是當前輸出。

詳細公式如下，兩個閘門由模型參數、記憶、輸入計算得來。

W、U為模型參數，。表示乘法

Diffusion Convolutional Gated Recurrent Unit (DCGRU)

本篇提出的DCGRU，即是將原先線性轉換的部分，都以擴散卷積替換，蠻讓人驚豔的想法。

u是update gate，C是臨時記憶，θ*g表示以θ為參數的擴散卷積

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做結合。