非負(fù)Tucker分解的隨機(jī)方差縮減乘性更新算法

白姍姍,史加榮

(西安建筑科技大學(xué) 理學(xué)院,陜西 西安 710055)

非負(fù)矩陣分解(Non-negative matrix factorization,NMF)將非負(fù)數(shù)據(jù)表示為非負(fù)基下的非負(fù)線性組合,已被廣泛應(yīng)用于圖像處理、文本數(shù)據(jù)挖掘等諸多領(lǐng)域[1,2]。面對結(jié)構(gòu)更加復(fù)雜的高維數(shù)據(jù),若仍運(yùn)用NMF方法將待研究的數(shù)據(jù)向量化,將會導(dǎo)致局部數(shù)據(jù)信息缺失,破壞數(shù)據(jù)的空間幾何結(jié)構(gòu)[3]。為此,Welling等[4]提出了具有更高數(shù)據(jù)壓縮性能的非負(fù)張量分解。

現(xiàn)有的張量分解一般分為兩類:標(biāo)準(zhǔn)分解/平行因子分解(CANDECOMP/PARAFAC,CP分解)和Tucker分解[5]。這兩種分解模型分別可看作奇異值分解(Single value decomposition,SVD)和主成分分析(Principle component analysis,PCA)的高階推廣,并且CP分解是Tucker分解模型的特例。非負(fù)Tucker分解(Non-negative Tucker decomposition,NTD)將高維非負(fù)張量分解為一個低維非負(fù)核心張量與一系列非負(fù)模式矩陣的模式積[6]。NTD使模型具有較強(qiáng)的可解釋性,近年來受到很大關(guān)注,已成功應(yīng)用于計算機(jī)視覺[7]與信號處理[8]等領(lǐng)域。

Kim等[9]最先引入NTD的乘性更新(Multiplicative update,MU)算法,Hazan等[10]提出了具有梯度思想的MU算法。盡管現(xiàn)有的算法取得了較好的效果,但它們收斂速度較慢,尤其不適用于高維數(shù)據(jù)。隨著深度學(xué)習(xí)的迅速興起,隨機(jī)梯度下降算法(Stochastic gradient descent,SGD)已成為求解大規(guī)模機(jī)器學(xué)習(xí)優(yōu)化問題的主流方法[11-14]。該算法具有參數(shù)更新過程簡單、收斂速度快且計算復(fù)雜度低等特點(diǎn)。盡管SGD具有許多吸引人的特性,但到目前為止,尚未見到將該算法擴(kuò)展到非負(fù)Tucker分解模型的研究。因此,本文基于隨機(jī)梯度下降思想提出了求解非負(fù)Tucker分解的一種新算法:隨機(jī)方差縮減乘性更新(Stochastic variance reduced multiplicative update for NTD,SVRMU_NTD)。該算法將隨機(jī)方差縮減梯度和乘性更新規(guī)則相結(jié)合,對非負(fù)的高維數(shù)據(jù)進(jìn)行Tucker分解,可在提高張量分解性能的同時降低計算復(fù)雜度。

1 非負(fù)Tucker分解

X=G×1A(1)×2A(2)×3…×NA(N)

(1)

則稱這種分解為Tucker分解。其中,Jn≤In,“×n”表示張量的n-模矩陣積,定義為

(2)

核心張量G可看作是張量X的壓縮版本。在一般情況下,分解后的張量存儲空間會比原來的張量小很多。圖1給出了一個三階張量Tucker分解的示意圖。

圖1 三階張量的Tucker分解示意圖

使用歐氏距離來度量張量X分解的逼近程度,即NTD對應(yīng)的最優(yōu)化模型見式(3)。

(3)

式中:‖·‖F(xiàn)表示張量的Frobenius范數(shù),稱(J1,J2,…,JN)為多重線性秩。求解式(3)的算法有很多,例如交替最小二乘法(Alternate least squares,ALS)[15],列坐標(biāo)下降(Column coordinate descent,CCD)[16],高階乘性更新(High order multiplicative update,HONMF)[17]等。但這些算法迭代效率較低且計算復(fù)雜度較高,不適用于求解高維張量分解問題。

2 求解NTD的隨機(jī)方差縮減乘性更新算法

2.1 非負(fù)Tucker分解的乘性迭代算法

在最優(yōu)化模型(見式(3))的目標(biāo)函數(shù)中,將X進(jìn)行n-模式化,有

(4)

與NMF的乘性迭代算法類似,文獻(xiàn)[18]提出了求解優(yōu)化模型(見式(3))的MU算法,其主要更新過程如下。模式矩陣A(n)的更新形式為

(5)

核心張量G的更新公式為

G←G.*(X×1(A(1))T…×N(A(N))T./

(G×1(A(1))TA(1)…×N(A(N))TA(N))

(6)

2.2 隨機(jī)方差縮減乘性更新算法

隨機(jī)方差縮減梯度算法(Stochastic variance reduction gradient,SVRG)[19]是在SGD的基礎(chǔ)上添加了方差縮減技巧,具有雙層循環(huán)結(jié)構(gòu)。在外部循環(huán)中,參數(shù)經(jīng)過若干次內(nèi)循環(huán)之后會保留一個“快照點(diǎn)”,然后需要計算損失函數(shù)在該點(diǎn)處全體樣本的平均梯度,從而加快了參數(shù)的迭代速率。本文基于SVRG提出一種新的求解非負(fù)Tucker分解的隨機(jī)方差縮減乘性更新算法SVRMU_NTD,其基本迭代過程如下。

圖2 SVRMU_NTD的非負(fù)Tucker分解流程

2.2.1 模式矩陣的計算

(7)

(8)

(9)

基于式(9),更新參數(shù)第n個模式矩陣

(10)

(11)

(12)

根據(jù)如下形式來更新步長矩陣

(13)

式中:αs為外循環(huán)第s次中隨迭代次數(shù)的增加而不斷縮減的學(xué)習(xí)率,即

αs+1=ραs,ρ∈(0,1)

(14)

2.2.2 核心張量的計算

一旦獲得N個模式矩陣{A(n)},可運(yùn)用梯度下降法來更新核心張量G。根據(jù)模型(3)得核心張量的梯度為

X×1(A(1))T…×N(A(N))T

(15)

迭代步長T按照以下形式選取

T=(λG)./(G×1(A(1))TA(1)…×N(A(N))TA(N))

(16)

式中:λ∈(0,1)表示更新核心張量的學(xué)習(xí)率。當(dāng)λ=1時,對應(yīng)NTD算法中G的更新公式。因此,核心張量的更新規(guī)則為

G←G-T.*(Gf)

(17)

算法的更新過程如算法1所示。

算法1非負(fù)Tucker分解的隨機(jī)方差縮減乘性更新算法(SVRMU_NTD)

3: Fors=0,1,…,do

5: Fort=1,2,…, do

6: Forn=1:N

12: End

13: End

14: 根據(jù)式(14)更新αs;

17: 根據(jù)式(16)更新迭代步長T;

18: 根據(jù)式(17)更新核心張量G;

19:End

3 數(shù)值實(shí)驗(yàn)

將SVRMU_NTD算法在人工合成數(shù)據(jù)集、高速公路交通視頻數(shù)據(jù)集和COVID-CT圖像集上進(jìn)行實(shí)驗(yàn),并與傳統(tǒng)的NTD算法和簡單版本的隨機(jī)乘性更新(Stochastic multiplicative update for NTD,SMU_NTD)算法進(jìn)行性能比較。

3.1 實(shí)驗(yàn)設(shè)置

給定非負(fù)張量X,它的重構(gòu)張量為X′,使用相對誤差來評價它的逼近性能

(18)

相對誤差越小,逼近性能就越好。

3.2 人工合成數(shù)據(jù)集

圖3 人工合成數(shù)據(jù)集迭代效率和時間效率對比

圖3(a)中,橫坐標(biāo)表示全局迭代次數(shù),縱坐標(biāo)表示相對誤差。從圖3(a)可看出:在第20次迭代時,NTD、SMU_NTD和SVRMU_NTD算法的相對誤差分別為0.438 3、0.214 2和0.021 5。NTD算法的迭代效率較低,難以在有限的迭代次數(shù)內(nèi)逼近最優(yōu)解,這可能是因?yàn)镹TD只使用了MU規(guī)則,更新過程簡單且計算復(fù)雜度較高。作為隨機(jī)梯度簡單版本的SMU_NTD算法,其迭代效率略強(qiáng)于NTD,采用了隨機(jī)梯度與乘性更新相結(jié)合,提高了分解性能。SVRMU_NTD算法迭代效率最高,先運(yùn)用方差縮減乘性更新來進(jìn)行非負(fù)矩陣分解,得到模式矩陣集;再通過梯度下降思想來更新核心張量,使其能夠在較少的迭代次數(shù)內(nèi)逼近最優(yōu)解,有效地提升了算法性能。

圖3(b)對比了3種算法的時間效率,其中:橫坐標(biāo)表示運(yùn)行時間,縱坐標(biāo)表示相對誤差。在最大迭代時間0.5 s內(nèi),這3種算法相對誤差隨迭代次數(shù)的增加而呈現(xiàn)出的變化趨勢。由圖3(b)可見,NTD算法很快達(dá)到某局部最優(yōu)解之后,盡管隨著時間的增加相對誤差仍保持不變,算法性能最低。SMU_NTD算法的時間效率稍微強(qiáng)于NTD,但明顯低于SVRMU_NTD算法。雖然SVRMU_NTD算法初始迭代較慢,但隨著時間的增加相對誤差迅速降低,一直保持下降趨勢,能夠高效、快速逼近目標(biāo)參數(shù)的最優(yōu)解。

3.3 交通視頻數(shù)據(jù)集

該段視頻數(shù)據(jù)集來自于華盛頓州交通部(https://www.wsdot.wa.gov/)。由254個西雅圖高速公路交通視頻序列組成,共有44個連續(xù)的交通高峰(慢速或停駛速度),45個中等交通流量(減速),165個輕交通流量(正常速度)。每個視頻的分辨率為320像素×240像素,每秒10幀,每個序列的大小為48像素×48像素。最后,為了減少不同照明條件的影響,對每個視頻片段減去均值圖像,將像素強(qiáng)度歸一化為單位方差。本文選取第100個屬于正常速度的高速公路交通視頻序列,該圖像集可表示為48×48×51的張量,部分圖像如圖4所示。

圖4 高速公路交通視頻的部分圖像

從圖5(a)可知:在有限的迭代次數(shù)內(nèi),NTD、SMU_NTD和SVRMU_NTD這3種算法的最終相對誤差分別為0.329 4、0.209 8和0.137 3。NTD到達(dá)某一局部最優(yōu)解之后,相對誤差幾乎不再變化,其迭代效率最低。SMU_NTD算法引入了隨機(jī)思想,雖加快了迭代效率,但很難在較少的迭代次數(shù)內(nèi)逼近最優(yōu)解。而SVRMU_NTD算法保留了隨機(jī)方差縮減的性質(zhì),在第二次迭代之后就接近局部最優(yōu)解,算法性能最高。由于隨機(jī)方差縮減梯度算法可逃離鞍點(diǎn),不斷地尋找更優(yōu)的局部最優(yōu)解,故相對誤差隨迭代次數(shù)的增加而不斷減少。

圖5(b)比較了3種算法的時間效率?？煽闯?在迭代時間為0.5 s內(nèi),這3種算法相對誤差隨迭代次數(shù)的增加而變化的趨勢。NTD算法在0.5 s內(nèi)迭代了214次,但相對誤差卻是0.320 3,這是由于自身單層循環(huán)結(jié)構(gòu)相對簡單,只運(yùn)用了MU規(guī)則,故迭代效率最低,在0.1 s后,盡管不斷地迭代其相對誤差幾乎保持不變。SMU_NTD在一定程度上提升了NTD的優(yōu)化效率,但時間效率較低于SVRMU_NTD算法,要使其達(dá)到最優(yōu)解還需更長的時間進(jìn)行迭代。SVRMU_NTD算法在相同時間內(nèi)只迭代了39次,但相對誤差卻達(dá)到0.137 7,具有非常強(qiáng)的矩陣分解性能,因?yàn)樵撍惴ńY(jié)合了“方差縮減”策略和乘性更新規(guī)則來校正梯度估計量,使其能夠穩(wěn)定、快速地逼近最優(yōu)解。與其他兩種算法相比,SVRMU_NTD算法在迭代效率與時間效率上都具有明顯優(yōu)勢。

圖5 高速公路交通視頻數(shù)據(jù)集迭代效率和時間效率對比

為不失一般性,考慮對核心張量維數(shù)的不同選取進(jìn)行實(shí)驗(yàn),通過改變(J1,J2,J3)的取值來判斷SVRMU_NTD算法的有效性。在集合{(5,5,8),(8,8,10),(10,10,12)}中來選取(J1,J2,J3),比較不同取值下算法的迭代效率,實(shí)驗(yàn)結(jié)果如圖6所示。

由圖6實(shí)驗(yàn)結(jié)果可知:(J1,J2,J3)在3種不同取值下SVRMU_NTD算法的最終相對誤差依次為0.357 1、0.252 6和0.145 2,運(yùn)行時間依次為0.254 3 s、0.275 9 s和0.278 8 s。在不同核心張量維數(shù)下,按(0,1)區(qū)間上的均勻分布隨機(jī)初始化核心張量G,故初始相對誤差隨核心張量維數(shù)的增加而降低?？梢?在有限的迭代次數(shù)內(nèi),相對誤差隨核心張量維數(shù)的不斷增加而減小,但時間也會隨之增長。對于較少的迭代次數(shù),較小的核心張量維數(shù)對應(yīng)的相對誤差快速下降,之后趨于平緩;而較大的核心張量維數(shù)對應(yīng)的相對誤差一直保持下降趨勢,迭代效率較高。因此,若將SVRMU_NTD算法應(yīng)用于高維復(fù)雜數(shù)據(jù),需考慮選取合適的核心張量維數(shù),使其在時間相對短的情況下,迭代效率能達(dá)到相對最優(yōu),從而使張量分解更加準(zhǔn)確、高效。

圖6 核心張量不同維數(shù)下的相對誤差

3.4 COVID-CT圖像集

為了更加說明所提算法的應(yīng)用價值,對COVID-19 CT數(shù)據(jù)進(jìn)行測試,比較以上3種算法的實(shí)際性能。該數(shù)據(jù)集是關(guān)于COVID-19最大的公開可用的CT圖像數(shù)據(jù)集[20],其中包含來自216名患者的349張COVID-19陽性CT圖像和397張COVID-19陰性CT圖像。本文選取COVID-19陽性CT圖像的前200幅掃描圖像,每幅圖像大小調(diào)整為180×180。因此,該數(shù)據(jù)張量的維數(shù)為180×180×200。部分原始圖像如圖7所示。

圖7 部分陽性CT圖像

圖8 不同核心張量維數(shù)下對COVID-CT圖像集的迭代效率對比

圖8(a)和圖8(b)分別表示核心張量維數(shù)為(15,15,15)和(20,20,20)的情況下,3種算法的相對誤差隨迭代次數(shù)的增加而變化的趨勢。從圖8可見:各算法的實(shí)際性能大體趨勢與交通視頻數(shù)據(jù)集基本保持一致。SVRMU_NTD算法性能明顯優(yōu)于其他兩種對比算法,相對誤差隨迭代次數(shù)的增加而迅速減小,當(dāng)(J1,J2,J3)=(20,20,20)時,相對誤差已達(dá)到0.233 7,這說明該算法張量分解結(jié)果更加準(zhǔn)確。同時可看出,核心張量維數(shù)越大,初始相對誤差越低,且能夠在有限的迭代次數(shù)內(nèi)快速逼近最優(yōu)解。

圖9展示了不同核心張量維數(shù)下,3種算法的時間效率對比。由圖9(a)和圖9(b)可知:NTD算法極易陷入局部最優(yōu)解,隨著迭代次數(shù)的增加相對誤差卻幾乎不再變化。相比其他兩種算法,SVRMU_NTD算法的性能最強(qiáng),在相同迭代時間3 s內(nèi),相對誤差達(dá)到最小,能夠在極少的迭代次數(shù)內(nèi)快速逼近最優(yōu)解。以核心張量維數(shù)(J1,J2,J3)=(20,20,20)為例,在運(yùn)行時間3 s內(nèi),NTD算法迭代了298次,相對誤差為0.503 8,SMU_NTD算法迭代了122次,相對誤差為0.348 3,而SVRMU_NTD算法僅迭代了24次,相對誤差卻達(dá)到0.267 0?？梢?SVRMU_NTD算法在迭代效率以及時間效率上都占有一定的優(yōu)勢。但總體而言,核心張量維數(shù)越大,初始相對誤差越小且所需時間也相應(yīng)延遲,故在實(shí)際應(yīng)用中需針對不同的數(shù)據(jù)選取合適的核心張量維數(shù),使其在迭代效率和時間效率上都能夠達(dá)到相對最優(yōu)。

圖9 不同核心張量維數(shù)下對COVID-CT圖像集的時間效率對比

4 結(jié)束語

本文提出了求解非負(fù)Tucker分解的隨機(jī)方差縮減乘性更新算法。此算法先將待分解的數(shù)據(jù)張量n-模式化,然后結(jié)合隨機(jī)方差縮減策略和乘性更新規(guī)則對模式化矩陣進(jìn)行非負(fù)分解,得到模式矩陣,最后利用梯度下降思想對核心張量進(jìn)行更新。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的NTD以及SMU_NTD算法相比,本文提出的算法加快了收斂速度且降低了計算復(fù)雜度,具有更好的數(shù)據(jù)張量分解效果,也適用于大規(guī)模并行計算。離線情況下,本文提出的算法具有計算代價較高、存儲空間較大等缺點(diǎn),如何運(yùn)用在線的隨機(jī)梯度下降算法來求解非負(fù)Tucker分解問題將是未來值得研究的問題。