基于自注意力機制的多模態語義軌跡預測*

劉 婕，張 磊，朱少杰，劉佰龍，張雪飛

(1.中國礦業大學礦山數字化教育部工程研究中心，江蘇 徐州 221116； 2.中國礦業大學計算機學院，江蘇 徐州 221116；3.內蒙古廣納信息科技有限公司，內蒙古 烏海 016000)

1 引言

隨著移動互聯網的發展和智能終端的普及，眾多社交媒體網站(如Twitter、Sina和Instagram等)每天產生數以億計的多模態語義軌跡數據。而多模態語義軌跡中存在時間依賴、空間依賴和活動依賴等多種依賴關系。空間依賴是指用戶在訪問下一位置時通常會考慮自身與目標場所的距離。時間依賴體現在用戶對所處時段的敏感性，即用戶在不同時段對訪問興趣點類型的偏好不同。活動依賴則是指用戶即將進行的活動類型可由用戶之前的活動序列推測得到，并且用戶已完成的活動類型在同一軌跡序列中再次出現的概率較低。這些依賴關系相互聯系緊密又具有復雜性，并且在軌跡預測中起到很重要的作用，準確分析和量化這些依賴關系能夠有效提升預測的準確率。

傳統的軌跡預測方法，如基于馬爾可夫[1,2]、矩陣分解[3]等方法，并不能很好地解決軌跡中的長期依賴問題。深度學習方法是處理長期依賴的有效方法。ST-RNN(SpatioTemporal Recurrent Neural Network)[4]聯合時空規律和循環神經網絡建模來處理時序關系。采用長短時記憶LSTM(Long Short-Term Memory)網絡[5，6]，通過時間步參數共享和門機制解決軌跡中的長期依賴。卷積神經網絡可以有效抽取軌跡的空間特征[7,8]。但是，這些方法沒有考慮或單純考慮時間和空間模態特征，忽略了軌跡的豐富語義特征。而針對多模態語義軌跡的研究較少，Karatzoglou等[9]在多維馬爾可夫思想的基礎上提出了PoVDSSA(Purpose-of-Visit-Driven Semantic Similarity Analysis)模型，實現了對語義軌跡的建模，并證明了加入了語義特征的預測模型可以縮短訓練時間，提高準確性和魯棒性[10]。Yao等[11]聯合時間、空間、活動文本和用戶偏好等多種模態特征，提出了SERM(Semantics-Enriched Recurrent Model)。上述方法雖然取得了不錯的成果，但它們均未對軌跡中的復雜依賴關系進行量化，并且在模型訓練過程中也并未處理特征分布偏移的問題。本文針對這2個方面進行設計改進，以提高預測有效性。

為了解決上述問題，本文提出了基于自注意力機制的多模態語義軌跡預測SAMSTP(Self- Attention mechanism based Multi-modal Semantic Trajectory Prediction)模型。該模型先對多種模態特征進行聯合嵌入表示，以聯合學習各模態特征及其相互之間的關系。隨后結合Position Encoding[12]對軌跡點的相對位置關系進行記憶，以彌補自注意力層會帶來的部分時序信息丟失的缺陷。然后設計自注意力機制準確量化和自動學習軌跡點間的復雜依賴關系，并且自注意力層在計算每個軌跡點的依賴權重時，軌跡點間計算步長始終為1，從而很好地解決了各依賴關系的長期性。而LSTM[12]則負責處理長軌跡序列時序上的長期依賴問題。最后本文設計模式規范化MN(Mode Normalization)對軌跡樣本進行實時監測和規范，以達到預防依賴關系失真并加快模型收斂速度的目的。

2 多模態語義軌跡預測

2.1 問題定義

定義1(網格索引序列) 對興趣點序列P={p1,…,pj,…,pDG}進行網格劃分生成位置索引序列L={l1,l2,…,lDM}。pj∈P是一個二元組(lonpj,lapj)，DG為數據集中興趣點總數。DM=Grid×Grid，表示劃分網格數。二元組元素lonpj和lapj分別定義為興趣點pj的經度和緯度。

給定劃分后網格索引序列L={l1,l2,…,lDM}，現在給定用戶序列U={u1,u2,…,uDu}，Du為用戶總數。下面為每個用戶ui∈U定義多模態語義記錄點序列：

定義2(多模態語義記錄點序列) 用戶ui的多模態語義記錄點序列是一個時間序列Raw(ui)={r1(ui),…,rk′(ui),…,rDs(ui)}。Ds表示用戶ui的記錄點總數。每個記錄點rk′(ui)∈Raw(ui)是一個四元組(lk′,tk′,ck′,fk′)。元組各元素定義如下：(1)tk′是時間戳；(2)lk′是用戶ui在時間tk′的網格位置索引，且lk′∈L；(3)ck′是描述用戶ui在時間tk′時活動的文本描述;(4)fk′是用戶ui在時間tk′時的活動類型。

用戶ui的記錄點序列Raw(ui)中，2個相鄰的位置記錄點時間相關性可能很低。因此，本文引入時間間隔約束機制將原始多模態語義軌跡序列劃分成多個多模態語義軌跡。

定義3(多模態語義軌跡序列) 定義用戶ui的一個多模態語義軌跡序列為T(ui)={r1(ui),…,rk(ui),…,rK(ui)}，1≤k≤K，0

定義4(多模態語義軌跡預測) 給定多模態語義軌跡序列Tn(ui)={r1(ui),r2(ui),…,rK(ui)}，多模態語義軌跡預測任務是將Tn(ui)中前K-1個點{r1(ui),r2(ui),…,rK-1(ui)}輸入到模型中，從網格位置索引序列L中預測地表真實位置lK。

Figure 1 Overall framework of SAMSTP 圖1 SAMSTP總體框架圖

2.2 總體框架

(1)復雜依賴關系計算，如圖1左上角的②。該模塊采用自注意力機制結合Position Encoding量化多模態語義軌跡中的復雜依賴關系。具體內容將在第3節進行詳細說明。

(2)LSTM網絡捕獲時序關系，如圖1右上角的③。對于K個記錄點的軌跡序列，LSTM層的時間步為K。將每個記錄點rk(ui)的依賴關系向量sk作為第k時間步LSTM單元的輸入，然后計算隱藏狀態值hk，如式(1)所示：

hk←f(W·hk-1+G·sk+b)

(1)

其中,隱藏狀態值hk∈RDh，Dh表示 LSTM單元中隱藏神經元的數量，代表第k時間步單元的隱藏狀態值。前一時間步隱藏狀態值hk-1、第k個記錄點復雜依賴向量sk、常數偏置項b經由非線性變換函數f(·)計算得到hk。公式涉及的參數有：參數矩陣W∈RDh×Dh，G∈RDh×De，常數偏置項b∈RDh。

(3)依賴關系失真預防及軌跡預測，如圖1右下角的④。該模塊主要包括MN機制規范化預防依賴關系失真和軌跡預測2部分。MN機制實時規范化軌跡樣本以預防依賴關系失真，并且加快模型收斂速度，該機制實現過程將在第4節進行具體介紹。

(2)

訓練過程中使用交叉熵作為損失函數。對于一個包含Z個樣本的訓練集，定義損失函數如式(3)所示：

(3)

其中，Θ={Et,El,Ec,Ef,Eu,W,G,H,b,a}為需估計的參數，δ為預定義常數以防止過擬合。其中，ynk表示第n條軌跡中第k個位置的預測概率。本文使用SGD(Stochastic Gradient Descent)和BPTT(Back Propagation Through Time)算法學習參數集Θ。

3 Self-attention計算復雜依賴關系

PE2i(k)=sin(k/100002i/De)

(4)

PE2i+1(k)=cos(k/100002i/De)

(5)

本文采用自注意力機制對多種依賴關系進行聯合學習，而不同于其他注意力預測方法對各特征分別設立獨立的注意力模塊，如DeepMove[14]。原因在于本文考慮到各依賴關系之間同樣具有相關性，將各特征聯合后采用自注意力機制更易于捕獲數據或特征的內部相關性，實現更精準的預測。

(6)

(7)

最后，將并行頭部產生的所有向量連接起來，形成依賴關系向量S，如式(8)所示：

S←Concat(M1,M2,…,Mi,…,MH)·WS

(8)

其中，復雜依賴關系向量S={s1,s2,…,sk,…,sK}∈RK×De，WS∈RDe×De為映射參數矩陣。

4 MN機制預防依賴關系失真

訓練過程中，軌跡樣本的模態特征會發生偏移而導致依賴關系失真，并且每種模態特征的偏移方向并不一致，若使用單一分布的規范化如BN(Batch Normalization)[15]，由于其并不適應多分布的軌跡樣本，反而會導致模態特征泛化失真，降低預測效果。所以，為了更準確地學習依賴關系權重，避免模態特征的偏移導致計算得到的依賴關系失真，本文設計MN機制對軌跡樣本進行多分布規范化，以適應每個模態特征不同的遷移方向，在訓練過程中實時監控并規范化特征分布，從而達到預防依賴關系失真的效果。并且MN機制能保持較大的梯度更新參數，明顯提升收斂速度，克服了大部分軌跡預測方法中建模復雜導致的參數量大，難以收斂的問題。

訓練中MN為每種模式分布確定新的分量估計，估計分量如式(9)～式(11)所示:

Nq←∑ngnq

(9)

(10)

(11)

(12)

5 實驗與結果分析

5.1 實驗數據及設置

本文實驗基于美國紐約市的Foursquare數據集。數據集包含了從2011年1月到2012年1月的30萬條Foursquare簽到記錄。首先提取不同用戶的簽到記錄，刪除記錄數小于50的用戶，并且根據時間約束tcon<10 h將序列劃分為不同長度的時空語義軌跡記錄。此外，刪除長度小于3的時間相關性序列。本文將興趣點GPS坐標通過網格劃分轉換為網格位置索引。經過以上處理，一共得到235個用戶的3 863條時空語義軌跡序列。本文隨機選取軌跡序列的80%作為訓練集，剩下的20%作為測試集。訓練集和測試集數據特征統計如表1所示。

Table 1 Statistics of data characteristics表1 數據特征統計

由表1可知，訓練集包含235個用戶的3 090條軌跡，所有軌跡點覆蓋9 337個網格位置，其中最長一條軌跡所包含的軌跡點數為83個。測試集同理。

本文實驗在Python 2.7下完成，采用版本號為2.2.4的Keras框架，TensorFlow版本號為1.5.0。所用設備主要硬件參數為：CPU 12核，內存32 GB,NVIDIA Tesla P100顯卡，顯卡內存為12 GB。

5.2 評價標準及參數設置

本文使用如下4種評價標準來衡量模型的性能：

(1)交叉熵損失CCEL(Categorical Cross- Entropy Loss)，即預測軌跡概率的損失值。計算公式如式(3)所示。CCEL用來評估模型對參數的敏感性。

(2)HR@k(Hitting Ratio @k)，即軌跡真實下一位置索引出現在Top-k預測索引列表中的概率。

(3)平均距離誤差ADE(Average Distance Error)，即計算軌跡真實下一位置索引和Top-5預測索引列表的地表真實距離平均誤差。

(4)模型收斂時間CT(Convergence Time)，CT根據迭代次數和單步平均迭代時間OAET(One-step Average Epoch Time)計算得出。

本文對參數進行了優化實驗，限于篇幅，此處不再具體展示實驗細節。通過實驗結果對比，本文最終設置各個嵌入維度Dt=Dl=De=Df= 50，LSTM隱藏單元數Dh=50，樣本分布模式數Q= 2，多頭自注意力機制頭數Heads=8，學習率(Learning Rate)LR=0.0005，批次大小BatchSize=100。

5.3 實驗內容

本文通過對不同模塊進行組合，來驗證模型中各模塊的有效性。實驗設置遵循控制變量原則。5種模塊組合方式設置如下：(1)LSTM，表示長短時記憶網絡；(2)LSTM-MN，表示在LSTM的基礎上增加MN模塊；(3)LSTM-BN，表示在LSTM的基礎上增加BN模塊；(4)SA-LSTM-MN，表示在LSTM-MN的基礎上增加自注意力模塊；(5)SA-LSTM-MN-P，表示在 SA-LSTM-MN 基礎上增加Position Encoding模塊(SA-LSTM-MN-P即代表SAMSTP模型)。

根據以上模塊組合方式，本文設計2個對照實驗：(1)比較SA-LSTM-MN、LSTM-MN和SA-LSTM-MN-P，驗證自注意力機制以及位置嵌入對復雜依賴關系計算的有效性；(2)比較LSTM-MN、LSTM-BN和LSTM，驗證MN機制的有效性。

本文選取以下模型與SAMSTP模型進行比較：(1) MF[3]：為用戶和位置學習低維向量，并為用戶的下一次訪問推薦最相似的位置；(2) HMM(Hidden Markov Model)[1]：學習隱馬爾可夫模型來選擇下一個位置預測概率最大的位置；(3) PoVDSSA[9]：建立了一個類似多維上下文感知的馬爾可夫鏈結構來建模豐富的語義軌跡；(4) ST-RNN[4]：基于遞歸神經網絡，著重對時空轉換矩陣的建模；(5) SERM[11]：將一個遞歸神經網絡的多因素(用戶、位置、時間、關鍵字)和過渡參數嵌入在同一的框架中進行聯合學習。以上方法參數均調至最優。

5.4 實驗結果分析

(1)先比較LSTM-MN、SA-LSTM-MN和SA-LSTM-MN-P。由表2知，相比LSTM-MN，SA-LSTM-MN各項評價標準均有所提高，表明使用自注意力機制計算復雜依賴關系的確能夠提高預測的準確率，然而增幅不大。這是因為單獨使用自注意力機制計算軌跡點依賴關系時，會丟失軌跡點之間的部分時序關系，所以預測效果提升不明顯。但是，SA-LSTM-MN-P的各評價標準均比LSTM-MN的高出許多，這是由于Position Encoding保留了軌跡點之間的相對位置關系，有效彌補了自注意力機制的不足，二者結合實現了復雜依賴關系的準確量化。由表2可知，SA-LSTM-MN-P的各HR@k分別比LSTM-MN高0.74%,1.72%,2.18%和2.45%，ADE下降了35 m。

Table 2 Performance of different combination of modules表2 模塊有效性表現

(2)表3中對比了LSTM、LSTM-BN和LSTM-MN在各個評價標準下達到最優表現所需的收斂時間CT以及單步平均時間OAET。可以看出，LSTM-BN和LSTM-MN收斂時間相比LSTM大大縮短，其中LSTM-MN的收斂速度在各標準下比LSTM分別提升了8.274，4.061，3.624，7.939和15.967倍，說明MN能大幅加快模型的收斂。但是因為LSTM-BN和LSTM-MN增加了計算量，所以OAET分別增加了7 s和12 s。在表2中，LSTM-BN在HR@1和HR@10時的準確率低于LSTM的，結合表3發現LSTM-BN雖然能加快模型的收斂，但是部分評價標準的表現會有所降低。這是由于在訓練過程中軌跡樣本的特征偏移方向并不一致，使用BN這樣的單一分布模式規范化并不能很好地預防依賴失真的問題。而LSTM-MN的各個評價標準的表現都優于LSTM和LSTM-BN的，表明引入MN采用多分布對軌跡樣本進行規范化是必要的，它能夠解決依賴關系失真問題，明顯提升預測的有效性。

Table 3 CT of optimal performance and the OAET for LSTM,LSTM-BN and LSTM-MN under LR=0.0005表3 LSTM、LSTM-BN和LSTM-MN在LR=0.0005時的CT最優表現及OAET

如表4所示，在相同數據集上，SAMSTP在各項評價標準下的表現均是最好的。SAMSTP與這些模型的預測有效性比較如下：(1)MF的預測效果是這些模型中最差的，因為它沒有捕捉到連續的轉移規律。(2)HMM性能較差的主要原因在于它依賴于用戶行為的分布假設，只對軌跡建模一階依賴關系，難以捕捉軌跡中的長期依賴。(3)ST-RNN將空間和時間劃分為若干個，并學習每個時空單元的轉換矩陣，導致參數量較大，影響預測的可靠性。(4)PoVDSSA模型利用類似多維上下文感知的馬爾可夫鏈結構對豐富的語義軌跡進行建模，但是仍舊不能很好地解決長期依賴問題。(5)SERM模型的效果僅次于SAMSTP的。因為SERM模型忽視了軌跡點之間的復雜依賴關系，并且沒有考慮多模態特征模式分布規范化的問題。由表4可知，SAMSTP的各HR@k分別比SERM的高1.97%,4.15%,3.62%和5.19%，ADE下降了155 m。

Table 4 Comparison of optimal performance for different models表4 不同模型最優表現對比

另外，為了驗證SAMSTP在提高模型收斂速度上的有效性，本文計算了各模型的CT最優表現。如表4所示,MF和HMM的模型結構簡單，參數量較小，所以收斂速度很快，但其預測效果較差。ST-RNN的模型結構復雜，參數量巨大，導致收斂時間明顯較長。PoVDSSA、SERM和SAMSTP都引入了豐富的語義信息，增大了訓練計算量，所需收斂時間比未考慮語義特征的模型更長。但是，SAMSTP收斂所需時間遠低于前二者，原因在于SAMSTP對訓練樣本進行規范化，使得模型始終保持較大的梯度更新參數，抑制梯度達到飽和，因此顯著提高了收斂速度。

6 結束語

現有的多模態語義軌跡預測方法中存在難以充分學習復雜依賴關系的缺點。針對這一問題，本文提出了基于自注意力機制的多模態語義軌跡預測模型。該模型通過對多模態特征的聯合嵌入，降低了數據的稀疏性；并采用Position Encoding對軌跡點進行編碼處理，彌補依賴關系計算中造成的時序信息丟失缺陷，增強軌跡點間時序關系。然后結合自注意力機制精準量化軌跡點之間的復雜依賴權重，從而顯著提高軌跡預測的有效性。本文還設計了MN機制實時監測數據模式，將軌跡樣本分配給不同的分布并對其進行規范化，有效解決了單一分布規范化會丟失模式信息的問題，從而減少特征偏移量，以達到預防依賴關系失真的目的。并且MN機制能夠加速模型的收斂。由此，預測的有效性和魯棒性得到了極大提升。本文在紐約真實軌跡數據集上進行了實驗，結果表明，與SERM相比，SAMSTP提高了預測準確率，預測總體速度提升了9.633倍，并且在各評價標準下表現最優。

未來工作的目標是引入更豐富的非結構化信息，如用戶之間的關系，以進一步提高本文模型的性能。