如果覺得我的算法分享對你有幫助，歡迎關注我的微信公眾號“圓圓的算法筆記”，更多算法筆記和世間萬物的學習記錄～

時間序列預測問題是根據(jù)一個序列的歷史值預測未來值。當同時預測多個時間序列，并且各個時間序列之間存在空間上的關系時，就不能只將每個時間序列單獨建模，而應該考慮不同時間序列之間的關系。例如，在交通預測場景中，需要預測不同地點的車流量，不同地點的車流量之間是存在空間上的關系的，例如A點的車20%在5分鐘后會開往B點。仍然用傳統(tǒng)的時間序列預測方法，即每個序列獨立地進行預測，無法捕捉這種不同地點的空間關系信息。

目前解決時間+空間預估的方法主要包括基于圖的時序預估和基于矩陣分解的時序預估兩種方法。本文通過6篇頂會論文介紹了這兩種類型方法的發(fā)展歷程。

1. 圖時序預估方法

本節(jié)介紹幾個圖模型中的基礎概念，感興趣的同學可以深入其他圖學習相關文章繼續(xù)學習。N個節(jié)點組成的圖可以由一個N*N的臨接矩陣和一個N*N的度數(shù)矩陣表示。臨接矩陣中第(i, j)個元素表示節(jié)點i和節(jié)點j之間在圖上的距離，這個距離根據(jù)具體任務和圖而定；度數(shù)矩陣是一個對角矩陣，第(i, i)個元素表示節(jié)點第i個節(jié)點和幾個邊相連。圖的拉普拉斯矩陣由臨接矩陣和度數(shù)矩陣計算得到，簡單來說，拉普拉斯矩陣衡量了圖中兩兩節(jié)點之間信息傳遞關系（具體來說，拉普拉斯矩陣是圖上的拉普拉斯算子，拉普拉斯算子是高維空間二階導數(shù)的推廣）。

通過拉普拉斯矩陣，我們可以將每個圖中每個節(jié)點的特征進行擴散到其他節(jié)點，得到每個節(jié)點考慮了圖中信息傳播后新的特征。圖卷積是圖模型的一種實例。在將傅立葉變換拓展到圖中時，發(fā)現(xiàn)傅立葉變換中的基就是圖的拉普拉斯矩陣的特征向量。這樣解決了Spatial卷積方法中，無法比較好的選擇鄰居節(jié)點、無向量化表示的問題。

拉普拉斯矩陣有不同的形式，例如最基礎的拉普拉斯矩陣L=D-A，還有如下正則化拉普拉斯矩陣、隨機游走拉普拉斯矩陣等，不同的拉普拉斯矩陣反應了圖上信息流動方式的不同先驗。

RNN是最基礎的時間序列預測深度學習模型，RNN天然的序列建模能力可以很好的處理時間序列數(shù)據(jù)。在RNN的基礎上，DIFFUSION CONVOLUTIONAL RECURRENT NEURAL NETWORK: DATA-DRIVEN TRAFFIC FORECASTING（ICLR 2018）提出DCRNN模型，通過將圖的思想引入RNN，使RNN能夠同時輸入空間中多個節(jié)點的時間序列，在學習時間維度依賴的同時，學習不同節(jié)點的空間關系。

GRU是RNN模型的一種，DCRNN在GRU的基礎上，將原來GRU中的全連接部分修改為diffusion convolutional layer（隨機游走拉普拉斯矩陣+全連接），公式可以表示為如下形式：

不論是普通的GRU還是DCRNN，都可以將整個圖上的所有節(jié)點序列同時輸入到模型中（相當于一個batch）。GRU在建模時，每個時間序列的表示使用共享的全連接層分別進行轉換，因此不同序列之間并沒有建立關系；而DCRNN中，模型根據(jù)臨接矩陣拉普拉斯矩陣的形式，可以生成一個不同節(jié)點表示的融合方式（矩陣），將每個序列的表示使用這個融合矩陣進行一次轉換，輸出的還是每個序列的表示，只不過通過融合矩陣建立的不同序列的關系，每個序列生成的表示都是其他序列的某種加權平均。其他部分和RNN類似，是序列建模的結構，模型整體結構如下圖：

另一種模型框架是Graph WaveNet for Deep Spatial-Temporal Graph Modeling（IJCAI 2019）提出的TCN+GCN的結構。TCN是一種應用于時間序列預測的CNN模型，通過空洞卷積增大感受野面積，通過因果卷積防止數(shù)據(jù)泄漏。GCN就是圖卷積神經網絡。Graph Wavenet采用的是一層時序模型+一層圖模型嵌套的方式實現(xiàn)的。第一層輸入圖中所有節(jié)點的時間序列數(shù)據(jù)，通過TCN每個序列獨立提取表示。在得到每個序列每個時刻的表示后，每個時刻內所有節(jié)點的表示使用GCN進行一次空間上的融合。假設輸入的維度是[N, T, D]，N表示節(jié)點數(shù)量，T表示時間長度，D表示特征維度。經過一層TCN后，維度變成[N, T', D']，這一步是每個序列獨立進行的。接下來在T維度上，每一個時刻t都進行圖卷積，得到[N, T', D'']。

由于在時序預估中，有一些場景并不存在明確的節(jié)點之間的圖關系，因此有一些工作將圖結構的學習也融入到時序預估中端到端訓練。也就是說，這類方法的拉普拉斯矩陣，是網絡直接學出來的，而不是根據(jù)預先定義的臨接矩陣和度數(shù)矩陣計算得到的。在Graph Wavenet中就采用了這種方式。Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks（KDD 2020）中對這類方法不同的拉普拉斯矩陣學習方式進行了對比。下表列出了不同的拉普拉斯矩陣生成方法的效果對比，這類方法的一半思路是根據(jù)每個節(jié)點的Embedding，通過不同的計算方式得到拉普拉斯矩陣中每個元素的值，這個值直接用于后續(xù)的圖學習，端到端和時序預估任務一起訓練。

除了GCN外，基于Attention的圖時序預估模型也是一種主流方法。GMAN: A Graph Multi-Attention Network for Traffic Prediction（AAAI 2020，GMAN）提出了基于Attention的圖時序預估模型，在時間維度和空間維度都是通過Attention實現(xiàn)的。GMAN采用的模型框架與DCRNN、GraphWavenet都不同，GMAN在每層并行進行時間維度和空間維度的信息提取，再通過Gate進行融合。在時間維度，采用類似于Transformer的Attention模型，Encoder內部、Decoder內部、Encoder和Decoder之間進行Attention。在空間維度，利用Attention機制計算每一對節(jié)點之間的Attention score，這個attention score的作用類似于拉普拉斯矩陣，用于生成融合了其他節(jié)點信息的當前節(jié)點表示。模型整體結構如下圖所示。

2. 基于矩陣分解的時序預估方法

基于分解的多序列聯(lián)合建模方法，利用矩陣分解的思路，該方法最早起源于Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction（NIPS 2016，TRMF）。整體思路如下圖，將所有時間序列組成一個矩陣N*T，然后通過矩陣分解的方法，將原矩陣分解成兩個子矩陣F（N*d）和T（d*T），其中d*T可以理解為d個組成當前時間序列的base序列，數(shù)據(jù)中的所有序列都是由這些base序列的線性組合得到的。同時，為了讓矩陣分解得到的base序列符合時間序列的平滑特性，會對生成的每個base序列使用自回歸模型進行約束。

在此基礎上，Think Globally, Act Locally: A Deep Neural Network Approach to High-Dimensional Time Series Forecasting（NIPS 2019，DeepGLO）提出了使用深度學習模型對base序列正則化。模型的損失函數(shù)由兩個部分組成，公式可以表示為：

第一項是矩陣分解的損失，第二項是分解得到的base序列使用深度模型進行預測的損失。模型采用兩個損失迭代的方式進行訓練。首先固定深度模型，最小化第一項矩陣分解損失；接下來固定矩陣分解結果，訓練深度時序模型，即固定第一項優(yōu)化第二項。文中采用的深度模型為TCN模型。

DeepGLO采用兩階段而非端到端的訓練方式，可能得到的不是最優(yōu)解。Temporal Latent Auto-Encoder: A Method for Probabilistic Multivariate Time Series Forecasting（AAAI 2021）設計了一種端到端的學習方法。原始的矩陣分解可以表示為Y=FX，進而可以表示為Y=FF'Y，該方法將原來的矩陣分解部分改為AutoEncoder，即通過Encoder隱式得到base序列，再通過Decoder還原原始序列。對于第二項時序約束，本文在Encoder和Decoder之間引入LSTM，利用LSTM對生成的base序列進行預測，以得到base序列的時序約束。整體損失仍然由兩部分組成，可以表示為如下形式，模型結構如下圖：

3. 總結

本文介紹了當面臨多個序列存在相關關系的時序預估問題時采用的方法。主要包括兩大類方法，分別為圖時序預估方法和基于分解的多序列聯(lián)合建模方法。其中，圖時序預估方法通過對時序模型中引入圖模型實現(xiàn)，例如用圖修改RNN的模塊、圖模型和時序模型交替提取信息、圖模型和時序模型分別提取信息再融合等思路。圖模型的使用也包括圖卷積網絡、基于Attention的網絡等?；诜纸獾亩嘈蛄新?lián)合建模方法建立在矩陣分解結合時序平滑性約束的基礎上。從最初的TRMF演變到使用深度學習模型進行時序平滑性約束，再到端到端的矩陣分解和時序平滑性約束端到端聯(lián)合學習

如果覺得我的算法分享對你有幫助，歡迎關注我的微信公眾號“圓圓的算法筆記”，更多算法筆記和世間萬物的學習記錄～

【歷史干貨算法筆記，更多干貨公眾號后臺查看】

五花八門的多模態(tài)模型如何選擇？

一網打盡：14種預訓練語言模型大匯總

NLP Prompt系列——Prompt Engineering方法詳細梳理

Domain Adaptation：缺少有監(jiān)督數(shù)據(jù)場景下的遷移學習利器

從ViT到Swin，10篇頂會論文看Transformer在CV領域的發(fā)展歷程