自步稀疏最優均值主成分分析

許子微，陳秀宏

（江南大學 數字媒體學院，江蘇 無錫 214122）

降維[1]是數據分類中的一個重要問題，其目的是學習一個變換矩陣，將高維數據投影到低維子空間中，使數據在低維子空間中得到有效地分類。經典的降維方法包括主成分分析(principal component analysis, PCA)[2-3]和線性判別分析(linear discriminant analysis, LDA)[4-5]，其中PCA是一種將數據信息投影到正交線性空間的無監督方法，原始PCA在對數據降維時，以平方歐氏距離來表示損失，而歐氏距離對噪聲及異常值敏感。于是提出許多PCA變體來降低異常值的影響，例如 Nie等[6-7]提出非貪婪L1范數最大化的魯棒主成分分析(robust principal component analysis,RPCA)，和基于L2,1范數的最優均值主成分分析(optimal mean robust principal component analysis,OMRPCA)來同時學習最優變換矩陣和最優均值。但通過RPCA和OMRPCA等模型得到的低維子空間的每個新特征都是高維空間中所有原始特征的線性組合，由于存在冗余特征，通常不適合分類。Zou等[8]提出了稀疏主成分分析(sparse principal component analysis, SPCA)。然而，因為在每個變換向量上施加L1范數，故SPCA不能聯合地選擇重要特征；Yi等[9]提出了聯合稀疏主成分分析(joint sparse principal component analysis,JSPCA)，利用L2,1范數來表示損失項和正則項，在避免異常值影響的同時能聯合地選擇重要特征，從而增強算法的分類精度。

以上方法的每一個樣本對應一個損失值，損失值的大小決定了樣本對模型的貢獻，這就表明了樣本之間存在差異性，而這些方法均同等地對待所有訓練樣本，沒有考慮樣本之間的差異性。受人類/動物學習過程的啟發，文獻[10-11]提出了自定步長(或課程) (self-pace learning, SPL)學習理論，其主要思想是以自定步長方式來實現從“簡單”到“復雜”樣本的訓練，最終學習得到一個成熟的模型。此后，Lu等[12]提出自步課程學習(selfpaced curriculum learning, SPCL)同時考慮訓練前已知的先驗知識和訓練過程中的學習進度。Yu等[13]提出了自步學習K均值聚類(self-paced learning for k-means clustering algorithm, SPKC)，將自步學習機制用于聚類方法。Hu等[14]提出自步核聯合稀疏表示高光譜圖像分類(kernel joint sparse representation based on self-paced learning for hyperspectral image classification, SPKJSR)，將自步學習機制用于高光譜圖像分類。

本文為充分考慮樣本之間的差異性，利用SPL思想提出自步稀疏最優均值主成分分析(sparse optimal mean principal component analysis based on self-paced learning, SPL-OMSPCA)，該模型放寬了對投影矩陣的正交約束，通過對訓練樣本由“簡單”到“復雜”的漸進學習過程，得到最優投影矩陣和最優樣本均值。該方法能更好地獲得樣本中重要的特征信息，避免異常值的影響，提高了算法的魯棒性。在6個不同數據集上的實驗表明，SPL-OMSPCA算法優于目前最先進的主成分分析方法。

1 相關工作

給定訓練樣本為X=[x1x2···xn]∈Rm×n，其中m為原始圖像的空間維數，n為訓練樣本的個數。

1.1 PCA模型

假設訓練樣本X已經中心化，即均值為零，則通常的PCA可以表示為

式中W為投影矩陣。該問題的最優解W的列對應于矩陣的前m個最大特征值對應的特征向量。

基于L2范數的均值的合理性只針對傳統的PCA方法，泛化能力較差，于是考慮以下最優均值PCA模型(OMPCA)：

若式(1)中的投影矩陣與恢復矩陣不相同，并以L2,1范數來表示損失函數以及稀疏正則化項，則有以下聯合稀疏主成分分析(JSPCA)模型：

式中：Q∈Rm×d是投影矩陣；P∈Rm×d為恢復矩陣。

1.2 自步學習(SPL)機制

受人類/動物學習過程的啟發，SPL以自定步長的方式實現從“簡單樣本”到“復雜樣本”迭代地訓練模型。其優化模型為

式中：α 為稀疏正則化控制參數；k是自步學習參數；變量vi用于決定選擇哪些樣本參與訓練模型；L(yi,g(xi,w))是樣本的損失函數，損失值的大小決定樣本的難易程度；f(vi,k) 是自步正則化函數。在算法迭代過程中，模型可以根據樣本難易程度，從簡單的樣本開始，學習到復雜的樣本。自步學習機制的有效性，特別是對高度損壞的數據的魯棒性，已經在各種計算機視覺任務中得到了驗證。

2 自步稀疏最優均值主成分分析模型(SPL-OMSPCA)

2.1 模型建立

SPL-OMSPCA的基本思想是：以L2,1范數表示損失函數和稀疏約束，并利用自步學習方案對參與訓練的樣本進行選擇。其中，損失函數是訓練樣本從低維變換空間中恢復原始數據產生的誤差，且包含需優化的均值向量。于是有以下優化模型：

式中：xi為第i個樣本；α 為稀疏正則化控制參數；k為自步控制參數；變量vi用于決定選擇哪些樣本參與訓練；b∈Rm×1是樣本均值；Q∈Rm×d是投影矩陣；P∈Rm×d是恢復矩陣且服從正交約束PTP=I。式(2)用損失值的大小決定樣本的難易程度。

上述方法是硬性閾值權值選擇方法，通過給每個樣本分配二元權值 (vi∈[0,1]) 來決定是否選擇樣本。但異常值在所有樣本中分布不均勻，所以硬性正則函數不能確定是否選擇這些樣本。相比于硬性閾值權值，軟權值給每個樣本分配0～1(包括0和1)的權值，顯示了樣本的潛在重要性，更好地實現了從簡單樣本逐步學習到復雜樣本的過程。所提最終優化算法為

式中 β 是間隔控制參數，控制0～1的模糊區間。因此軟閾值權值可以通過明確樣本間差異，準確選擇樣本，進一步避免異常值的影響。另外，這里存在一個隱形變量 μ (μ>1)，用來作為自步控制參數k減小的步長。目標函數式(3)轉化為

式中：V=diag(v1,v2,···,vn)；1 是全為1的列向量；對角矩陣D=diag(d11,d22,···,dnn) 的對角元素定義為

式中：A=X?b1T；i(i=1,2,···,n) 表示矩陣的第i列；對角矩陣H=diag(h11,h22,···,hmm) 的對角元素定義為

式中：j(j=1,2,···,m) 表示矩陣的第j行；δ 為一個很小的數。

2.2 模型求解

因為式(4)含有P、Q、b及v共4個變量，直接求解非常困難，所以本文使用交替迭代求解[15]的方法，分別求得自步學習權重v、最優投影矩陣Q、最優均值b以及恢復矩陣P。

2.2.1 固定P、Q、b求 自步學習權重v

當P、Q和b固定時，式(4)轉化為

令Li=||xi?b?PQT(xi?b)||2，則上式可表示為

式(7)的目標函數關于vi求偏導并令其為0得vi的解

2.2.2 固定P、Q、v求 解最優均值b

當固定P、Q和v時，式(4)轉化為

式(9)的目標函數關于b求偏導并令其為零，得到

c=(b1T?X)VD1

令 ，則式(10)轉化為

若I?PQT?QPT+QQT為非奇異的，則式(11)的解為c=0，從而有

若I?PQT?QPT+QQT為奇異的，設其奇異值分解為E1W1U1T, 其 中W1=diag(σ1,σ2,···,σs,0,···,0),σ1≥σ2≥···≥σs>0，則式(11)的解為

c=U1z

其中z=[0,···,0,zs+1,···,zm]T∈Rm為任意的。特別地，如令zs+1=1，zs+2=···=zm=0，則式(11)的一個特解為U1的第s+1列，即c=(U1)s+1，從而有

2.2.3 固定P、v、b求 解投影矩陣Q

固定P、v、b后，式(4)轉化為

式(15)的目標函數關于Q求偏導，并令其為0得

從而有

2.2.4 固定Q、v、b求 解恢復矩陣P

固定Q、v、b后，式(4)轉化為

或等價形式為

約束條件PTP=I意味著P是列正交矩陣。設 (X?b1T)VD(X?b1T)TQ的奇異值分解為E2W2U2T，則由文獻[9]中定理知，式(17)的最優解為

以上過程不斷迭代,直到收斂條件滿足為止，具體算法如算法1。

算法1 SPL-OMSPCA

輸入 樣本X，維度d，參數k、α、β 和步長 μ；

輸出 投影矩陣Q。

迭代執行以下操作，直到模型收斂：

1)通過式(8)計算v；

2)通過式(12)、(13)計算b；

3)通過式(16)計算Q；

4)通過式(18)計算P；

5)通過式(5)計算D；

6)通過式(6)計算H；

7) 更新k：k=k/μ。得到投影矩陣Q之后，運用最近鄰分類器(nearest neighbor classifier, NN)進行分類：

式中：c為測試樣本y的預測標簽；ci為第i個樣本的類標簽。

在算法1中，主要的計算復雜度為奇異值分解和矩陣求逆，故本算法時間復雜度最高為O(m3)，假設算法迭代T次，則該部分的時間復雜度為O(Tm3) ， 從而整個算法的時間復雜度為O(Tm3)。

3 實驗

為評估SPL-OMSPCA算法的有效性，本文將在UMIST[16]、JAFFE[17]、AR[18]、BIO[19]、COIL20[20]及MNIST[21]數據集上進行測試，每次實驗獨立隨機，重復20次取平均識別率和標準差作為最后實驗結果，并與PCA、SPCA、OMRPCA和JSPCA算法作對比。

3.1 數據集

為測試SPL-OMSPCA對異常值的魯棒性，將UMIST數據集的每個圖像隨機添加 1 3×13 的塊遮擋；隨機抽取JAFFE數據集50%的圖像添加13×13塊遮擋，而對AR、BIO、COIL20和MNIST數據集隨機添加10%的椒鹽噪聲。各數據集的具體特征如表1所示，而各數據集的部分圖像如圖1。

表1 不同數據集的屬性及特點Table 1 Attributes and characteristics of different datasets

圖1 部分含噪數據集的可視化Fig.1 Visualization of some datasets with noise

3.2 實驗結果及分析

在各數據集的每類中隨機選取L張圖像作為訓練樣本，其余作為測試樣本。圖2給出了每個算法對不同數據集，在不同子空間維度上的分類精度。對UMIST、JAFFE和COIL20數據集，分別取9、10和5，則由圖2(a)、(b)和(e)可看出，SPL-OMSPCA整體優于其他對比算法；對AR數據集，取13，由圖2(c)可知，SPL-OMSPCA明顯優于OMRPCA和SPCA，而略優于其他算法；對BIO和MNIST數據集，分別選取20和10，由圖2(d)與2(f)可以看出，由于此類數據集中的樣本較為相似，當子空間維數較低時，SPL-OMSPCA與其他對比算法幾乎保持一致的精度，但隨著子空間維數的增加，本文算法精度持續保持平穩狀態，且明顯優于其他算法。表2列出了不同訓練樣本數下，5種算法在不同數據集上的分類精度與標準差，表中數據為子空間維數從5～100變化時，每個算法取得的最高精度，其中黑色加粗字體表示訓練樣本相同時，同一設置下幾種算法中的最高分類精度。

表2 在6個不同噪聲數據集上各種PCA算法的分類精度及其標準差Table 2 Average classification accuracy and standard deviation of various PCA algorithm on six data sets with different noise training samples

圖2 不同算法在6個數據集上不同子空間維度的分類精度Fig.2 Classification accuracies of different algorithm in different subspace dimensions on six datasets

為進一步證明實驗的合理性，選取JAFFE和COIL20數據集，L分別取10和9，子空間維度取10。SPL-OMSPCA模型中，每一次迭代中更新均值，圖3展示了2個數據集從1 024個特征中隨機抽取的10個特征的均值變化，由圖3可看出均值隨迭代次數增加逐漸趨于平穩。模型考慮樣本自身差異性，引入自步學習機制，利用損失值判斷樣本的難易程度，賦予樣本軟權重vi，并且放寬對投影矩陣的正交約束，以L2,1范數來表示損失函數和稀疏約束，由此即使對于有噪聲的樣本，也能極大程度地進行重構，圖4展示了對于隨機添加50%塊噪聲的JAFFE數據集，5種算法得到的部分重構圖像，明顯SPL-OMSPCA模型對含噪聲塊圖像的重構更好。表3展示了迭代過程中JAFFE數據集部分樣本的vi的變化情況，其中一行表示一個樣本的變化。從表3可看出，隨迭代次數的增加，對損失值大小的限制逐漸放寬，實現從“簡單樣本”到“復雜樣本”的學習。此外，圖5給出了算法在UMIST和JAFFE上的收斂情況，其中，訓練樣本數L分別為9、10，子空間維數為100，最大迭代次數為30。由圖5可見，本文所提出的算法具有收斂性。

圖3 均值變化圖Fig.3 Graph of the mean value

圖4 不同算法對部分JAFFE數據集的重構圖像Fig.4 Reconstructed images of partial JAFFE datasets by different algorithms

圖5 目標函數收斂圖Fig.5 Convergence graph of objective value

綜上所述，SPL-OMSPCA模型對噪聲樣本具有更高的魯棒性，且能取得比其他算法更高的識別率。

3.3 參數設置

由式(3)提出的問題可知，參數k和 β 的值決定了學習過程中樣本的選取，故選擇合適的參數可以提升算法的分類效果。假設初始訓練時最大損失為Lm， 由式(3)取適當的k和 β 滿足：

為簡化計算，令k=1/β，則有

對步長參數 μ 和稀疏正則化控制參數 α 將通過實驗確定，由圖6可見，SPL-OMSPCA算法在不同參數組合下得到不同分類效果。具體地，UMIST數據集上L=9 時，在(α,μ)=(0.001,1.25)處可取得最高精度；JAFFE數據集上L=10 時，在(α,μ)=(10,1.15)處取得最高精度；AR數據集上L=13 時，在 ( α,μ)=(0.01,1.15) 處取得最高精度；BIO數據集上L=20 時，在 ( α,μ)=(1000,1.1) 時取得最高精度；COIL20數據集上L=5 時，(α,μ)=(1000,1.15)時取得最高精度；MNIST數據集上L=20 時，在 ( α,μ)=(1000,1.15) 取到最高精度。

圖6 不同參數上的分類精度Fig.6 Classification accuracy on different parameters

4 結束語

本文提出了一種新的無監督降維算法?自步稀疏最優均值主成分分析(SPL-OMSPCA)算法。基于對樣本自身差異性的考慮，引入自步學習的思想，實現樣本從“簡單”到“復雜”的訓練，且在迭代過程中，自動更新均值，而后通過對投影矩陣添加L2,1范數的行稀疏約束，一致選擇樣本，進一步提高算法的識別精度。理論分析和實驗結果都證明了SPL-OMSPCA模型的分類優勢。雖然SPL-OMSPCA的性能優于其他PCA方法，但它還是一種無監督方法，不能使用類標簽來提取有區別的特征，因此它還不能提取最有效的分類特征。在未來，可將之擴展到半監督分類問題。