概率張量分解綜述

史加榮， 張安銀

(1.西安建筑科技大學(xué) 理學(xué)院， 陜西 西安 710055；2.西安建筑科技大學(xué) 建筑學(xué)院, 陜西 西安 710055)

作為一類數(shù)據(jù)分析工具，低秩矩陣分解已被廣泛地應(yīng)用在機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺、數(shù)據(jù)挖掘和信號(hào)與圖像處理等諸多研究領(lǐng)域。低秩矩陣分解主要包括主成分分析[1]、奇異值分解[2]和非負(fù)矩陣分解[3]等模型，它們需要完整的輸入數(shù)據(jù)。在數(shù)據(jù)獲取時(shí)若出現(xiàn)數(shù)據(jù)丟失或者較大的噪聲腐蝕，前述的傳統(tǒng)低秩分解方法往往不能給出理想的結(jié)果，而概率矩陣分解在一定程度上能克服這些缺陷[4-9]。與矩陣分解相比，概率矩陣分解要求低秩成分是隨機(jī)的，這不但可以增加模型的魯棒性，而且有利于研究數(shù)據(jù)的生成方式。

隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)規(guī)模急劇擴(kuò)大，使得高維數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜。傳統(tǒng)的機(jī)器學(xué)習(xí)方法用向量或矩陣形式來(lái)表示數(shù)據(jù)，因而不能很好地刻畫數(shù)據(jù)的多線性結(jié)構(gòu)。作為向量和矩陣的高階推廣，張量表示在一定程度上能夠避免上述問題。因此，基于張量的機(jī)器學(xué)習(xí)方法已經(jīng)受到廣泛關(guān)注，成為當(dāng)今機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域的一個(gè)新的研究方向。平行因子分解(Candecomp/Parafac，CP)和塔克分解(Tucker)是張量分解的兩類最重要的代表模型，它們分別是主成分分析與奇異值分解的高階推廣[10]，已成功地應(yīng)用到計(jì)算機(jī)視覺[11-14]、人臉識(shí)別[15-17]、交通網(wǎng)絡(luò)分析[18]、社會(huì)網(wǎng)絡(luò)分析[19]和國(guó)際關(guān)系分析[20 ]等領(lǐng)域中。

在獲取高維數(shù)據(jù)的過程中，部分元素可能丟失或者不準(zhǔn)確。低秩張量恢復(fù)是解決上述問題的一類方法，它根據(jù)待研究數(shù)據(jù)張量的近似低秩結(jié)構(gòu)來(lái)恢復(fù)出低秩成分與噪聲[21-26]。Liu等[27-28]認(rèn)為低秩張量恢復(fù)充分利用了數(shù)據(jù)所有維度的信息，能有效恢復(fù)或預(yù)測(cè)丟失數(shù)據(jù)。但現(xiàn)有的低秩張量恢復(fù)方法也有一定的弊端，如：確定張量的秩是多項(xiàng)式非確定性(Non-deterministic Polynomial，NP)問題，低秩成分是確定的而不是隨機(jī)的。這些問題可能會(huì)導(dǎo)致過擬合，不利于低秩模型的生成。概率張量分解能夠很好地避免上述問題，已成為處理高維數(shù)據(jù)的一類重要方法。本文對(duì)主要的概率張量模型進(jìn)行綜述。

1 基本知識(shí)

1.1 CP分解

張量CP分解是將一張量分解成一組秩1張量的線性組合。令y∈RI1×I2×…×IN是一個(gè)CP秩為R的N階張量，其CP分解形式為

(1)

圖1 3階張量的CP分解

對(duì)于某個(gè)固定的n，假設(shè)因子矩陣A(n)未知而其余N-1個(gè)因子矩陣已知，則可通過求解如下的最優(yōu)化問題來(lái)得到最優(yōu)的A(n)：

(2)

令B(n)=A(N)⊙…⊙A(n+1)⊙A(n-1)⊙…⊙A(1)，則最優(yōu)化問題(2)等價(jià)于

(3)

其中Y(n)是張量y的n-模式矩陣。使用最小二乘法，得到A(n)的最優(yōu)解，然后，通過交替迭代方法，可求出y的較優(yōu)的CP分解形式。

1.2 Tucker分解

圖2 3階張量的Tucker分解

N階張量y∈RI1×I2×…×IN的Tucker分解是將它分解為一個(gè)核心張量與N個(gè)矩陣的模式積，即

y=C×1U(1)×2U(2)×3…×NU(N)

[C;U(1),U(2),…,U(N)]，

(4)

其中C∈RJ1×J2×…×JN為核心張量，U(n)∈RIn×Jn為因子矩陣，n=1,2,…,N。3階張量的Tucker分解示意圖如圖2所示。

為得到最優(yōu)的Tucker張量分解，可求解下列最優(yōu)化問題：

(5)

(6)

使用高階奇異值分解(Higher-Order Singular Value Decomposition，HOSVD)，可近似求出問題(5)的最優(yōu)解[30]。

如果Tucker分解中的核心張量C是超對(duì)角的，且J1=J2=…=JN，則Tucker分解就退化成CP分解。換言之，CP分解是Tucker分解的一種特殊情況。本文采用了Acar等人[29]的張量符號(hào)，關(guān)于張量分解的更多知識(shí)可參考文獻(xiàn)[9-10]和[31]。

2 概率張量CP分解

在進(jìn)行CP分解之前，需要事先確定張量的CP秩。計(jì)算張量的CP秩是NP難的，這無(wú)疑增加了模型的復(fù)雜性，而概率張量CP分解在一定程度上避免了上述不足。下面對(duì)概率分解模型做簡(jiǎn)要綜述。

2.1 貝葉斯張量CP分解

對(duì)于給定的含噪聲的不完全N階張量y∈RI1×I2×…×IN，將其分解為一個(gè)潛在的低秩張量χ與一個(gè)噪聲張量ε之和，即

y=χ+ε，

(7)

低秩張量χ的CP分解模型為

(8)

于是被觀測(cè)數(shù)據(jù)的似然函數(shù)為

(9)

為了能自動(dòng)確定CP秩和有效避免過擬合，用連續(xù)型參數(shù)控制潛在空間的每一維變量。為此，假設(shè)因子矩陣A(n)的各行相互獨(dú)立且分別服從均值為0、精度矩陣(協(xié)方差矩陣的逆)為Λ的高斯分布，即

(10)

為了使用全貝葉斯框架，進(jìn)一步假設(shè)噪聲ε的精度τ也服從伽馬分布，即p(τ)=Gam(τ|a0,b0)。記A={A(1),A(2),…,A(N)}，θ={A,λ,τ}，則觀測(cè)數(shù)據(jù)的聯(lián)合分布為

(11)

易知p(θ|yΩ)∝p(yΩ,θ)，使用變分貝葉斯方法對(duì)參數(shù)θ進(jìn)行估計(jì)[32]?；诰祱?chǎng)理論[33]，從而對(duì)丟失的數(shù)據(jù)進(jìn)行預(yù)測(cè)：

?p(yi1i2…iN|A,τ)q(A)q(λ)q(τ)dAdτ，

(12)

這種算法能夠根據(jù)λ自動(dòng)確定CP秩，避免了傳統(tǒng)方法的弊端，但其缺點(diǎn)是計(jì)算復(fù)雜度較高。

2.2 貝葉斯魯棒CP分解

在貝葉斯張量CP分解的基礎(chǔ)上，再考慮數(shù)據(jù)張量還受到稀疏噪聲的腐蝕。于是，數(shù)據(jù)張量y的魯棒CP分解形式為

y=χ+s+ε，

(13)

其中s為稀疏噪聲張量，ε為噪聲張量。低秩張量χ的CP分解仍為公式(8)?；诖耍挥^測(cè)數(shù)據(jù)yΩ的似然函數(shù)為

(14)

當(dāng)(i1,i2,…,iN)?Ω，則張量sΩ對(duì)應(yīng)的分量為0。

仍假設(shè)因子矩陣A(n)服從高斯分布，其分布密度參見公式(10)。為簡(jiǎn)化問題，假設(shè)參數(shù)λ的分布密度函數(shù)為

(15)

其中c0,d0為超參數(shù)。

對(duì)于稀疏噪聲sΩ，同樣使用分層框架：

(16)

記θ={A(1),A(2),…,A(N),sΩ,λ,γ,τ}，其觀測(cè)數(shù)據(jù)的聯(lián)合分布[34]為

(17)

使用變分貝葉斯方法對(duì)參數(shù)進(jìn)行估計(jì)，過程與貝葉斯張量CP分解類似。該模型在全貝葉斯框架下使用了分層的思想，由于添加了稀疏噪聲，故增強(qiáng)了模型的魯棒性，對(duì)預(yù)測(cè)數(shù)據(jù)具有較好的效果。雖然這種推斷方法收斂速度很快，但計(jì)算復(fù)雜度仍較高。

2.3 Beta負(fù)二項(xiàng)CP分解

非負(fù)張量y∈RI1×I2×…×IN的CP分解也可以表示成如下形式：

(18)

其中R為張量y的CP秩。對(duì)于張量y，文獻(xiàn)[35]提出了如下生成模型：

(19)

其中α(n),gr,c,ε為超參數(shù)， Pois(·)、Dir(·)、Beta(·)分別表示泊松(Poisson)、狄利克雷(Dirichlet)和貝塔(Beta)分布。由于Gamma-Poisson混合分布等價(jià)于負(fù)二項(xiàng)分布[35]，且pr服從Beta分布，故稱上述模型為Beta負(fù)二項(xiàng)分布CP分解。模型(19)不是共軛的，為此，引入張量y的兩個(gè)等價(jià)的參數(shù)化。

y(i)～Mult(y(i);ζ)，

(20)

上述模型能夠較好地處理分散數(shù)據(jù)，對(duì)參數(shù)的假設(shè)巧妙地運(yùn)用了先驗(yàn)和似然函數(shù)互為共軛的性質(zhì)，降低了計(jì)算復(fù)雜度。

2.4 MCMC貝葉斯張量分解

d{U,V,T,α,θU,θV,θT}。

(21)

使用采樣方法來(lái)避免復(fù)雜的積分，即MCMC方法：從某個(gè)建議分布中生成一個(gè)序列樣本，當(dāng)這個(gè)樣本遵循特定的性質(zhì)具有顯著的細(xì)致平衡時(shí)，相應(yīng)的馬爾科夫鏈就會(huì)收斂到期望的分布。通過下式進(jìn)行近似預(yù)測(cè)：

(22)

上述模型使用了時(shí)間維度上的信息，能夠更有效地處理時(shí)態(tài)關(guān)系數(shù)據(jù)。使用MCMC采樣方法取代復(fù)雜積分，降低了計(jì)算復(fù)雜度。

2.5 乘性伽馬過程張量分解

(23)

其中1≤r≤R,1≤n≤N。對(duì)于λr的精度τr，進(jìn)一步假設(shè)其先驗(yàn)分布為

(24)

其中ac為超參數(shù)。稱上述模型為乘性伽馬過程CP分解[37]。

記λ=(λ1,λ2,…,λR)T，δ=(δ1,δ2,…,δR)T，則隨機(jī)參數(shù)的概率聯(lián)合分布為

(25)

對(duì)于連續(xù)型數(shù)據(jù)觀測(cè)χ，令χ=y+ε。假設(shè)噪聲張量ε服從高斯分布，于是模型的似然函數(shù)為

(26)

對(duì)于二元數(shù)據(jù)，模型的似然函數(shù)為L(zhǎng)ogistic函數(shù)，即

(27)

2.6 多視覺張量分解

將M個(gè)3階張量y(1),y(2),…,y(M)∈RN×Dm×L一起進(jìn)行低秩分解：

y(m)=χ×2W(m)+ε(m)，

(28)

Khan等[38]對(duì)上述模型提出如下假設(shè)：

(29)

(30)

前述模型的聯(lián)合概率分布為

(31)

3 概率張量Tucker分解

3.1 指數(shù)族張量分解

以三階張量y∈RI1×I2×I3的Tucker分解為例，含噪聲的分解模型可以表示為

y=[C;U(1),U(2),U(3)]+ε，

(32)

其中U(m)∈RIm×Jm，C∈RJ1×J2×J3，ε∈RI1×I2×I3為噪聲張量。將式(32)兩邊向量化，有y=Wc+e，其中列向量y和c的維數(shù)分別是I1I2I3和J1J2J3，W=U(3)?U(2)?U(1)，e為噪聲向量。在傳統(tǒng)的Tucker分解中，一般假設(shè)噪聲服從高斯分布，并基于極大似然估計(jì)來(lái)求解U(m)和C。然而，對(duì)于其他類型的噪聲分布，之前的估計(jì)方法是不合理的，為此，Hayashi等[39]提出了指數(shù)族張量分解。似然函數(shù)可以表示為

(33)

其中θ=Wc，D=I1I2I3表示θ的維數(shù)，hd表示yd服從指定的指數(shù)分布，Expon(·)表示指數(shù)族分布。為了防止過擬合的發(fā)生，在對(duì)數(shù)似然函數(shù)logp(y|θ)上加兩個(gè)正則項(xiàng)，即

(34)

其中ψhd(θd)為對(duì)數(shù)分割函數(shù)，第三部分對(duì)應(yīng)向量c的標(biāo)準(zhǔn)高斯先驗(yàn)，第四部分對(duì)應(yīng)因子矩陣U(m)的精度為αm的球形高斯先驗(yàn)。

在使用期望最大化(Expectation-maxinization，EM)算法估計(jì)參數(shù)時(shí)，會(huì)遇到兩個(gè)困難：在期望(E)時(shí)，先驗(yàn)分布和似然函數(shù)是非共軛的；在最大化(M)時(shí)，對(duì)數(shù)分割函數(shù)是非線性的。為了解決上述問題，文獻(xiàn)[39]使用拉普拉斯(Laplace)和高斯過程(Gaussian Process)來(lái)近似EM算法。

3.1.1 基于Laplace近似的后驗(yàn)概率推斷

3.1.2 基于高斯過程的期望近似

對(duì)數(shù)似然函數(shù)的期望近似表示為

(35)

關(guān)于U(1)對(duì)(35)式求偏導(dǎo)，根據(jù)高斯過程的積分和導(dǎo)數(shù)性質(zhì)，求出U(1)、U(2)和U(3)。

前述方法對(duì)多維數(shù)據(jù)使用了指數(shù)族張量分解，并使用高斯過程來(lái)降低EM算法的高復(fù)雜度，得到參數(shù)的較好估計(jì)。

3.2 無(wú)限Tucker分解

假設(shè)觀測(cè)數(shù)據(jù)y∈RI1×I2×…×IN是由與之同型的潛在數(shù)據(jù)M產(chǎn)生的，即

(36)

這里i=(i1,i2,…,iN)。將M進(jìn)行Tucker分解：M=[C;U(1),U(2),…,U(N)]，其中C∈Rr1×r2×…×rN，U(n)∈RIn×rn，n=1,2,…,N。文獻(xiàn)[40]和[41]提出了一種無(wú)限Tucker分解。

以概率單位(Probit)噪聲為例，使用變分期望最大化方法來(lái)推斷參數(shù)。通過引入變量zi，將概率單位模型分解成如下形式：

(37)

其中p(yi|zi)=δ(yi=1)δ(zi>0)+δ(yi=0)δ(zi≤0)，p(zi|mi)=N(zi|mi,1)，δ(·)是指標(biāo)函數(shù)。因?yàn)閷W(xué)生t分布可以表示成一個(gè)Gamma分布與一個(gè)高斯分布的卷積，所以服從學(xué)生t分布的張量M的密度函數(shù)可以表示為

(38)

其中TN表示張量高斯分布。于是數(shù)據(jù)集的聯(lián)合概率分布為

p(y,Z,M,η,U)=p(y|Z)p(Z|M)p(M|η,U)p(η)p(U)，

(39)

其中U={U(1),U(2),…,U(N)}，p(M|η,U)為張量高斯分布，p(η)為Gamma分布，p(U)為L(zhǎng)aplace先驗(yàn)。

使用變分EM算法對(duì)參數(shù)進(jìn)行估計(jì)。在期望(E)時(shí)，假設(shè)模型參數(shù)之間相互獨(dú)立，使用q(Z,M,η)=q(Z)q(M)q(η)來(lái)近似后驗(yàn)分布p(Z,M,η|y,U)，通過變分推斷來(lái)最小化q(Z)q(M)q(η)與p(Z,M,η|y,U)的KL散度，即

(40)

在最大化(M)時(shí)，關(guān)于U最大化對(duì)數(shù)似然函數(shù)的期望，即

(41)

使用梯度下降法求解上述最優(yōu)化問題。類似求解高斯噪聲與數(shù)據(jù)丟失情形。

無(wú)限Tucker分解把數(shù)據(jù)從有限維空間映射到無(wú)限可數(shù)維空間，雖然提高了模型的精度，但卻增加了模型的復(fù)雜度。

4 總結(jié)與展望

本文研究了概率張量分解模型，并將其歸結(jié)為兩類。第一類是概率張量CP分解模型，主要包括貝葉斯張量CP分解、貝葉斯魯棒CP分解、Beta負(fù)二項(xiàng)CP分解和MCMC貝葉斯張量分解等。第二類是概率Tucker張量分解，包括指數(shù)族的張量分解和無(wú)限Tucker分解。對(duì)這兩類概率張量分解模型分別進(jìn)行了簡(jiǎn)要的綜述，并評(píng)價(jià)了它們的優(yōu)缺點(diǎn)。

現(xiàn)有的概率張量分解模型大多假設(shè)噪聲類型是高斯的，并在全貝葉斯框架下推斷參數(shù)，同時(shí)張量的秩不再像傳統(tǒng)方法需要人工確定。這些處理方式增加了模型的魯棒性，在一定程度上避免了過擬合現(xiàn)象。在估計(jì)參數(shù)時(shí)，大多采用貝葉斯變分推斷、Gibbs采樣和EM方法，從而有效地降低了模型的復(fù)雜度。雖然概率張量分解模型已經(jīng)取得了很好的效果，但在理論和應(yīng)用上仍存在著很多挑戰(zhàn)。對(duì)于不同的實(shí)際問題，選擇適合的噪聲類型與概率分布是建立概率張量分解模型的關(guān)鍵。此外，概率非負(fù)張量分解比概率張量分解在理論與算法上具有更大的難度，是值得探索的一個(gè)研究方向。在今后的研究中，將重點(diǎn)考慮概率分布參數(shù)的先驗(yàn)知識(shí)和稀疏噪聲的選取，并設(shè)計(jì)具有較低計(jì)算復(fù)雜度的算法。