基于矩陣型慣性投影神經(jīng)網(wǎng)絡(luò)的非負(fù)矩陣分解算法

李小玲,夏又生

(福州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建福州 350108)

0 引言

非負(fù)矩陣分解(nonnegative matrix factorization，NMF)是一種有效的特征學(xué)習(xí)技術(shù)，旨在將一個(gè)高維的非負(fù)矩陣分解為兩個(gè)低秩非負(fù)矩陣的乘積，可以有效地進(jìn)行數(shù)據(jù)降維，并得到基于部分的表示.

Paatero等[1]最先引入正矩陣分解這一思想. 在NMF的求解算法，乘法更新算法[2]易于實(shí)現(xiàn)，但無法保證收斂到駐點(diǎn)[3]. 為了解決上述缺陷，Berry等[4]提出了交替非負(fù)最小二乘法(ALS). 而后，Lin[5]提出了投影梯度法，大大提高了交替非負(fù)最小二乘法的收斂速度. 基于NMF的基本模型，眾多改進(jìn)的 NMF 算法[6-8]也相繼被提出，其中Li 等[6]提出局部NMF用于人臉檢測，Hoyer[7]將稀疏編碼的思想融入到NMF中，Cai等[8]提出的圖正則化非負(fù)矩陣分解(graph regularized NMF，GNMF)可以將數(shù)據(jù)的內(nèi)在結(jié)構(gòu)嵌入低維表示.

作為一種并行優(yōu)化方法，神經(jīng)動(dòng)力學(xué)優(yōu)化方法在處理優(yōu)化問題中展現(xiàn)出優(yōu)越的搜索能力. Li等[9]解決了一類矩陣不等式約束矩陣的最小二乘問題形式； Huang等[10]提出了求解矩陣值優(yōu)化問題的連續(xù)時(shí)間和離散時(shí)間兩種矩陣型投影神經(jīng)網(wǎng)絡(luò)； Ye等[11]提出了一種求解盒約束條件下矩陣變量非線性優(yōu)化問題的矩陣型神經(jīng)動(dòng)力學(xué)方法. 在Dai等[12]的向量模型的基礎(chǔ)上，本研究提出一個(gè)基于連續(xù)時(shí)間矩陣型慣性投影神經(jīng)網(wǎng)絡(luò)的NMF算法，并將其運(yùn)用到人臉識別. 理論分析說明基于矩陣型神經(jīng)網(wǎng)絡(luò)的交替迭代算法能夠收斂到矩陣非負(fù)分解優(yōu)化問題的偏最優(yōu)解. 比較4種基于常見的非負(fù)矩陣分解算法，計(jì)算結(jié)果驗(yàn)證了所提出算法的有效性.

1 非負(fù)矩陣分解

V≈WH

基于NMF模型，Cai等[8]提出了圖正則化非負(fù)矩陣分解方法，目的是有效表示數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，為了加強(qiáng)稀疏性，Dai等[12]引入了稀疏正則化模型. 稀疏圖正則化NMF優(yōu)化模型為：

由于問題(I)是一個(gè)雙凸優(yōu)化模型[13-14]，為了求解問題(I)，將其分解為如下兩個(gè)凸優(yōu)化子問題：

2 矩陣型神經(jīng)網(wǎng)絡(luò)

2.1 慣性投影神經(jīng)網(wǎng)絡(luò)模型

為了解決優(yōu)化問題(Ⅱ)，Dai等[12]提出一個(gè)向量型慣性投影神經(jīng)網(wǎng)絡(luò)模型. 為了加速和并行化，提出一種矩陣型慣性投影神經(jīng)網(wǎng)絡(luò)(matrix inertial projection neural network，Matrix-IPNN), 即：

(1)

(2)

2.2 穩(wěn)定性分析

由于網(wǎng)絡(luò)(1)和(2)結(jié)構(gòu)相似，所以不失一般性，針對網(wǎng)絡(luò)(1)給出穩(wěn)定性分析.

證明 首先考慮X≥L，即證明X-L≥0，記Z=X-L，則式(1)可變換為：

(3)

(4)

(5)

式(5)兩邊同時(shí)乘以eθt并積分，可得：

(6)

(7)

式(7)兩邊同時(shí)除以θ，整理得：

(8)

(9)

定理1定義N(X)=X-PΩ(X-?f(X))，如果滿足下列兩個(gè)條件.

其中：θ是N(X1)-N(X2)和X1-X2的夾角.

2)δλ2>1.則式(1)的狀態(tài)解將全局收斂到問題(Ⅱ)的最優(yōu)解.

證明 首先證明, 式(1)的狀態(tài)解X(t)有界.考慮X*∈Ω，定義李雅普諾夫函數(shù)：

(10)

對式子(10)關(guān)于t求一階導(dǎo)，有：

(11)

同理可得V(t)關(guān)于t的二階導(dǎo)為：

(12)

將式(11)和式(12)加權(quán)求和，由N(X)=X-PΩ(X-?f(X))，有：

為了更直觀的表現(xiàn)小學(xué)生口算速度發(fā)展的趨勢，以年級為橫坐標(biāo)，廣度為縱坐標(biāo)，對4種口算（不進(jìn)位加法、進(jìn)位加法、不退位減法、退位減法）廣度的發(fā)展趨勢折線圖進(jìn)行分析，具體如圖2所示．

(13)

已知N(X*)=0，根據(jù)式(13)和條件(a)可得：

因此有：

(14)

式(14)可改寫為：

(15)

這表明函數(shù)：

(16)

單調(diào)非增. 因此，對任意t>0，有：

(17)

(18)

(19)

(20)

(21)

(22)

根據(jù)無窮積分的比較判別法和式(22)，有：

(23)

根據(jù)無窮級數(shù)的性質(zhì)，以及式(22)～(23)可得：

(24)

由條件1)可得：

備注： 在定理1中，條件1)可滿足.接下來討論參數(shù)δ的存在性.對任意X1和X2，有：

根據(jù)歐拉離散化，式(1)可改寫為如下差分形式：

Xi+1=Xi+hXi;Yi+1=Yi+h(-λYi+PΩ(Xi-?f1(Xi))-Xi)

(25)

根據(jù)定理1的結(jié)果和數(shù)值ODE理論[15]，當(dāng)h足夠小時(shí)，算法(25)將收斂于(Ⅱ)的最優(yōu)解.

3 非負(fù)矩陣分解算法

3.1 交替迭代算法描述

基于Matrix-IPNN，提出一個(gè)求解稀疏圖正則化NMF問題的交替迭代算法.

算法1 基于Matrix-IPNN交替迭代優(yōu)化稀疏圖正則化非負(fù)矩陣分解問題Output: W*∈Rm×r+, H*∈Rr×n+while iterε doInitialization: YH0=[0]r×n, i=0while i

3.2 交替迭代算法的收斂性

在問題(I)中約束是無界的，但可以很容易地給變量W和H加上一個(gè)較大的上界.此外，由于在一般情況下r<

定理2在問題(Ⅰ)中，為W和H增設(shè)上界UW和UH，并設(shè)W列滿秩和H行滿秩，則：

1) {(Wk,Hk)}至少存在一個(gè)聚點(diǎn)；

2) {(Wk,Hk)}的所有聚點(diǎn)都是偏最優(yōu)解，且其目標(biāo)函數(shù)值相同.

證明 首先，根據(jù)引理1可得0≤Wk≤UW及0≤Hk≤UH，因此序列{(Wk,Hk)}包含在一個(gè)緊集內(nèi).其次，子問題(Ⅱ)和問題(Ⅲ)可分別轉(zhuǎn)化為如下二次規(guī)劃的形式：

由W列滿秩和H行滿秩知WTW和HHT是正定的.結(jié)合L是半正定矩陣[16]可知，問題(Ⅱ)和(Ⅲ)是嚴(yán)格凸規(guī)劃，即問題(Ⅱ)和(Ⅲ)都有唯一解.根據(jù)文獻(xiàn)[13]的定理4.9可得結(jié)論.

根據(jù)雙凸綜述文獻(xiàn)的定理4.1[13]，可知問題(Ⅰ)的偏最優(yōu)解也是問題(Ⅰ)的駐點(diǎn).

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證該算法有效性，與利用投影神經(jīng)網(wǎng)絡(luò)求解非負(fù)矩陣分解算法(PN3MF)[14]、 圖正則化非負(fù)矩陣分解算法(GNMF)[8]、 混合非負(fù)矩陣分解算法(HNMF)[17]、 離散神經(jīng)動(dòng)力學(xué)算法(DTPNN)[18]等4種NMF算法進(jìn)行比較. 各算法的計(jì)算復(fù)雜度見表1.

表1 各算法的計(jì)算復(fù)雜度

表1中PN3MF復(fù)雜度中的t表示每次找步長時(shí)做Armijo不等式判斷的平均次數(shù). Matrix-IPNN含有內(nèi)循環(huán)，復(fù)雜度中的K表示內(nèi)循環(huán)的次數(shù).

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

這里主要討論上述5種算法在30 s內(nèi)的收斂速度. 矩陣V、W和H都是隨機(jī)生成的，介于0和1之間的數(shù). 令m=1 000，n=1 000，r=50，h=0.05，K=1 000，max_iter=3 000，α=0，β=0和λ=20，圖1展示了運(yùn)行時(shí)間跟目標(biāo)函數(shù)的關(guān)系. 根據(jù)圖1可知，在有限的時(shí)間內(nèi)Matrix-IPNN的目標(biāo)函數(shù)比其他幾個(gè)算法下降得更快.

圖1 收斂速度比較

4.2 非負(fù)矩陣分解算法在人臉識別的應(yīng)用

為說明所提的矩陣型慣性投影神經(jīng)網(wǎng)絡(luò)在人臉識別問題上的有效性，在不同的數(shù)據(jù)集上進(jìn)行數(shù)值實(shí)驗(yàn)，并給出詳細(xì)的實(shí)驗(yàn)結(jié)果.

4.2.1數(shù)據(jù)集

本實(shí)驗(yàn)使用兩個(gè)公開人臉圖像數(shù)據(jù)集： ORL數(shù)據(jù)集和Yale數(shù)據(jù)集. 數(shù)據(jù)集詳情如下：

1) ORL數(shù)據(jù)集. 包含40個(gè)人共400張灰度圖像, 每個(gè)人有10張圖像，尺寸為112 px×92 px.

2) Yale數(shù)據(jù)集. 包含15個(gè)人共165張灰度圖像, 每人11張圖像，尺寸為64 px×64 px.

圖2～3分別展示了ORL與Yale 數(shù)據(jù)集的部分人臉樣本. 在實(shí)驗(yàn)中，對兩個(gè)數(shù)據(jù)集都進(jìn)行隨機(jī)劃分，將每個(gè)人的4張灰度圖像用于訓(xùn)練，其余圖像用于測試.

圖2 ORL數(shù)據(jù)集示例圖像

圖3 Yale數(shù)據(jù)集示例圖像

4.2.2識別結(jié)果

假設(shè)B是測試集中圖像的總數(shù)，B1是被正確識別的圖像的數(shù)量，識別正確率[19]定義如下：

圖4的子圖(a)和(b)分別展示了各算法在ORL和Yale上的識別正確率隨著重構(gòu)空間維數(shù)r的變化.對于每個(gè)給定的r，在隨機(jī)劃分的訓(xùn)練集和測試集上執(zhí)行20次訓(xùn)練及測試. 實(shí)驗(yàn)中Matrix-IPNN的參數(shù)設(shè)置為h=0.05，K=1 000，max_iter=3 000，α=10，β=1，λ=20和ε=e-5.

圖4 ORL和Yale上各算法識別正確率的變化趨勢

在實(shí)驗(yàn)中，Matrix-IPNN算法的識別正確率始終可以保持較高水平. 實(shí)驗(yàn)結(jié)果說明Matrix-IPNN算法在人臉識別問題中是有效的.

5 結(jié)語

本研究通過擴(kuò)展向量型IPNN提出矩陣型IPNN，證明了矩陣型IPNN的穩(wěn)定性. 進(jìn)而提出基于矩陣型IPNN交替迭代求解NMF問題的算法，分析了時(shí)間復(fù)雜度和收斂性，將其應(yīng)用于人臉識別. 實(shí)驗(yàn)結(jié)果表明，與常見的NMF算法相比，提出的算法在識別正確率和速度上有明顯改進(jìn).