基于最大熵與相關性分析的非負矩陣分解

馮本勇 徐勇軍

1(石家莊工商職業學院 河北 石家莊 050000)

2(中國科學院計算技術研究所 北京 100190)

0 引 言

矩陣分解(MF)模型是多元分析中降維和特征學習的有效方法,高維數據樣本被格式化為矩陣,然后分解成低維矩陣的乘積[1]。非負矩陣分解(NMF)是最流行的矩陣分解模型之一,它允許將一個非負輸入矩陣分解成兩個低階非負矩陣,通過原始特征的分布因子分解,樣本由學習的潛在因子的相加組合重構,該方法由于其泛化能力較強得到了廣泛的應用[2-3]。

為了學習高質量的潛在因子,學者在許多類MF模型中研究了潛在因子的性質。主流研究學派建議減少共適應,以便有效地捕捉數據中罕見的隱藏模式。黃衛春等[4]提出了一種正交約束非負矩陣三因子分解(NMTF),使潛在因子的多樣性最大化,從而得到嚴格的聚類解釋。Chen提出在奇異值分解(SVD)中為學習的潛在因子分配權重,而不是矩陣項。余江蘭等[5]提出了非負多矩陣分解(NMMF),它將用戶項矩陣與兩個輔助矩陣一起分解,以合并邊界信息。徐霜等[6]提出了一種改進NMF(ENMF)來進一步從一系列矩陣中提取知識。然而,上述方法受到硬幾何約束的巨大計算量的限制,并且這些經典的方法主要集中在如何整合更多的輔助信息和領域知識上,而對學習的潛在因子的特性關注較少[7]。

為此,本文提出一種多分量NMF同時學習多組潛在因子,并使用Hilbert-Schmidt獨立性準則來發現多樣性信息,從而可以對數據的多方面進行探索。劉國慶等[8]利用大錐罰函數尋找具有大互角的潛在因子,可以很好地推廣到其他不可知的數據中。另外,為了有效地分解高度混合的數據,李向利等[9]提出了一種最小體積約束的NMF(MVCNMF)來學習彼此相對相似的潛在因子,MVCNMF模型也成功地應用于高相關度的人臉圖像處理。但是上述方法未能解決各因素的相關性進行建模,并且缺乏對詞或像素等原始輸入特征應如何分布的因子內分析。

為解決上述問題,提出一種基于最大熵與相關性分析的非負矩陣分解方法(MECNMF),利用最大熵原理描述非負矩陣分解中的潛在因子分布,以捕捉語義質量的潛在因子特性,并提出一種基于相似性的方法來度量差異性。另外,將自適應加權策略引入因子間的相互關系,使得每個潛在因子能夠無監督地獲得自適應權重。在多個數據集上的實驗結果表明,本文方法具有良好的性能。

1 研究方法

1.1 非負矩陣分解

X=UV

(1)

(2)

NMF的損失函數測量X和UV之間的重構誤差。平方歐幾里得距離和廣義Kullback-Leibler散度是最常用的距離度量[4]。平方歐幾里得距離損失函數為:

(3)

1.2 最大熵理論

1.2.1分布狀態分析

NMF框架中的關鍵問題是找出哪些潛在因子對數據的語義重構貢獻更大,從而更好地擬合輸入矩陣X。如圖1所示,從式(2)的數據重構角度來看,NMF可以類比為一種深度神經網絡(DNN)模型的作用。

圖1 NMF框架

在圖1的左半部分,輸入樣本xns被轉換成K個潛在因子的組合uks,其中表示向量vns作為網絡權重。與DNN的區別有三個方面:首先,將所有樣本數據同時送入NMF,而DNN是將樣本數據分批送入;其次,uks是無監督自動學習的,不需要任何指導性標簽數據;最后,NMF無非線性激活函數。

在這種無監督學習環境下,本文提出兩種基于對潛在因子的直觀分析的自適應加權策略,如圖1的右側所示。首先,一個潛在因子應該對更多原始特征中的語義進行編碼。如果uk的分布主要集中在一些原始特征上,那么它很可能產生過擬合現象,并且設置的權重應該更小。為此,本文提出一種最大熵測量方法g(uk)來定量分析潛在因子的分布狀態。其次,如果uk與其他潛在因子區別較大,那么uk很可能會受噪聲和離群值的影響,從而在語義重構過程中無法與其他潛在因子進行良好的協作。因此,提出一種互相關測量方法h(uk)來定量分析潛在因子分布之間的關系。然后,將兩個測量值整合,分配給各個潛在因子的自適應權重中。最后,進行Sigmoid變換,進一步增強了處理非線性數據的能力。

為了改善數據表示,每一個潛在因子首先需要傳達完整的語義。在NMF中,一個潛在因子uk表示為原始輸入特征的分布,每個條目umk表示第m個原始特征對uk的重要性。根據以上分析,需要定量地測量uk的分布狀態。

信息熵是對事件狀態的不可預測性的度量[8]。在此,潛在因子uk相當于一個“事件”,原始特征表示可能存在的狀態,uk關于它們的歸一化分布表示可能性,其表示為:

(4)

(5)

1.2.2相關性分析

從上述分析來看,既要考慮到要素的分布特征,又要考慮它們之間的相關性。如果uk在M維特征空間中分布較稀疏,就會形成一個相對松散的語義空間,其中可能混雜噪聲。相反,緊湊的語義空間著重于大多數數據點,因此應適當促進潛在因子之間的相關性,這種自適應協作可以揭示不同潛在主題之間的協方差結構[7]。

針對潛在因子提出各種相關措施[8],采用了廣泛使用的分布向量間的余弦相似性,但用其他相似性度量標準也是可行的。即uk與其他語言的整體語義相關性被定義為余弦相似度的總和,其計算式為:

(6)

式中:絕對值|umk|表示uk對第m個原始特征的權重,整體語義相關性的范圍為[0,K]。若h(uk)的值較高,表明uk與其他潛在因子相關性較好。隨著重構誤差減小,增加h(uk)將促進潛在因子之間的相互協作,并加強學習語義空間的緊湊性。

1.2.3加權轉換

根據上述對潛在因子的分析,除了最小化分解損失之外,還有兩個項可以如式(5)和式(6)中那樣進行最大化。一種方法是將它們規范化,然后附加到損失函數中,但也存在較明顯的缺陷。首先,為了將損耗最小化問題與兩個目標最大化相結合,需要通過一些減法操作和兩個超參數來平衡它們。但是,參數調整過程非常困難,因為這三個項的取值范圍彼此相差較大。另外,最大熵和互相關約束不會直接施加在單個潛在因子上,而是間接地作為除了重構誤差之外的損失。因此,本文提出一種自適應加權策略,將兩種測量結果以緊密耦合的方式集成到重構損耗中。

對目標矩陣X的行、列甚至向量分配特定權重的常規加權策略,MECNMF通過對語義重構的貢獻來權衡單個uk。對于每個潛在因子uk,為其分配一個非負權重變量λk。隨著λk的變大,uk在表示學習中的作用越來越重要。λk=0說明uk因其較差的表達能力而被完全刪除。

根據分布狀態分析,如果uk具有較高的g(uk)值,則其分布更可靠并且可以更好地編碼語義信息,即權重λk與測量值g(uk)之間存在正相關。因此,與g(uk)相對應的權重部分的計算式為:

(7)

式中:f(·)是雙曲正切函數f(z)=tanh(z),有平滑數據的作用,然后除以最大值f(log2M),此時取值范圍擴大到[0,1]。

如果uk具有較高的h(uk)值,則它可以更好地與其他部分協作并增強語義空間的緊湊性。所以λk和h(uk)之間存在的相關性程度較高。與h(uk)相對應的權重部分的計算式為:

(8)

除以最大值f(K)后,其取值范圍可以擴大到[0,1]。使用可調超參數α,可將這兩個權重值可以整合到一起,并且可以計算出λk:

(9)

式中:0≤α≤1。利用上述權重變量λk,可以用其加權形式λkuk來改進uk。此外,除了自適應權值λk所傳遞的最大熵和互相關度量外,還需要提高uk處理非線性數據的能力。作為深度神經網絡的基本組成部分,漸近激活函數已經具備能夠使神經網絡逼近任何函數的能力。因此,用激活函數進一步加強uk:

(10)

式中:σ(·)是Sigmoid函數。因此,式(2)中輸入樣本向量xn的線性重構可以轉化為:

(11)

一個新的損失函數可表示為:

(12)

注意,MECNMF不同于傳統的加權NMF,因為分配給潛在因子的權重是通過兩個建議的測量值進行自適應學習,而不需要先驗知識。式(12)中的最終損失函數與NMTF中的類似,因為輸入矩陣X被分解為三個矩陣。然而,矩陣Λ中的元素不再是自由參數,而是以非線性的方式從矩陣U進行自適應學習。

1.3 算法優化

1.3.1對V進行優化

(13)

通過采用與文獻[5]相同的辦法,可以采用乘法運算得到V:

(14)

1.3.2對U進行優化

由于包含非線性分析函數g(·)和h(·),L對U求導比較復雜。因此,本設計采用經典梯度法對U進行優化,當L對U求偏導數時,首先求解對角權矩陣Λ對U的梯度,因為這是其中最復雜的部分。λk對uij求偏導數公式如下:

(15)

f(g(uk))對uij求偏導數公式如下:

(16)

(17)

(18)

式中:sign(·)是符號函數。f(h(uk))對uij求偏導數公式如下:

(19)

(20)

(21)

給定上述對角線權重矩陣的導數,可以很容易求出L對uij的偏導數:

4(σ(UΛ)VVT?σ′(UΛ)ΛT)ij+βsign(uij)

(22)

式中:σ′(·)是σ(·)函數的導數;?表示逐點矩陣乘法。在給定步長η的情況下,可以通過向其梯度相反的方向移動來更新U:

(23)

根據以上分析,本文提出一種如算法1中描述的迭代優化算法。在每一次迭代中,使用式(14)中的乘法更新規則來更新矩陣V,如第4行所示。還有一個內部迭代,用式(23)更新矩陣U,如第6-12行所示。外迭代和內迭代的最大次數分別為T和S。在實際應用中,選擇合適的步長η有些困難,因為當η值不適合時,優化過程要么存在收斂慢的問題,要么出現來回振動問題。通過文獻[8]中的自適應調整規則,引用文中的衰減策略:

η(t)=η(0)×γt

(24)

式中:γ是衰減率。當輸出矩陣收斂或達到最大迭代次數時,將結束迭代。

算法1MECNMF優化算法

輸入:數據矩陣X,潛在因子數K,超參數α、β。

輸出:基本矩陣U,表示矩陣V。

2.fort=1→Tdo

3.(1) 根據式(14)更新V:

5.(2) 根據式(23)更新U:

6.fors=1→Sdo

8.if 收斂 then

9. break

10. end if

11. end for

12.U(t)←U(t,s)

13.if 收斂 then

14. break

15. end if

16. end for

17.U←U(t),V←V(t)

1.3.3收斂性分析

為了達到優化目的,提出了算法1,它是傳統的NMF乘法更新算法和梯度下降算法的結合,證明這種新算法的收斂性很重要。令L(t)表示為第t次迭代后的損失,改進的優化過程在運行時會產生一系列損失:

L(0),L(1),…,L(t-1),L(t),L(t+1),…,L(T)

(25)

式中:L(0)是初始損失。如果可以證明上述序列是單調遞減的,由于損失函數值總是非負的,那么經過足夠的迭代次數,優化過程無疑會收斂到某一點,最終結果至少是一個局部最優解。

在算法1中,每個迭代步驟都包含兩個子步驟,分別是V和U的優化。因此,每一步損失L(t)可以進一步分為兩個子損失:

…,L(t-1,v),L(t-1,u),L(t,v),L(t,u),L(t+1,v),L(t+1,u),…

(26)

1.4 復雜性分析

T代表外部最大迭代次數,S代表內部最大迭代次數,M、N、K分別代表輸入樣本數量、原始特征、潛在因子。

在算法1中,主要的運算是求導和矩陣運算。為了方便起見,本文假設所有浮點運算的時間復雜度都是相同的。根據迭代公式,可以得出NMF和MECNMF的計算復雜度如表1所示。可以看出,當K<

表1 NMF和MECNMF的計算復雜性

2 實驗與結果分析

2.1 數據集

此次實驗使用了5個數據集,其中2個是文檔數據集,另外3個是圖像集。表2統計了貢獻度較高的數據。

表2 數據集統計

(1) 20NG:20新聞組語料庫是一個約20 000個新聞文件的集合,分為20個不同的組和6個普通類別。它包含18 291個文檔和9 313個經過預處理的常用詞。本文把普通類別作為聚類的基本依據。

(2) WebKB:WebKB語料庫包含4所大學計算機科學系的人工分類網頁。網頁分為7個類別,刪除了其中的3個類別,這些刪除的類別包含很少的樣本,或者沒有特定的含義,其余4個類別共4 168頁、7 770個術語。

(3) COIL20:COIL20是一個圖像數據集,包含20個對象從不同角度的形態,圖像是像素大小為32×32的灰度圖像,每個對象有72幅不同的圖像,每個對象的圖像歸為一個簇。

(4) Yale:Yale是一個包含15個人、像素大小為32×32灰度圖像的人臉圖像數據集。每個實驗對象有11幅不同面部表情或形態的圖像。每個人的所有圖像歸為一個簇。

(5) NUS-WIDE-OBJECT(簡稱NUS):NUS-WIDE-OBJECT數據集是NUS-WIDE的一個子集,它是一個真實的Web圖像數據集,它包含了31個類別的30 000幅圖片。參考文獻[9]后,本文移除了帶有多個標簽的圖像,并從每個類別中隨機選擇了100幅圖像。每個圖像由500個維度BoW向量表示。

2.2 不同算法間比較

MECNMF是NMF及其變形的一種通用方法。將所提出的加權策略和非線性變換應用于具有代表性的NMF基線,以驗證其靈活性。還將MECNMF與最近提出的NMF方法進行了比較,以說明其優越性。所有算法的比較結果及說明如下:

(1) NMF[2]:通過使用式(3)中的平方歐幾里得距離損失函數實現NMF。將輸入矩陣X分解為子矩陣U和V,其中V是輸入樣本的潛在表示。

(2) MECNMF[10]:MECNMF通過在因子分解過程中自適應學習潛在因子的權重來改進NMF。通過分布狀態分析、相關分析和非線性變換,改進了表示矩陣V。

(3) SNMF[11]:正則化NMF最常采用稀疏NMF(SNMF)。矩陣V的L1范數被附加到式(3)中,用于表示稀疏數據。

(4) MECSNMF[12]:與MECNMF類似,最大熵相關稀疏矩陣分解(MECSNMF)通過在因子分解過程中自適應學習潛在因子的權重來改進SNMF,非線性變換進一步提高了對數據非線性建模的能力。

(5) NWNMF[13]:Ncut-weighted NMF(NWNMF)使用特征相似圖計算X的權重,然后將NMF應用于加權X以學習數據表示。

(6) MECNWNMF[14]:最大熵相關Ncut-weighted MF(MECNWNMF)通過應用狀態分布分析、相關分析和非線性變換改進了NWNMF,增強了數據表示。

(7) NMTF[15]:非負矩陣三因子分解(NMTF)將輸入矩陣X分解為三個子矩陣,X=USV,其中V為表示矩陣。

(8) GNMF[16]:圖正則化NMF(GNMF)構造了一個相似圖來編碼數據樣本之間的幾何關系,并進一步令相似樣本在表示空間中處于相鄰位置。

(9) LCNMF[17]:相反在MECNMF的外部分析中,Large-Cone NMF(LCNMF)采用了促進潛在因子多樣性的large-cone懲罰。large-cone懲罰分為兩種形式,一種是由這些因素形成的平行面體積,另一種是它們成對夾角的總和。因此,LCNMF有兩種變體,大體積NMF(LVNMF)和大角度NMF(LANMF)都與MECNMF進行了比較。

(10) DNMF[18]:Dropout NMF(DNMF)試圖通過以一定概率隨機刪除潛在因子來促進其語義獨立性。與MECNMF和LCNMF不同,潛在因子之間的相關性和多樣性對它并沒有很大影響。

2.3 實驗參數設置

在分析實驗結果之前,本文比較并解釋了不同算法間的參數設置。在所有三個MECNMF中,對于20NG、WebKB、COIL20、Yale和NUS數據集,平衡參數α設置為0.5,β分別設置為1、10-1、10-3、10-3和10-2。優化參數設置如下:(1) 優化U的初始步長η(0),令20NG為50,令WebKB為10,令COIL20、Yale和NUS均為1;(2) 將所有數據集的衰減率γ設置為0.999 9;(3) 這些數據集的最大外部迭代數T為500;(4) 所有數據集的最大內部迭代數S為15。

對于所有5個數據集中的11個NMF變體,潛在因子K的數量設置為50。SNMF和MECSNMF中稀疏項的平衡參數的取值范圍是{10-3,10-2,…,103}。在NMTF中,雖然U和V的潛在維度可能不同,但值都設置為50。為了與MECNMF進行比較,進一步將NMTF的內矩陣S設為對角矩陣。對于GNMF、LVNMF、LANMF和DNMF,按照原文件中的參數值設置超參數。當NMF、MECNMF、SNMF、MECSNMF、NWNMF、MECNWNMF和NMTF收斂速度過快時,將最大迭代次數T設置為100,而將GNMF、LVNMF、LANMF和DNMF的值設置為1 000,因為它們的收斂速度很慢。MECNMF、MECSNMF和MECNWNMF的最大內部迭代次數S為15。對于所有的NMF方法,本文計算聚類結果的方法是在表示矩陣上采用K-Means算法。

2.4 評價指標

本文采用聚類準確度(ACC)和歸一化互信息(NMI)進行評價。用an和ln表示xn的原始聚類標記和預測聚類標記。ACC計算公式如下:

(27)

式中:map(l)=argkmax(|{xi|li=l,ai=k}|)將簇標簽映射到相應的原始標簽;δ(·,·)檢查兩個標簽是否相等,若相等則ACC為1,否則為0。互信息(MI)是決定集群劃分的方法:

(28)

式中:C和C′是同一樣本集的兩個不同的聚類;p(ci)測量了分配給聚類ci的整組樣本的比例;p(ci,cj)是聯合概率。為了更進一步直觀了解,通過采用熵來規范化MI(C,C′):

(29)

式中:H(C)表示聚類熵。

2.5 聚類結果

表3涵蓋了以上5個數據集上所有算法的聚類結果。用黑體表示原始NMFs和相應MECNMFs之間較好的結果,并且在所有參與比較的方法中最好的結果下加下劃線。可以發現:

表3 各個模型在不同數據集上的表現

與大多數算法相比,MECNMF在所有5個數據集上都表現出更好的性能,并且MECNMF(MECNMF、MECSNMF和MECNWNMF)始終優于原始算法(NMF、SNMF和NWNMF)。這有力地證明了對于具有代表性的NMF模型,本文算法比其他算法的性能較優越以及更能廣泛被運用。因此,與傳統的加權NWNMF相比,該策略能有效地提高潛在因子的權重。MECNMF在所有數據集上表現的性能都優于LVNMF和LANMF。此外,LVNMF和LANMF在數據集20NG上表現的性能比NMF要差,其原因在于緊湊的論題可以更好地適應輸入數據。20NG數據集是一個松散分類的新聞語料庫,數據中存在噪聲和冗余。如果不考慮潛在因子之間的關系,學習到的語義空間很容易被誤導。然而,MECNMF通過提高語義空間的緊湊性可以解決這個問題。DNMF性能優于NMF,但比MECNMF差。這說明對學習過程中潛在因子之間的關系進行建模確實可以改善NMF,并且MECNMF的顯式分析比DNMF中的內部丟棄表現得更好。最后,所有的MECNMF總是比NMTF表現更好,因此所提出的加權策略發揮了作用,而不是簡單地在因子分解中插入一個對角矩陣。

2.6 參數分析

2.6.1α敏感性分析

圖2 平衡參數α分析

2.6.2β敏感性分析

圖3 平衡參數β分析

2.6.3K的敏感性分析

影響NMF性能的另一個參數是潛在因子K的數量。對于一個給定的數據集,潛在因子的數量不能預先精確估計。較小的K值不能學習數據中全部的信息,而較高的K值會增加計算復雜度和學習參數的難度。因此,有必要分析該算法對K的敏感性,為此本文進行了當K∈{20,30,40,50,60,70,80,90,100}時的實驗。圖4描繪了當K取不同值時4種算法的聚類結果變化情況。理想情況下,隨著K的增加,聚類結果變得更好。然而,在實驗過程中,曲線是波動的,但總體趨勢是向上的。不穩定的主要原因可能是本文采用梯度下降法對算法進行了優化,算法往往受到初始化值等因素的影響,有可能陷入局部優化。此外,參數的隨機性也會導致曲線波動。然而,無論K值如何變化,本文提出的改進算法(MECNMF和MECNWNMF)總是比原算法(NMF和NWNMF)性能更好。考慮到性能和時間消耗,綜上所述,將K設置為50。

圖4 平衡參數K分析

2.7 語義空間分析

首先,MECNMF考慮了潛在因子的分布狀態,并強制它們從原始特征中編碼更多的信息,以減少語義歧義。g(·)函數用來衡量一個潛在因子對語義的編碼程度。當α=1(表示為MECNMF-g)時,它是影響權重的唯一因素。如果有效地降低模糊度,uk的分布將集中在更多的原始特征上,并且g(uk)需要取較高的值。圖5描繪了MECNMF、MECNMF-g和NMF收斂后g(·)函數的值。為了便于說明,潛在因子按g(·)值的升序排列,僅取前15個值。可以看出,MECNMF和MECNMF-g的g(·)值均比NMF的大,因為它們可以編碼更多的原始語義以減少歧義。盡管不明顯,MECNMF-g的g(·)值略大于MECNMF,因為它的加權策略只考慮了最大熵度量。

圖5 信息熵函數分析

其次,MECNMF還考慮了潛在因子之間的相關性,并將其歸納為一個緊湊的語義空間,過濾掉異常值和噪聲。用h(·)函數來度量語義空間的緊密性,當α=0(表示為MECNMF-h)時,它是權重中唯一需要考慮的因素。當MECNMF、MECNMF-h和NMF收斂后,在圖6中繪制出h(·)的值。為了便于說明,潛在因子按h(·)的升序排列,僅描繪了前15個值。很明顯,MECNMF和MECNMF-h都比NMF有更大的h(·)值,因為潛在因子需要學習一個緊湊的語義空間。另外,由于MECNMF-h的加權策略只考慮了語義的緊湊性,所以它的h(·)值比MECNMF大。總之,分布狀態函數g(·)和相關函數h(·)在MECNMF學習過程中都起著舉足輕重的作用,而且二者的融合進一步提高了系統的性能。

圖6 因子相關函數分析

2.8 收斂性與計算效率

進行了證明算法的收斂性和收斂速度的實驗。圖7描繪了上述數據集的收斂曲線,x軸表示迭代次數,y軸表示目標函數值。可以看到,本文算法在上述5個數據集上經過大約200次迭代后達到收斂,這說明本文算法收斂速度很快。

圖7 收斂函數

如表1所示,當K<

3 結 語

為解決傳統非負矩陣分解不考慮潛在因子的相關性與分布特征等缺點,提出一種基于最大熵與相關性分析的非負矩陣分解方法。通過多個數據集的實驗可得出如下結論:

(1) 對于具有代表性的NMF模型,MECNMF比其他算法的性能更優越,且具備更好的泛化能力,另外,算法的收斂速度很快。

(2) MECNMF通過提高語義空間的緊湊性可以提高潛在因子的權重,有效地解決語義空間容易被誤導的問題,并且MECNMF的顯式分析比DNMF中的內部丟棄表現得更好。

(3) 分布狀態函數和相關函數在MECNMF學習過程中都起著舉足輕重的作用,而且二者的融合進一步提高了系統的性能。