占善華，武繼剛，房小兆

(1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006; 2. 廣東司法警官職業(yè)學(xué)院 信息管理系， 廣東 廣州 510520)

0 引 言

近些年，學(xué)者們提出了大量的維度約簡方法。這些方法可簡單的分為3大類：有監(jiān)督、無監(jiān)督和半監(jiān)督方法[1,2]。有監(jiān)督和半監(jiān)督方法一般利用標(biāo)簽信息來指導(dǎo)轉(zhuǎn)換矩陣的學(xué)習(xí)[3,4]。而無監(jiān)督方法旨在不利用的任何標(biāo)簽信息的條件下自適應(yīng)地挖掘隱藏在數(shù)據(jù)中的信息來學(xué)習(xí)特征轉(zhuǎn)換矩陣[5-7]。線性鑒別分析(linear discriminant analysis，LDA)和主成分分析(principle component analysis，PCA)是最具代表性的有監(jiān)督和無監(jiān)督降維方法[5,8]。但這兩種方法不能發(fā)現(xiàn)數(shù)據(jù)的非線性結(jié)構(gòu)。

基于高維數(shù)據(jù)一般都分布于低維流行空間的假設(shè)，大量基于流行學(xué)習(xí)的方法被提出來用于解決非線性維度約簡問題。例如，局部保持投影(locality preserving projection，LPP)。近鄰保持嵌入(neighborhood preserving embedding，NPE)。但是，這兩種方法都對(duì)近鄰參數(shù)的選取較為敏感。為了克服這個(gè)問題，稀疏保持投影(sparsity preserving projection，SPP)被提了出來。但其缺點(diǎn)是圖構(gòu)建方法具有較大的運(yùn)算代價(jià)，限制了其在大尺度數(shù)據(jù)情形下的應(yīng)用[9]。為了克服這個(gè)缺陷，Yang等提出構(gòu)建L2-graph來代替L1-graph的非線性維度約簡方法，稱之為基于協(xié)同表示的投影學(xué)習(xí)(collaborative representation based projection，CRP)[9]。近年來，低秩表示受到了極大的關(guān)注[10]。Zhang等提出了一種低秩保持嵌入方法來應(yīng)對(duì)非線性維度約簡。Wong等基于低秩表示也提出了一種新穎和簡單的非線性維度約簡方法，稱之為低秩嵌入(low-rank embedding，LRE)[4]。與LRPE相比，LRE將投影學(xué)習(xí)和圖構(gòu)建融入到一個(gè)聯(lián)合框架，能夠?qū)W習(xí)到一個(gè)全局最優(yōu)投影矩陣。在文獻(xiàn)[11]中，低秩和稀疏被同時(shí)用于指導(dǎo)投影矩陣的學(xué)習(xí)。但是，因?yàn)檫@些方法在圖的構(gòu)建或投影矩陣的學(xué)習(xí)過程中均等地對(duì)待所有特征，這些方法對(duì)噪聲和離群點(diǎn)較為敏感。

針對(duì)上述問題，本文提出一種無監(jiān)督維度約簡方法，稱之為自適應(yīng)圖嵌入的魯棒稀疏局部保持投影(robust sparse locality preserving projection with adaptive graph embedding，RSLPP_AGE)。該方法旨在設(shè)計(jì)一個(gè)聯(lián)合優(yōu)化框架來自適應(yīng)獲得數(shù)據(jù)的全局最優(yōu)投影矩陣和仿射圖。該方法并不直接從原始高維數(shù)據(jù)中學(xué)習(xí)仿射圖，而是從更具鑒別性的低維表征數(shù)據(jù)中學(xué)習(xí)，使其對(duì)噪聲更具魯棒性。為了捕獲數(shù)據(jù)的全局結(jié)構(gòu)，引入了一個(gè)PCA約束性，使其能夠保持?jǐn)?shù)據(jù)的主要信息。為了進(jìn)一步提高對(duì)噪聲的魯棒性，在投影矩陣上引入了一個(gè)行稀疏約束，使其能夠自適應(yīng)地從復(fù)雜的高維數(shù)據(jù)中選擇最重要的特征來指導(dǎo)投影矩陣和仿射圖的學(xué)習(xí)。

1 局部保持投影

局部保持投影(LPP)是一種非常具有代表性的基于流行學(xué)習(xí)的維度約簡方法。對(duì)于訓(xùn)練集X=[x1,x2,…,xn]∈Rm×n，其中一列表示一個(gè)樣本，LPP首先從訓(xùn)練集中構(gòu)建近鄰圖W∈Rn×n，然后使用如下目標(biāo)函數(shù)來學(xué)習(xí)用于非線性降維的投影矩陣Q∈Rm×d

(1)

(2)

其中，ψ(xj)表示樣本第xj的k近鄰集合。

問題(2)是典型的特征值分解問題。從模型(2)中能夠發(fā)現(xiàn)，LPP能夠在維度約簡過程中保持?jǐn)?shù)據(jù)的近鄰結(jié)構(gòu)。

2 自適應(yīng)圖嵌入的魯棒稀疏局部保持投影

2.1 學(xué)習(xí)模型

如前所述，LPP能夠很好保持?jǐn)?shù)據(jù)的局部近鄰結(jié)構(gòu)。但是，其性能取決于所構(gòu)建的近鄰圖W的質(zhì)量。一般的，原始數(shù)據(jù)含有較多的冗余特征和噪聲，從原始數(shù)據(jù)中往往難以發(fā)現(xiàn)數(shù)據(jù)的本質(zhì)結(jié)構(gòu)。而在不精確的仿射圖上指導(dǎo)下，難以得到合理的投影矩陣Q。此外，LPP將投影矩陣學(xué)習(xí)和仿射圖學(xué)習(xí)分為兩個(gè)獨(dú)立的步驟，難以得到全局最優(yōu)的投影矩陣。LPP還忽略了數(shù)據(jù)的全局結(jié)構(gòu)，表明其并沒有充分利用數(shù)據(jù)的結(jié)構(gòu)信息來指導(dǎo)投影矩陣的學(xué)習(xí)，因此限制了其性能。基于此，本文提出了改進(jìn)方法。

首先，為了捕獲數(shù)據(jù)的全局結(jié)構(gòu)，我們將PCA約束項(xiàng)引入到LPP，并提出了如下學(xué)習(xí)模型

(3)

其中，X=PQTX+E是PCA的變體形式[3]，E∈Rm×n表示誤差或噪聲，λ2是一個(gè)正值懲罰項(xiàng)參數(shù)。引入PCA變體項(xiàng)使得方法能夠同時(shí)捕獲數(shù)據(jù)的全局和局部結(jié)構(gòu)信息。其次，原始高維數(shù)據(jù)可能含有大量冗余特征和噪聲，一種合理的模型應(yīng)該能夠自適應(yīng)地從中選擇更具鑒別力的特征來指導(dǎo)模型的訓(xùn)練?；诖耍疚姆椒ㄒ肓司哂刑卣鬟x擇能力的l2,1范數(shù)約束

(4)

最后，考慮到預(yù)定義的圖W并不能保證投影矩陣Q的全局最優(yōu)性，我們對(duì)模型(4)進(jìn)一步做如下改進(jìn)來學(xué)習(xí)全局最優(yōu)的投影矩陣

(5)

其中，λ1是正值懲罰項(xiàng)參數(shù)，用于平衡對(duì)應(yīng)項(xiàng)在模型訓(xùn)練中的作用。式(5)即為本文提出的學(xué)習(xí)模型。

2.2 模型優(yōu)化求解

問題(5)包含4個(gè)未知參數(shù)，難以求解。本節(jié)利用交替迭代方向乘子法來對(duì)其進(jìn)行優(yōu)化以得到其局部最優(yōu)解[10,11]。問題(5)的拉格朗日函數(shù)表示如下

(6)

其中，μ和C分別是懲罰項(xiàng)參數(shù)和拉格朗日乘子。各變量的優(yōu)化過程如下：

Q-Step：問題(5)關(guān)于變量Q的求解問題為

(7)

求L(Q)關(guān)于變量Q的偏導(dǎo)數(shù)，得到

(8)

(9)

P-Step：在固定其它未知變量時(shí)，變量P的優(yōu)化問題為

(10)

W-Step：關(guān)于變量W的優(yōu)化問題為

(11)

(12)

從式(12)中能夠發(fā)現(xiàn)，問題(12)關(guān)于變量W的各行是獨(dú)立的。通過逐行求解W，可得到其最優(yōu)解為[13,14]

(13)

E-Step：關(guān)于變量E的優(yōu)化問題為

(14)

上式是一個(gè)典型的稀疏約束求解問題，通過求解上式，能夠得到變量E的最優(yōu)解為

E=Ωλ2/μ(X-PQTX+C/μ)

(15)

其中，Ω表示收縮算子(shrinkage operator)。

μ和C-Step：這兩個(gè)變量的迭代方式表示如下

(16)

其中，μ0是常數(shù)。

RSLPP_AGE的優(yōu)化步驟總結(jié)如下：

算法1：RSLPP_AGE (solving (5))

Input:Training dataX,parametersλ1,λ2,andλ3, dimensiond.

Initialization: Exploiting PCA to initialize data reconstruction matrixP,Q=P,E=0,C=0,μ=0.01,ρ=1.1,μ0=105.

while not converged do

UpdateQby using (9)；

UpdatePby solving (10)；

UpdateWby using (13) and then implementW=max(W,0);

UpdateEby using (15)；

UpdateCandμby using (16).

end while

Output:Q

3 計(jì)算復(fù)雜度與收斂性分析

計(jì)算復(fù)雜度：本節(jié)并不考慮一些基本矩陣運(yùn)算的計(jì)算復(fù)雜度。事實(shí)上，算法1中僅含兩個(gè)具有高計(jì)算復(fù)雜度的運(yùn)算，即矩陣的逆運(yùn)算和SVD運(yùn)算。SVD運(yùn)算的計(jì)算復(fù)雜度為O(d3)；對(duì)于維度為m×m的矩陣，其逆運(yùn)算的計(jì)算復(fù)雜度為O(m3)[15,16]。因此，算法1中第Q和P的優(yōu)化步驟的計(jì)算復(fù)雜度為O(m3)和O(d3)。對(duì)于其它步驟而言，能夠發(fā)現(xiàn)它們并不包含復(fù)雜的運(yùn)算，因此可以忽略這些步驟的計(jì)算復(fù)雜度。根據(jù)以上分析，考慮到d?m，算法1總的計(jì)算復(fù)雜度為O(τm3)，其中τ表示算法的迭代步驟。

收斂性分析：如前所述，我們將一個(gè)復(fù)雜的非凸優(yōu)化問題轉(zhuǎn)換為了4個(gè)簡單的凸優(yōu)化問題，而我們又知道問題(5)的目標(biāo)函數(shù)值在迭代中單調(diào)下降，目標(biāo)函數(shù)值是有下界的。因此從問題(5)的單調(diào)性和有界性能夠得出結(jié)論，算法1的優(yōu)化過程能夠收斂到一個(gè)局部最優(yōu)解。

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

4.1 實(shí)驗(yàn)設(shè)置

數(shù)據(jù)集：Extended Yale B、CMU PIE和AR等3個(gè)人臉數(shù)據(jù)集和COIL20目標(biāo)數(shù)據(jù)集被選取用于評(píng)價(jià)所提出的方法的有效性。Extended Yale B數(shù)據(jù)集包含2414張正面人臉圖像，該數(shù)據(jù)庫中的人臉含有不同的光照變換，共含有38類，每類含有59張-64張圖像。CMU PIE人臉數(shù)據(jù)集含有11 554張圖像和68類，這些樣本從5個(gè)不同的角度下獲得。AR人臉數(shù)據(jù)集是一個(gè)比較具有難的人臉數(shù)據(jù)集，該數(shù)據(jù)集上含有大量不同人臉表情、光照和遮擋(眼鏡和圍巾遮擋)的人臉圖像。在本章，一個(gè)來自于120個(gè)類的含有3120張人臉圖像的子集被選擇用于測(cè)試。COIL20是一個(gè)比較流行的目標(biāo)數(shù)據(jù)集，該數(shù)據(jù)集含有1440張圖像和20個(gè)類。每一個(gè)目標(biāo)含有72張不同角度的目標(biāo)圖像。圖1展示了這些數(shù)據(jù)集的典型樣例圖像。

對(duì)于以上數(shù)據(jù)集，所有圖像都被統(tǒng)一縮放為32*32的尺寸，然后為了提高計(jì)算效率，我們進(jìn)一步使用PCA來降低特征維度，其中PCA降維率為98%，上述數(shù)據(jù)集降維后的特征維度尺寸分別為148，497，157和175[4]。

對(duì)比方法：本節(jié)與一些較為相關(guān)的方法進(jìn)行對(duì)比，包括經(jīng)典的NPE，SPP，PCA以及基于這些方法改進(jìn)的稀疏PCA(sparse PCA，SPCA)[17]，LPP正交LPP(orthogonal LPP，OLPP)[18]，CRP[9]，低秩保持投影(low-rank preserving projection，LRPP)[19]，LRE[4]和LRPE[20]。在以上這些方法中，LPP，OLPP，NPE，SPP和CRP可視為基于局部結(jié)構(gòu)信息的特征抽取方法。而其它方法都是基于全局和局部結(jié)構(gòu)信息的方法。

圖1 4種典型圖片數(shù)據(jù)集

參考文獻(xiàn)[7]的實(shí)驗(yàn)設(shè)置，在AR數(shù)據(jù)集上，我們從每類中隨機(jī)選取4,6,8和12個(gè)樣本作為訓(xùn)練樣本，然后將其它樣本作為測(cè)試樣本。對(duì)于其它數(shù)據(jù)集，我們從每類隨機(jī)選取10,15,20和25個(gè)樣本作為訓(xùn)練樣本，將其余的樣本作為測(cè)試樣本。我們將各種算法重復(fù)執(zhí)行20次，然后將它們的均值結(jié)果進(jìn)行對(duì)比。在這些數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果見表1-表4。

表1 各種方法應(yīng)用在Extended Yale B數(shù)據(jù)集上的平均分類準(zhǔn)確類對(duì)比

表2 各種方法應(yīng)用在CMU PIE數(shù)據(jù)集上的平均分類準(zhǔn)確類對(duì)比

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

表1-表4的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，與其它方法相比，所提出的RSLPP_AGE 在人臉分類和目標(biāo)分類任務(wù)上都獲得了最好的效果。此外，從這些表所列的對(duì)比結(jié)果還能發(fā)現(xiàn)：

(1)在人臉數(shù)據(jù)集上，即Extended Yale B，CMU PIE和AR數(shù)據(jù)集，基于流行學(xué)習(xí)的方法，如LPP，NPE，SPP，和CRP等獲得了優(yōu)于PCA的效果，然而，在COIL20數(shù)據(jù)集上，這些方法比PCA性能要差一些。這些實(shí)驗(yàn)結(jié)果表明人臉數(shù)據(jù)庫可能含有非線性的流行結(jié)構(gòu)，而基于流行學(xué)習(xí)的特征抽取方法在這些數(shù)據(jù)集上表現(xiàn)更好。

表3 各種方法應(yīng)用在AR數(shù)據(jù)集上的平均分類準(zhǔn)確類對(duì)比

表4 各種方法應(yīng)用在COIL20數(shù)據(jù)集上的平均分類準(zhǔn)確類對(duì)比

(2)在3個(gè)較為復(fù)雜的人臉數(shù)據(jù)集上，SPP，CRP，和LRPE獲得了優(yōu)于LPP和OLPP的性能。與LPP和OLPP相比，SPP、CRP和LRPE都利用了數(shù)據(jù)的表示結(jié)構(gòu)來指導(dǎo)模型的訓(xùn)練。因此在這些數(shù)據(jù)集上的對(duì)比結(jié)果表明了基于表示的方法對(duì)于諸如多種光照、表型和遮擋等噪聲情形更魯棒。

(3)在這4個(gè)數(shù)據(jù)集上，所提出的方法顯著優(yōu)于PCA和LPP，表明在特征抽取中捕獲數(shù)據(jù)局部結(jié)構(gòu)和流行結(jié)構(gòu)上的重要性。

5 結(jié)束語

本文提出了一種魯棒的維度約簡方法，與其它方法相比，通過將相似圖學(xué)習(xí)和投影學(xué)習(xí)融入到一個(gè)聯(lián)合優(yōu)化框架，能夠?qū)W習(xí)到全局最優(yōu)的投影矩陣。此外，我們的方法通過在更緊湊的低維表征空間學(xué)習(xí)相似圖，能夠發(fā)現(xiàn)數(shù)據(jù)最本質(zhì)的相似結(jié)構(gòu)。更重要的是，通過行稀疏范數(shù)的引入，本方法能夠在維度約簡過程中選擇最重要的特征，極大提高了對(duì)于噪聲的魯棒性。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了所提出方法的有效性。