基于L1-范数的最大间距准则

陈思宝，陈道然，罗　斌

(1.安徽大学计算机科学与技术学院，安徽合肥 230601； 2.安徽省工业图像处理与分析重点实验室，安徽合肥 230039)



基于L1-范数的最大间距准则

陈思宝1,2，陈道然1,2，罗斌1,2

(1.安徽大学计算机科学与技术学院，安徽合肥 230601； 2.安徽省工业图像处理与分析重点实验室，安徽合肥 230039)

在进行线性投影降维时，由于传统的最大间距准则(Maximum Margin Criterion，MMC)算法基于L2-范数，易于受到野值(outliers)及噪声的影响.该文提出一种基于L1-范数的最大间距准则(L1-norm-based MMC，MMC-L1)降维方法，它充分利用L1-范数对野值及噪声的强鲁棒性以及最大间距准则，提出了一种快速迭代优化算法，并给出了其单调收敛到局部最优的证明.在多个图像数据库上的实验验证了该方法的鲁棒性与高效性.

最大间距准则(MMC)；L1-范数；线性投影；降维

1　引言

在统计模式识别和图像处理领域中，高维数据是限制多种模式识别技术的主要因素.当训练样本的数目相对于特征数目较小时，大量的特征会降低分类器的性能，而且会出现由“维数灾难”[1]造成的“峰化现象”.此外，在高维空间中存在着测度的“集中现象”，即样本数据点之间距离的度量可区分性随着样本数据维数的增加而减弱.为了克服这些问题并且使得后续的数据表示或分类更加稳健，对高维数据进行降维就成了一个非常重要的步骤.

众所周知，经典的线性投影降维方法通常将高维训练数据用向量形式进行表示，再进行线性投影降维和特征提取，其中最经典的特征提取方法主要有主成分分析(Principal Component Analysis，PCA)、线性判别分析(Fisher Linear Discriminant Analysis，LDA)[1]和最大间距准则(MMC)[2,3].PCA中的线性转换矩阵W∈Rp×q由样本协方差矩阵的最大特征向量(主成分)构成，它尽可能的保持方差中的信息，并通过扩展正交成分上的数据，获得较小的重构误差.但是最大特征值对应的特征向量所提供的去相关和统计显著性的测量并不能保证分类器中类别的必要结构信息.此外，与模型相关的分类信息可能会被忽略，因此PCA在很大意义上是次优的.LDA[1]选择使得Fisher准则函数达到最大的向量作为最佳投影方向，从而使得训练样本在该方向上投影后，得到最大的类间离散度和最小的类内离散度.然而，在人脸图像识别领域存在着大量的典型的小样本问题，在该类问题中，类内散布矩阵通常是奇异的.这主要是因为待识别图像向量的维数较高，而在实际问题中难以找到或根本不可能找到足够多的训练样本来保证类内散布矩阵的可逆性.

为了避免模式识别中的小样本问题，Li[2]、Song[3]等人提出了一种基于最大间距准则(MMC)[2,3]的特征抽取方法，它是基于特征空间的类间散度与类内散度的差的最大化，其目的是寻求一组最佳鉴别矢量为投影轴进行投影变换，使得特征空间样本的类间散度的最大，类内散度最小.然而，MMC是基于L2-范数来计算相应的目标函数.当训练数据中存在野值或噪声时，所取得的投影方向不稳定，因为L2-范数中的平方操作放大了野值的影响，因此亟待需要解决MMC的鲁棒性问题.

显而易见，相对于L2-范数，L1-范数[4～7]中的绝对值操作减弱了对野值的影响，因此L1-范数对野值具有很强的鲁棒性.最新文献中也出现了基于L1-范数的线性投影降维方法，诸如：基于L1-范数的PCA(L1-norm-based Principal Component Analysis，PCA-L1)[4]及基于L1-范数的LDA(L1-norm-based Fisher Linear Discriminant Analysis，LDA-L1)[5,6].PCA-L1通过最大化特征空间中的基于L1-范数的方差以获得局部最优投影向量，但是PCA-L1没有充分利用训练数据中的类别信息以获得更有判别能力的投影方向.LDA-L1通过最大化基于L1-范数的类间离散度和基于L1-范数的类内离散度的比率以获得局部最优投影向量.

受L1-范数在PCA与LDA上运用取得的强鲁棒性的启发，为了克服MMC在数据含噪和有野值情况下的脆弱性，本文提出基于L1-范数的最大间距准则，即MMC-L1.MMC-L1不仅充分利用L1-范数对野值及噪声的强鲁棒性，而且充分利用最大间距准则以获得更具有判别能力的投影方向.相比于以前的方法对野值及噪声具有更强的鲁棒性，并且在分类识别的性能上取得了显著提高.

2　基于L1-范数的最大间距准则

2.1问题公式化

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

(1)

通过简单的转换，式(1)可以写成

(2)

从式(2)中可以看出，MMC的目标函数依据L2-范数距离准则.然而，平方操作会放大异常值的影响，因此，基于L1-范数的最大间距准则的目标函数如下：

(3)

(4)

其中，wTw=1.根据式(4)所求的一系列最优解也许不同于根据式(3)所求的最优解，但是它旨在寻求一个充分逼近.然而，绝对值操作并不是可微的，因此不易于直接获得式(4)的全局最优解.下面一节，描述了利用一个迭代算法找到式(4)局部最优解的过程.

2.2寻找MMC-L1单个投影方向

我们采用一种梯度法来迭代计算MMC-L1最优投影方向w.在迭代的第t(t=0,1,2,…)步时，由于目标函数J(w(t))中存在绝对值符号，然而绝对值操作是非凸的，故为了消除绝对值符号，分别定义符号函数:

(5)

再利用w(t+1)=w(t)+γg(w(t))来更新MMC-L1最优投影方向w(t)，其中

(6)

0<γ<1为学习步长.循环交替计算式(5)的符号函数及式(6)的梯度公式来求解MMC-L1最优投影方向w.在迭代过程中，若目标函数J(w(t+1))停止增长，则终止循环.否则，更新符号函数式(5)并继续循环，直到找到满足条件的投影向量w.由下一节的迭代收敛性可知，在每次循环计算式(5)与式(6)后，式(4)中的目标函数J(w(t+1))都保持非降.

2.3MMC-L1多个投影方向扩展

(7)

(8)

(9)

算法1MMC-L1算法

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

1.记l=0，Wl为空；

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

②初始化：设迭代次数t=0，并生成一个任意p维的非零向量β(0)；

③计算符号函数：

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

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

5.如果l+1

3　实验结果及分析

为了验证所提出的MMC-L1方法的鲁棒性及最终识别性能，本文选择在3个常用的人脸图像数据库(AR[9]、ORL[10]及Extended Yale B[11])上进行先降维后分类识别的对比实验.在实验中，我们选择六种对比方法，分别是MMC-L1、MMC、LDA-L1、LDA、PCA-L1和PCA.为了保证实验结果的公平与合理性，同类实验中的参数设置均一致.为简化实验，我们先采用最近邻分类器进行分类识别，再测试不同分类器对识别率的影响.

3.1AR人脸数据库

AR[9]人脸数据库由西班牙巴塞罗那计算机视觉中心建立，包括3120幅图像，共120个人，每人26幅图像，采集环境中的摄像机参数、光照环境、摄像机距离等都受到严格控制.所有人脸图像都被缩放到50×40大小，量化到256级灰度.

3.1.1权重参数α对识别率的影响

本节展示了MMC-L1和MMC中的权重参数α对识别率的影响.其中每类的前一半作为训练集，余下的作为测试集.权重参数α的大小依次为0.0001、0.0005、0.001、0.005、0.01、0.05、0.1、0.5、1、5、10，实验效果如图1所示.

图1表明，在提取投影向量的过程中，随着权重参数α的逐渐增加，MMC的识别率逐渐增加，而MMC-L1的识别率先逐渐升高再逐渐降低.当α<10时，MMC-L1的识别率高于MMC，因此选择一个合适的权重参数α至关重要.

3.1.2测试训练集的大小对识别率的影响

为了验证不同的训练集大小对识别率的影响，本节选择每类中前k(k=2,…,20)幅图像作为训练集，余下的作为测试集.实验效果如图2所示.

图2表明，同等条件下，随着训练样本数目的增多，与其它方法相比，MMC-L1算法的识别率一直最高，这表明训练集的大小对最终识别率有很大的影响，但不影响MMC-L1算法的高效性.

3.1.3测试不同的投影轴数对识别率的影响

线性投影降维是处理高维数据的一个重要步骤.为验证不同的投影轴数对识别率的影响，本节依次选择1,2,…,30个投影轴数进行测试，其中每类的前一半作为训练集，余下的作为测试集.实验效果如图3所示.

图3表明，随着投影轴数的逐渐增加，各种方法的识别率逐渐增高，并且当投影轴数足够大时，识别率都达到一个饱和值.然而，当投影轴数相同时，MMC-L1方法的识别率比其它方法的识别率高.

3.2ORL人脸数据库

ORL[10]数据库是一个最为常用的人脸数据库，它由40个人，每个人10幅92×112的灰度人脸正面图像组成，每张人脸图像都有姿态、表情和面部饰物的变化.所有的人脸图像都被缩放到64×64大小，量化到256级灰度.

测试噪声对识别率的影响:为了验证MMC-L1对噪声的鲁棒性，本节在加有高斯噪声或椒盐噪声的人脸图像上进行对比分类识别实验.图4(a)和图4(b)分别为加入高斯噪声和椒盐噪声后的部分图像示例，图像加入高斯噪声的方差或椒盐噪声的密度从小到大依次为0.0001、0.0005、0.001、0.005、0.01、0.05、0.1.实验效果如图5所示.

图5表明，当噪声的方差或密度较小时，MMC-L1和LDA-L1算法的识别率相差很小，但是随着噪声方差或密度的逐渐增加，MMC-L1的识别率高于LDA-L1的识别率，而且一直高于其它算法的识别率，这说明当受到较强的外界条件干扰时，MMC-L1具有更好的鲁棒性.

3.3Extended Yale B人脸数据库

Extended Yale B[11]人脸数据库包含38个人共2414幅图片，其中人脸图像的姿态和光照变化都是在严格控制的条件下采集的.本节依据文献[11]的方法将Extended Yale B人脸数据库分成5个子库，分别为subfea1、subfea2、subfea3、subfea4和subfea5，其中subfea1中的图像光照强度正常，而subfea2、subfea3、subfea4和subfea5的光照强度依次减弱，因此本部分为了去除光照强度对实验效果的影响，选择Extended Yale B数据库中光照条件较好的两个子库subfea1和subfea2分别作为训练集和测试集，所有人脸图像都被缩放到32×32大小，量化到256级灰度.

3.3.1测试不同大小的随机缺失遮挡块对识别率的影响

为了验证所提出的MMC-L1的鲁棒性，本节对训练集subfea1中的人脸图像设置不同比例的缺失或遮挡，设置人脸图像缺失或遮挡的百分比分别为5%、10%，15%，20%，25%，30%，35%，40%、45%、50%.图6(a)为部分不同比例块随机缺失示例，图6(b)为部分不同比例块随机遮挡示例.实验效果如图7所示.

图7表明，当图像的随机缺失遮挡比例逐渐增大时，各种算法的识别率逐渐降低，而且MMC-L1的识一直高于其它算法的识别率，这说明MMC-L1具有较强的鲁棒性.

3.3.2测试不同分类器对识别率的影响

为了测试不同分类器对所提方法最终识别率的影响，本节选择3个常用的分类器(最近邻分类器、SVM分类器和最近中心分类器)来测试各个算法的最终识别率.选择子库subfea1和subfea2分别作为训练集和测试集，并在测试某一个分类器的过程中设置不同的降维投影轴数，图8显示了各种方法随着不同的投影维数在三种分类器下的识别率变化趋势.

从图8(a)～(c)可知，对同一分类器，当改变投影轴数时，识别率会随着投影轴数的增加而提高，并且在三个不同分类器的实验中MMC-L1的识别率一致最高，其中采用SVM分类器时MMC-L1的识别率最高，因此可知在三种常见的分类器下，MMC-L1表现出一致的较高识别性能.

4　结束语

本文在PCA-L1、LDA-L1和MMC方法的基础上，提出基于L1-范数的最大间距准则(MMC-L1).该方法充分利用L1-范数对野值及噪声的强鲁棒性，充分利用最大间距准则，提出了一个单调优化迭代算法来求解其最优投影矩阵，并给出了其单调收敛到局部最优的证明.在多个图像数据库上的实验结果表明，所提出的MMC-L1对野值及噪声具有强鲁棒性，并且比其它方法具有更好的识别性能.注意到，本文所提出的方法仅仅是收敛到局部最优.在后续的工作中，我们将继续深入研究如何找到全局最优.

[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月出生于安徽天长.现为安徽大学副教授，硕士生导师，目前从事图像处理与模式识别方面的研究.

E-mail:sbchen@ahu.edu.cn

陈道然女，1989年5月出生于河南信阳.现为安徽大学计算机应用技术专业硕士研究生，主要从事图像处理与模式识别方面的研究.

E-mail：youzi-90@163.com

罗斌男，1963年5月出生于安徽合肥，现为安徽大学计算机应用技术系博士生导师，主要从事计算机视觉与模式识别方面的研究.

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;责任编辑：梅志强

国家863计划项目(No.2014AA015104);国家自然科学基金(No.61202228，No.61472002);安徽省高校自然科学研究重点项目(No.KJ2012A004);安徽省电力公司科技项目(No.521200130MOU，No.5212M01353B4)

TP391.4

A

0372-2112 (2016)06-1383-06