基于L1-范數(shù)的最大間距準(zhǔn)則

陳思寶，陳道然，羅　斌

(1.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，安徽合肥 230601； 2.安徽省工業(yè)圖像處理與分析重點實驗室，安徽合肥 230039)

?

基于L1-范數(shù)的最大間距準(zhǔn)則

陳思寶1,2，陳道然1,2，羅斌1,2

(1.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，安徽合肥 230601； 2.安徽省工業(yè)圖像處理與分析重點實驗室，安徽合肥 230039)

在進(jìn)行線性投影降維時，由于傳統(tǒng)的最大間距準(zhǔn)則(Maximum Margin Criterion，MMC)算法基于L2-范數(shù)，易于受到野值(outliers)及噪聲的影響.該文提出一種基于L1-范數(shù)的最大間距準(zhǔn)則(L1-norm-based MMC，MMC-L1)降維方法，它充分利用L1-范數(shù)對野值及噪聲的強魯棒性以及最大間距準(zhǔn)則，提出了一種快速迭代優(yōu)化算法，并給出了其單調(diào)收斂到局部最優(yōu)的證明.在多個圖像數(shù)據(jù)庫上的實驗驗證了該方法的魯棒性與高效性.

最大間距準(zhǔn)則(MMC)；L1-范數(shù)；線性投影；降維

1　引言

在統(tǒng)計模式識別和圖像處理領(lǐng)域中，高維數(shù)據(jù)是限制多種模式識別技術(shù)的主要因素.當(dāng)訓(xùn)練樣本的數(shù)目相對于特征數(shù)目較小時，大量的特征會降低分類器的性能，而且會出現(xiàn)由“維數(shù)災(zāi)難”[1]造成的“峰化現(xiàn)象”.此外，在高維空間中存在著測度的“集中現(xiàn)象”，即樣本數(shù)據(jù)點之間距離的度量可區(qū)分性隨著樣本數(shù)據(jù)維數(shù)的增加而減弱.為了克服這些問題并且使得后續(xù)的數(shù)據(jù)表示或分類更加穩(wěn)健，對高維數(shù)據(jù)進(jìn)行降維就成了一個非常重要的步驟.

眾所周知，經(jīng)典的線性投影降維方法通常將高維訓(xùn)練數(shù)據(jù)用向量形式進(jìn)行表示，再進(jìn)行線性投影降維和特征提取，其中最經(jīng)典的特征提取方法主要有主成分分析(Principal Component Analysis，PCA)、線性判別分析(Fisher Linear Discriminant Analysis，LDA)[1]和最大間距準(zhǔn)則(MMC)[2,3].PCA中的線性轉(zhuǎn)換矩陣W∈Rp×q由樣本協(xié)方差矩陣的最大特征向量(主成分)構(gòu)成，它盡可能的保持方差中的信息，并通過擴展正交成分上的數(shù)據(jù)，獲得較小的重構(gòu)誤差.但是最大特征值對應(yīng)的特征向量所提供的去相關(guān)和統(tǒng)計顯著性的測量并不能保證分類器中類別的必要結(jié)構(gòu)信息.此外，與模型相關(guān)的分類信息可能會被忽略，因此PCA在很大意義上是次優(yōu)的.LDA[1]選擇使得Fisher準(zhǔn)則函數(shù)達(dá)到最大的向量作為最佳投影方向，從而使得訓(xùn)練樣本在該方向上投影后，得到最大的類間離散度和最小的類內(nèi)離散度.然而，在人臉圖像識別領(lǐng)域存在著大量的典型的小樣本問題，在該類問題中，類內(nèi)散布矩陣通常是奇異的.這主要是因為待識別圖像向量的維數(shù)較高，而在實際問題中難以找到或根本不可能找到足夠多的訓(xùn)練樣本來保證類內(nèi)散布矩陣的可逆性.

為了避免模式識別中的小樣本問題，Li[2]、Song[3]等人提出了一種基于最大間距準(zhǔn)則(MMC)[2,3]的特征抽取方法，它是基于特征空間的類間散度與類內(nèi)散度的差的最大化，其目的是尋求一組最佳鑒別矢量為投影軸進(jìn)行投影變換，使得特征空間樣本的類間散度的最大，類內(nèi)散度最小.然而，MMC是基于L2-范數(shù)來計算相應(yīng)的目標(biāo)函數(shù).當(dāng)訓(xùn)練數(shù)據(jù)中存在野值或噪聲時，所取得的投影方向不穩(wěn)定，因為L2-范數(shù)中的平方操作放大了野值的影響，因此亟待需要解決MMC的魯棒性問題.

顯而易見，相對于L2-范數(shù)，L1-范數(shù)[4～7]中的絕對值操作減弱了對野值的影響，因此L1-范數(shù)對野值具有很強的魯棒性.最新文獻(xiàn)中也出現(xiàn)了基于L1-范數(shù)的線性投影降維方法，諸如：基于L1-范數(shù)的PCA(L1-norm-based Principal Component Analysis，PCA-L1)[4]及基于L1-范數(shù)的LDA(L1-norm-based Fisher Linear Discriminant Analysis，LDA-L1)[5,6].PCA-L1通過最大化特征空間中的基于L1-范數(shù)的方差以獲得局部最優(yōu)投影向量，但是PCA-L1沒有充分利用訓(xùn)練數(shù)據(jù)中的類別信息以獲得更有判別能力的投影方向.LDA-L1通過最大化基于L1-范數(shù)的類間離散度和基于L1-范數(shù)的類內(nèi)離散度的比率以獲得局部最優(yōu)投影向量.

受L1-范數(shù)在PCA與LDA上運用取得的強魯棒性的啟發(fā)，為了克服MMC在數(shù)據(jù)含噪和有野值情況下的脆弱性，本文提出基于L1-范數(shù)的最大間距準(zhǔn)則，即MMC-L1.MMC-L1不僅充分利用L1-范數(shù)對野值及噪聲的強魯棒性，而且充分利用最大間距準(zhǔn)則以獲得更具有判別能力的投影方向.相比于以前的方法對野值及噪聲具有更強的魯棒性，并且在分類識別的性能上取得了顯著提高.

2　基于L1-范數(shù)的最大間距準(zhǔn)則

2.1問題公式化

J(W)=tr(WTSbW-αWTSwW)

(1)

通過簡單的轉(zhuǎn)換，式(1)可以寫成

(2)

從式(2)中可以看出，MMC的目標(biāo)函數(shù)依據(jù)L2-范數(shù)距離準(zhǔn)則.然而，平方操作會放大異常值的影響，因此，基于L1-范數(shù)的最大間距準(zhǔn)則的目標(biāo)函數(shù)如下：

(3)

(4)

其中，wTw=1.根據(jù)式(4)所求的一系列最優(yōu)解也許不同于根據(jù)式(3)所求的最優(yōu)解，但是它旨在尋求一個充分逼近.然而，絕對值操作并不是可微的，因此不易于直接獲得式(4)的全局最優(yōu)解.下面一節(jié)，描述了利用一個迭代算法找到式(4)局部最優(yōu)解的過程.

2.2尋找MMC-L1單個投影方向

我們采用一種梯度法來迭代計算MMC-L1最優(yōu)投影方向w.在迭代的第t(t=0,1,2,…)步時，由于目標(biāo)函數(shù)J(w(t))中存在絕對值符號，然而絕對值操作是非凸的，故為了消除絕對值符號，分別定義符號函數(shù):

(5)

再利用w(t+1)=w(t)+γg(w(t))來更新MMC-L1最優(yōu)投影方向w(t)，其中

(6)

0<γ<1為學(xué)習(xí)步長.循環(huán)交替計算式(5)的符號函數(shù)及式(6)的梯度公式來求解MMC-L1最優(yōu)投影方向w.在迭代過程中，若目標(biāo)函數(shù)J(w(t+1))停止增長，則終止循環(huán).否則，更新符號函數(shù)式(5)并繼續(xù)循環(huán)，直到找到滿足條件的投影向量w.由下一節(jié)的迭代收斂性可知，在每次循環(huán)計算式(5)與式(6)后，式(4)中的目標(biāo)函數(shù)J(w(t+1))都保持非降.

2.3MMC-L1多個投影方向擴展

(7)

(8)

(9)

算法1MMC-L1算法

輸出：投影矩陣W=[w1,…,wq]∈Rp×q.

1.記l=0，Wl為空；

2.計算投影向量wl+1:

②初始化：設(shè)迭代次數(shù)t=0，并生成一個任意p維的非零向量β(0)；

③計算符號函數(shù)：

④更新為β(t+1)=β(t)+γg(t)，其中

4.合并Wl，wl+1:Wl+1=[Wl,wl+1]，其中

5.如果l+1

3　實驗結(jié)果及分析

為了驗證所提出的MMC-L1方法的魯棒性及最終識別性能，本文選擇在3個常用的人臉圖像數(shù)據(jù)庫(AR[9]、ORL[10]及Extended Yale B[11])上進(jìn)行先降維后分類識別的對比實驗.在實驗中，我們選擇六種對比方法，分別是MMC-L1、MMC、LDA-L1、LDA、PCA-L1和PCA.為了保證實驗結(jié)果的公平與合理性，同類實驗中的參數(shù)設(shè)置均一致.為簡化實驗，我們先采用最近鄰分類器進(jìn)行分類識別，再測試不同分類器對識別率的影響.

3.1AR人臉數(shù)據(jù)庫

AR[9]人臉數(shù)據(jù)庫由西班牙巴塞羅那計算機視覺中心建立，包括3120幅圖像，共120個人，每人26幅圖像，采集環(huán)境中的攝像機參數(shù)、光照環(huán)境、攝像機距離等都受到嚴(yán)格控制.所有人臉圖像都被縮放到50×40大小，量化到256級灰度.

3.1.1權(quán)重參數(shù)α對識別率的影響

本節(jié)展示了MMC-L1和MMC中的權(quán)重參數(shù)α對識別率的影響.其中每類的前一半作為訓(xùn)練集，余下的作為測試集.權(quán)重參數(shù)α的大小依次為0.0001、0.0005、0.001、0.005、0.01、0.05、0.1、0.5、1、5、10，實驗效果如圖1所示.

圖1表明，在提取投影向量的過程中，隨著權(quán)重參數(shù)α的逐漸增加，MMC的識別率逐漸增加，而MMC-L1的識別率先逐漸升高再逐漸降低.當(dāng)α<10時，MMC-L1的識別率高于MMC，因此選擇一個合適的權(quán)重參數(shù)α至關(guān)重要.

3.1.2測試訓(xùn)練集的大小對識別率的影響

為了驗證不同的訓(xùn)練集大小對識別率的影響，本節(jié)選擇每類中前k(k=2,…,20)幅圖像作為訓(xùn)練集，余下的作為測試集.實驗效果如圖2所示.

圖2表明，同等條件下，隨著訓(xùn)練樣本數(shù)目的增多，與其它方法相比，MMC-L1算法的識別率一直最高，這表明訓(xùn)練集的大小對最終識別率有很大的影響，但不影響MMC-L1算法的高效性.

3.1.3測試不同的投影軸數(shù)對識別率的影響

線性投影降維是處理高維數(shù)據(jù)的一個重要步驟.為驗證不同的投影軸數(shù)對識別率的影響，本節(jié)依次選擇1,2,…,30個投影軸數(shù)進(jìn)行測試，其中每類的前一半作為訓(xùn)練集，余下的作為測試集.實驗效果如圖3所示.

圖3表明，隨著投影軸數(shù)的逐漸增加，各種方法的識別率逐漸增高，并且當(dāng)投影軸數(shù)足夠大時，識別率都達(dá)到一個飽和值.然而，當(dāng)投影軸數(shù)相同時，MMC-L1方法的識別率比其它方法的識別率高.

3.2ORL人臉數(shù)據(jù)庫

ORL[10]數(shù)據(jù)庫是一個最為常用的人臉數(shù)據(jù)庫，它由40個人，每個人10幅92×112的灰度人臉正面圖像組成，每張人臉圖像都有姿態(tài)、表情和面部飾物的變化.所有的人臉圖像都被縮放到64×64大小，量化到256級灰度.

測試噪聲對識別率的影響:為了驗證MMC-L1對噪聲的魯棒性，本節(jié)在加有高斯噪聲或椒鹽噪聲的人臉圖像上進(jìn)行對比分類識別實驗.圖4(a)和圖4(b)分別為加入高斯噪聲和椒鹽噪聲后的部分圖像示例，圖像加入高斯噪聲的方差或椒鹽噪聲的密度從小到大依次為0.0001、0.0005、0.001、0.005、0.01、0.05、0.1.實驗效果如圖5所示.

圖5表明，當(dāng)噪聲的方差或密度較小時，MMC-L1和LDA-L1算法的識別率相差很小，但是隨著噪聲方差或密度的逐漸增加，MMC-L1的識別率高于LDA-L1的識別率，而且一直高于其它算法的識別率，這說明當(dāng)受到較強的外界條件干擾時，MMC-L1具有更好的魯棒性.

3.3Extended Yale B人臉數(shù)據(jù)庫

Extended Yale B[11]人臉數(shù)據(jù)庫包含38個人共2414幅圖片，其中人臉圖像的姿態(tài)和光照變化都是在嚴(yán)格控制的條件下采集的.本節(jié)依據(jù)文獻(xiàn)[11]的方法將Extended Yale B人臉數(shù)據(jù)庫分成5個子庫，分別為subfea1、subfea2、subfea3、subfea4和subfea5，其中subfea1中的圖像光照強度正常，而subfea2、subfea3、subfea4和subfea5的光照強度依次減弱，因此本部分為了去除光照強度對實驗效果的影響，選擇Extended Yale B數(shù)據(jù)庫中光照條件較好的兩個子庫subfea1和subfea2分別作為訓(xùn)練集和測試集，所有人臉圖像都被縮放到32×32大小，量化到256級灰度.

3.3.1測試不同大小的隨機缺失遮擋塊對識別率的影響

為了驗證所提出的MMC-L1的魯棒性，本節(jié)對訓(xùn)練集subfea1中的人臉圖像設(shè)置不同比例的缺失或遮擋，設(shè)置人臉圖像缺失或遮擋的百分比分別為5%、10%，15%，20%，25%，30%，35%，40%、45%、50%.圖6(a)為部分不同比例塊隨機缺失示例，圖6(b)為部分不同比例塊隨機遮擋示例.實驗效果如圖7所示.

圖7表明，當(dāng)圖像的隨機缺失遮擋比例逐漸增大時，各種算法的識別率逐漸降低，而且MMC-L1的識一直高于其它算法的識別率，這說明MMC-L1具有較強的魯棒性.

3.3.2測試不同分類器對識別率的影響

為了測試不同分類器對所提方法最終識別率的影響，本節(jié)選擇3個常用的分類器(最近鄰分類器、SVM分類器和最近中心分類器)來測試各個算法的最終識別率.選擇子庫subfea1和subfea2分別作為訓(xùn)練集和測試集，并在測試某一個分類器的過程中設(shè)置不同的降維投影軸數(shù)，圖8顯示了各種方法隨著不同的投影維數(shù)在三種分類器下的識別率變化趨勢.

從圖8(a)～(c)可知，對同一分類器，當(dāng)改變投影軸數(shù)時，識別率會隨著投影軸數(shù)的增加而提高，并且在三個不同分類器的實驗中MMC-L1的識別率一致最高，其中采用SVM分類器時MMC-L1的識別率最高，因此可知在三種常見的分類器下，MMC-L1表現(xiàn)出一致的較高識別性能.

4　結(jié)束語

本文在PCA-L1、LDA-L1和MMC方法的基礎(chǔ)上，提出基于L1-范數(shù)的最大間距準(zhǔn)則(MMC-L1).該方法充分利用L1-范數(shù)對野值及噪聲的強魯棒性，充分利用最大間距準(zhǔn)則，提出了一個單調(diào)優(yōu)化迭代算法來求解其最優(yōu)投影矩陣，并給出了其單調(diào)收斂到局部最優(yōu)的證明.在多個圖像數(shù)據(jù)庫上的實驗結(jié)果表明，所提出的MMC-L1對野值及噪聲具有強魯棒性，并且比其它方法具有更好的識別性能.注意到，本文所提出的方法僅僅是收斂到局部最優(yōu).在后續(xù)的工作中，我們將繼續(xù)深入研究如何找到全局最優(yōu).

[1]Duda R O,Hart P E,Stork D G.Pattern Classification[M].Second Edition.New York:John Wiley & Sons,2001.2-4.

[2]Haifeng Li,Tao Jiang,Keshu Zhang.Efficient and robust feature extraction by maximum margin criterion[J].IEEE Transactions on Neural Networks,2006,17(1):157-165.

[3]Fengxi Song,David Zhang,Qinglong Chen,et al.Face recognition based on a novel linear discriminant criterion[J].Pattern Anal Applic,2007,10(3):165-174.

[4]Kwak N.Principal component analysis based on L1-norm maximization[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(9):1672-1680.

[5]Haixian Wang,Xuesong Lu,Zilan Hu,et al.Fisher discriminant analysis with L1-norm[J].IEEE Transactions on Cybernetics,2013,44(6):828-842.

[6]Fujin Zhong,Jiashu Zhang.Linear discriminant analysis based on L1-norm maximization[J].IEEE Transactions on Image Processing,2013,22(8):3018-3027.

[7]Haixian Wang,Qin Tang,Wenming Zheng.L1-norm-based common spatial patterns[J].IEEE Transactions on Biomedical Engineering,2012,59(3):653-662.

[8]Obozinski G,Bach F,Jenatton R.Structured sparse principal component analysis[J].HAL-INRIA,2009,43(6):1505-1527.

[9]Martinez A M,Benavente R.The AR Face Database[R].USA:Purdue University,1998.

[10]Samaria F,Harter A.Parameterisation of a stochastic model for human face identification[A].Proceedings of the Second IEEE Workshop on Applications of Computer Vision[C].Sarasota:IEEE,1994.138-142.

[11]Imran Naseem,Roberto Togneri,Mohammed Bennamoun.Linear regression for face recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(11):2106-2112.

陳思寶男，1979年8月出生于安徽天長.現(xiàn)為安徽大學(xué)副教授，碩士生導(dǎo)師，目前從事圖像處理與模式識別方面的研究.

E-mail:sbchen@ahu.edu.cn

陳道然女，1989年5月出生于河南信陽.現(xiàn)為安徽大學(xué)計算機應(yīng)用技術(shù)專業(yè)碩士研究生，主要從事圖像處理與模式識別方面的研究.

E-mail：youzi-90@163.com

羅斌男，1963年5月出生于安徽合肥，現(xiàn)為安徽大學(xué)計算機應(yīng)用技術(shù)系博士生導(dǎo)師，主要從事計算機視覺與模式識別方面的研究.

L1-Norm-Based Maximum Margin Criterion

CHEN Si-bao1,2,CHEN Dao-ran1,2,LUO Bin1,2

(1.SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei,Anhui230601,China;2.KeyLaboratoryforIndustrialImageProcessingandAnalysisofAnhuiProvince,Hefei,Anhui230039,China)

When performing dimensionality reduction with linear projections,maximum margin criterion (MMC) is often affected by outliers and noises due to L2-norm.In this paper,L1-norm-based maximum margin criterion (MMC-L1) is proposed for dimensionality reduction.It makes full use of Maximum Margin Criterion and strong robustness of L1-norm to outliers and noises.A rapid iterative optimization algorithm,with its proof of monotonic convergence to local optimum,is given.Experiments on several public image databases verify the robustness and efficiency of the proposed method.

maximum margin criterion (MMC);L1-norm;linear projection;dimensionality reduction

2014-12-01;修回日期:2015-05-05;責(zé)任編輯：梅志強

國家863計劃項目(No.2014AA015104);國家自然科學(xué)基金(No.61202228，No.61472002);安徽省高校自然科學(xué)研究重點項目(No.KJ2012A004);安徽省電力公司科技項目(No.521200130MOU，No.5212M01353B4)

TP391.4

A

0372-2112 (2016)06-1383-06