基于雙向稀疏Transformer的多變量時序分類模型

王慧強,陳楚皓,呂宏武,米海林

(哈爾濱工程大學 計算機科學與技術學院,哈爾濱 150001)

0 引 言

多變量時間序列(Multivariate Time Series,MTS)是按時序獲取的事件序列,其中每個事件由多個屬性的觀測值構成[1].MTS的分析評估有助于從更多維度上掌握事物的實時發展演化趨勢,在生理健康、運動識別、金融行情評估[2]、交通流量預測[3]等領域發揮著重要作用.

與單變量時間序列(Time Series,TS)相比,MTS具有兩個顯著特征.一方面,由于真實場景中的時序數據種類多、樣本數量量級差距大、時序長度不一、特征個數不同,數據往往具有差異化的分布特征和統計信息,這對MTS分類模型提出了巨大的挑戰.另一方面,來自不同領域的時序數據的時序波動程度差異巨大(如圖1(a)、圖1(b)所示),加劇了時序分類問題的復雜性,制約了分類準確度的提升.

圖1 呈現周期性的時序數據Fig.1 Time series data with periodicity

針對第一方面,目前諸多學者對多變量時序分類問題已經進行了諸多研究.例如文獻[4,5]基于動態時間歸整(Dynamic Time Warping,DTW),通過尋找兩個長度不同的多變量時間序列的最佳對齊方式,計算對齊后兩序列間的距離來完成時序分類任務.文獻[6,7]等通過選擇最具代表性的子序列獲取序列特征完成分類.這些方法需要時間序列數據中的領域知識,還會產生巨大的特征空間,使得后續特征選擇變得困難,并且在多變量時序分類場景下的準確度較低.

針對第2個方面,越來越多的學者將CNN、RNN、LSTM等深度學習模型引入多變量時序分類領域.基于深度學習的方法可借助端到端的訓練,不需要了解數據領域知識,可以避免巨大特征空間的產生,但存在歷史數據的周期性捕獲能力不足的問題.

與傳統深度學習模型相比,Transformer模型憑借著自注意力(self-attention)機制[8],具備更強的長期依賴性捕獲能力,在長時序問題上表現出巨大的潛力.但是,self-attention機制中使用的標準點積運算的時間復雜度均為O(L2)(L為時間序列長度),隨著L的增長運算成本會呈指數級增加,同時,文獻[9]提出Transformer存在長輸入堆疊層的內存瓶頸,J層編碼器/解碼器的堆棧使總內存使用量到達O(J×L2),這限制了Transformer模型在接受長序列輸入時的可擴展性.此外,self-attention機制沒有對輸入進行偏置假設,甚至訓練數據的順序信息都要通過訓練學習.因此,沒有經過預訓練的Transformer模型很容易在小、中規模數據集上過擬合.這些問題極大限制了Transformer模型在多變量時序分類領域的應用.

為了減小Transformer的時間復雜度,大量學者進行了探索.文獻[9]認為Transformer中學習到的self-attention矩陣的數據存在長尾分布,注意力數據在大多數數據點上通常非常稀疏.受此啟發,本文注意到self-attention機制具有雙向稀疏性,提出基于雙向稀疏選擇Transformer的時序分類模型(Bidirectional Sparse Transformer,BST),將self-attention機制時間復雜度降至O((lnL)2).本文的主要貢獻有以下3點:

1)本文提出了一種時間復雜度為O((lnL)2)的雙向稀疏注意機制,有效地提高了self-attention機制的效率.

2)基于KL散度構建活躍度評價函數,并將評價函數的非對稱問題轉變為對稱權重問題,得到簡潔的評價函數.

3)在前兩點的基礎之上構建多變量時序分類通用Transformer框架,捕捉時序數據的波動依賴,完成多變量時間序列分類任務.實驗結果表明,與其他模型相比,本文提出的模型能夠提高長序列時序數據的分類準確度.

1 相關工作

1.1 多變量時間序列分類方法

近幾年來,多變量時序數據分類的研究已經取得很大進展,這些研究主要可分為基于距離的方法、基于可解釋模式的方法和基于深度學習的方法.

基于距離的方法通常利用領域知識,計算樣本范數完成分類.文獻[4]通過DTW尋找長度不同的時間序列的最佳對齊方式,計算每個維度的距離衡量時間序列的相似度.文獻[5]認為多變量時間序列各維度之間存在一定的聯系,基于多維點計算距離完成時序分類.基于距離的方法使用少量樣本就可以完成訓練,但會生成較大的特征空間.

基于模式的方法將多變量時間序列轉變為特征,然后將這些特征送入分類器進行分類.文獻[6]提出模式袋模型(Bag Of Patterns,BOP),通過滑動窗口機制將多變量時間序列分解為子序列進而轉變為模式元素來進行分類.文獻[7]將不同長度的子序列嵌入到統一網絡,通過計算正負樣本之間的距離選擇出最具有代表性和多樣化的子序列,進一步提高了分類精度.基于模式的方法清晰明了且可解釋性高,但依賴數據集,可拓展性、可推廣性不高.

隨著近年來深度學習的迅猛發展,越來越多的人將深度學習應用到多變量時間序列領域.文獻[10]基于CNN,使用隨機設置參數的卷積核對多變量時間序列進行轉換,極大提高了分類效率,但CNN并不完全適用于處理多變量時間序列,隨著數據集的增大模型準確度沒有明顯的提高.文獻[11]將LSTM和CNN混合使用完成數據嵌入,再通過squeeze-extraction模塊生成多變量時間序列的潛在模式完成分類.文獻[12]把多變量時序數據維度隨機組合成不同的組,通過注意力層訓練樣本的權重,將同一類中訓練樣本的加權組合,成功將模型擴展到半監督領域.

由于使用堆疊的LSTM和CNN,文獻[11]和文獻[12]都存在無法充分利用歷史數據捕獲數據中的周期性的問題.文獻[13]摒棄LSTM+CNN的模式,采用兩個Transformer子層分別提取多變量時序特征和維度特征,使用門控機制將兩種特征合并,探索了Transformer架構在多變量時序分類領域的應用.它使用Transformer捕捉時間序列特征,降低了梯度消失或者梯度爆炸的風險,但是Transformer的時間復雜度仍為O(L2),會產生高時間、高內存消耗,從而限制了模型在多變量時序數據的應用.

1.2 高效Transformer模型

2 基于雙向稀疏機制的Transformer框架

為提高多變量時序分類中長序列數據分類的準確度,本節提出一種適用于長序列時序分類的Transformer時序分類框架,將Transformer的時間復雜度降至O((lnL)2).

2.1 問題定義

多變量時序數據集X可表示為:

X={X1,X2,X3,…,Xi,…,XN},N為序列樣本的個數.

本文意在訓練一個分類模型f,f可將每個序列樣本Xi映射到相應的分類yi.

f(Xi)→yi,yi∈{0,1,2,…,K}

2.2 模型架構

本文的模型概況如圖2所示.模型可分為3個部分,數據嵌入、編碼器和分類器.

圖2 BST模型結構圖Fig.2 Architecture of the BST model

分類器:使用LogSoftmax層作為分類器,完成下游任務分類并獲得輸出結果.

2.3 雙向稀疏注意力機制

Self-attention機制是Transformer中的重要組成部分,它直接將時間序列中任意兩個時刻的數據通過一個計算步驟直接聯系起來,所以遠距離時刻依賴特征之間的距離被極大縮短,有效地利用這些特征捕獲時間序列中數據相互依賴的特征.標準的Transformer[8]中self-attention的輸入為查詢矩陣Q、鍵值矩陣K、值矩陣V,注意力計算如公式(1)所示:

(1)

其中,Q∈RLQ×dQ,K∈RLK×dK,V∈RLV×dV,在實際情況中通常令dQ=dK=dV=d,LQ=LK=LV=L,L為輸入序列長度,d為序列維度,A稱為注意力矩陣.為更方便討論self-attention機制,用qi、ki、vi分別代表Q、K、V中的第i行,也是Q、K、V中第i個query、key、value.

公式(1)需要二次點積計算[8],這是阻礙Transformer模型提高分類預測能力的主要缺點.由研究可知,self-attention矩陣的數據存在長尾分布,對于訓練有素的Transformer,其注意力矩陣A通常是極具稀疏性的[16],這表明可以在不顯著影響性能的情況下引入某種形式的稀疏性.文獻[9]中探討了注意力矩陣A中query的稀疏性,認為自注意力矩陣的稀疏性表現為不同的query對key表現出的關心程度不同,并據此將query劃分為active query、lazy query兩類,通過篩去lazy query的方式完成查詢矩陣稀疏化.

本文繪制了文獻[9]中基于單向稀疏Transformer模型在訓練過程中注意力矩陣A的熱力圖,如圖3(a)所示.從圖中可以看,query對于不同的key具有不同的關注度(即不同的活躍度,活躍度越高,自注意力得分越高),key對于不同的query關注度也不同.經過單向稀疏化后注意力矩陣A在query上表現出的稀疏性雖有明顯下降,但是在key上仍然存在明顯的稀疏性,這說明了對Q、K進行雙向稀疏化的可行性及必要性.據此,本文基于活躍度評價函數對query、key進行篩選完成對Q、K的稀疏化,從而提出一種時間復雜度為O((lnL)2)的Transformer多變量時序分類模型.

圖3 雙向稀疏化前后注意力得分矩陣熱力圖Fig.3 Heat map of attention score matrix before and after bidirectional sparsification

(2)

使用雙向稀疏化的自注意力公式進行訓練,得到注意力矩陣A的熱力圖如圖3(b)所示.可以看出經過雙向稀疏化后,不同的query、key的活躍程度區別更加明顯,活躍的query與key明顯增多,說明雙向稀疏機制確實篩選出了活躍度高的query和key.雙向稀疏自注意力機制的具體過程如圖4所示.

圖4 Self-attention雙向稀疏機制Fig.4 Bidirectional sparse mechanism for self-attention

2.4 活躍度評價函數

從2.3節可知,模型需要評價query和key的活躍程度以考查query和key的稀疏性,因此需要構建活躍度評價函數.文獻[18]通過核函數的表示方法,將自注意力標準化公式中的每一個qi的注意力以概率形式進行表示:

(3)

(4)

通過KL散度計算每一個查詢向量的后驗概率分布p(kj|qi)與平均分布q(kj|qi)的KL散度距離,來計算qi的活躍度計算公式M為:

(5)

由公式(5)可知,qi活躍度評價函數M的時間復雜度為O(L),評價Q整體活躍度的時間復雜度為O(L2),本文進一步將計算M的時間復雜度降低至O((lnL)2).

(6)

據此,評價整體活躍度的時間復雜度從O(L2)轉變為O((lnL)2).此外,由于公式(5)和公式(6)中采用的核函數是非對稱的,不能直接用于key的活躍度評判,為此還需要將非對稱問題轉換成對稱問題.

Self-attention中點積運算的基本作用是學習自我對齊,即確定單個token相對于序列中所有其他tokens的相對重要性,物理意義在于計算兩個向量的相似度[20].在以NLP為代表的Transformer應用中Q、K的對齊關系如圖5左圖所示,Q、K、V具有相同的物理意義,都表示同一樣本中不同token組成的矩陣,而Q、K矩陣的點乘本質上是計算每個token與其他tokens的相似度.不同于其他的Transformer應用領域,如圖5右圖所示,時間序列領域過程中數據具有明顯的單向性,在實際應用中不能建立出未來時刻與當前時刻的聯系,因此確定未來時刻相對現在的相對重要性并非必要的.此外,在訓練過程中計算未來時刻與當前時刻的注意力得分,雖然可以帶來較低的損失,但是存在較快過擬合的風險.

圖5 不同領域對齊關系Fig.5 Alignment in different domains

因此本文采取單側計算self-attention的方法,將注意力矩陣A將變成上三角形,等效于一個對稱矩陣.令Q=K,可以僅通過訓練單個Q就完成上述的工作.

仍然利用雙向稀疏方法,對Q進行兩次抽樣篩選,得到稀疏化之后的矩陣的Q1、Q2,多頭注意力機制變為:

(7)

使用Q1、Q2代替原有的Q、K,可以很好地解決核函數的非對稱性問題,讓整個評價函數具有廣泛的適用性.

3 仿真實驗及分析

本文使用University of East Anglia(UEA)多變量時序分類檔案[4]中的9個數據集評估所提出的模型的性能.所有實驗均在具有32GB內存的NVIDIA GeForce RTX 2080 GPU上進行.

3.1 數據集

UEA多變量時序分類檔案是多變量時序分類領域公開的數據集集合,共包含30個時間序列數據集,本文挑選其中的9個數據集評估本文的模型,包括心房顫動(AtrialFibrillation,AF)、乙醇濃度(EthanolConcentration,EC)、面部檢測(FaceDetection,FD)、手指動作(FingerMovements,FM)、手部移動(HandMovementDirection,HMD)、昆蟲振動(InsectWingbeat,IW)、交通分類(PEMS-SF,PS)、電位調節(SelfRegulationSCP2,SRS2)、步行跳躍(StandWalkJump,SWJ).它們來自不同的領域,樣本的時間序列長度從50～2500不等,可以充分考查模型的通用性.本文遵照數據集發布者劃分的訓練集、測試集比例.9個數據集的具體情況如表1所示.

表1 實驗中使用的UEA數據集Table 1 UEA datasets used in the experiment

3.2 評估指標及參照模型

本文統計每個數據集上的各個分類模型的分類精度,并計算每個模型的平均排名和成功次數(某數據集上分類精度最高記為成功).此外,由于每個數據集的樣本數目不同、特征維度不同、時間序列長度不同,只計算上述3個評估指標難免有失偏頗,因此本文繪制臨界差異圖(Critical Difference Diagram),并計算每類平均誤差(Mean Per-Class Error,MPCE).MPCE所有數據集每類的平均誤差,它可以評估一個模型在多個數據集的聯合分類效果.MPCE如公式(9)所示:

(8)

(9)

為了充分評估本文BST模型對于多變量時序分類的效果,將BST與其他分類模型進行比較.參照模型可分為3類:

1)時序分類通用基準模型:ED_I[4].

2)多變量時序分類基準模型:DTW_I、DTW_D[4].

3)多變量時序分類領域7種先進的模型:RLPAM[1]、WEASEL+MUSE[6]、ShapeNet[7]、ROCKET[10]、MLSTM-FCN[11]、TapNet[12]、MiniRocket[19].

RLPAM:一種基于強化學習的多變量時序分類框架,通過模式挖掘來識別多變量時序分類中可解釋的、重要的模式完成分類.

WEASEL+MUSE:一種基于BOP的多變量時間序列分類框架,使用滑動窗口在時間序列的不同維度上進行抓取,將多變量時間序列轉變為大量模式特征,并使用卡方檢驗來進行特征選擇完成分類.

ShapeNet:一種基于時序子序列shapelet和深度學習的多變量時間序列分類框架,采用擴張因果卷積神經網絡(Dilated Causal Convolutional Network,DC CNN)學習時序子序列的新表示,選擇其中具有代表性和多樣性的時序子序列完成分類.

ROCKET:一種基于深度學習的多變量時序分類框架,使用權重、形狀、偏重隨機的卷積核變換時間序列,然后利用轉換后的特征完成分類.

MLSTM-FCN:一種基于深度學習的多變量時間序列分類框架,該模型由LSTM層、堆疊的CNN層、Squeeze-Extraction層生成多變量時間序列的潛在模式,然后利用多層感知機(Multilayer Perceptron,MLP)完成分類.

TapNet:一種基于深度學習的多變量時間序列分類框架,模型使用隨機群置換的多層卷積網絡和注意力網絡,從多變量時序數據中學習低維特征完成分類.

MiniRocket:MiniRocket在Rocket的基礎上進行了改進,不再使用隨機卷積核,而是使用一組幾乎完全固定的小卷積核對多變量時序數據進行轉換完成分類.

3.3 分類結果

9個數據集上的分類結果如表2所示.“N/A”表示無法產生結果.

表2 各分類算法實驗結果Table 2 Experimental results of classification algorithms

觀察表2結果可知,BST模型在所有模型中取得了最佳平均排名,平均排名為1.78,優于所有參照模型.圖6為根據實驗結果繪制的臨界差異圖,可以綜合評估多個模型在多個數據集上的表現.可以看出,BST模型性能最好,它的結果比排名第2的RLPAM模型小1.1左右,領先37.2%.就MPCE而言,BST取得了在9個數據集上最小每類平均誤差,與排名第2的RLPAM相差0.03,提升2.5%.就成功次數而言,BST取得了4次成功,在所有數據集上獲得最多的成功次數.此外,BST模型在EC數據集上提升效果明顯,分類準確率提高30.9%.

圖6 臨界差異圖Fig.6 Critical difference diagram

3.4 實驗結果分析

為深入分析模型的分類效果,本節以HMD數據集為例,采用t-SNE算法以二維圖像的形式可視化時間序列嵌入.HMD數據集共包含4個不同種類的160個訓練樣本,使用不同的數字(0,1,2,3)來區分不同的類別.圖7(a)為HMD數據集原始數據的嵌入結果,圖7(b)為數據經過模型編碼器學習處理后的嵌入結果.可以看出,原始數據嵌入后不同類別的樣本分布散亂、沒有規律,而經過編碼器處理后,數據分類明顯,說明BST模型確實完成了分類任務.

圖7 數據編碼前后t-SNE嵌入對比Fig.7 Comparison of t-SNE embedding before and after data coding

從表2可知,本文的模型并非在所有的數據集中表現優越.為了探究原因,選擇了HMD數據集和PS數據集進行分析.圖8(a)為HMD數據集中隨機挑選的樣本某個特征隨時間變化的情況,圖8(b)為PS數據集中隨機挑選的樣本某個特征隨時間變化的情況.可以看出,HMD數據集中的時序特征隨著時間的起伏、波動變化頻率很高,數據具有很強的時序性和周期性.對于這樣的數據集,BST模型能夠充分發揮作用,捕獲時序之間的隱含聯系完成分類任務.然而PS數據集中的時序特征隨著時間的起伏波動變化變化頻率低,包含的時序性不強,BST模型捕捉到的時序性有限,但BST模型在PS數據集上的準確度排名第4,依然保持在中等偏上的水平.

圖8 HMD和PS特征變化趨勢Fig.8 Change trend of HMD and PS characteristics over time

此外,本文嘗試將數據增強引入BST模型,以提升模型分類準確度.本文采用文獻[17]提出的cutmix、cutout、mixup、windowwarp 4種操作的最佳組合方式,保持其余實驗參數設置不變,完成數據增強.BST模型有無數據增強的實驗結果如表3所示.從表3可以看出,BST模型使用數據增強和不使用數據增強獲得的準確度差異最高相差3.21%,最低相差1.01%,波動范圍在模型正常波動范圍內,數據增強對提高BST模型準確度沒有明顯的幫助.

表3 BST模型有無數據增強結果對比Table 3 Results of BST model with and without data enhancement

4 結 語

本文針對多變量時序數據分類中數據難以捕捉時序特征、周期特征的問題,提出了BST雙向稀疏Transformer分類框架.建立使用單側注意力的活躍度評價函數,并在此基礎之上提出self-attention的雙向稀疏機制,將Transformer的時間復雜度降至O((lnL)2).實驗證明,BST模型在UEA時序分類檔案中的9個長序列數據集上取得最高平均排名,在臨界差異圖中領先第2名37.2%.由于篇幅和時間的限制,本文僅討論了BST模型在提高多變量時序分類準確度的效果,沒有與其他深度學習模型的時空消耗進行比較.此外,BST模型目前尚不適用于時序性不強的數據集.