任維雅，李國輝

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

?

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

任維雅，李國輝

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

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

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

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

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

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

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

1嶺回歸

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

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

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

2)當(dāng)1≤g≤k-2，有

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

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

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

(1)

直接求導(dǎo)可得：

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

(2)

式中，I為單位矩陣。

2多變量標(biāo)簽矩陣

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

(3)

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

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

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

標(biāo)簽矩陣的具體構(gòu)造步驟為：

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

根據(jù)上述步驟，提出兩種構(gòu)造T的方法：

1)構(gòu)造方法1：當(dāng)i=j時(shí)，Tij=1，否則Tij=0。要求d≥k，通常可取d=k。

2)構(gòu)造方法2：在d維空間中生成k個(gè)隨機(jī)頂點(diǎn)，使用施密特正交化方法生成k個(gè)新頂點(diǎn)，以構(gòu)造T。

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

3稀疏平滑嶺回歸

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

(4)

將這個(gè)假設(shè)稱為全局維度平滑性假設(shè)，其數(shù)學(xué)的表示為最小化如式(5)所示的正則化項(xiàng)：

=trace(PTDP)-trace(PTWP)

=trace(PTLP)

(5)

考慮正則化項(xiàng)R，嶺回歸最小化目標(biāo)變?yōu)椋?/p>

(6)

式中，λ1λ2>0是平衡各正則化項(xiàng)的參數(shù)。

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

(7)

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

4算法實(shí)現(xiàn)

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

(8)

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

(9)

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

固定其他變量，求P：

(10)

于是，

(11)

固定其他變量，求H：

(12)

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

(13)

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

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

5實(shí)驗(yàn)

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

表1　4個(gè)數(shù)據(jù)集的統(tǒng)計(jì)指標(biāo)

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

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

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

3)TDT2數(shù)據(jù)集。TDT2數(shù)據(jù)集[20]是一個(gè)文本數(shù)據(jù)集，包括9394個(gè)文本文件。每個(gè)文本文件被一個(gè)36771維的向量表示。樣本點(diǎn)最多的前15類數(shù)據(jù)的各自前50個(gè)樣本點(diǎn)作為實(shí)驗(yàn)數(shù)據(jù)集使用。

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

通?？刹捎弥鞒煞址治?Principal Component Analysis,PCA)將數(shù)據(jù)先降維至一個(gè)合適的維數(shù)以提高運(yùn)算效率。另外，數(shù)據(jù)的預(yù)處理方法是對數(shù)據(jù)進(jìn)行平方和歸一化操作。

5.2　實(shí)驗(yàn)流程

5.2.1監(jiān)督分類學(xué)習(xí)實(shí)驗(yàn)

選擇一個(gè)數(shù)據(jù)集，確定在每類樣本中要挑選的訓(xùn)練樣本個(gè)數(shù)NL，實(shí)驗(yàn)流程如下：

1)在每類樣本中隨機(jī)選擇NL個(gè)樣本組成訓(xùn)練集，余下樣本作為測試集；

2)用不同方法學(xué)習(xí)線性投影矩陣；

3)對測試集樣本進(jìn)行投影；

4)通過最近鄰方法(1-NN)確定測試樣本的預(yù)測標(biāo)簽，計(jì)算每類方法在測試樣本上的識別準(zhǔn)確率；

5)重復(fù)以上流程50次。

5.2.2標(biāo)簽矩陣實(shí)驗(yàn)

構(gòu)造5個(gè)不同的標(biāo)簽矩陣，對比這些標(biāo)簽矩陣對RR和SRR方法的影響。這些標(biāo)簽矩陣包括：

(a)COIL20　　　　　　　　　　　(b)Yale

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

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

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

3)Y3：通過T構(gòu)造法2構(gòu)建標(biāo)簽矩陣，令d=2k。

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

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

5.3　實(shí)驗(yàn)結(jié)果

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

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

表2　不同方法在USPS數(shù)據(jù)集上的識別率

表3　不同方法在Yale數(shù)據(jù)集上的識別率

表4　不同方法在COIL20數(shù)據(jù)集上的識別率

表5　不同方法在TDT2數(shù)據(jù)集上的識別率

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

5.4　算法分析

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

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

(14)

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

(15)

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

當(dāng)一個(gè)向量所有值相同時(shí)，其稀疏度則為0%，當(dāng)一個(gè)向量只有一個(gè)元素不為0時(shí)，其稀疏度達(dá)到最大，取值為100%。

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

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

5.5　稀疏約束拓展

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

(16)

(17)

(18)

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

(19)

(20)

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

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

6結(jié)論

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

表8　不同稀疏約束的SRR方法在4個(gè)數(shù)據(jù)集上的識別率

參考文獻(xiàn)(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

文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(611701586)；數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室開放資助項(xiàng)目(Grant 2013A08)

收稿日期：*2014-12-26

doi:10.11887/j.cn.201506023