導(dǎo)語(yǔ)據(jù) Uber 統(tǒng)計(jì)，2018年，全年的網(wǎng)約車使用次數(shù)達(dá)180億次，超過全球人口的兩倍。準(zhǔn)確的網(wǎng)約車訂單預(yù)測(cè)，能夠更好的調(diào)度車輛，提高車輛的利用率，減少等待時(shí)間，從而緩解交通擁堵，具有重要的經(jīng)濟(jì)和社會(huì)意義。近年來大火的圖神經(jīng)網(wǎng)絡(luò) GNN 相當(dāng)于提供了一種新的建模和解決時(shí)空數(shù)據(jù)預(yù)測(cè)的手段。 ST-MGCN 是滴滴出行 AI Lab 發(fā)表于 AAAI 2019 的一種基于時(shí)空多圖卷積網(wǎng)絡(luò)的網(wǎng)約車需求量預(yù)測(cè)模型。區(qū)域級(jí)需求預(yù)測(cè)是網(wǎng)約車服務(wù)的關(guān)鍵技術(shù)。準(zhǔn)確的網(wǎng)約車需求量預(yù)測(cè)可以指導(dǎo)車輛的調(diào)度，提高車輛的利用率，減少等待時(shí)間，以及緩解交通擁堵。區(qū)域之間所存在復(fù)雜的時(shí)空依賴關(guān)系使得這個(gè)問題具有很大挑戰(zhàn)。已有方法主要關(guān)注于建模相鄰區(qū)域在空間上的歐式相關(guān)性（Euclidean correlations），而作者發(fā)現(xiàn)距離較遠(yuǎn)區(qū)域之間的非歐相關(guān)性也對(duì)預(yù)測(cè)至關(guān)重要。
本文提出了時(shí)空多圖卷機(jī)網(wǎng)絡(luò) spatiotemporal multi-graph convolution network (ST-MGCN)，一個(gè)新的用于網(wǎng)約車需求預(yù)測(cè)的深度學(xué)習(xí)模型。作者首先將區(qū)域間的非歐相關(guān)性建模到多個(gè)圖，然后用多圖卷積（multi-graph convolution）來建模其相關(guān)性。用全局上下文信息（global contextual information）來建模時(shí)序信息，并進(jìn)一步提出了上下文門控循環(huán)神經(jīng)網(wǎng)絡(luò)模型（contextual gated recurrent neural network），給歷史數(shù)據(jù)分配權(quán)重。在兩個(gè)數(shù)據(jù)集上表現(xiàn)強(qiáng)于已有算法的 10% 以上。 論文背景據(jù) Uber 統(tǒng)計(jì)，2018年，全年的網(wǎng)約車使用次數(shù)達(dá)180億次，超過全球人口的兩倍。準(zhǔn)確的網(wǎng)約車訂單預(yù)測(cè)，能夠更好的調(diào)度車輛，提高車輛的利用率，緩解交通擁堵，具有重要的經(jīng)濟(jì)和社會(huì)意義。 網(wǎng)約車需求量預(yù)測(cè)問題可以通過其數(shù)據(jù)建模方式來理解。以1小時(shí)為時(shí)間單位，1km*1km 的網(wǎng)格為空間單位，某城市某個(gè)小時(shí)訂單量可以用如下所示的2d格點(diǎn)圖片來表示，每個(gè)格點(diǎn)的數(shù)值是在該時(shí)間段內(nèi)該區(qū)域所產(chǎn)生的滴滴打車的訂單數(shù)的總和。那么所謂網(wǎng)約車需求量預(yù)測(cè)，就是已知過去幾個(gè)小時(shí)每個(gè)格點(diǎn)的訂單數(shù)，預(yù)測(cè)未來的訂單數(shù)。 基于 grid 建模數(shù)據(jù)的示意圖 實(shí)際上，直接做網(wǎng)約車需求量預(yù)測(cè)的文章并不多，但這個(gè)問題可以歸結(jié)為交通流預(yù)測(cè)，并且本文的對(duì)比算法也是交通流預(yù)測(cè)模型，在同一網(wǎng)約車數(shù)據(jù)集上的表現(xiàn)。此外，交通流預(yù)測(cè)屬于城市計(jì)算問題（urban computing）Yu Zheng. 2014. Urban Computing Concepts, Methodologies, and Applications。這個(gè)概念由當(dāng)時(shí)還在微軟亞洲研究院的鄭宇提出。與我們生活息息相關(guān)的很多問題都可以歸結(jié)為城市計(jì)算問題。比如車輛調(diào)度問題，輸電網(wǎng)優(yōu)化，物流及供應(yīng)鏈管理，霧霾預(yù)測(cè)等。它們的特點(diǎn)是同時(shí)具有時(shí)間和空間兩個(gè)維度的信息。近年來大火的圖神經(jīng)網(wǎng)絡(luò) GNN 相當(dāng)于提供了一種新的建模和解決時(shí)空數(shù)據(jù)預(yù)測(cè)的手段。 問題定義本文要解決的問題是，如何能夠更好的建模多個(gè)區(qū)域之間所存在的非歐且多模態(tài)的時(shí)間和空間相關(guān)性，以實(shí)現(xiàn)高準(zhǔn)確率的網(wǎng)約車需求量預(yù)測(cè)。 問題的數(shù)學(xué)表述如下，輸入連續(xù) T 個(gè)時(shí)刻的格點(diǎn)集合 X（格點(diǎn)的值為訂單數(shù)），輸出下一時(shí)刻的訂單數(shù)，通過訓(xùn)練學(xué)習(xí)得到該映射函數(shù) f。 這里的多模態(tài)可以理解為多重維度的關(guān)系。如下圖所示，圖中區(qū)域1和區(qū)域2在空間上是相鄰關(guān)系，他們可能會(huì)有相似的約車量。區(qū)域1和區(qū)域3在功能上是相似的，可能在用車的 pattern 上存在比較高的相似性。區(qū)域4與區(qū)域1在同一條路旁邊，同理，他們也會(huì)存在某種約車的相似性。 此外，訂單數(shù)還與時(shí)間緊密相關(guān)，比如早晚高峰，節(jié)假日等，會(huì)對(duì)用車數(shù)產(chǎn)生比較大的影響，且會(huì)呈現(xiàn)某種周期性。所以，作者總結(jié)了這個(gè)問題所面臨的兩個(gè)挑戰(zhàn)?？臻g上，需要學(xué)習(xí)區(qū)域間存在的多模態(tài)非歐相關(guān)性。時(shí)間上，需要學(xué)習(xí)復(fù)雜的多個(gè)時(shí)刻的時(shí)間依賴關(guān)系。 時(shí)空數(shù)據(jù)預(yù)測(cè)的相關(guān)工作可以分為兩類：1. 將數(shù)據(jù)建模成為 2d image 上的格點(diǎn)，使用 CNN 的方法進(jìn)行預(yù)測(cè)；2. 將數(shù)據(jù)建模到 graph 的節(jié)點(diǎn)上，基于圖的方法進(jìn)行預(yù)測(cè)。建模稱為 2d image 的方法無法處理非歐數(shù)據(jù)（CNN 所處理的規(guī)整的網(wǎng)格是歐式空間）。假如就這個(gè)問題而言，我們建模為 1km*1km 的網(wǎng)格，那么整個(gè)城市不同區(qū)域使用的分辨率都是相同的，如果我們希望在市中心用更高的分辨率，郊區(qū)用更低的分辨率，或者加入某些興趣點(diǎn)，這種方法是無法實(shí)現(xiàn)的。而現(xiàn)有基于 graph 的方法，雖然在區(qū)域建模上具有很高靈活性，但是無法建模上述區(qū)域間多模態(tài)的相關(guān)性。 算法框架作者基于對(duì)網(wǎng)約車需求量預(yù)測(cè)問題的理解以及先驗(yàn)知識(shí)，設(shè)計(jì)了如下的算法框架。 主要分為三部分。 將每一幀的數(shù)據(jù)建模成為三張 graph。每張 graph 上的節(jié)點(diǎn)相同，即城市的網(wǎng)格化劃分。連邊通過如下圖所示的規(guī)則進(jìn)行構(gòu)建。根據(jù)不同維度的相關(guān)性（鄰域信息、功能相似度、交通連通性）確定節(jié)點(diǎn)之間的連邊值。 時(shí)間維度的預(yù)測(cè)：將T個(gè)歷史時(shí)間步的信息融合到一張圖上。 空間維度的預(yù)測(cè)：將一個(gè)時(shí)刻的不同的相關(guān)性的圖合成一個(gè)圖。這就是論文題目中所說的多圖卷積。 Contextual Gated Recurrent Neural Network (CGRNN)這是算法框架中的第二步，將 T個(gè)時(shí)間步的歷史數(shù)據(jù)融合為一張圖，這里所謂的 Contextual Gated 是指將歷史數(shù)據(jù)每一幀通過圖卷積網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)融合，并且通過全局 pooling 得到該小時(shí)的全局信息。這個(gè)全局信息再與原來的 T個(gè)時(shí)間步的數(shù)據(jù)做點(diǎn)乘，得到了帶權(quán)重的歷史數(shù)據(jù)。然后迭代地輸入到 RNN 中進(jìn)行時(shí)間維度的信息融合，最終得到一張圖。這里的 RNN 是權(quán)值共享的，也就是對(duì)于圖上的每個(gè)頂點(diǎn)都過同一個(gè) RNN，它們的所訓(xùn)練的是一套參數(shù)（工程上是可以實(shí)現(xiàn)的）。這樣的好處有兩點(diǎn)：1. 學(xué)習(xí)更加 general 的時(shí)序維度的匯聚方法，2. 減少模型復(fù)雜程度，使得更容易訓(xùn)練。 pooling 操作如下所示，將 t 時(shí)刻 graph 上所有節(jié)點(diǎn)的值都加起來，然后除以節(jié)點(diǎn)的個(gè)數(shù)。 這里需要注意的點(diǎn)是，每一幀數(shù)據(jù)做圖卷積的方法是使用 k-ordered ChebNet。這個(gè)方法與我們熟知的圖卷積網(wǎng)絡(luò) GCN 的區(qū)別是，GCN 可以簡(jiǎn)單地認(rèn)為是 1-ordered ChebNet，只是匯聚一階鄰居。如文中給出的示意圖所示。黑色是中心節(jié)點(diǎn)，黃色是 1階鄰居，紅色是 2階鄰居。通過 k-ordered ChebConv，可以實(shí)現(xiàn) k 階領(lǐng)域的信息交互。使用 k 層的 GCN 堆疊也可以實(shí)現(xiàn) k 階鄰域信息角度，但是隨著層數(shù)增加，訓(xùn)練難度加大。所以，這可能是作者做模型選擇的考慮點(diǎn)之一。 下面是相關(guān)的運(yùn)算公式：
對(duì) GCN 也不太熟悉的同學(xué)可以這樣通俗的理解 GCN 的作用。每個(gè) graph，都有對(duì)應(yīng)的表示節(jié)點(diǎn)連接關(guān)系的鄰接矩陣，還有數(shù)值在主對(duì)角線上，表示節(jié)點(diǎn)一階鄰居個(gè)數(shù)的度矩陣。拉普拉斯矩陣是通過鄰接矩陣、度矩陣，用上面圖中的公式計(jì)算得到的一個(gè)方陣。
在圖卷積中，拉普拉斯矩陣中的元素，用來充當(dāng)節(jié)點(diǎn)之間信息匯聚時(shí)，鄰居節(jié)點(diǎn)的特征向量相加中前面對(duì)應(yīng)的權(quán)重。下圖是算法框架中第三步的內(nèi)容（這兩步都用到 k-ordered ChebConv）。其中不考慮多圖的匯聚，花括號(hào)中的內(nèi)容就是一個(gè)圖上進(jìn)行卷積的操作。第一個(gè)方陣就是拉普拉斯矩陣，第二個(gè)矩陣是這本卷積層的輸入的鄰居節(jié)點(diǎn)的特征向量（維度是 V*P，V 是節(jié)點(diǎn)個(gè)數(shù)，編號(hào)等同于拉普拉斯矩陣中節(jié)點(diǎn)編號(hào)，也就是節(jié)點(diǎn)在行向量的排序，P 是特征向量維度）。這兩個(gè)矩陣進(jìn)行矩陣乘法，得到的就是每個(gè)節(jié)點(diǎn)匯聚了其鄰居節(jié)點(diǎn)特征的新的特征信息。這里的鄰居節(jié)點(diǎn)根據(jù)算法的 k-ordered 所定義的 k 而不同，而范圍不同，且會(huì)體現(xiàn)到拉普拉斯矩陣上。第三個(gè)矩陣 W 起到的作用等價(jià)于 MLP，做特征向量維度的變換。
感興趣的同學(xué)可以閱讀下面資料獲取更詳細(xì)的信息：GCN 作者 Kipf 的blog Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering，回顧頻譜圖卷積的經(jīng)典?工作: 從ChebNet到GCN，拉普拉斯矩陣， Multi-Graph Conv算法的第三步所進(jìn)行的是多圖的信息匯聚。下圖是以單個(gè)節(jié)點(diǎn)的視角來看這個(gè)算法的運(yùn)行。首先，每個(gè)節(jié)點(diǎn)先各自通過 k-ordered ChebConv，然后在進(jìn)行多圖匯聚，匯聚操作的單位是節(jié)點(diǎn)。在這里是將前面分別建模了鄰居信息、功能相似度、交通連通性的三個(gè)圖進(jìn)行匯聚。
下圖是具體的多圖匯聚的公式，括號(hào)內(nèi)就是普通的 k階 ChebConv，匯聚的方法可以是加和、平均、基于 attention 的匯聚等。
實(shí)驗(yàn)模型基于滴滴打車在北京和上海兩個(gè)城市的歷史訂單數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。對(duì)比了一些基本的時(shí)序預(yù)測(cè)（如果不考慮圖上節(jié)點(diǎn)之間的空間相關(guān)性，可以看成時(shí)序預(yù)測(cè)問題）模型，基于 image 建模的算法，基于 graph 的算法等。均得到了 10% 的提升。并且進(jìn)一步試驗(yàn)了去掉 multi-graph 中的某個(gè)圖，以及替換時(shí)間維度信息的匯聚方法，均證明當(dāng)前的模型是最好的。
總結(jié)作者提到，接下來會(huì)將算法推廣到其他的時(shí)空數(shù)據(jù)預(yù)測(cè)問題上，比如交通流、人流、霧霾預(yù)報(bào)等，以及提高模型的能力，以滿足多個(gè)時(shí)間步的預(yù)測(cè)需求。 此外，筆者認(rèn)為，基于該文章的多圖數(shù)據(jù)融合機(jī)制，增加高精度的降水短臨預(yù)報(bào)（例如，提供分鐘級(jí)、街道級(jí)降水預(yù)報(bào)的彩云天氣，http:/// ）可以顯著提升訂單數(shù)的預(yù)測(cè)準(zhǔn)確性。 本文提到的 k-order ChebNet 和上次讀書會(huì)分享的 GeniePath：自適應(yīng)感受路徑的圖神經(jīng)網(wǎng)絡(luò) GeniePath 復(fù)現(xiàn)代碼 Github 鏈接，都是可以進(jìn)行 k-hop 鄰居信息匯聚的方法，可以簡(jiǎn)單地認(rèn)為 GeniePath 是增加了 LSTM 的存儲(chǔ) cell 的 GCN，以實(shí)現(xiàn)文章提到的自適應(yīng)感受野的目的。本文的代碼復(fù)現(xiàn)，后續(xù)會(huì)發(fā)到的鏈接（https://github.com/shawnwang-tech/ST-MGCN-pytorch ）。感興趣的讀者可以 star 關(guān)注。 視頻回顧讀書會(huì)視頻分享鏈接： https://www.bilibili.com/video/av62438890 參考資料· 作者個(gè)人主頁(yè)： http://www-scf./~yaguang · 論文地址： http://www-scf./~yaguang/papers/aaai19_multi_graph_convolution.pdf · slides： http://www-scf./~yaguang/papers/aaai19_multi_graph_convolution_slides.pdf · poster： http://www-scf./~yaguang/papers/aaai19_stmgcn_poster.pdf · echarts格點(diǎn)地圖 https://echarts.baidu.com/examples/editor.html?c=map-bin · 鄭宇：深度學(xué)習(xí)在時(shí)空數(shù)據(jù)中的應(yīng)用 https://mp.weixin.qq.com/s/GakpFYtiNrVMNjPXUVjn1A · Junbo Zhang, Yu Zheng, Dekang Qi. AAAI 2017. Deep Spatio-Temporal Residual Networks for Citywide Crowd Flows Prediction https:///abs/1610.00081 · 回顧頻譜圖卷積的經(jīng)典工作: 從ChebNet到GCN： https://www.bilibili.com/read/mobile/2855698 |
|
|
