论文笔记：Autoregressive Tensor Factorizationfor Spatio-temporal Predictions
0 摘要
????????張量因子tensor factorization分解方法在時空數(shù)據(jù)分析領(lǐng)域很受歡迎，因?yàn)樗鼈兡軌蛱幚矶喾N類型的時空數(shù)據(jù)，處理缺失值，并提供計(jì)算效率高的參數(shù)估計(jì)程序。
????????然而，現(xiàn)有的張量因子分解方法并沒有嘗試學(xué)習(xí)空間自相關(guān)。這些方法使用先前推斷的空間依賴性，通常導(dǎo)致插值和未知位置預(yù)測問題的性能較差。
????????本文提出了一種新的張量因子分解方法，通過同時學(xué)習(xí)空間和時間的自相關(guān)來估計(jì)低秩潛在因子。在現(xiàn)有空間自回歸模型的基礎(chǔ)上引入了新的空間自回歸正則化方法，并給出了一種有效的估計(jì)方法。
?
1 introduction
? ? ? ? 在時空數(shù)據(jù)分析任務(wù)中時，數(shù)據(jù)的數(shù)量級、數(shù)量的類型、數(shù)據(jù)缺失值的處理，是目前主要研究的問題。
????????向量自回歸模型(VAR)和高斯過程(GP)是對多元時間序列進(jìn)行預(yù)測的常用方法。這些方法將線性或非線性的空間和時間相關(guān)性納入預(yù)測。然而，當(dāng)我們試圖分析一個多元時間序列時，VAR和GP需要指數(shù)計(jì)算成本。因此，這些模型在分析大尺度時空數(shù)據(jù)時是不可行的。
????????大尺度時空數(shù)據(jù)分析的替代方法是矩陣/張量分解技術(shù)。
?????????為了將空間和時間依賴性整合到分解中，大多數(shù)現(xiàn)有的分解方法都采用了基于圖的正則化項(xiàng)[Collaborative filtering with graph information: Consistency and scalable methods, NIPS 2015]，通過表示空間和時間結(jié)構(gòu)的輔助圖，使得隱藏層因子平滑化。
????????這些方法需要事先對加權(quán)時空圖矩陣進(jìn)行推理，但是對于如何構(gòu)造加權(quán)時空圖矩陣，幾乎沒有統(tǒng)一的準(zhǔn)則。因此，這些方法的性能很大程度上依賴于權(quán)值和圖結(jié)構(gòu)的選擇。此外，這些方法在出現(xiàn)負(fù)相關(guān)的情況下是不夠的。
論文筆記:Temporal Regularized Matrix Factorization forHigh-dimensional Time Series Prediction_UQI-LIUWJ的博客-CSDN博客
????????Yu等人[Temporal regularized matrix factorization for high-dimensional time series prediction NIPS?2016]最近提出了一種新的方法，稱為時間正則化矩陣分解(TRMF)，該方法在分解框架中引入了自回歸正則化器。然而，他們沒有考慮學(xué)習(xí)空間依賴性的問題。因此，我們能否對未知的位置進(jìn)行精確的插值和預(yù)測仍然是個問題。
????????在本文中，我們解決了插值和預(yù)測未知位置的未來觀測的問題。
????????為了解決這個問題，我們提出了一種新的張量分解方法，通過同時學(xué)習(xí)每個張量潛在因子的時空自相關(guān)，將張量分解為潛在因子。
????????我們在傳統(tǒng)自回歸模型的基礎(chǔ)上引入了空間自回歸正則化器。結(jié)合我們的空間自回歸正則化器和時間自回歸正則化器[11]，我們可以預(yù)測未知位置的特征觀測值。
????????此外，利用數(shù)據(jù)中所有觀測值均為非負(fù)值的特性，我們可以從時空數(shù)據(jù)中提取出更穩(wěn)健和可解釋的潛在因子。
????????為了估計(jì)因子矩陣和系數(shù)的空間和時間自回歸模型，我們展示了一個計(jì)算效率高的程序。
????????我們在三個公開的時空數(shù)據(jù)集上實(shí)驗(yàn)評估了我們提出的方法的預(yù)測性能，并證明了它如何顯著提高插值和預(yù)測未知位置觀測的預(yù)測精度。
?2 Preliminary
2.1 張量分解
????????我們把，T個時間戳、M種數(shù)據(jù)源、P個位置觀測到的時空數(shù)據(jù)表示為一個三向張量
? ? ? ? ?X中被觀測到的點(diǎn)被記為：
? ? ? ? ?對于P、T、M我們有：、、。其中
K<<min(P,T,M)
? ? ? ? 一個最naive的張量分解式子為：
????????圖拉普拉斯正則化被廣泛應(yīng)用于張量分解方法中，其分解具有空間和時間依賴性。表示第N個因子矩陣的加權(quán)鄰接矩陣為，則拉普拉斯矩陣為
? ? ? ? ?于是圖拉普拉斯正則項(xiàng)可以寫成
?????????雖然它在時空分析中顯示出有用，但是鄰接矩陣權(quán)值的構(gòu)造依賴于用戶的選擇
?2.2? 2D-AR
????????為了考慮圖像分析中的空間自相關(guān)性，在計(jì)算機(jī)視覺領(lǐng)域提出了二維自回歸模型(2D-AR)。
? ? ? ? 我們定義一個L階滯后集以及權(quán)重集合
? ? ? ? ?2D-AR是希望
????????2D-AR模型在許多任務(wù)中都取得了成功，比如估計(jì)圖像的觀測值。然而，由于該方法是為計(jì)算機(jī)視覺設(shè)計(jì)的，所以它只適用于一組具有網(wǎng)格形狀的位置。?
?3 提出的模型
3.1 自回歸張量分解
損失函數(shù)為：
?
?g1,g2分別是空間和時間自回歸正則項(xiàng)，PΩ表示只考慮 observed entry
?????????為了學(xué)習(xí)潛在因素的空間依賴性，我們提出了兩種基于空間自回歸模型的空間正則化器。這個公式的主要優(yōu)點(diǎn)是，我們提出的方法不需要預(yù)先推斷空間和時間的相關(guān)性。這種方法可以學(xué)習(xí)到適合每個潛在因素的個體依賴關(guān)系。
3.2 空間自回歸模型????????
????????與前面2.2所提及的2D-AR模型假設(shè)不同，由于道路網(wǎng)絡(luò)的拓?fù)錀l件或傳感器的目的，傳感器的位置并不總是處于網(wǎng)格形狀。因此，該方法不適用于時空數(shù)據(jù)分析。
????????為了解決這些問題，我們提出了一種有向自回歸(DAR)正則化方法.
????????我們的關(guān)鍵假設(shè)是，傳感器觀測值之間有一個基于方向的依賴關(guān)系，因此傳感器的觀測值可以由這些系數(shù)、基于距離的權(quán)重和其鄰居的觀測值的總和來近似。
????????我們在圖2中說明了DAR的主要思想。我們將2π角分成N個離散方向，并定義每個方向的系數(shù)參數(shù)。
?????????
? ? ? ? ?定義DAR模型的系數(shù)為，點(diǎn)p最近的k個鄰居為Ep，Ep中的點(diǎn)p'的權(quán)重值為，其中
? ? ? ? ?于是我們DAR的懲罰函數(shù)為：
?????????np’表示了從p到p'的方向，歸一化權(quán)值可以表示位置之間的逆距離
?3.3 參數(shù)估計(jì)
????????我們通過將損失函數(shù)重寫為約束極小化問題，提出了另一種極小化程序來實(shí)現(xiàn)我們所提出的方法的極小化
????????
?3.3.1? 更新 θ1
? ? ? ? 從定義中，我們知道，和相關(guān)的損失函數(shù)是：
?
? ? ? ? ?通過最小二乘法，我們有：、????????
? ? ? ? 其中?矩陣表示
?
?其中
3.3.2 更新 Θ2
線性代數(shù)筆記： Cholesky分解_UQI-LIUWJ的博客-CSDN博客
?????????wl的參數(shù)估計(jì)問題等于求解嶺回歸問題[11]，我們可以用Cholesky分解方法求解，其計(jì)算復(fù)雜度為
?3.3.3 更新U(1) 【空間特征矩陣】
? ? ? ? 空間特征矩陣U(1)的損失函數(shù)為：?
其中，Gk就是Bk
????????由于這是一個凸極小值問題，我們交替地通過求解最小二乘問題來更新每個因子向量u(1) k:
?
? ? ? ? ?這里=
? ? ? ? 通過將損失函數(shù)的梯度設(shè)置為0，我們有：
?
?其中
3.3.4 更新 U(2)?
? ? ? ? U(2)的更新可以寫成?
?
?其中
由于該問題屬于一類圖正則化交替最小二乘問題，因此我們可以利用共軛梯度下降算法得到最小值（時間復(fù)雜度?）?
?4 實(shí)驗(yàn)
4.1?城市交通需求預(yù)測實(shí)驗(yàn)
????????我們使用了紐約市出租車和豪華轎車委員會提供的出租車運(yùn)輸記錄數(shù)據(jù)集和在紐約記錄的自行車共享系統(tǒng)數(shù)據(jù)集。
????????對于出租車數(shù)據(jù)集，我們預(yù)測出租車在紐約不同位置下車的客戶數(shù)量。由于該數(shù)據(jù)集中的記錄由GPS位置組成，我們構(gòu)建了面積為500m2的網(wǎng)格。
? ? ? ? 對于自行車共享系統(tǒng)數(shù)據(jù)集，我們預(yù)測將自行車歸還給不同自行車站的客戶數(shù)量。
????????出租車數(shù)據(jù)和自行車共享系統(tǒng)數(shù)據(jù)的觀測地點(diǎn)分別為640個和344個。觀測數(shù)據(jù)每30分鐘收集一次。
?????????我們在每個數(shù)據(jù)集中使用了兩周的記錄。
? ? ? ? ?我們選取過去七天中的每一天作為測試日，并將測試日的前七天作為訓(xùn)練數(shù)據(jù)。
????????然后我們隨機(jī)選取10%的位置作為未知的測試位置，其余位置作為已知的訓(xùn)練位置。
????????我們使用我們提出的方法：DAR正則化(DAR)， DAR正則化與非負(fù)約束(DAR+NN)進(jìn)行實(shí)驗(yàn)。我們將該方法與高斯過程(GP)、快速多元時空分析(fast)和時間正則化矩陣分解(TRMF)進(jìn)行了比較。因?yàn)镕AST不能對未知位置進(jìn)行預(yù)測，所以我們首先對未知位置進(jìn)行插值觀測，然后進(jìn)行預(yù)測。
?????????對于我們提出的方法的空間正則化器DAR的系數(shù)W(1)，我們采用k-NN，其權(quán)重設(shè)置為高斯相似測度，其中rp是 第p個sensor的GPS位置，σ是加權(quán)系數(shù)（因?yàn)椴煌珿PS位置之間的差距相對來說很小，我們設(shè)置σ為100）。然后我們對每一行進(jìn)行歸一化。
????????對于FAST和TRMF，我們使用了元素設(shè)置為高斯相似測度的全連通圖拉普拉斯矩陣。
????????對于我們提出的DAR正則化方法，我們將角度劃分的數(shù)量N設(shè)置為4或8，KNN的鄰居數(shù)量為4或8。超參數(shù)λ1和λ2分別設(shè)為{0,0.1,1.0,10.0}。我們通過五倍交叉驗(yàn)證調(diào)整了超參數(shù)。
????????對于GP，我們使用5000個隨機(jī)采樣數(shù)據(jù)點(diǎn)進(jìn)行訓(xùn)練，并通過最大似然估計(jì)程序優(yōu)化超參數(shù)。
????????我們對GP、FAST、TRMF和張量微積分使用了公開可用的matlab代碼。
????????在三種不同類型的預(yù)測任務(wù)中評估了每種方法的表現(xiàn)。在前人[11]工作的基礎(chǔ)上，我們利用歸一化偏差(ND)作為誤差測量:
?????????
????????結(jié)果如表一、二所示。每個單元格的左右兩邊的值對應(yīng)于在不同的測試天進(jìn)行7次測試得到的ND的平均值和標(biāo)準(zhǔn)偏差。黑體數(shù)字表示所有方法中最小的平均誤差。?
??????
????????從這些結(jié)果中，我們證實(shí)了我們提出的方法與DAR正則化器在預(yù)測整個數(shù)據(jù)集的特征觀測和未知位置插值任務(wù)上優(yōu)于其他方法。
????????同時加入DAR正則化和非負(fù)約束的方法在沒有非負(fù)約束的情況下表現(xiàn)出了更好的性能，因?yàn)檫@種約束可以避免過擬合。
????????在紐約出租車數(shù)據(jù)和共享單車系統(tǒng)中，我們的DAR正則化器的改進(jìn)率分別為42.9%和9.8%。該方法在第一個任務(wù)上的改進(jìn)是由于減少了插值未知位置觀測的預(yù)測誤差，因?yàn)槲覀兊姆椒梢岳每臻g自回歸正則化器學(xué)習(xí)每個潛在因子的不同空間依賴性。
????????然而，現(xiàn)有的方法不能同時學(xué)習(xí)空間和時間依賴性。通過對共享單車系統(tǒng)數(shù)據(jù)集的實(shí)驗(yàn)，FAST在預(yù)測已知位置的未來觀測任務(wù)上表現(xiàn)出了最好的性能。
?????????為了檢驗(yàn)我們提出的方法的定性性能，我們用圖3中的NY出租車數(shù)據(jù)集來說明DAR正則化器的估計(jì)預(yù)測。
????????紅線和藍(lán)線分別是預(yù)測值和地面真實(shí)值。??黑色實(shí)線表示訓(xùn)練期的結(jié)束。?黃色背景的紅線是預(yù)測的結(jié)果。
????????從這張圖中，我們證實(shí)了我們所提出的方法通過捕捉時間動態(tài)準(zhǔn)確地預(yù)測了已知位置的觀測結(jié)果。它對未知位置的預(yù)測也表現(xiàn)良好。這些結(jié)果支持了我們提出的DAR正則化器學(xué)習(xí)空間和時間依賴性的有效性。
? ? ? ??
?
?????????在圖4中，我們用紐約出租車數(shù)據(jù)來說明提取的時間和空間因素。
????????在這些圖中，我們還展示了在沒有非負(fù)約束的情況下提取的時間因素。
????????從圖4a中，我們確認(rèn)了在每個時間因子中提取了不同的動態(tài)特征，并且具有非負(fù)約束的空間因子比沒有該約束的空間因子獲得了光滑且易于解釋的形狀。?
????????從藍(lán)色的時間因子及其對應(yīng)的空間因子4b，我們可以很容易地理解這個因子出現(xiàn)在每天下午和帝國大廈附近。
????????紅色的時間因子和相應(yīng)的空間因子4c表明，曼哈頓和布魯克林的日常交通都發(fā)生在夜間。
總結(jié)
以上是生活随笔為你收集整理的论文笔记：Autoregressive Tensor Factorizationfor Spatio-temporal Predictions的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 反距离插值 IDW
- 下一篇： 错误处理笔记 导入 torch.util