組加權約束的核稀疏表示分類算法

鄭建煒 楊 平 王萬良 白 琮

(浙江工業大學計算機科學與技術學院 杭州 310023) (zjw@zjut.edu.cn)

?

組加權約束的核稀疏表示分類算法

鄭建煒 楊 平 王萬良 白 琮

(浙江工業大學計算機科學與技術學院 杭州 310023) (zjw@zjut.edu.cn)

提出了一種稱為核加權組稀疏表示分類器(kernel weighted group sparse representation classifier, KWGSC)的新型模式分類算法. 通過在核特征空間而非原輸入空間引入組稀疏性和保局性，KWGSC能夠獲得更有效的鑒別性重構系數用于分類表示. 為獲得最優重構系數，提出了一種新的迭代更新策略進行模型求解并給出了相應的收斂性證明以及復雜度分析. 對比現存表示型分類算法，KWGSC具有的優勢包括：1)通過隱含映射變換，巧妙地規避了經典線性表示算法所固有的規范化問題；2)通過聯合引入距離加權約束和重構冗余約束，精確地推導出查詢樣本的目標類別標簽；3)引入l2,p正則項調整協作機制中的稀疏性，獲得更佳的分類性能. 人造數值實驗表明：經典線性表示型算法在非范數歸一化條件下無法找到正確的重構樣本，而KWGSC卻未受影響. 實際的公共數據庫驗證了所提分類算法具有魯棒的鑒別力，其綜合性能明顯優于現存算法.

稀疏表示技術；保局性；組稀疏正則項；核技術；范數歸一化問題

近年來，稀疏表示技術(sparse representation, SR)已經在機器視覺、模式識別和信號處理等眾多領域獲得了廣泛應用和一致認可，包括圖像修復[1]、特征提取[2]、視頻檢測[3]和目標跟蹤[4]等.針對目標信號，SR搜尋少量基向量對其進行線性組合表示，采用稀疏正則化項解決解空間的病態問題，為信號分類增加魯棒性和鑒別性，其基向量稱為原子，而所有輸入樣本集合則稱為字典.許多現實信號，如圖像和音頻等，被公認為具有稀疏先驗本質.稀疏性約束不僅能夠給出目標解的唯一性，更能夠幫助解析真實的信號結構，獲得魯棒的抗噪能力.此外，信號的稀疏表示還能夠帶來解卷和分離等輔助功能，有益于后續分類問題.雖然原始的稀疏最優化是一個非凸問題，但其l1范數凸擴展以及更新優化策略已被廣泛地研究改進[5-6].

Wright等人[7]將完整的輸入樣本集作為訓練字典，提出了一種鑒別性稀疏表示分類器(sparse representation classifier, SRC)并在人臉識別中獲得了卓越的性能.針對過完備的輸入字典，SRC通過稀疏的原子數據對輸入信號作近似線性表示，并選擇最小重構誤差的類別標簽為目標模式歸屬.雖然SRC在信號去噪[8]、時間序列分類[9]、超分辨率重建[10]等眾多研究中都獲得了成功應用，但其對稀疏性的過分強調卻遭到了其他科研工作者的質疑[11-13].鑒于稀疏性約束在高維特征中具有計算耗時較大的缺陷，Zhang等人[13]認為沒有必要在線性回歸問題中添加稀疏約束，并進一步指出SRC分類器的性能較NN，INNC[14]等近鄰型算法突出的根本原因并非其稀疏性，而是數據間的協作關系所致，從而提出了協作表示分類器(collaborative representation classifier, CRC).CRC采用l2范數替換耗時的l1范數，在保持鑒別能力的同時獲得了算法運行效率的大幅度提升.值得注意的是，SRC和CRC都屬于無監督型算法，其在模式鑒別過程中并未引入輸入特征的類組標簽信息.為進一步提升識別性能，Majumdar等人[15]引入類組稀疏正則項，以類內協作類間稀疏為基本思想提出了組稀疏分類器(group sparse classifier, GSC)，將l2,1范數作為線性重構表示的約束.類似地，Jin等人[16]也采用組稀疏編碼進行圖像分類，以過完備字典為基礎，搜尋稀疏組原子進行測試樣本表示.理論分析和實驗結果都表示GSC具有較SRC和CRC更強的分類性能，鑒于此，GSC得到了廣泛應用且其改進算法不斷涌現[17].

雖然上述經典表示型算法都具有可靠的鑒別能力，但是仍存在著3個關鍵問題有待解決：

1) SRC，CRC，GSC從范數約束形式出發，分別通過稀疏性、協作性和監督性為主旨構建分類模型，其全局表示過程中都忽略了輸入特征的局部分布結構，但事實上局部保持特性(又稱保局性)被認為是非常有益的分類器屬性之一[18]；

2) 限于線性本質，SRC和CRC等算法在應用于具有同向分布性質的輸入特征時都表現出較弱的分類性能[6]，本文稱之為范數歸一化問題；

3) 實際分類任務中，字典矩陣的過完備性條件[7]并不一定滿足，導致SRC解的稀疏性不足，依靠協作機制進行重構鑒別[19]，本文稱之為稀疏性不足問題.

針對保局性問題，Fan等人[20]通過樣本距離對反映數據分布結構，以測試樣本與輸入特征間的歐氏距離約束l1范數正則項，提出加權稀疏表示分類器(weighted sparse representation classifier，WSRC).類似地，加權協作表示分類器(weighted collaborative representation classifier, WCRC)[21-22]和加權組稀疏算法(weighted group sparse representation, WGSR)[23-24]分別將局部約束添加至l2范數和l2,1范數上，通過保局性引導進一步提升了CRC和GSC的分類性能.然而，現實分類數據往往具有復雜分布特征，包括多模態分布和奇異點分布等，簡單的距離加權約束并不能直觀地反映輸入特征形態.并且，對于GSC而言，單純距離約束往往會破壞其組范數特性.

針對范數歸一化問題，核技術[25]被廣泛應用于表示型算法擴展，包括核稀疏表示分類器(kernel SRC，KSRC)[26-28]、核協作表示分類器(kernel CRC，KCRC)[21]及其加權版本[6,21].這些核算法通過隱含變換將輸入特征映射至高維特征空間(又稱核特征空間)，并進行線性分類操作.為解決隱含變換的計算問題，核算法采用核函數替代高維特征數據的內積運算.眾所周知，核技術能夠捕獲輸入特征更多的非線性結構，其性能優于相應的線性分類器.然而，核算法對于鑒別性能提升的根源仍未得到理論分析和驗證，而且迄今為止關于GSC分類器的核化擴展算法仍未見報道.

針對稀疏性不足問題，Xu等人[29]理論證明了在lp(0

綜上所述，本文提出了核加權組稀疏表示分類器(kernel weighted group sparse representation classifier, KWGSC)，以l2,p組范數為約束，引入核技巧將GSC算法進行非線性擴展.此外，兼顧距離加權和重構加權約束表示系數，使KWGSC在不破壞類組結構的前提下提升算法的鑒別能力.

1 相關工作

以SRC和CRC為代表，本節簡要描述表示型算法的基本原理.將所有的輸入特征樣本X=(X1,X2,…,Xc)∈m×n作為字典數據，其中Xi=(xi1,xi2,…,xini)∈m×ni是第i類數據的訓練樣本子集，m維輸入特征xij表示第i類目標對象的第j個樣本，c是目標類別總數，ni為第i類特征樣本數，

所有的表示型算法都具有相似的模型原理，即以過完備輸入字典為前提，所有樣本一致分布于某子空間內.換言之，任意測試樣本y可通過訓練特征樣本進行協作線性表示，即

y=X1θ1+X2θ2+…+Xcθc=

x11θ11+x12θ12+…+xcncθcnc=Xθ，

(1)

其中,θ=(θ11,θ12,…,θcnc)T∈n是輸入特征X對應的重構編碼系數向量.一般采用式(2)優化求取最佳的θ解.

(2)

(3)

其中，參數λ需要人工設定，用于平衡重構誤差和系數值之間的貢獻度，一般較高的λ值對應于更為稀疏的編碼系數解θ.根據β，Z，η，p各值的變化，式(3)可以演化為不同的稀疏(或協作)表示型算法.在得到優化系數θ*后，設δi(θ*)為選擇符號，表示將θ中除第i類外所有元素都置為0的向量，則測試樣本可由各類訓練樣本進行重構，即y=Xδi(θ*),i=1,2,…,c.最終可將y歸類為具有最小重構誤差的類別標簽k，即

(4)

1.1 經典表示型分類算法

經典的表示型分類算法直接以測試樣本和訓練特征樣本的原始形式作為模型數據，同時忽略考慮樣本間的分布加權約束，即采用β=y，Z=X，η=1n(元素都為1的n維矩陣)，在不同的p值范數約束下進行算法模型描述.

當p=1時，即是經典的稀疏表示分類器SRC[7].按照文獻[7]理論分析，在l1范數約束和過完備訓練特征條件下，通過式(3)求得的編碼系數θ具有稀疏性.即在式(1)中，假設測試樣本y是第i類目標數據，則除θi(第i類訓練特征所對應的編碼系數)外的所有編碼系數值都為零.

當p=2時，則是經典的協作表示分類器CRC[13].與SRC強調稀疏性不同，Zhang等人[13]認為SRC算法的鑒別性能之所以較KNN，INNC[14]等最近鄰型算法更為突出，其本質原因是由于數據間的協作表示而非稀疏性.因此，CRC采用l2范數作為編碼系數的約束，大大提升了其運行效率.值得注意的是，CRC的編碼系數不會趨向于絕對零值，從理論上不具備稀疏性.然而，其中更具表示能力的訓練特征仍對應更高的編碼系數值，因此我們依然可以稱之為稀疏表示型算法.

當p=12時，式(3)轉變為l分類器LHC[19].稀疏性范數約束l1要求模型輸入具有充足的訓練樣本，因而獲得接近于l0范數的稀疏解.然而，現實分類問題如圖像識別等往往存在高維數小樣本的情形，使得SRC解的稀疏性較弱，類似于CRC的協作分類機制.通過LHC算法得到的編碼系數較SRC更為稀疏，在樣本數受限的應用中有效地平衡了協作表示和稀疏表示的貢獻.

SRC，CRC，LHC都是無監督學習算法，在模型構建過程中忽略了樣本標簽信息，其性能有待進一步提升.GSC采用l2,1范數約束，設定p為2,1，對不同類別的特征樣本作l1范數約束，而同類樣本則采用l2范數約束，因此算法具有組稀疏性.已有的研究結果表明，GSC的綜合識別性能優于SRC和CRC[16-17]，其模型求解策略與SRC基本一致，需要通過迭代更新進行編碼系數優化求解，效率遜于CRC的閉式求解方案.

1.2 加權表示型分類算法

如引言所述，SRC，CRC，GSC這3種分類器通過稀疏性、協作性以及監督性進行模型描述構建，但卻忽視了輸入樣本的局部分布結構因素.然而，保局性在眾多模式分類和機器學習算法中已被廣泛應用，包括數據分簇[30]、流形挖掘[31]、多任務學習[32]等領域.文獻[18,33]直接表明數據保局因子較稀疏性等更有模型指示意義.基于此，已有不少保局性表示型分類算法提出.由于保局性一般以權值形式約束于編碼系數，因此該類算法可以統稱為加權表示型分類算法.

與經典表示型算法類似，保持式(3)其余部分不變，編碼系數權值通過η實現，其值一般取決于測試樣本與輸入特征的歐氏距離，即

(5)

其中，ηij代表第i類數據第j個編碼系數值的加權因子，帶寬參數σ需要人工經驗設定，一般取為平均距離方差較為合理.

SRC，CRC的加權版算法分別為WSRC[20]和WCRC[21]，在η權值的影響下，遠距離樣本的編碼系數值趨向于零，而近鄰樣本獲得較高編碼系數的機率相對更大.因此WSRC和WCRC具有保局特性以及奇異點抑制特性.此外，部分加權表示型算法[22]采用訓練樣本構建加權因子而非通過測試樣本計算，實驗結果表明其性能弱于WSRC和WCRC.

1.3 核表示型分類算法

模式分析的典型研究方向，包括分簇、低秩、主成分、關聯性以及識別等任務，都需要通過用戶指定的特征映射操作將輸入數據進行模式變換.相反地，核方法通過核技術的引入，以原輸入特征的成對相似性函數替換特征映射，通過隱含變換實現非線性空間中的線性操作，其典型代表有支持向量機[34]、核主成分分析[35]以及核Fisher鑒別分析[36]等.KSRC[26]和KCRC[21]分別通過核函數的引入，實現了在核特征空間中的稀疏表示系數計算.

假設測試樣本y和輸入特征X可通過非線性映射φ變換至高維F空間，將β和Z分別表述為φ(y)和Φ(X)，其中Φ是φ的矩陣描述形式，則式(3)可以改寫為

(6)

其中，暫時忽略加權因子，即令η=1n.由于φ是一個未知的隱含映射，核方法通過核函數替代F空間中兩兩特征樣本的內積計算，用于算法的優化求解實現，即式(6)調整為

(7)

其中K=Φ(X)TΦ(X)∈n×n是對稱半正定的核矩陣[36]，k(·,y)=(k(x11,y),k(x12,y),…,k(xcnc,y))T=Φ(X)Tφ(y).常見的核函數k(a,b)包括線性核、多項式核以及高斯核，其中應用最為廣泛的是高斯核函數，表達式為

(8)

式(8)是本文實驗所選用的核函數形式，其中帶寬參數σ需要人工設定，用于控制高維核空間中樣本對內積的具體取值.

聯合添加核函數式(8)和加權因子式(5)于編碼系數計算式(3)，即可得到核加權表示型分類算法，文獻[6,21]都通過數值實驗和實際數據實驗驗證了其性能優于常規的核化表示分類算法和加權表示分類算法.

2 核加權組稀疏分類算法KWGSC

根據第1節相關工作闡述，稀疏表示型算法，如GSC，WSRC，KCRC等，都通過協作表示原理，以重構誤差最小為目標進行樣本判別，在模式識別領域獲得了廣泛的應用，取得了卓越的成效.總體來說，此類方法的核心問題是：選擇最具代表性且對應范數值最小的數據進行測試樣本重構表示，以誤差最小化為準則進行模式鑒別，其中包括2個關鍵點，即精確重構以及最小化范數值.基于此，本節首先詳細闡述了數據歸一化形式與特征優選的聯系，然后提出KWGSC算法，并對其模型優化進行了分析求解和收斂性證明.

2.1 稀疏表示與規范化問題

在模式識別領域，分類模型在實際應用中往往都會對輸入特征進行不同形式的規范化操作，包括均值化處理[36-37]和范數歸一化處理[21]等.不同預處理操作能夠規范輸入特征數據的分布狀態并提升分類器的數值穩定性.然其對分類性能的具體影響仍未得到充分地理論分析與實驗驗證.本節從具體數值實例出發(如圖1和圖2所示)，分析討論稀疏表示型算法受范數歸一化操作的影響.

Fig. 1 Numeric examples for the norm normalization problem with different sparse representation algorithms.圖1 非歸一化數據對不同稀疏表示型算法影響的數值示例

Fig. 2 Norm normalization problem.圖2 范數歸一化問題

在圖1(a)中，通過標準高斯分布給出了3類人工設定數據，分別為以坐標(1,2)為中心的圓形數據，以坐標(5,0)為中心的方形數據以及以坐標(1,-3)為中心的三角形數據.圖1(a)中實心圓點是圓形數據的中心，作為測試樣本，余下的所有輸入數據作為訓練樣本.從圖1可見，在范數值不一致的輸入數據中，大部分稀疏表示型算法都沒能選擇最優的訓練樣本進行線性重構，呈現出較弱的鑒別力，稱之為范數歸一化問題.該問題導致高范數值訓練數據被選擇為重構樣本的概率大大提升.在圖1給定的數據中，圓形、方形和三角形3類樣本的l2范數值域分別為(0.433，17.668)，(13.194，48.659)，(3.494，31.602)，其中方形和三角形數據的范數值明顯高于圓形數據，也更有可能被選為表示樣本.在圖1(b)中，SRC的非零系數所對應的樣本分別為一個方形和一個三角形，都不是正確的圓形數據，違背了SRC算法提出時類內線性表示的基本思想；CRC和GSC不是嚴格意義上的稀疏表示算法，本文選用前15%大的系數值進行顯示.在圖1(c)中，CRC的有效表示樣本包括3種不同類型的輸入數據，但以三角形和方形居多.在圖1(d)中，GSC通過組約束，剔除了方形表示樣本，然而三角形表示樣本數仍然多于同類圓形樣本.取決于保局特性，圖1(e)中WSRC選擇了正確的同類樣本進行稀疏表示，然而歸一化問題仍然存在，其表示樣本具有同類數據中較大的范數值.

圖2進一步闡明了范數歸一化操作對表示型分類算法的意義.在圖2(a)中，X1={x11,x12,x13}和X2={x21,x22,x23}是2類經過l2范數歸一化的數據，按簇分布于單位圓上.將x11作為測試樣本，余下的作為訓練樣本.點q1是x12與x13連線以及x11與原點連線的交點，其至原點的歐氏距離設為b1.類似地，點q2是x12與x21連線以及x11與原點連線的交點，q2到原點的歐氏距離設為b2.假定x11可以通過x12和x13線性表示，由于輸入樣本分布于單位圓上，因此可以得到:

圖2(b)顯示了沒有經過范數歸一化操作的2類數據，其中圓點數據的坐標為x11=(0.5,-0.8)，x12=(0.9,-0.5)，x13=(0.1,0.04)，方塊數據的坐標為x21=(3.4,1.5)，x22=(3.3,-1.0)，x23=(3.1,0.5)，則有

x11=(x12x13)(1.163,-5.465)T=

(x22x23)(0.575,-0.451)T=

X(0,1.163,-5.465,0,0,0)T=

X(0,0,0,0,0.575,-0.451)T，

(9)

其中X=(x11,x12,…,x23)是訓練數據矩陣.

類似地，將所有數據作l1范數歸一化，有x11=(0.38,-0.62)T，x12=(0.64,-0.36)T，x13=(0.71,0.29)T，x21=(0.69,0.3)T，x22=(0.77,-0.23)T，x23=(0.86,0.14)T，以及

x11=(x12x13)(1.252,-0.589)T=

(x22x23)(1.9,-1.248)T=

X(0,1.252,-0.589,0,0,0)T=

X(0,0,0,0,1.9,-1.248)T.

(10)

最后，再將所有數據作l2范數歸一化，有x11=(0.53,-0.85)T，x12=(0.87,-0.49)T，x13=(0.93,0.37)T，x21=(0.91,0.4)T，x22=(0.96,-0.29)T，x23=(0.99,0.16)T，以及

x11=(x12x13)(1.269,-0.624)T=

(x22x23)(2.62,-1.5)T=

X(0,1.269,-0.624,0,0,0)T=

X(0,0,0,0,2.62,-1.5)T.

(11)

聯合式(9)～(11)可見，在輸入數據沒有經過歸一化操作時，式(9)中x12和x13對應的系數l1范數為6.63，而x22和x23對應的系數l1范數為1.03.因此，x22和x23被錯誤地選擇為重構表示測試數據x11，而非x12和x13.當輸入數據經過l1歸一化操作后，式(10)中x12，x13和x22，x23對應的系數l1范數分別1.84和3.14.因此，x12和x13被正確選擇為重構表示數據.進一步地，當輸入數據經過l2歸一化操作后，式(11)中x12，x13和x22，x23對應的系數范數分別1.89和4.12，不僅能獲得所需的正確結果，且其范數差異較l1歸一化操作時更大，更具有鑒別性.該結論與圖2(a)的理論分析具有一致性，說明歸一化操作對稀疏表示型算法的影響以及l2范數歸一化的優越性.

2.2 KWGSC算法描述

綜合第1節和2.1節分析，本節提出核加權組稀疏表示分類算法KWGSC，包含組稀疏范數、保局性、核函數等有利分類的技術.值得強調的是：

2) 理想情況下，輸入特征樣本Z具有充分完備性，則表示系數的非零元素嚴格對應y的同類訓練樣本[7].很明顯，稀疏性約束(如l0范數)在該情形下的重構表示中起關鍵作用.然而，由于l0約束的NP難問題，實際應用中極限稀疏的系數解很難得到，更多地依賴協作機制進行重構表示(如SRC中的l1正則項以及CRC中的l2正則項).為有效地平衡協作性和稀疏性的貢獻，本文將范數約束擴展至(0,1]范圍(區別于LHC中的固定值1/2)，并以組范數約束的形式構建目標函數.

結合式(3)(6)以及l2,p組范數約束的KWGSC目標模型為

(12)

(13)

其中,di與WSRC和WCRC中的權值意義一致，其元素dij在核特征空間中的取值為

(14)

此外，ri是類組加權系數，借鑒線性回歸分類器的思想[39]，其值表示為

(15)

其中,Ki=Φ(Xi)TΦ(Xi)∈ni×ni是第i類核矩陣，ki(·,y)=(k(xi1,y),k(xi2,y),…,k(xini,y))=Φ(Xi)Tφ(y)是y與第i類輸入數據的核向量.可見ηi=ridi由2部分組成：第1部分ri是第i類樣本Xi重構測試樣本y的冗余，其值越小，代表y屬于第i類的概率越大，相應第i類的重構系數θi越大；第2部分di用于懲罰遠距離樣本，dij值越大，說明相應的樣本xij離y越遠，對應重構系數θij越小.

通過式(13)可見，對比GSC，KWCRC，WSRC等現存算法，KWGSC在核特征空間通過類組加權和距離加權凸顯了表示系數的組結構特性，具有更多的鑒別性信息.結合式(4)和式(15)，在最優化目標函數式(13)后，KWGSC通過表示系數θ*所建的模式鑒別規則為

(16)

即在核特征空間中，選擇重構誤差最小的類為測試樣本y的類別標簽.

2.3 優化求解和收斂性分析

現有稀疏表示型算法中CRC，KCRC，KWCRC等協作表示算法都具有閉式解，而SRC，GSC等(包括相應衍生算法)則需要迭代操作計算最優系數解，包括特征標記法[40]、梯度投影法[41]、同倫分析法[42]、近端梯度法[43]等.KWGSC算法在核特征空間中兼顧類組重構和樣本加權約束.因此，現有的迭代求解算法無法直接應用于計算KWGSC的目標系數θ*.針對該問題，本節采用一種新的迭代策略進行組l2,p問題優化求解.為簡化公式描述，引入矩陣Π=diag((η1,η2,…,ηc))∈n×n，并定義=2,p，將核加權組稀疏的目標模型表示為

(17)

對式(17)依系數向量θ求微分可得:

Kθ-k(·,y)+λΠTDΠθ=0，

(18)

(19)

則可得:

θ=(K+λΠTDΠ)-1k(·,y).

(20)

需要注意的是:式(20)中D的計算包含系數θ.因此，系數θ的優化策略是一個迭代更新過程，所提的核加權編碼求解具體方案如算法1所示，其實現過程中，值得強調3點：

2) 從式(20)可見，編碼系數θ的更新是一個閉式求解公式，易于直觀實現.本文將初始θ(1)值取為n維元素恒等于1n的向量.

算法1. 核加權編碼系數迭代求解算法.

輸入: 帶類別標簽的特征樣本X，待測樣本y，參數值λ，σ，p，最大迭代數tmax；

輸出: 最優編碼系數θ*.

① 計算核矩陣K以及待測樣本y與各特征樣本的核函數值k(·,y);

② 依式(14)計算距離加權d，依式(15)計算重構加權r;

③ 根據d和r得到η，并構建權值矩陣Π;

④ 迭代t=1，設初始編碼系數為θ(t);

⑤ 依η和θ(t)構建塊對角矩陣D;

⑥ 按照式(20)求解θ(t+1);

⑦ 滿足收斂則輸出θ*，反之則令t=t+1，并轉步驟④.

引理1. 給定任意非零向量x和y，當p∈(0,1]時，

(21)

證明. 根據凹函數定義[44]，當p∈(0,1]時，已知凹函數xp在定義域(0,∞)中有yp-xp+pyp-1(x-y)≥0.對非零向量xi和yi則有:

(22)

將式(22)中所有的i∈{1,2,…,c}相加，則式(21)得證.

證畢.

定理1. 通過算法1迭代計算，目標函數式(17)的值逐次下降直至收斂.

證明. 定義第t次迭代時的誤差向量為et=φ(y)-Φ(X)θt，由于θt+1是式(18)的解，則有:

Φ(X)TΦ(X)θt+1-Φ(X)Tφ(y)+

λΠTDtΠθt+1=0.

(23)

通過對式(23)兩邊分別點乘θt-θt+1可得:

λ(θt-θt+1)TΠTDtΠθt+1=

(θt-θt+1)TΦ(X)T(φ(y)-Φ(X)θt+1)=

(Φ(X)θt-y+y-Φ(X)θt+1)T·

(φ(y)-Φ(X)θt+1)=-(et-et+1)Tet+1.

(24)

結合引理1和式(24)有：

λtr((θt-θt+1)Tθt+1ΠTDΠ)=

(et-et+1)Tet+1.

(25)

此外,

(et-et+1)Tet+1.

(26)

將式(25)與式(26)相加可以得到:

(et-et+1)T(et-et+1)≥0,

即目標函數式(17)在迭代更新過程中逐次降值，并具有明確的下確界0，則該算法收斂性得證.

證畢.

3 實驗分析

3.1 數據庫描述與實驗設置

1) 數據庫.采用AR人臉數據庫、COIL20物體圖像數據庫以及MNIST手寫字體數據庫驗證所提算法的性能.AR數據庫包含126個目標人物的4 000多幅正臉圖像，囊括光照、表情變化以及面部裝飾等情形.由于KWGSC并未針對外物遮擋進行算法設計，因此本文選擇AR數據庫中的非遮擋子集進行識別率測試[45]，包括50個男性目標和50個女性目標，每個目標選擇7個訓練樣本和7個測試樣本，所有圖像均被預處理至60×43灰度像素.COIL20物體圖像庫包含20個目標對象，每個對象由位置固定的攝像機拍下其水平旋轉的72張照片.所有目標圖像都經過邊緣裁剪且縮放至40×40灰度像素，本文隨機選擇每類30個樣本作為訓練數據集，余下的所有樣本作為測試集.MNIST數據庫包含70 000個手寫字圖像，并劃分為訓練集和測試集.與文獻[21]類似，本文針對每個數字(0～9共10個數字)，從訓練集中隨機選擇50個樣本，從測試集中隨機選擇70個樣本，共計500個訓練數據和700個訓練數據進行實驗分析，該數據集中的所有圖像都統一裁剪調整至28×28灰度像素.

Fig. 3 Recognition performance versus parameter changes for different competing algorithms.圖3 不同算法識別率隨正則化參數變化的對比

2) 輸入特征形式.在不同的實驗過程中，輸入的特征數據包括原始灰度像素值和子空間投影樣本.原始灰度像素值將輸入圖像按列展開并串聯成單方向向量.以AR數據庫為例，將其中的任意訓練或測試樣本都調整為60×43=2 580×1的特征串.子空間投影樣本則將上述向量特征進行維數約簡操作，包括經典的主成分分析算法(principal component analysis, PCA)和最新提出的迭代最近鄰線性投影算法(iterative nearest neighbors linear projections, INNLP)[14].PCA以最大化訓練樣本散度為目標函數，旨在保留輸入數據的主分布結構;INNLP則采用迭代最近鄰法進行鄰域矩陣構建，并以局部結構保持為目標函數計算線性投影矩陣，其正則化參數在本文中恒設為0.05.

3) 分類算法.選用不同的稀疏型分類算法進行實驗效果對比，包括經典線性算法SRCF[7](F表示采用特征標記法訓練)、CRC[13]、LHC[19]和GSC[16]，距離加權線性算法WSRC[20]和WCRC[21]，核化算法KSRCF[28]、KSRCH[27](H表示采用同倫法訓練)、KCRC[6]和KWCRC[21].此外，本文還引入經典分類算法最近鄰分類器(NNC)、新晉的迭代最近鄰分類器(INNC)以及兩者各自的核化版本KNNC[34]和KINNC[14]作為對比分類模型，以豐富的數據驗證所提算法KWGSC的鑒別性能.所對比的算法中，除NNC和KNNC外，都包含需要人工設定的正則化參數值λ，本文采用4倍交叉驗證進行最優值確定.針對任意分類算法，考慮λ={10-8,10-7,…,10-1,100}進行鑒別分類，在不同輸入特征維數中選取具有最高平均識別率的λ值為最終模型參數.除λ參數值外，各核化版算法都采用高斯核函數作為模型運行組件，其帶寬參數σ需要人工確定，本文將其統一設置為輸入特征距離矩陣的平均值.如無特殊聲明，組范數l2,p中的參數值p默認為1.圖3以GSC，KCRC，KSRCF，KSRCH，KWGSC算法為例，采用AR人臉數據庫和MNIST手寫字體數據庫為輸入特征，給出了不同正則化參數值環境下的算法分類性能對比結果，降維技術為PCA.其中，識別率的計算公式為1-mn，m是識別錯誤樣本數，n是所有測試樣本總數.從圖3結果可以得到如下3點：

1) 參數λ的最優值一般都小于1，且位于(10-4,10-1)區間內的可能性更高；

2) 隨參數λ值在(10-8,10-1)區間內變化，各算法的識別率波動較小，尤其在(10-8,10-4)區間內，各算法的識別率基本保持不變，僅KSRCH算法在AR數據庫中有較大的差異；

3) 各算法在不同輸入特征維數下的最優參數選值非常穩定，如KWGSC，GSC，KSRCH算法都嚴格保持一致，而KCRC和KSRCF算法的最優 值變化也非常接近.

上述3點綜合表明了稀疏表示型算法的人工待選參數確定較為直觀，減輕了算法實際應用的繁瑣程度.

3.2 歸一化范數分析

如3.1節所述，輸入特征的不同范數形式對稀疏表示型算法的性能具有明顯的影響，本節以GSC和KWGSC兩種算法為例，以MNIST，AR，COIL20三個數據庫為應用對象，在不同范數歸一化形式下進行算法識別率對比，如圖4所示.其中，降維技術仍然選用PCA，算法名稱_l2表示在l2范數歸一化中的識別率曲線，算法名稱_l1表示在l1范數歸一化中的識別率曲線，而算法名稱_l0則表示保持輸入特征不變無范數歸一化時的識別率曲線.

從圖4可見：隨著范數歸一化約束的變化，線性算法GSC的識別率具有較大幅度的變化，在不同子空間維數下誤差達到2%～6%；單獨對比GSC的識別率發現，在不同的范數歸一化約束中，l2范數的識別率最高，而l0非歸一化的識別率最低；此外，KWGSC算法通過引入高斯函數，輸入特征在F空間中具有恒為l2規范化的特點，因此其識別率在不同數據庫、不同子空間維數下的變化較小，誤差基本保持在1%以內.圖4所示實驗結果與正文理論分析部分完全吻合.在后續實驗中，為保證線性算法的識別率，統一采用l2范數進行輸入特征歸一化處理.

Fig. 4 Recognition performance versus norm changes for GSC and KWGSC.圖4 GSC和KWGSC兩種算法在不同歸一化范數下的識別率對比

3.3 識別性能分析

確定最優模型參數和歸一化范數形式后，本節驗證所提算法在不同目標對象和不同輸入特征維數下的識別率性能.針對MNIST手寫字體數據庫，表1給出了所有分類器在不同目標數字下的識別率(輸入特征是150維的PCA降維樣本).表1中黑體數字表示相同維數特征下所有算法的最高識別率，帶單下劃線的數字表示第2高識別率，帶雙下劃線的數字則表示第3高識別率.通過表1可知，MNIST數據庫中不同數字對象的識別難度各異，其中數字“2”是識別率最高的對象，包括KWGSC和NNC在內共計8種分類器對其取得了100%的識別率，而最低的識別率也達到了97.1%；數字“9”是綜合識別率最低的對象，其最高識別率僅為87.1%，由WSRC和KSRCH獲得.在15種分類器的對比中，本文所提的KWGSC具有最優的綜合識別率，共計獲得4個最優值(黑體)、4個次優值(單下劃線)以及2個第3優值(雙下劃線)，表明其在不同目標對象下具有更為穩定的分類性能.雖然分類器WSRC也獲得了4個最優值(黑體)，但其只有1個次優值(單下劃線)，且沒有第3優值(雙下劃線)，因此在該實驗對比中排第2.

特征維數測試中，分別以原始輸入特征和通過PCA，INNLP處理后的子空間特征進行分類實驗，子空間維數選為{50,100,150,200,250,300}，表2～4顯示了各分類器在所有數據庫中的識別性能對比，其中DR表示維數約簡操作(dimensionality reduction).

Table 1 Recognition Rate for Different Numbers on MNIST

Table 2 Recognition Rate versus Different Feature Dimensions on the MNIST Database

Table 3 Recognition Rate versus Different Feature Dimensions on the AR Database

Table 4 Recognition Rate versus Different Feature Dimensions on the COIL20 Database

從表2～4可以得出5個結論：

1) 考慮到實際圖像數據的分布多樣性，無法從所對比的15種算法中確定具有絕對優勢的分類模型，大部分分類器在不同輸入特征中的表現有一定波動，本文嘗試從中挖掘相對穩定且高性能的分類算法.

2) NNC，INNC及相應核化算法的綜合識別率相對低于其余稀疏型分類器.在MNIST手寫字體數據庫中，NNC和KNNC在PCA子空間中的最高識別率僅為86.3%，而其余算法的最低識別率達到87%，最高達到93.4%(KWGSC)；類似地，KINNC在INNLP子空間中的最高識別率僅為55.4%，遠低于余下算法的最低識別率62.9%.說明采用最近鄰模式進行鑒別判定無法勝任現實數據的精確分類，而協作表示對于復雜分布數據具有有益的模式鑒別效果.

3) 線性算法SRCF，CRC，LHC，GSC的對比中，LHC較SRCF和CRC有微弱優勢，說明合理地平衡稀疏性和協作性能夠提升分類性能；GSC在COIL20物體圖像庫的PCA子空間中略遜于LHC算法，而在余下分類實驗中都優于其他3種線性表示型算法.其中，在AR數據庫，GSC的最高識別率為94.0%，優于同條件下的所有14種算法.究其原因，GSC采用有監督的l2,1范數作為重構系數約束，引入類別標簽引導最優系數計算，優于單一的l1，l2，l范數約束.

4) 核化算法的綜合識別率明顯高于對應的線性算法.KCRC，KSRCF，KWCRC，KWGSC等核分類算法在表2～4不同輸入特征的識別率中大部分高于相應的CRC，SRCF，WCRC，GSC算法，驗證了正文中關于核化算法具有更高鑒別性的論點.

Fig. 5 Recognition performance versus p in KWGSC.圖5 KWGSC在不同稀疏值p下的算法識別率測試

5) KWGSC算法兼具了上述結論中的所有優勢，包括核化、監督性、距離加權等，并且添加了重構冗余系數約束，其綜合識別率明顯優于其他算法.從表2～4可見，KWGSC在所有3個數據庫中都具有最多的最優值、次優值和第3優值，在MNIST，AR，COIL20中的最高識別率分別達到93.4%，94.7%，99.8%.此外，KWGSC算法的穩定性也優于其他算法，在不同數據庫中的波動明顯小于其他所對比的算法.

通過表1～4的實驗可知，KWGSC分類器在鑒別性能和分類穩定性上都優于其余對比分類器.本節進一步測試KWGSC在組范數參數值p變化時的分類性能.圖5給出了在p∈{0.1,0.2,…,0.9,1.0}時KWGSC的識別率，其中NONE,PCA和INNLP分別表示原始輸入特征、PCA降維至150和INNLP降維至150時的識別率.從圖5可見，KWGSC的分類性能總體上隨p值變化波動較小，其識別率保持在2%內，其中在MNIST的PCA和INNLP子空間和COIL20的PCA和NONE空間中的識別率基本保持不變.同時，圖5進一步顯示了KWGSC的最優值并不一定來源于p=1，而是以[0.5,0.8]區間為最佳，該結果一方面驗證了LHC算法[19]的基本思想，同時也表明了LHC中將p值固定為12的缺陷.因此，本文在KWGSC分類算法中并未明確約束組范數值p，使之能夠在不同的分類任務中依目標數據進行參數優選，勝任分布特性更為復雜的異構數據.

3.4 運行效率分析

除識別性能外，運行效率是影響分類算法實際應用能力的另一關鍵指標.本節選擇在MNIST，AR，COIL20數據庫中表現較為穩健的9種分類算法進行測試效率對比，包括SRCF，CRC，GSC，LHC，WCRC，KSRCF，KCRC，KWCRC，KWGSC.表5顯示了各算法在不同數據庫中單個樣本的測試時間，其中各單元格所對應的識別率為表2～4原始維數列.所有的數據都通過10次實驗運行并取平均值得到，實驗平臺為Intel Core i5 CPU，雙核主頻2.80 GHz，內存4 GB，32位Win 7操作系統以及Matlab 2014運行軟件.結合表1～5所示，CRC和KCRC在識別率上雖然與SRCF以及KSRCF較為接近，但是其運行效率卻遠遠優于SRC型算法，達到了毫秒級的反應速度，完全可以勝任視頻跟蹤等在線應用系統；加權型表示算法WCRC以運行效率減弱為代價提升鑒別性能，從表4可見其運行時間接近于CRC算法的30倍，而識別率提升則并不顯著，因此實用性欠佳；GSC的識別率僅次于KWGSC，但其實現過程需要迭代計算操作(類似于SRCF)，因此運行效率較低；LHC的運行效率與GSC較為接近，而其綜合識別性能弱于GSC，算法優勢并不明顯；最后，KWGSC的運行效率高于SRCF，KSRCF，GSC，LHC，WCRC等算法，僅次于CRC和KCRC，在大部分應用中都達到了10 ms級的運行效率(除AR數據庫外)，考慮到其具有最高最穩定的鑒別性能，因此值得推廣應用.需要注意的是，GSC與KWGSC的求解算法類似，KWGSC的運行效率優于GSC得益于重構系數和距離加權的引入，使得其能夠在更少的迭代次數下獲得算法收斂.

Table 5 Testing Time of Competing Algorithms

4 總 結

通過數值實驗分析了不同范數歸一化操作對經典線性表示模型的影響以及核化算法的魯棒性，以此為基礎提出核加權組稀疏分類算法(KWGSC).該算法以l2,p范數約束為基礎引入核技術，通過距離約束和重構冗余加權提升算法的組稀疏特性和分類鑒別能力.本文所提算法在AR人臉數據庫、COIL20物體圖像庫以及MNIST手寫字體數據庫中獲得高識別率，明顯優于現有的表示型分類算法.此外，為獲得最優的重構系數，提出一種新的迭代更新策略用于模型優化求解，通過有限次迭代操作即可達到算法的全局最優解，實驗驗證該算法的運行效率優于經典的GSC算法和SRC算法.總體來說，本文的創新點包括：

1) 首次采用數值實驗和圖例分析范數歸一化操作對分類性能的影響進行深度研究；

2) 對GSC算法進行核化擴展，并在距離加權的基礎上添加類組重構加權，提升算法識別能力；

3) 以組范數l2,p，其中p∈(0,1]為約束，并在核空間中提出快速高效的迭代優化算法用于模型求解.

分析研究發現，所提算法KWGSC雖然易于實現且性能卓越，但實現過程中需要固定受限的核函數，如高斯核或其擴展核函數，不適于算法的多核操作應用.此外，KWGSC算法并沒有對輸入數據進行特征加權約束，不適于遮擋應用環境和高含噪特征樣本.因此，后續工作將集中進行多核擴展和特征加權研究.

[1]Zhang Jian, Zhao Debin, Gao Wen. Group-based sparse representation for image restoration[J]. IEEE Trans on Image Processing, 2014, 23(8): 3336-3351

[2]Yang Wankou, Wang Zhenyu, Sun Changyin. A collaborative representation based projections method for feature extraction[J]. Pattern Recognition, 2015, 48(1): 20-27

[3]Tao Jianwen, Chung F L, Wang Shitong, et al. Sparse label propagation: A robust domain adaptation learning method[J]. Journal of Software, 2015, 26(5): 977-1000 (in Chinese)

(陶劍文, Chung F L, 王士同, 等. 稀疏標簽傳播: 一種魯棒的領域適應學習方法[J]. 軟件學報, 2015, 26(5): 977-1000)

[4]Hu Zhaohua, Yuan Xiaotong, Li Jun, et al. Robust fragments-based tracking with multi-feature joint kernel sparse representation[J]. Journal of Computer Research and Development, 2015, 52(7): 1692-1704 (in Chinese)

(胡昭華, 袁曉彤, 李俊, 等. 基于目標分塊多特征核稀疏表示的視覺跟蹤[J]. 計算機研究與發展, 2015, 52(7): 1692-1704)

[5]Candes E J, Tao T, Near-optimal signal recovery from random projections: Universal encoding strategies[J]. IEEE Trans on Information Theory, 2006, 52(12): 5406-5425

[6]Liu Weiyang, Yu Zhiding, Lu Lijia, et al. KCRC-LCD: Discriminative kernel collaborative representation with locality constrained dictionary for visual categorization[J]. Pattern Recognition, 2015, 48(10): 3076-3092

[7]Wright J, Yang A Y, Ganesh A, et al. Robust face recognition via adaptive sparse representation[J]. IEEE Trans on Pattern Analysis & Machine Intelligence, 2014, 44(12): 2368-2378

[8]Liu Jianwei, Cui Lipeng, Liu Zeyu, et al. Survey on the regularized sparse models[J]. Chinese Journal of Computers, 2015, 38(7): 1307-1325 (in Chinese)

(劉建偉, 崔立鵬, 劉澤宇, 等. 正則化稀疏模型綜述[J]. 計算機學報, 2015, 38(7): 1307-1325)

[9]Chen Zhihua, Zuo Wangmeng, Hu Qinghua, et al. Kernel sparse representation for time series classification[J]. Information Sciences, 2015, 292: 15-26

[10]Wang Lingfeng, Yan Hongping, Lü Ke, et al. Visual tracking via kernel sparse representation with multikernel fusion[J]. IEEE Trans on Circuits and Systems for Video Technology, 2014, 24(7): 1132-1141

[11]Rigamonti R, Brown M A, Lepetit V. Are sparse representations really relevant for image classification?[C] //Proc of the 27th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2011: 1545-1552

[12]Shi Qinfeng, Eriksson A, Anton H, et al. Is face recognition really a compressive sensing problem?[C] //Proc of the 27th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2011: 553-560

[13]Zhang Lei, Yang Meng, Feng Xiangchu. Sparse representation or collaborative representation: Which helps face recognition?[C] //Proc of Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2011: 471-478

[14]Timofte R, Gool L V. Iterative nearest neighbors[J]. Pattern Recognition, 2015, 48(1): 60-72

[15]Majumdar A, Rabab K W. Fast group sparse classification[J]. Canadian Journal of Electrical and Computer Engineering, 2009, 34(4): 136-144

[16]Huang Jin, Nie Feiping, Huang Heng, et al. Supervised and projected sparse coding for image classification[C] //Proc of the 27th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2013: 438-444

[17]Wang Lijun, Lu Huchuan, Wang Dong. Visual tracking via structure constrained grouping[J]. IEEE Signal Processing Letters, 2015, 22(7): 794-798

[18]Wei Jiangshu, Lü Jiancheng, Zhang Yi. Robust classifier using distance-based representation with square weights[J]. Soft Computing, 2015, 19(2): 507-515

[19]Zhong Dexing, Xie Zichao, Li Yanrui, et al. Loosel1/2regularized sparse representation for face recognition[J]. IET Computer Vision, 2015, 9(2): 251-258

[20]Fan Zizhu, Ni Ming, Zhu Qi, et al. Weighted sparse representation for face recognition[J]. Neurocomputing, 2015, 151: 304-309

[21]Timofte R, Gool L V. Adaptive and weighted collaborative representation for image classification[J]. Pattern Recognition Letters, 2014, 42: 127-135

[22]Wu Jiqing, Timofte R, Gool L V. Learned collaborative representations for image classification[C] //Proc of IEEE Winter Conf on Applications of Computer Vision. Piscataway, NJ: IEEE, 2015: 456-463

[23]Chao Yuwei, Ye Yiren, Chen Yuwen, et al. Locality-constrained group sparse representation for robust face recognition[C] //Proc of IEEE Int Conf on Image Processing. Piscataway, NJ: IEEE, 2011: 761-764

[24]Tang Xin, Feng Guocan, Cai Jiaxin. Weighted group sparse representation for under sampled face recognition[J]. Neurocomputing, 2014, 145: 402-415

[25]Muller K, Mika S, Ratsch G, et al. An introduction to kernel-based learning algorithms[J]. IEEE Trans on Neural Networks, 2001, 12(2): 181-201

[26]Zhang Li, Zhou Weida, Chang P C, et al. Kernel sparse representation-based classifier[J]. IEEE Trans on Signal Processing, 2012, 60(4): 1684-1695

[27]Kang Cuicui, Liao Shengcai, Xiang Shiming, et al. Kernel Homotopy based sparse representation for object classification[C] //Proc of the 21st Int Conf on Pattern Recognition (ICPR). Piscataway, NJ: IEEE, 2012: 1479-1482

[28]Gao Shenghua, Tsang I W, Chia L T. Sparse representation with kernels[J]. IEEE Trans on Image Processing, 2013, 22(2): 423-434

[29]Xu Zongben, Chang Xiangyu, Xu Fengmin, et al. L1/2 regularization: A thresholding representation theory and a fast solver[J]. IEEE Trans on Neural Networks and Learning Systems, 2012, 23(7): 1013-1027

[30]Nie Feiping, Wang Xiaoqian, Huang Heng. Clustering and projected clustering with adaptive neighbors[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 977-986

[31]Wang Lingfeng, Wu Huaiyu, Pan Chunhong. Manifold regularized local sparse representation for face recognition[J]. IEEE Trans on Circuits and Systems for Video Technology, 2015, 25(4): 651-659

[32]Wang Shengzheng, Jing Peng, Liu Wei. Anl2/l1regularization framework for diverse learning tasks[J]. Signal Processing, 2015, 109: 206-211

[33]Wang Jinjun, Yang Jianchao, Yu Kai, et al. Locality-constrained linear coding for image classification[C] //Proc of IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3360-3367

[34]Richard O D, Peter E H, David G S. Pattern Classification[M]. New York: Wiley, 2001

[35]Jerome F, Trevor H, Robert T. The Elements of Statistical Learning: Data Mining, Inference, and Prediction[M]. Berlin: Springer, 2001: 534-553

[36]Yan Hui, Jian Y. Sparse discriminative feature selection[J]. Pattern Recognition, 2015, 48(5): 1827-1835

[37]Zhang Pan, Lian Qiusheng. Low-rank relaxed collaborative representation combined with global and local features for face recognition[J]. Journal of Computer Research and Development, 2014, 51(12): 2663-2670 (in Chinese)

(張盼, 練秋生. 融合整體與局部特征的低秩松弛協作表示[J]. 計算機研究與發展, 2014, 51(12): 2663-2670)

[38]Zheng Zhonglong, Huang Xiaoqiao, Chen Zhongyu, et al. Regression analysis of locality preserving projections via sparse penalty[J]. Information Sciences, 2015, 303: 1-14

[39]Naseem I, Togneri R, Bennamoun M. Linear regression for face recognition[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 32(11): 2106-2112

[40]Rajat R, Battle A, Lee H, et al. Self-taught learning: Transfer learning from unlabeled data[C] //Proc of the 20th Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2006: 801-808

[41]Liu J, Ji S, Ye J. SLEP: Sparse learning with efficient projections[CP/OL]. Arizona: Arizona State University, 2009[2014-10-12]. http://www.public.asu.edu/～jye02/Software/SLEP

[42]Salman A M, Romberg J. Dynamic updating forl1minimization[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 421-434

[43]Beck A, Teboulle M. A fast iterative shrinkage thresholding algorithm for linear inverse problems[J]. SIAM Journal of Imaging Sciences, 2009, 2(1): 183-202

[44]Boyd S, Vandenberghe L. Convex Optimization[M]. Cambridge, UK: Cambridge University Press, 2009

[45]Yang Meng, Zhang Lei, Yang Jian, et al. Regularized robust coding for face recognition[J]. IEEE Trans on Image Processing, 2013, 22(5): 1753-1766

Zheng Jianwei, born in 1982. PhD and associate professor at Zhejiang University of Technology. His main research interests include machine learning, data mining, and computer vision.

Yang Ping, born in 1992. Master candidate at Zhejiang University of Technology. His main research interests include machine learning, data mining, and computer vision (2111412076@zjut.edu.cn).

Wang Wanliang, born in 1957. PhD and professor at Zhejiang University of Technology. His main research interests include deep learning, artificial intelligence and network control (wwl@zjut.edu.cn).

Bai Cong, born in 1981. PhD and lecturer at Zhejiang University of Technology. His main research interests include imagevideo retrieval and computer vision (congbai@zjut.edu.cn).

Kernel Sparse Representation Classification with Group Weighted Constraints

Zheng Jianwei, Yang Ping, Wang Wanliang, and Bai Cong

(CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023)

A new classification method called KWGSC (kernel weighted group sparse representation classifier) is proposed for pattern recognition. KWGSC integrates both group sparsity and data locality in the kernel feature space rather than in the original feature space. KWGSC can learn more discriminating sparse representation coefficients for classification. The iteratively update solution of thel2,p-norm minimization problem for KWGSC is also presented. There are several appealing aspects associated with KWGSC. Firstly, by mapping the data into the kernel feature space, the so-called norm normalization problem that may be encountered when directly applying sparse representation to non-normalized data classification tasks will be naturally alleviated. Secondly, the label of a query sample can be inferred more precisely by using of distance constraints and reconstruction constraints in together. Thirdly, thel2,pregularization (wherep∈(0,1]) is introduced to adjust the sparsity of collaborative mechanism for better performance. Numeric example shows that KWGSC is able to perfectly classify data with different normalization strategy, while conventional linear representation algorithms fail completely. Comprehensive experiments on widely used public databases also show that KWGSC is a robust discriminative classifier with excellent performance, being outperforming other state-of-the-art approaches.

sparse representation (SR); locality-constraint; group sparse regularizer; kernel trick; norm normalization problem

2015-08-11；

2016-02-16

國家自然科學基金項目(61602413,61379123,61502424)；國家科技支撐計劃基金項目(2012BAD10B01)；浙江省自然科學基金項目(LY15F030014,LY15F020028)

TP391.4

This work was supported by the National Natural Science Foundation of China (61602413, 61379123, 61502424), the National Key Technology R&D Program of China (2012BAD10B01), and the Natural Science Foundation of Zhejiang Province of China (LY15F030014, LY15F020028).