任維雅，李國輝

(國防科技大學 信息系統(tǒng)與管理學院， 湖南 長沙　410073)

?

面向監(jiān)督學習的稀疏平滑嶺回歸方法*

任維雅，李國輝

(國防科技大學 信息系統(tǒng)與管理學院， 湖南 長沙410073)

摘要：嶺回歸是監(jiān)督學習中的一個重要方法，被廣泛用于多目標分類和識別。嶺回歸中一個重要的步驟是定義一個特殊的多變量標簽矩陣，以實現對多類別樣本的編碼。通過將嶺回歸看作是一種基于圖的監(jiān)督學習方法，拓展了標簽矩陣的構造方法。在嶺回歸的基礎之上，進一步考慮投影中維度的平滑性和投影矩陣的稀疏性，提出稀疏平滑嶺回歸方法。對比一系列經典的監(jiān)督線性分類算法，發(fā)現稀疏平滑嶺回歸在多個數據集上有著更好的表現。另外，實驗表明新的標簽矩陣構造方法不會降低原始嶺回歸方法的表現，同時還可以進一步提升稀疏平滑嶺回歸方法的性能。

關鍵詞：嶺回歸；多分類；全局維度平滑性；監(jiān)督學習

監(jiān)督學習是機器學習和模式識別中一個重要的學習內容，被應用于包括人臉識別、文本識別及圖像分類等諸多領域。在大數據應用需求的背景下，監(jiān)督學習面臨兩個重要問題：一是提高分類器的分類準確率問題；二是能夠給出對新樣本的顯式映射，即解決“out-of-sample”問題。

為解決以上兩個問題，近年來涌現出一系列基于線性投影的機器學習方法。這些方法包括：基于流形學習的方法，如局部保持投影(Locality Preserving Projections，LPP)[1]和鄰域保持嵌入(Neighborhood Preserving Embedded，NPE)[2]等；度量學習(metric learning)方法，如KISS(Keep It Simple and Straightforward)方法[3]、最大邊界近鄰學習(Large Margin Nearest Neighbor learning，LMNN)[4]和信息論度量學習(Information Theoretic Metric Learning，ITML)[5]等；其他一些著名的機器學習方法，如線性判別分析(Linear Discriminant Analysis，LDA)[6-7]、局部敏感判別分析(Locality Sensitive Discriminant Analysis，LSDA)[8]和間隔判別分析(Marginal Fisher Analysis，MFA)[9]等。

嶺回歸(Ridge Regression,RR)方法[10-13]是一種利用正則化的最小二乘法方法，最早只設計了單變量標簽[11-13]。文獻[10]推廣了原始嶺回歸方法，將單變量標簽擴展成多變量標簽，以解決多分類問題。嶺回歸方法[10]是一種監(jiān)督學習方法，由于其出色的學習性能，目前正受到越來越為廣泛的關注。它主要包括以下步驟：①生成訓練樣本點的多變量標簽矩陣；②學習線性分類器，即投影矩陣；③對新樣本進行分類識別。

文獻[10]指出嶺回歸的多變量標簽矩陣方法是特定的。然而，通過將嶺回歸學習方法納入基于圖(graph-based)的監(jiān)督學習方法，發(fā)現多變量標簽矩陣的構造方法是可以靈活設定的，學習投影矩陣的稀疏性往往是一個優(yōu)良投影矩陣必備的潛在特征。因此在嶺回歸學習方法中引入投影矩陣的稀疏性約束就得到稀疏平滑嶺回歸方法。

1嶺回歸

嶺回歸方法[10]使用正則單形頂點(regular simplex vertices)[14]作為訓練樣本的多變量標簽，將高維特征空間映射到低維特征空間，并使樣本投影到這些正則單形頂點的周圍。記訓練樣本為X=[x1,…,xn]∈Rm×n，對應標簽為L=[l1,…,ln]，其中l(wèi)i∈{1,2,…,k}，代表訓練樣本共有k個類別。

記Ti∈Rk-1(i=1,2,…,k)為一個正則k單形的頂點，T=[T1,T2,…,Tk]∈R(k-1)×k。T構造方法如下：

1)T1=[1,0,…,0]T且T1,i=-1/(k-1),i=2,…,k。

2)當1≤g≤k-2，有

Ti,g+1=0,g+2≤i≤k-1。

這k個頂點分布在以原點為圓心的超球面上，是k-1維空間中最平衡和對稱的分隔點，任意兩點之間的距離相等。

嶺回歸方法最小化如式(1)所示的目標函數：

(1)

直接求導可得：

P=(XXT+λ1I)-1XY

(2)

式中，I為單位矩陣。

2多變量標簽矩陣

嶺回歸方法實質上是一種基于圖的監(jiān)督線性學習方法，在此基礎之上，可以拓展多變量標簽矩陣的構造方法。首先考察兩個經典的基于圖的線性投影算法：局部保持投影LPP[1]和鄰域保持嵌入NPE[2]。LPP和NPE優(yōu)化如式(3)所示的目標函數：

(3)

如果認為具有相同標簽的樣本是相互相似的，則嶺回歸學習方法符合基于圖的學習方法對于相似樣本的約束。實際上，觀察式(1)，可以發(fā)現嶺回歸的標簽矩陣約束了相同標簽的樣本在投影后的距離，使之趨于接近。另外，不同于LPP和NPP方法，嶺回歸方法通過標簽矩陣的約束避免了解的病態(tài)性問題。在LPP和NPP方法中，如果沒有正交約束，不同標簽的樣本在投影后的距離將趨于無窮大；而在嶺回歸方法中，標簽矩陣的約束使得不同標簽的樣本在投影后的距離將趨于一個固定間隔。

因此，嶺回歸的多變量標簽矩陣只要滿足以上對同標簽樣本的約束和不同標簽樣本的約束，即可納入為基于圖的監(jiān)督學習方法。在基于圖的監(jiān)督學習方法的框架下，嶺回歸的多變量標簽矩陣可以通過如下方法構造：

記多變量標簽矩陣Y∈Rn×d(d是樣本投影后的新維度大小)。嶺回歸方法[10]使用正則單形頂點，且d=k-1。這種構造方法較為嚴格，實際上，只需在d維空間中構造k個相互正交、長度為1的頂點就可以滿足基于圖的學習方法的要求。d的大小是可以定義的，這意味著投影后樣本的維度也是可以預先定義的。

標簽矩陣的具體構造步驟為：

1)在d維空間中構造k個相互正交、長度為1的頂點，記為T=[T1,T2,…,Tk]∈Rd×k。

根據上述步驟，提出兩種構造T的方法：

1)構造方法1：當i=j時，Tij=1，否則Tij=0。要求d≥k，通常可取d=k。

2)構造方法2：在d維空間中生成k個隨機頂點，使用施密特正交化方法生成k個新頂點，以構造T。

構造方法1最直觀簡單，構造方法2可以控制維度。在第五節(jié)中將給出不同構造方法對嶺回歸多分類識別率的影響。

3稀疏平滑嶺回歸

將所有樣本點在維度上的坐標記為一個維度點d(i)(X的第i行)，可以使用多種權重[15]度量方法度量其相似性。使用核權重對它們的相似性進行衡量，即如果點d(i)是點d(j)(i≠j)s個最近點之一或點d(j)是點d(i)的s個最近點之一，則：

(4)

將這個假設稱為全局維度平滑性假設，其數學的表示為最小化如式(5)所示的正則化項：

=trace(PTDP)-trace(PTWP)

=trace(PTLP)

(5)

考慮正則化項R，嶺回歸最小化目標變?yōu)椋?/p>

(6)

式中，λ1λ2>0是平衡各正則化項的參數。

比起大多線性學習方法，經典的KISS度量學習方法和MFA方法學習得到的投影矩陣往往具有較好的稀疏性，較好的稀疏度有利于提高投影的魯棒性，提高模型的泛化能力。因此，進一步對嶺回歸投影矩陣增加稀疏度要求，式(6)變?yōu)樽钚』缡?7)所示的目標函數：

(7)

將解決式(7)所示問題(問題(7))的方法稱為稀疏平滑嶺回歸(Sparse smooth Ridge Regression，SRR)方法。

4算法實現

通過變量分別優(yōu)化的方法解決問題(7)，即通過固定其他參數求解某一個參數。采用Inexact ALM[16](augmented Lagrange multiplier)方法，通過一個附屬變量拆分目標函數的變量，式(7)可以重寫為：

(8)

式(8)的拉格朗日函數為：

(9)

式中，Q是拉格朗日乘子，μ≥0是懲罰參數。

固定其他變量，求P：

(10)

于是，

(11)

固定其他變量，求H：

(12)

其中,Θβ(x)=sign(x)max(|x|-β,0)是軟閾值操作子[17]，且有：

(13)

通過Inexact ALM[16]方法解決問題(7)的完整算法見算法1。

算法1　解決問題(7)的完整算法

5實驗

本節(jié)面向監(jiān)督學習進行多分類實驗，通過對測試樣本的識別準確率來衡量不同算法的水平。實驗用的線性投影方法共8種，包括：LPP、NPE、KISS、LSDA、MFA、LDA、RR、SRR。同時，實驗分析了不同標簽矩陣對嶺回歸方法的影響。數據集包括圖像數據集、人臉數據集、手寫體數據集和文本數據集，表1給出了4個數據集的統(tǒng)計指標，圖1展示了一些數據集的原始圖像示例。

表1　4個數據集的統(tǒng)計指標

5.1　數據集

1)COIL20數據集。COIL20數據集[18]包括20個類別圖像，每類圖像包含72張不同視角的圖像。每張圖像降采樣后的大小是32×32像素，被表示為一個1024維的向量。

2)Yale數據集。Yale數據集[19]包含15個人物，共165張灰度照片。每個人物有11張表情和外形不同的照片，每張圖片降采樣后的大小是32×32像素，由一個1024維的向量表示。

3)TDT2數據集。TDT2數據集[20]是一個文本數據集，包括9394個文本文件。每個文本文件被一個36771維的向量表示。樣本點最多的前15類數據的各自前50個樣本點作為實驗數據集使用。

4)USPS數據集。USPS數據集[21]是一個手寫體數據集，包括9298張圖片，來自10個類別。每張圖片大小為16×16像素，由一個256維的向量表示。

通常可采用主成分分析(Principal Component Analysis,PCA)將數據先降維至一個合適的維數以提高運算效率。另外，數據的預處理方法是對數據進行平方和歸一化操作。

5.2　實驗流程

5.2.1監(jiān)督分類學習實驗

選擇一個數據集，確定在每類樣本中要挑選的訓練樣本個數NL，實驗流程如下：

1)在每類樣本中隨機選擇NL個樣本組成訓練集，余下樣本作為測試集；

2)用不同方法學習線性投影矩陣；

3)對測試集樣本進行投影；

4)通過最近鄰方法(1-NN)確定測試樣本的預測標簽，計算每類方法在測試樣本上的識別準確率；

5)重復以上流程50次。

5.2.2標簽矩陣實驗

構造5個不同的標簽矩陣，對比這些標簽矩陣對RR和SRR方法的影響。這些標簽矩陣包括：

(a)COIL20　　　　　　　　　　　(b)Yale

(c) USPS圖1　COIL20,YaleB和USPS數據庫上的圖片示例Fig.1　Sample images in COIL20, Yale and USPS database

1)Y1：原始嶺回歸構造法[10]。

2)Y2：使用第2節(jié)的構造法1，取d=k(d是構造頂點T的維度，k是樣本類別數目)。Y2是一個0-1矩陣，每行只有一個1，其余為0。

3)Y3：通過T構造法2構建標簽矩陣，令d=2k。

4)Y4：使用T構造法2，令d=3k。

5)Y5：使用T構造法2，令d=m。其中，m是樣本數據X的原始維度。

5.3　實驗結果

多分類實驗結果如表2～5所示。SRR方法在實驗數據集上表現良好，特別在TDT2文本數據庫和COIL20圖像數據庫上表現優(yōu)異。觀察USPS數據庫和Yale數據庫，如表2、表3所示，當訓練集數目逐漸增加時，部分經典方法識別效果反而下降，這可能是因為訓練出現了過擬合現象。與此同時，SRR方法依然表現良好，體現出較好的泛化能力。

在標簽矩陣實驗中(見表6)，標簽矩陣并沒有降低RR方法的識別率，這說明將嶺回歸方法看作是一種基于圖的學習方法并由此設計標簽矩陣是合理的。這意味著標簽矩陣的作用是盡量使投影后的樣本同類聚集，異類等距分隔。另外，設計的標簽矩陣在SRR方法上比原始標簽矩陣有一定的提升，這驗證了拓展標簽矩陣設計的價值。

表2　不同方法在USPS數據集上的識別率

表3　不同方法在Yale數據集上的識別率

表4　不同方法在COIL20數據集上的識別率

表5　不同方法在TDT2數據集上的識別率

表6　使用不同標簽矩陣的嶺回歸方法在各數據集上的識別率(NL=5)

5.4　算法分析

參數選擇是一項重要的工作，文中所使用的對比方法采用其文獻所提議的最佳參數。對于SRR方法，可通過有限網格法[22]選擇參數。實驗采取的參數為：對于USPS，TDT2和Yale數據庫，λ1=0.01，λ2=0.01，λ3=0.01；對于COIL20數據庫，λ1=0.001，λ2=0.01，λ3=0.1。使用核權重(式(4))來度量維度間的相似度，所有實驗取s=5。簡單起見，文中使用Y2作為SRR的標簽矩陣。

分析表示投影矩陣P的稀疏度，投影矩陣的稀疏度可定義如式(14)：

(14)

式中，行向量P(i)的稀疏度sparsity(P(i))可由向量稀疏度[23]計算得到：

(15)

式中，Pij是P(i)的第j個元素。

當一個向量所有值相同時，其稀疏度則為0%，當一個向量只有一個元素不為0時，其稀疏度達到最大，取值為100%。

表7為不同算法得到的投影矩陣的平均稀疏度。由表可看出，SRR方法得到的投影矩陣比RR和其他大多對比方法得到的投影矩陣具有更高的稀疏度。KISS度量學習方法往往可以得到具有最大稀疏度的投影矩陣。對比表2～5和表7，發(fā)現投影矩陣稀疏性的提高往往帶來識別率上的提升。KISS方法要求相似樣本盡量聚集，其對異類樣本間的距離沒有約束，這可能是其投影矩陣稀疏性高但其識別率不如SRR方法的原因。

表7　不同算法得到的投影矩陣的平均稀疏度(NL=5)

5.5　稀疏約束拓展

投影矩陣的稀疏性對算法性能有著一定的影響，除了約束外，還可以考察如式(16)所示的正則化項：

(16)

(17)

(18)

求解式(17)和式(18)可參考求解式(7)的算法，相應地，只需將式(12)分別替換為式(19)、式(20)。

(19)

(20)

其中，Γ是l2,1范數(行稀疏)操作子(參照文獻[28]的列稀疏操作子)，Ω是l1/2,1，范數操作子[27]。

表8中列出了SRR系列算法在不同數據庫上所達到的識別率和對應的參數值λi(i=1,2,3)，其中，參數選擇是通過有限網格法[22]進行的，網格值為{0.0001, 0.001, 0.01, 0.1, 1, 10}。就識別率而言，SRR_1，SRR_2和SRR_3表現相近，總體來說，SRR_2表現最好，SRR_1次之，SRR_3最差。

6結論

擴展了嶺回歸方法中多變量標簽矩陣的構造方法，使同類樣本在投影后相互聚集，使類別不相同的樣本在投影后實現固定間隔分割。通過投影過程中對維度操作的分析，得出全局維度平滑性，同時引入投影矩陣的稀疏性，拓展了RR方法，形成SRR方法。實驗分析表明：SRR方法在多個數據集上具有良好的表現，其投影矩陣具有良好的稀疏性，另外，新的標簽矩陣構造方法可以進一步提高SRR方法的性能。

表8　不同稀疏約束的SRR方法在4個數據集上的識別率

參考文獻(References)

[1]He X F, Niyogi P.Locality preserving projections[J]. Advances in Neural Information Processing Systems, 2004, 16:153-160.

[2]He X F, Cai D, Yan S C, et al. Neighborhood preserving embedding[C]//Proceedings of IEEE International Conference on Computer Vision, 2005:1208-1213.

[3]Koestinger M, Hirzer M, Wohlhart P, et al. Large scale metric learning from equivalence constraints[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition, 2012:2288-2295.

[4]Weinberger K Q, Saul L K. Fast solvers and efficient implementations for distance metric learning[C]//Proceedings of the 25th International Conference on Machine Learning, 2008:1160-1167.

[5]Davis J V, Kulis B, Jain P, et al. Information-theoretic metric learning[C]//Proceedings of the 24th International Conference on Machine Learning, 2007:209-216.

[6]Lu J W, Plataniotis K N, Venetsanopoulos A N. Face recognition using LDA-based algorithms[J]. IEEE Transactions on Neural Networks, 2003, 14(1):195-200.

[7]Welling M. Fisher linear discriminant analysis[J]. Department of Computer Science, 2008, 16(94):237-280.

[8]Cai D, He X F, Zhou K, et al. Locality sensitive discriminant analysis[C]//Proceedings of the 20th International Joint Conference on Artifical Intelligence, 2007:708-713.

[9]Xu D, Yan S C, Tao D C, et al. Marginal fisher analysis and its variants for human gait recognition and content-based image retrieval[J]. IEEE Transactions on Image Processing, 2007, 16(11): 2811-2821.

[10]An S, Liu W Q, Venkatesh S.Face recognition using kernel ridge regression[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, 2007:1-7.

[11]Saunders C, Gammerman A, Vovk V. Ridge regression learning algorithm in dual variables[C]// Proceedings of the 15th International Conference on Machine Learning (ICML98), 1998: 515-521.

[12]Hoerl A E, Kennard R W. Ridge regression: applications to nonorthogonal problems[J]. Technometrics, 1970, 12(1):69-82.

[13]Hoerl A E, Kennard R W. Ridge regression: biased estimation for nonorthogonal problems[J]. Technometrics, 1970, 12(1):55-67.

[14]Parks H R, Wills D C. An elementary calculation of the dihedral angle of the regularn-simplex[J]. The American

Mathematical Monthly (Mathematical Association of America), 2002, 109 (8): 756-758.

[15]Ren W Y, Li G H, Tu D, et al. Nonnegative matrix factorization with regularizations[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2014, 4(1): 153-164.

[16]Lin Z, Chen M, Wu L,et al. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[R]. Technical Report, UILU-ENG-09-2215, 2009.

[17]Candès E J, Li X D, Ma Y,et al. Robust principal component analysis[J]. Journal of the ACM, 2011, 58(3):1-37.

[18]Nene S A, Nayar S K, Murase H. Columbia object image library (COIL-20)[R]. Technical Report CUCS-005-96, 1996.

[19]Belongie S, Kriegman D, Ramamoorthi R. UCSD computer vision[EB/OL].[2014-07-02]. http://vision.ucsd.edu/content/yale-face-database.

[20]Cieri C, Graff D, Liberman M, et al. The TDT-2 text and speech corpus[C]//Proceedings of the DARPA Broadcast News Workshop, 1999: 57-60.

[21]Hull J J. A database for handwritten text recognition research[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(5): 550-554.

[22]Chapelle O, Zien A. Semi-supervised classification by low density separation[C]//Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics,2005:57-64.

[23]Hoyer P O. Non-negative matrix factorization with sparseness constraints[J]. Journal of Machine Learning Research, 2004, 5: 1457-1469.

[24]Vogt J, Roth V. A complete analysis of the I_1, p Group-Lasso[C]//Proceedings of the 29th International Conference on Machine Learning, 2012.

[25]Chartrand R. Exact reconstruction of sparse signals via nonconvex minimization[J]. IEEE Signal Processing Letters, 2007, 14(10):707-710.

[26]Chartrand R, Staneva V. Restricted isometry properties and nonconvex compressive sensing[J]. Inverse Problems, 2008, 24(3):1-14.

[27]Xu Z B, Chang X Y, Xu F M, et al.L1/2regularization:a thresholding representation theory and a fast solver[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7): 1013-1027.

[28]Liu G C,Lin Z C,Yu Y.Robust subspace segmentation by low-rank representation[C]// Proceedings of the 27th International Conference on Machine Learning, 2010:663-670.

http://journal.nudt.edu.cn

Sparse smooth ridge regression method for supervised learning

RENWeiya,LIGuohui

(College of Information System and Management, National University of Defense Technology, Changsha 410073, China)

Abstract：Ridge regression is an important method in supervised learning. It is wide used in multi-class classification and recognition. An important step in ridge regression is to define a special multivariate label matrix, which is used to encode multi-class samples. By regarding the ridge regression as a supervised learning method based on graph, methods for constructing multivariate label matrix were extended. On the basis of ridge regression, a new method named sparse smooth ridge regression was proposed by considering the global dimension smoothness and the sparseness of the projection matrix. Experiments on several public datasets show that the proposed method performs better than a series of state-of-the-art supervised linear algorithms. Furthermore, experiments show that the proposed label matrix construction methods do not reduce the performance of the original ridge regression. Besides, it can further improve the performance of the proposed sparse smooth ridge regression.

Key words：ridge regression; multi-class classification; global dimension smoothness; supervised learning

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-2486(2015)06-121-08

作者簡介：任維雅(1988—)，男，河南周口人，博士研究生，E-mail：weiyren.phd@gmail.com；李國輝(通信作者)，男，教授，博士，博士生導師，E-mail：gli2010a@163.com

基金項目：國家自然科學基金資助項目(611701586)；數學工程與先進計算國家重點實驗室開放資助項目(Grant 2013A08)

收稿日期：*2014-12-26

doi:10.11887/j.cn.201506023