史加榮， 張安銀

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

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

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

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

1 基本知識

1.1 CP分解

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

(1)

圖1 3階張量的CP分解

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

(2)

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

(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分解是將它分解為一個核心張量與N個矩陣的模式積，即

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是超對角的，且J1=J2=…=JN，則Tucker分解就退化成CP分解。換言之，CP分解是Tucker分解的一種特殊情況。本文采用了Acar等人[29]的張量符號，關(guān)于張量分解的更多知識可參考文獻[9-10]和[31]。

2 概率張量CP分解

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

2.1 貝葉斯張量CP分解

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

y=χ+ε，

(7)

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

(8)

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

(9)

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

(10)

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

(11)

易知p(θ|yΩ)∝p(yΩ,θ)，使用變分貝葉斯方法對參數(shù)θ進行估計[32]?；诰祱隼碚揫33]，從而對丟失的數(shù)據(jù)進行預(yù)測：

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

(12)

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

2.2 貝葉斯魯棒CP分解

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

y=χ+s+ε，

(13)

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

(14)

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

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

(15)

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

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

(16)

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

(17)

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

2.3 Beta負二項CP分解

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

(18)

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

(19)

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

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

(20)

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

2.4 MCMC貝葉斯張量分解

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

(21)

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

(22)

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

2.5 乘性伽馬過程張量分解

(23)

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

(24)

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

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

(25)

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

(26)

對于二元數(shù)據(jù)，模型的似然函數(shù)為Logistic函數(shù)，即

(27)

2.6 多視覺張量分解

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

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

(28)

Khan等[38]對上述模型提出如下假設(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è)噪聲服從高斯分布，并基于極大似然估計來求解U(m)和C。然而，對于其他類型的噪聲分布，之前的估計方法是不合理的，為此，Hayashi等[39]提出了指數(shù)族張量分解。似然函數(shù)可以表示為

(33)

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

(34)

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

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

3.1.1 基于Laplace近似的后驗概率推斷

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

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

(35)

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

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

3.2 無限Tucker分解

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

(36)

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

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

(37)

其中p(yi|zi)=δ(yi=1)δ(zi>0)+δ(yi=0)δ(zi≤0)，p(zi|mi)=N(zi|mi,1)，δ(·)是指標函數(shù)。因為學生t分布可以表示成一個Gamma分布與一個高斯分布的卷積，所以服從學生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)為Laplace先驗。

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

(40)

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

(41)

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

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

4 總結(jié)與展望

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

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