自適應圖嵌入的魯棒稀疏局部保持投影

占善華，武繼剛，房小兆

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

0 引 言

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

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

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

1 局部保持投影

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

(1)

(2)

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

問題(2)是典型的特征值分解問題。從模型(2)中能夠發現，LPP能夠在維度約簡過程中保持數據的近鄰結構。

2 自適應圖嵌入的魯棒稀疏局部保持投影

2.1 學習模型

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

首先，為了捕獲數據的全局結構，我們將PCA約束項引入到LPP，并提出了如下學習模型

(3)

其中，X=PQTX+E是PCA的變體形式[3]，E∈Rm×n表示誤差或噪聲，λ2是一個正值懲罰項參數。引入PCA變體項使得方法能夠同時捕獲數據的全局和局部結構信息。其次，原始高維數據可能含有大量冗余特征和噪聲，一種合理的模型應該能夠自適應地從中選擇更具鑒別力的特征來指導模型的訓練。基于此，本文方法引入了具有特征選擇能力的l2,1范數約束

(4)

最后，考慮到預定義的圖W并不能保證投影矩陣Q的全局最優性，我們對模型(4)進一步做如下改進來學習全局最優的投影矩陣

(5)

其中，λ1是正值懲罰項參數，用于平衡對應項在模型訓練中的作用。式(5)即為本文提出的學習模型。

2.2 模型優化求解

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

(6)

其中，μ和C分別是懲罰項參數和拉格朗日乘子。各變量的優化過程如下：

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

(7)

求L(Q)關于變量Q的偏導數，得到

(8)

(9)

P-Step：在固定其它未知變量時，變量P的優化問題為

(10)

W-Step：關于變量W的優化問題為

(11)

(12)

從式(12)中能夠發現，問題(12)關于變量W的各行是獨立的。通過逐行求解W，可得到其最優解為[13,14]

(13)

E-Step：關于變量E的優化問題為

(14)

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

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

(15)

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

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

(16)

其中，μ0是常數。

RSLPP_AGE的優化步驟總結如下：

算法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 計算復雜度與收斂性分析

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

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

4 實驗結果與分析

4.1 實驗設置

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

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

對比方法：本節與一些較為相關的方法進行對比，包括經典的NPE，SPP，PCA以及基于這些方法改進的稀疏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可視為基于局部結構信息的特征抽取方法。而其它方法都是基于全局和局部結構信息的方法。

圖1 4種典型圖片數據集

參考文獻[7]的實驗設置，在AR數據集上，我們從每類中隨機選取4,6,8和12個樣本作為訓練樣本，然后將其它樣本作為測試樣本。對于其它數據集，我們從每類隨機選取10,15,20和25個樣本作為訓練樣本，將其余的樣本作為測試樣本。我們將各種算法重復執行20次，然后將它們的均值結果進行對比。在這些數據集上的實驗結果見表1-表4。

表1 各種方法應用在Extended Yale B數據集上的平均分類準確類對比

表2 各種方法應用在CMU PIE數據集上的平均分類準確類對比

4.2 實驗結果分析

表1-表4的實驗結果可以發現，與其它方法相比，所提出的RSLPP_AGE 在人臉分類和目標分類任務上都獲得了最好的效果。此外，從這些表所列的對比結果還能發現：

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

表3 各種方法應用在AR數據集上的平均分類準確類對比

表4 各種方法應用在COIL20數據集上的平均分類準確類對比

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

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

5 結束語

本文提出了一種魯棒的維度約簡方法，與其它方法相比，通過將相似圖學習和投影學習融入到一個聯合優化框架，能夠學習到全局最優的投影矩陣。此外，我們的方法通過在更緊湊的低維表征空間學習相似圖，能夠發現數據最本質的相似結構。更重要的是，通過行稀疏范數的引入，本方法能夠在維度約簡過程中選擇最重要的特征，極大提高了對于噪聲的魯棒性。在多個數據集上的實驗驗證了所提出方法的有效性。