基于蒙特卡洛方法的非負矩陣分解初始化

陳紅莉

(武漢大學數學與統計學院,湖北武漢 430072)

1 引言

非負矩陣分解(NMF)是1999年由Lee和Seung[1]首次提出的,有著比較廣泛的應用,如圖像處理[1]、文本聚類[2]和社區發現[3]等.相較于其他的矩陣分解,由于元素的非負性,所以可解釋性很強.比如:在處理圖像時,負的像素點是沒有意義的;在文本聚類時,正值代表文檔以一定概率屬于某個主題,負值則沒有任何實際意義.

非負矩陣分解數學描述如下:給定非負矩陣A∈Rm×n,希望找到兩個非負矩陣W∈Rm×k和H∈Rk×n,使得A≈WH.可以通過以下優化問題來找到W和H,

解決非負矩陣分解的方法有很多,比較常見的是由Lee和Seung在2001年提出的基準算法(Multiplicative Update Rules)[4]、Lin在2007年提出的投影梯度法[5]以及Kim和Park在2008年提出的交替非負最小二乘法(ANLS)[6].

不同于某些迭代算法,非負矩陣分解初始值的選擇對于算法效果有很大影響.由Qiao提出的SVD-NMF[7]和Boutsidis等人提出的NNDSVD[8]算法都是基于矩陣A的奇異值分解,但是當矩陣A的維數很大時,對A直接進行奇異值分解是耗時的.不同于這兩種方法,本文不直接對原矩陣A進行奇異值分解.本文利用Frieze等人[9]的思想,通過抽樣構造一個更小的矩陣,對這個小矩陣來做奇異值分解,從而實現對W和H的初始化,這大大節省了算法的計算時間.

2 預備知識

首先,介紹一種最為經典的非負矩陣分解算法,即由Lee和Seung在2001年提出的基準算法(Multiplicative Update Rules)[4],以下簡稱MU算法.在本文的數值實驗部分,將會用到MU算法.MU算法步驟如下

步驟1初始化,?i,a,b,j.

步驟 2對于k=1,2,···,

從式子(2.1)和(2.2)中可以看出,如果在第k次迭代中W和H是非負的,那么在第k+1次迭代中,MU算法依然能夠保證W和H是非負的.并且,Lee和Seung[4]已經證明在MU算法下,目標函數f(W,H)是非增的,即f(Wk,Hk?1)≤f(Wk?1,Hk?1),f(Wk,Hk)≤f(Wk,Hk?1).

由于本文提出的算法涉及到抽樣,下面給出對向量和矩陣進行抽樣的假設.

假設2.1[10]給定向量x∈Rn,假設可以根據分布Dx來對i∈{1,2,...,n}進行抽樣,也就是說i被抽中的概率為

假設2.2[10]給定矩陣A∈Rm×n,假設滿足以下假設

1.可以對矩陣A的行標i∈{1,2,···,m}進行取樣,矩陣A的第i行被選中的概率為

2. 對于任意的i∈{1,2,···,m},可以根據分布DA(i,·)來對矩陣A的列標j∈{1,2,···,n}進行抽樣,也就是說j被抽中的概率為

定理2.3[9]給定矩陣A∈Rm×n,獨立的按照概率分布

從行標中取p個樣本:i1,···,ip.記S∈Rp×n為規范化后的子矩陣,即對于t∈{1,···,p},則對于任意給定的θ>0,滿足

在第3節,會根據定理2.3說明本文提出的初始化方法(KFV-NMF)的可行性.

3 NMF初始化算法

由定理2.3,可以看出,若按照滿足假設2.2的概率分布來抽樣:假設抽取了矩陣A的p行,并按照定理2.3所說的構造一個p×n階的矩陣S,則可以用STS來近似ATA.A的奇異值分解可以通過ATA的譜分解得到,盡管這里可以從STS的譜分解入手,但并不打算這樣做,因為STS是一個n×n階的矩陣,維數也是很大的.這里可以對S的列進行同樣的操作,從S中抽取p列,類似的得到一個p×p階的矩陣W,則WWT近似SST,故最終可以直接對一個p×p階的矩陣W做奇異值分解,從而近似得到矩陣A的右奇異向量,這大大減少了計算時間.這種思想是Frieze等人[9]提出的,本文借鑒這種思想提出了一種更節時的非負矩陣分解初始化方法,記此算法為KFV-NMF.

下面,給出算法的具體流程.

1 FKV-NMF初始化輸入:A,p,k,images/BZ_7_413_771_440_805.png.1.對A的行進行取樣:獨立的按照滿足假設2.2的概率概率分布P=(P1,P2,···,Pm).抽取p個行標,記為i1,i2,...,ip,即Pi=kA(i,·)k2 kAk2.F構造 p × n 階矩陣 S,其中 S(t,·)=A(it,·)/p pPit,t=1,2,···,p.2.對S的列進行抽樣:獨立的按照滿足假設2.1的概率概率分布P0=(P01,P02,···,P0n).抽取 p 個列標,記為 j1,j2,···,jp,即P0j=pX DA(it,·)(j)/p.t=1 q構造 p × p 階矩陣 W,其中 W(·,t)=S(·,jt)/pP0 jt,t=1,2,···,p.3.計算矩陣W前k個奇異值?σ1,?σ2,···,?σk以及對應的左奇異向量?u1,?u2,...,?uk.4.構造n×k階矩陣?V:?V=(ST?u1?σk).5.令W0=max(?,A?V),H0=max(?,?VT).輸出:W0和H0.?σ1,ST?u2 ?σ2,...,ST?uk

下面,給出一個定理,并以此來說明算法FKV-NMF中第2步的具體實施方法.

定理3.1假設矩陣A∈Rm×n滿足假設2.2,S和W如算法FKV-NMF中第1和2步所構造,則

證由有

由算法FKV-NMF的流程可以看出,本文提出的初始化算法FKV-NMF的數值計算時間大大減少的原因在于:本文不是對原矩陣A直接進行奇異值分解,而是通過抽樣構造一個更小的矩陣W,對小矩陣W做奇異值分解,這使得算法FKV-NMF在奇異值分解上花費的時間大大減少,而現有的基于奇異值分解的初始化算法都是直接對原矩陣A進行奇異值分解,這是本文提出的算法數值計算時間較其他算法減少的原因.另外,通過簡單計算可以發現:算法FKV-NMF中矩陣中的每一列可以近似看作矩陣A的右奇異向量,Frieze等人在其文章[9]中也說明了這一點,這也是算法FKV-NMF的理論依據.

當然,算法FKV-NMF也有弊端:此算法雖然在奇異值分解上節省了很多時間,但是它還要計算用于抽樣的概率分布P和P0,這是有點耗時的.一般來說,基于奇異值分解的初始化算法使用的都是截斷奇異值分解,比如前文提到的初始化算法SVD-NMF和NNDSVD.隨著k值的減小,截斷奇異值分解所使用的時間也在不斷減少,當k小到某一程度時,算法FKV-NMF在進行奇異值分解上節省的時間便不再占優勢.但是,這也是算法FKV-NMF可以進一步改進的地方,比如可以考慮使用其他更加快速有效的抽樣方法.

4 數值實驗

在本次實驗中,測試了兩組數據:第一組是隨機生成的服從均值為0、方差為1的高斯分布的隨機數,這里取絕對值來保證矩陣元素的非負性,即A=|N(0,1)|,維數是500×300.第二組是人臉數據庫ORL,ORL數據庫一共包含400張92×112像素的圖片,一共40個人,每人10幅不同表情的臉.在計算不同算法的時間和誤差的實驗中,將這400張人臉圖像組成了一個10304×400的矩陣,作為算法的輸入.在進行人臉重構實驗時,選取其中360張圖像作為訓練集,40張圖像作為測試集.

在實驗中,將本文提出的算法FKV-NMF與兩種比較常見的基于SVD的初始化算法SVD-NMF和NNDSVD作了比較.非負矩陣分解算法采用的是經典的MU算法.誤差采用公式

在表1和表2中,分別計算了在k等于不同值時,SVD-NMF、NNDSVD和FKV-NMF三種不同的初始化算法所用的時間和所產生的誤差.另外,由于本文提出的算法涉及到抽樣技術,所以算法效果會有稍許波動,為公平起見,實驗重復20次,取平均值.

表1 三種不同的初始化算法所用的時間

表2 三種不同的初始化算法所產生的誤差

從表1和表2中,可以看出:就時間來方面說,本文提出的FKV-NMF初始化算法所用的時間要比SVD-NMF和NNDSVD小的多.就誤差方面來說,初始化誤差比NNDSVD要大一些,但是比SVD-NMF要小.所以本文提出的初始化算法在大大節約了時間的同時,誤差也在可接受的范圍內.

圖1 使用不同初始化算法后,隨著迭代次數增加,MU算法誤差變化情況

在圖1中,展現了SVD-NMF、NNDSVD和FKV-NMF三種不同初始化算法對于非負矩陣分解算法誤差的影響.圖中曲線表示隨著迭代次數增加,誤差的變化情況.從圖1中可以看出,在使用SVD-NMF、NNDSVD和FKV-NMF三種不同的初始化算法后,使用MU算法進行非負矩陣分解時,隨著迭代次數的增加,誤差均在減少,直到達到一個平穩值.NNDSVD的初始化誤差雖然最小,但誤差很快便不再下降.在隨機生成的數據(Random)上,大約100次迭代后,誤差幾乎不再下降,在ORL數據集上,大約200次迭代后,誤差幾乎也不再下降,而且最終誤差比其他兩種方法都要高的多.本文提出的FKV-NMF雖然最終誤差比SVD-NMF稍高,但是相差并不多.而且在迭代的最初始階段,使用本文提出的FKV-NMF初始化方法的誤差要比SVD-NMF低一些.

下面,展示了使用不同初始化算法后,MU算法迭代次數為1000時,ORL數據庫部分人臉圖像的重構情況.圖2是人臉的重構圖像,第1到第3行使用的初始化算法依次是SVDNMF、NNDSVD和FKV-NMF.在表3中,計算了重構圖像的信噪比(SNR),第1到第7列分別表示7個重構圖像.信噪比是用來衡量圖像質量的一種方式,信噪比越大,表示重構的人臉圖像質量越好.這里信噪比的計算公式為:其中g(i,j)表示原始圖像的灰度值,f(i,j)表示重構圖像的灰度值.

圖2 ORL數據集人臉的重構圖像

表3 重構圖像的信噪比(SNR)

從圖2和表3中,可以看出:從重構圖像的清晰度來看,使用SVD-NMF和本文提出的FKV-NMF初始化算法圖像清晰度相差無幾,而使用NNDSVD初始化算法的重構圖像效果則稍差.從SNR的值來看,使用SVD-NMF和本文提出的FKV-NMF初始化算法圖像的SNR值相差并不多,而使用NNDSVD初始化算法的重構圖像SNR值要明顯小于其他兩者.

通過以上數值實驗,可以看到:本文提出的初始化算法FKV-NMF的運行時間較SVDNMF和NNDSVD大大減少,也在一定程度上保持了精度.