最小類內方差支持向量引導的字典學習

王曉明,徐 濤,冉 彪

(西華大學 a.計算機與軟件工程學院; b.機器人研究中心,成都 610039)

0 概述

稀疏表達(Spare Representation,SR)利用超完備的基向量有效表示樣本數據,廣泛應用于圖像分類[1-3]、超分辨率[4]、壓縮[5]和去噪[6]等方面。將超完備的基向量稱為字典,其中的每一個基向量稱為原子。模式分類技術利用數據的鑒別信息,從真實樣本數據中學習完備的字典以提高分類效率。此類基于模式分類的字典學習算法被稱為鑒別性字典學習(Discriminative Dictionary Learning,DDL)。

DDL利用具有信息鑒別能力的訓練樣本學習超完備字典以提高編碼系數的鑒別性能,在圖像分類中的廣泛應用使其成為當前研究的熱點之一。研究人員現已提出一系列DDL算法,其中的一種字典學習算法旨在利用字典的重構誤差進行分類。文獻[7]提出結構不一致和共享特性的聚類字典學習算法。文獻[8]提出特定類別的子詞典與細粒度共享的字典學習算法。這兩種字典學習算法結合字典的結構特性,強制性地為字典增加鑒別信息,然而在類別數量巨大的分類任務中不能取得理想的分類結果。另一種字典學習算法通過尋找最優字典提高字典鑒別能力。文獻[9]通過學習字典和分類器對原始KSVD算法[10]進行擴展,提出鑒別性KSVD算法(Discriminative KSVD,D-KSVD),提高了字典的鑒別能力。文獻[11]在D-KSVD算法的基礎上增加一致性類標簽限制條件,提出類標簽一致KSVD算法(Label Consistent KSVD,LC-KSVD),提高了編碼系數的鑒別能力。由于LC-KSVD算法忽略了原子間的相似特征,鑒別性能提高有限,因此文獻[12]提出局部特征和類標嵌入約束的字典學習算法(Locality Constrained and Label Embedding Dictionary Learning,LCLE-DL),在一定程度上解決了原子相似性對鑒別性能的影響問題。文獻[13]提出有監督的邏輯損失函數字典學習策略。文獻[14]闡述了泛化任務驅動字典學習框架。文獻[15]通過間隔最大化思想研究字典學習問題,并采用多類損失函數進行字典學習。文獻[16]提出Fisher鑒別字典學習算法(Fisher Discrimination Dictionary Learning,FDDL),FDDL兼顧重構誤差和編碼系數的鑒別能力,采用類別特性策略學習結構化字典,通過對編碼系數引入Fisher鑒別準則提高字典鑒別能力,但是FDDL算法在處理多樣本的問題中時間開銷較大。文獻[17]提出的大間隔字典學習算法將SVM的大間隔原理作用于字典訓練過程,提高字典的鑒別能力。文獻[18]提出支持向量引導的字典學習算法(Support Vector Guided Dictionary Learning,SVGDL),將標準的SVM[19]作為鑒別項用于編碼系數向量,在編碼系數的更新過程中采用二次合頁損失函數計算其加權距離的平方并更新編碼系數。通過引入固定參變量證明FDDL算法固定的權值分配策略僅是SVGDL算法的特例,并將范數作為稀疏控制條件,表明其在時間效率和識別率上均優于FDDL算法。

本文基于SVGDL算法的權值分配策略,提出最小類內方差支持向量引導的字典學習算法(Minimum Class Variance Support Vector Guided Dictionary Learning,MCVGDL),將MCVSVM算法作為鑒別項并與協作表達(Collaboration Representation,CR)相結合。MCVSVM是對標準SVM的改進,其最優分類超平面更符合數據特征的空間分布情況,也是對標準SVM最優超平面的修正。實驗將MCVGDL算法與SVM、CRC、SRC、KSVD、D-KSVD、LC-KSVD、FDDL和SVGDL算法在多個常用數據集上進行對比。

1 相關工作

1.1 l2范數協作表述理論

鑒于稀疏表達優化l0和l1的時間開銷問題,文獻[20]提出結合最小二乘和l2范數的協作表達算法。文獻[21]進一步分析了協作表達和稀疏表達在分類問題上的工作原理。

(1)

1.2 支持向量引導的字典學習模型

SVGDL[18]是一種改進的鑒別性字典學習模型,其將協作表達式(1)和標準的SVM相結合,通過引入固定參變量,證明了FDDL算法固定分配權值的策略是其自由分配權值的特例。SVGDL算法模型為:

(2)

其中,w是標準SVM的分類超平面,b是對應的偏置,類標簽向量y=[y1,y2,…,yn],β是平衡參數,旨在協調l2范數和鑒別項之間的關系,H(S,y,w,b)定義為:

(3)

1.3 最小類內方差支持向量機

SVM[19]是典型的大間隔分類器,廣泛應用于模式識別和機器學習中。然而,傳統SVM建立的超平面是基于最大間隔原則[14],從而導致該方法僅考慮每類數據邊界上的樣本點,而沒有利用數據的分布信息,因而在一定程度上制約了其泛化能力的進一步提高。針對這一問題,文獻[22]提出最小化類內方差支持向量機。MCVSVM可以看作是一種結合SVM和Fisher線性鑒別的分類器,與標準SVM不同,MCVSVM建立的決策超平面既考慮了數據的邊界信息,又考慮了數據的分布信息。因此,其不易受到例外樣本點和噪音的影響,具有更強的魯棒性和更好的泛化性能。MCVSVM的定義為:

s.t.yi(wTsi+b)≥1-ξi,i=1,2,…,n

(4)

其中,ξ=[ξ1,ξ2,…,ξn]是松弛向量,θ是懲罰系數,控制著錯誤分類數據的懲罰程度,θ越大,懲罰程度越大,θ越小,懲罰程度越小,Sω是類內散度矩陣,其定義為:

(5)

s.t.0≤αi≤θ,i=1,2,…,n,αTy=0

(6)

文獻[23]將二分類MCVSVM擴展成多分類問題,并取得了優于SVM的分類實驗結果。由于MCVSVM兼顧大間隔和數據分布信息,具有更好的魯棒性和泛化能力。因此,MCVGDL使用MCVSVM對SVGDL算法進行改進。

2 MCVGDL算法

SVGDL算法采用標準SVM[19]作為鑒別項,通過大間隔編碼系數引導字典學習,僅考慮每類編碼系數邊界上的樣本點表示系數樣本點,而沒有利用編碼系數的空間分布信息。與SVGDL算法不同,MCVGDL算法采用MCVSVM[22-23]作為編碼系數的鑒別性條件,同時兼顧邊界上的編碼系數及其空間分布信息。

2.1 MCVGDL算法的目標函數

受MCVSVM[22-23]和SVGDL[18]啟發,本文使用MCVSVM替換式(2)中SVGDL算法的鑒別條件,并借鑒文獻[18]的一對多策略建立如式(7)所示的MCVGDL算法目標優化函數:

(7)

2.2 MCVGDL算法的求解

借鑒文獻[18]的求解方法,雖然MCVGDL算法并不是聯合的凸優化問題,但固定其中的多個變量后,式(7)轉化為可交替優化的凸優化問題。因此,采用交替優化策略分別更新字典D、編碼系數矩陣S和MCVSVM分類器{w,b}。

2.2.1 編碼系數S更新

借鑒文獻[18,24]的更新方法,固定字典D、w、b和拉普拉斯矩陣Lc。更新每一個si,目標函數式(7)轉換為如下方式求解:

(8)

(9)

si=A-1B

(10)

其中,I是單位矩陣。

(11)

(12)

2.2.2 字典D更新

借鑒文獻[25]的更新方法,固定編碼系數S、w、b和拉普拉斯矩陣Lc。目標函數式(7)轉變為求解協作表達字典D的更新過程。更新的D的目標函數為:

(13)

該目標函數可以通過文獻[25]的拉格朗日對偶問題求得,給出J(D)的Lagrange函數為:

J(D,λ)=Tr[(X-DS)T(X-DS)]+

s.t.λj>0,?j∈{1,2,…,K}

(14)

其中,λ是Lagrange乘子,可求得其對偶問題為:

Tr(DTD-DST(SST+Λ)-1(DST)T-cΛ)

s.t.λj>0,?j

(15)

其中,Λ=diag(λ),通過求其對偶問題并將所得最優解λ代入DT=(SST+Λ)-1(DST)T,可得字典D的最優解。

2.2.3 MCVSVM的W、b和L更新

固定字典D和編碼系數S,式(7)的優化問題轉變為求解多類MCVSVM的二次規劃問題。本文使用二范數的MCVSVM作為模型式(7)的鑒別條件,同時采用一對多的策略訓練多類模型。二范數的MCVSVM定義如下:

s.t.yi(wTsi+b)≥1-ξi,i=1,2,…,n

(16)

綜合以上更新過程,MCVGDL算法具體步驟如下:

輸出訓練后的字典D、W、b和拉普拉斯矩陣L

1.T=0

2.For i=1 to n

使用式(10)更新si;

else

使用式(12)更新si

end For

3.借鑒分類字典學習算法[25]更新字典D;

4.借鑒最小類內方差支持向量機[22]求解二次規劃問題的方法,更新W、b和拉普拉斯矩陣L;

5.若相鄰兩次迭代后目標函數值之差小于收斂閾值Delta,則迭代終止,否則返回步驟2繼續執行,直到收斂或達到最大迭代次數T終止;

6.End

2.3 分類方法

(17)

3 實驗結果與分析

為保證實驗公平性,本文所有實驗均基于Intel i3-4130 @3.40 GHz的處理器,4 GB內存空間,64位Windows 7旗艦版系統軟件和MATLAB R2013b版本應用軟件。

MCVGDL算法模型涉及3個主要參數,分別是平衡參數α、β和MCVSVM懲罰系數θ。實驗中為防止過擬合的產生,采用交叉驗證方式自由選取參數,并且需綜合多因素以獲得良好的模型性能。對于實驗中涉及的人臉識別數據集和物體識別數據集的參數設置,將在對應的實驗與數據集中給出模型的參數設置。

由于MCVGDL算法是基于協作表達和SVM結合的算法,同時針對SVGDL使用MCVSVM進行改進,因此將基于協作表達的CRC分類算法[20]、基于稀疏表達的SRC分類算法[26]、SVM算法[19]及SVGDL算法[18]在USPS[27]手寫數字數據集上進行實驗對比。同時,與KSVD[10]、D-KSVD[9]、LC-KSVD[11]、LCLE-DL[12]、FDDL[16]、BDLRR[28]等學習算法在人臉識別(Extended Yale B[29]、Yale[30]、ORL[31]和AR[32])和物體識別(COIL20[33]、COIL100[34]和Caltech101[35])數據集上進行實驗對比。LC-KSVD2算法是對LC-KSVD1算法的改進且效果更好,本文中的LC-KSVD特指LC-KSVD2。另外,對于人臉識別數據集還增加了基于稀疏表示和圖像預處理的ASF-SRC算法[36]進行對比。實驗部分給出MCVGDL和其他8種對比算法在Extended Yale B、Yale、ORL、COIL20、COIL100和Caltech101數據集上的實驗結果,比較不同訓練樣本條件下的識別準確率。

由于字典大小(即字典所包含原子的個數)對識別率存在影響,因此為說明字典原子個數K對識別率的影響,本文將分別在Yale B、Yale和ORL 3個人臉數據集上隨機選擇樣本并固定訓練樣本,同時調整KSVD、D-KSVD、LC-KSVD、FDDL、SVGDL和MCVGDL算法的字典原子個數,給出調整字典原子個數后的識別率變化曲線,通過其平均識別率的變化曲線對字典原子個數進行具體分析。

3.1 手寫數字識別

美國郵政的USPS[27]手寫數字數據集收集了9 298張0～9數據的數字圖像,每一張圖像大小為16像素×16像素。雖然該手寫數字數據集中的類別較少,但是簡單的筆畫構成增加了識別難度,使得同類數字的個體特征差異較大,字典學習方法能有效學習其固有特征。對其分別選擇7 291張圖像作為訓練數據,剩余的2 007張作為測試數據。MCVGDL參數設置為α=1e-3、β=1e-7和θ=10,并固定字典原子個數。由于MCVGDL算法采用二范數的正則項作為(協作稀疏表達)稀疏控制條件,使用SVM的大間隔分類理論和Fisher線性鑒別分析作為模型的鑒別性條件引導字典學習,進一步探究了結合SVM的鑒別字典學習方法與基于協作表示和稀疏表示的分類方法的鑒別性能和優勢。因此,在USPS手寫數據集上將MCVGDL和CRC、SRC、SVM、SVGDL算法進行對比。表1是USPS手寫數字的平均識別率,相比于CRC、SRC、SVM算法,本文算法提高了2%～3%,相比于SVGDL算法提高了1%～2%,說明將SVM作為基于協作表達或者基于稀疏表達的字典學習的鑒別條件,可以增強字典模型的鑒別能力,考慮編碼向量的空間分布信息可以有效提高模型的分類性能,在一定程度上增強了模型的泛化性能,使得模型分類能力得到進一步提升。

表1 USPS手寫數字的平均識別率

3.2 人臉識別

3.2.1 Extended Yale B數據集上的實驗結果

由耶魯大學計算視覺與控制中心創建的Extend Yale B人臉數據庫中共有38個類別,包含不同光照條件和面部表情的2 414張正臉圖像。每一個人有64張192像素×168像素的圖像。為保證實驗公平性,采用大小為32像素×32像素的圖像作為實驗數據,并隨機為每一類別選擇數量為5、10、20、30的圖像作為訓練數據,剩余部分作為測試數據。MCVGDL的參數設置為α=2e-3、β=1e-7和θ=20,固定字典原子個數K為190、380、760、1 140,實驗結果如表2所示。

表2 Extended Yale B數據集上的識別率和標準差

3.2.2 Yale數據集上的實驗結果

由耶魯大學計算視覺與控制中心創建的Yale人臉數據集中共有15個類別的165張圖像。每一個人具有11張不同光照、姿態、表情的面部圖像。為保證實驗公平性,采用大小為32像素×32像素的圖像作為訓練數據和測試數據,并隨機為每一類別選擇數量為2、4、6、8的圖像作為訓練集,剩余部分作為測試數據。MCVGDL的參數設置為α=2e-3、β=1e-7和θ=20,固定字典原子個數K為30、60、90、120,實驗結果如表3所示。

表3 Yale數據集上的識別率和標準差

3.2.3 ORL數據集上的實驗結果

由劍橋大學AT&T實驗室創建的ORL人臉數據集包含40個人的400張人臉圖像,每一個類別有10張圖像。該數據集包含每一個人不同時期、視角、表情和面部細節的圖像。為保證實驗公平性,所有實驗采用大小為32像素×32像素的圖像作為訓練數據,并隨機為每一類別選擇數量為2、4、6、8的圖像作為訓練數據,剩余部分作為測試數據。MCVGDL的參數設置為α=2e-3、β=1e-7和θ=20,固定字典原子個數K為80、160、240、320,實驗結果如表4所示。

表4 ORL數據集上的識別率和標準差

3.2.4 AR數據集上的實驗結果

AR人臉數據集包含126個類別且超過4 000張的人臉圖像。與Extended Yale B不同的是,其具有更加豐富的面部表情(微笑、生氣和尖叫等)、光照變化和面部遮擋等。對于AR人臉集,分別選擇50個男性和50個女性共2 600張圖像(每人26張)作為實驗數據,并隨機為每一類別選擇數量為3、5、7的圖像作為訓練數據,剩余部分作為測試數據,參數設置為α=2e-3、β=1e-7和θ=20,固定字典原子個數K為300、500、700,實驗結果如表5所示。

表5 AR數據集上的識別率和標準差

3.3 物體識別

3.3.1 COIL20和COIL100數據集上的實驗結果

由哥倫比亞大學創建的COIL20圖像數據集包含20個類別不同物體從不同角度每隔5秒拍攝的1 440張圖像,每一類別有72張圖像,其大小為32像素×32像素。實驗中隨機為每一類別選擇數量為5、10、20、30的圖像作為訓練數據,剩余部分作為測試數據。圖1是COIL20數據集中的部分樣本圖像。

圖1 COIL20數據集示例圖像

MCVGDL模型的參數設置為α=2e-3、β=1e-7和θ=10,固定字典原子個數K為100、200、400、600,實驗結果如表6所示。

表6 COIL20數據集上的識別率和標準差

COIL100數據集包含了100個類別從不同角度拍攝的7 200張圖像,模型參數設置與COIL20一致,選擇數量為5、10、15、20的圖像作為訓練集,剩余部分作為測試數據,固定字典原子個數K為500、1 000、1 500、2 000,實驗結果如表7所示。

表7 COIL100數據集上的識別率和標準差

3.3.2 Caltech101數據集上的實驗結果

加利福尼亞理工學院創建的Caltech101圖像數據集包含超過29 780張101類的不同物體圖像。由于物體數據集的固有特性,借鑒文獻[11]的實驗布局方式,隨機為每一類別分別選取數量為5、10、15、20的圖像作為訓練數據,剩余部分作為測試數據,并固定字典的原子個數。MCVGDL模型的參數設置為α=2e-3、β=1e-7和θ=10,固定字典原子個數K為510、1 020、1 530、2 040,實驗結果如表8所示。

表8 Caltech101數據集上的識別率和標準差

3.4 字典大小對識別率的影響

字典在稀疏表達和協作表達的應用中具有重要作用,且獲得合適大小的字典也十分重要。字典的大小影響著鑒別性字典的鑒別能力,合適的字典大小有助于提高識別率和降低計算開銷。在限定訓練樣本的前提下,通過字典大小的調節可以保證較高的識別率,同時能降低計算開銷。

針對Extend Yale B隨機為每一類別選擇32張圖像作為訓練數據,字典原子個數K依次按照78,116,154,…,1 218變化,每一次為每一類別增加一個字典原子的方式遞增,即每次增加38個字典原子。每次固定字典原子個數K后,Extend Yale B數據集的實驗結果是20次隨機選擇圖像進行訓練和測試得到的平均識別率。圖2是Extend Yale B數據集上KSVD、D-KSVD、LC-KSVD、FDDL、SVGDL和MCVGDL算法字典原子個數K變化后的識別率曲線。

圖2 Extend Yale B數據集上字典原子數變化情況下的算法識別率比較

針對Yale和ORL數據集分別為每一類別選擇8張圖像作為訓練數據,并固定訓練數據。對于Yale數據集,字典原子個數K依次按照30、45、60、75、90、105、120的大小變化。對于ORL數據集,字典原子個數K依次按照80、120、160、200、240、280、320的大小變化。每次固定字典原子個數K后,Yale和ORL數據集的實驗結果是50次隨機選擇不同訓練和測試樣本得到的平均識別率。圖3和圖4分別給出了Yale和ORL數據集上KSVD、D-KSVD、LC-KSVD、FDDL、SVGDL和MCVGDL算法字典原子個數K變化后的識別率曲線。

圖3 Yale數據集上字典原子數變化情況下的算法識別率比較

圖4 ORL數據集上字典原子數變化情況下算法識別率比較

3.5 結果分析

由于MCVGDL結合了SVM和協作表達,采用MCVSVM對SVGDL算法進行改進,因此本文提出最小類內方差支持向量引導的字典學習算法。該算法不僅考慮每類數據邊界上的樣本點,而且利用數據的分布信息,同時,其采用的MCVSVM可以看作是SVM和Fisher線性鑒別的分類器,與FDDL采用Fisher鑒別條件所不同的是,MCVSVM利用了SVM大間隔原理最大化數據類別間的距離,并自動分配權值,MCVGDL與SVGDL類似,是對FDDL固定分權模式的改進。

表2～表8列出了KSVD、LC-KSVD、D-KSVD等11種算法與本文提出的MCVGDL算法的平均識別率。在Extended Yale B、Yale、ORL和AR數據集上的實驗結果表明,本文算法在小數量的樣本條件下識別率相比于SVM和CRC算法有大幅提升,最高提升了12%,相比于SVGDL和FDDL平均提升了1%～2%,最高提升了3%。隨著樣本數量的增加,MCVGDL算法依然表現出了優于其他算法的分類性能。當訓練樣本數量增加到一定程度時,所有算法均表現出良好的分類性能,然而在大部分情況下MCVGDL分類性能最好,但是訓練樣本的增加必然會增加模型的訓練時間,從而證明MCVGDL算法對于樣本條件的魯棒性,同時說明了采用MCVSVM對SVGDL進行改進的合理性,以及大間隔分類器考慮數據信息分布的必要性。在COIL20不同數量訓練樣本的情況下,當訓練樣本為5時,SVM表現出優于其他算法的分類性能,但是MCVGDL相比于FDDL、SVGDL仍然提高了1%～2%,相比于FDDL、SVGDL和MCVGDL字典學習算法均表現出更好的分類性能。當訓練樣本增加到10和20時,FDDL、SVGDL、KSVD、D-KSVD、LC-KSVD和MCVGDL在分類性能上非常接近,MCVGDL相比于其他算法仍有不同程度的提高,相比于CRC和SRC平均提高了5%,說明將SVM和協作表達相結合可以提高字典的鑒別能力。在COIL100數據集上,訓練樣本為5時,SVM表現出優于其他算法的分類性能。隨著訓練樣本的增加,MCVGDL具有更高的識別率,當訓練樣本個數增加到20時,BDLRR識別率達到87.4%,優于其他算法,但是MCVGDL仍然表現出優于SVGDL的識別率和穩定性,說明了采用MCVSVM對SVGDL改進是有效的。在Caltech101不同訓練樣本的條件下,MCVGDL在大部分情況下的識別率均優于FDDL、KSVD、D-KSVD、LC-KSVD算法,但是在訓練樣本數為5的條件下BDLRR算法的識別率更高。隨著樣本數量的增加,MCVGDL表現出優于SVGDL算法的識別率,表明融合Fisher準則的MCVSVM對SVGDL算法的改進思路是正確有效的。

圖2～圖4是本文算法和其他典型字典學習算法在固定訓練樣本條件下,調整字典原子個數K對識別率的影響。可以看出,MCVGDL和SVGDL算法在3個數據集上(Extended Yale B、Yale和ORL)均表現出了良好的穩定性和識別率。KSVD、D-KSVD、FDDL和LC-KSVD算法在字典原子數量增加到一定程度時,識別率呈現遞減趨勢,尤其是KSVD算法,其對于字典原子大小的選擇非常敏感。MCVGDL和SVGDL都表現出對字典原子數K較強的魯棒性,但是MCVGDL展現出更高的識別率,說明了SVGDL和MCVGDL可以在大樣本條件下,兼顧識別性能和運算性能,選擇合適大小的字典,降低時間開銷,同時保證了良好的識別性能。

不同訓練樣本和字典數量情況下的實驗說明了通過SVM引導字典學習可以獲得更好的分類性能。相比于SVGDL采用標準的SVM作為鑒別項,MSVGDL采用MCVSVM作為鑒別項,既考慮了大間隔原理,也考慮了類內散度(數據的分布信息)。實驗結果表明,改進類內方差的MCVGDL算法可以在一定程度上提高模型的穩定性和識別率。

4 結束語

為提高基于字典學習算法的分類性能,本文利用MCVSVM算法對SVGDL算法進行改進,通過兼顧最大化間隔原理和數據分布信息得到最大化類間間隔和最小化類內方差的分類器,并充分考慮編碼向量的分布信息,保障同類樣本編碼向量總體一致,同時降低向量間對應分量的耦合度及修正SVM分類矢量,充分挖掘編碼向量鑒別信息,從而更好地引導字典學習,提高字典鑒別能力。實驗結果表明,在不同樣本和字典原子數量條件下,該算法對于人臉和物體均具有較高的識別率。但本文采用單一合成字典學習模型,限制了字典鑒別能力的提高,因此融合解析字典與合成字典的雙字典學習算法將是下一步的研究重點。