半监督有局部差异的图嵌入算法*

梁兴柱， 林玉娥， 林玉荣

(1.安徽理工大学 计算机科学与工程学院, 安徽 淮南 232011；2.哈尔滨工业大学 航天学院，黑龙江 哈尔滨 150001)

0 引 言

对于人脸识别任务，如何将高维的数据样本降成一个低维的样本是取得良好识别结果的关键一步，这就需要相应的特征提取算法，目前主要包括二大类特征提取算法，一类是属于无监督的算法，如主成分分析(PCA)[1]和局部保持投影(LPP)[2]算法；另一类是有监督算法，如线性判别分析(LDA)[1]。通常在人脸识别任务中，当标注类别的样本充足时，有监督算法能够获得更好的识别结果。而其中的LPP算法虽然也是无监督算法，但从理论上讲较PCA算法更适合分类，并且也比较容易扩展成为有监督算法，因此，该算法一经提出就受到了广泛的关注。如文献[3]提出的有监督LPP，通过利用样本标签来提高算法的识别性能；但是LPP在保持图像之间的局部结构时，使得邻域内的样本投影后比较接近，当邻域内的样本过于接近时，容易造成邻域内样本之间的差异信息丢失，即过学习问题，使得分类性能不够好，因此,文献[4]则结合信息理论，提出了有监督局部差异投影(SLSDP)算法，并取得了较好的识别结果。

虽然有监督算法能够获得较好的识别性能，但是在现实问题中，更多时候能够获得大量样本，而有类别标签的样本却是少量的，因此，半监督学习算法运用而生。这类算法的目标就是充分利用这些有标签和无标签的数据样本来增加分类精确度。如文献[5]对LDA扩展提出的半监督判别分析(SDA),但是该算法没有用到样本的局部信息，因此，文献[6]和文献[7]分别提出了利用局部信息的半监督算法，但这种只强调局部信息，容易出现过学习问题，且其目标函数存在着小样本问题。本文受文献[4]启发，提出了一种半监督有局部差异的图嵌入算法(SLDGEA)。SLDGEA同时考虑使用有标签样本和无标签样本，在最小化训练样本近邻相似散度的同时，最大化训练样本近邻差异散度，对于两部分样本所起作用的大小，可通过参数来调整。最后人脸库上的实验结果表明了该算法的有效性。

1 相关算法介绍

1.1 局部保持投影算法

假设X=[x1…xi…xN]表示全体训练样本集，N表示样本数目，n表示样本的维数，LPP算法的思想是使得样本降维后在低维空间里尽可能地保持原来的邻近关系。设G={X,S}为无向有权图，每个样本点xi为图中的一个顶点，S为相似度矩阵，Sij表示样本i和j的相似度可按下式计算

(1)

其目标是最小化下式

trWTXLXTW,

(2)

(3)

上述近邻关系是按式(1)来确定的，属于无监督算法，当式(1)中的权值Sij加入训练样本的类别信息，则上面的就有监督算法，有监督算法的Sij计算公式如下

Sij=

(4)

式(3)即是LPP算法的目标函数，同时式(3)也提供了一个统一的线性图嵌入框架，可以通过选择不同的L和D，得到不同的线性特征提取算法，如LPP,UDP和MFA，以及SLSDP算法。

1.2 SLSDP算法

无论是LPP还是有监督的LPP算法，都仅强调了保持图像之间的局部结构，从而将造成邻域内样本之间的差异信息丢失，即过学习问题，从而将使算法性能下降，SLSDP则解决了这一问题。修改上述图嵌入算法框架相应的L和D，则有SLSDP算法的目标函数，其意义是使得所求的W能够有效地保持了图像空间的局部结构的同时，最大化训练样本的近邻差异信息，即

(5)

上式中的近邻系数Sij根据式(4) 计算，差异系数Bij由下式计算

(6)

详细求解可参见文献[4]。

2 SLDGEA

本文所提出的算法实际上是对图嵌入算法框架的扩展，故此称之为SLDGEA，其思想是充分利有标签和无标签的训练样本来构造目标函数，从而使得求出的投影矩阵更有效，达到提高分类效果的目标。首先给出SLDGEA的目标函数。

假设有样本X，其前N个数据样本为有类别标签的,后M个点是不带类别标签，X={XN,XM}={x1,…,xN,xN+1,…,xN+M}，本文算法就是利用这两部分样本来构造目标函数，其意义是要保证在低维子空间中保持原有样本的近邻结构，同时保证样本的差异性，因此,要求所求的基向量w应同时满足

w=arg minwTGLw,

(7)

w=arg maxwTGBw,

(8)

式中GL=XLSXT称之为近邻相似散度矩阵，GB=XLBXT称为近邻差异散度矩阵，考虑到样本部分有标签，部分无标签，因此,wTGLw和wTGBw又要分解成如下形式

wTGLw=wTGL1w+αwTGL2w,

(9)

wTGBw=wTGB1w+βwTGB2w.

(10)

式(9)和式(10)的右边第一部分GL1和GB1是利用有标签样本计算出来的，第二部分GL2和GB2是利用无标签样本计算出来的，α,β∈[0,1]是调节因子，用来控制无标签样本在目标函数中所起作用的大小，对于式(7)和式(8)可以写成一式，因此，综合式(7)和式(8)，加上正交约束条件，可得到SLDGEA的目标函数，而为了避免已有半监督算法的小样本问题，这里采用差形式的目标函数，即

(11)

对于上式的求解，根据Lagrange乘子法构造函数

(12)

(GB-GL)wi=λiwi,i=1,2,…,l.

(13)

最后选择对应前d(通常d

3 实验结果与讨论

本文为了验证提出SLDGEA的性能，分别在ORL (http:∥www.cl.cam.ac.uk/ research/dtg/attarchive/facedatabase.html)和UMIST (http:∥images.ee.umist.ac.uk/danny/database.html)人脸库上进行了实验。采用最近邻算法进行分类。ORL人脸库是由剑桥大学AT&T实验室创建的，有40个人的400幅图像，每人10幅，每幅图像尺寸为112×92。UMIST 人脸库是由英国曼彻斯特大学创建的，包括20人的共564幅图像，每人19～48幅不等，由于该库人脸样本数目不等，因此,实验中选用UMIST 的子库进行分析。该子库由20人组成，每个人含有15张不同姿势的照片，共300张，每幅图像尺寸为112×92。

将本文SLDGEA与经典SDA[5]和SLDA[6]在提取不同特征数目下识别性能进行了比较,分别选择ORL和UMIST人脸库前5幅图像作为训练样本，剩余作为测试样本，对于SLDGEA的参数设置α=0.5，β=0.5，对于有类别的近邻定为ss=2～7(ss表示不同有标签训练样本数目，如表1和表2中)，无标签样本的近邻定为5。对于3种算法，无标签样本数目，统一定为每类3个，3种算法提取的最大特征数目为C(与样本类别数目一致)个，实验结果如图1和图2所示。本文进一步在2个人脸库上，每人随机选择T幅图像作为训练样本，T的取值分别为2～6(ORL)和3～7(UMIST，由于该人脸库每类样本数目较多，故开始测试时多选一个)，剩余图像作为测试样本。取10次平均识别结果作为每种算法的识别结果，实验结果如表1与表2所示。

图1 ORL人脸库识别率随特征数目变化的结果

图2 UMIST人脸库识别率随特征数目变化的结果

图1和图2的结果表明了3种算法随着提取特征数目变化其相应识别性能的变化趋势。SLDGEA在2个人脸库上都取得了优于SLDA和SDA的识别结果，在大约与样本类别一致的特征数目时取得了较稳定的识别结果。这说明本文算法，即在保持局部结构的同时，保持样本的差异性所提取的特征是有效的。另外,也可看出，3种算法的识别率并不是一直在增加，有时会出现一些小的波动，但在大约靠近C个特征数目时，都达到了较稳定的识别结果。

表1 ORL人脸库的识别结果

表2 UMIST人脸库上的识别结果

表1和表2的结果进一步表明：本文提出的半监督算法在保持局部结构的同时，考虑保持样本的差异性是有效的、可行的，明显优于另外2种方法。在每类样本数目少的ORL上时，当有3个标注标签的样本即可取得较好的效果，在UMIST上，在4个样本时可取得较理想的效果。

4 结束语

本文结合局部差异算法，提出了一种SLDGEA。该算法的特点是能够同时利用有标签和无标签样本，同时能够保持图像之间的差异信息，能够避免过学习问题。另外，SLDGEA有效地解决了小样本问题，这是因为其采用了差形式的目标函数，因此,无需对矩阵进行求逆计算。实验结果表明了该方法的有效性,在具有较少的标注样本时，SLDGEA也能取得较满意的结果，更适合现实的应用。和已有的经典算法相比，其识别率也有显著的提高，在ORL人脸库上5个训练样本时，其识别率提高了2.25 %，在UMIST人脸库上6个训练样本时,其识别率提高了2.23 %。

参考文献:

[1] Belhumeur P N ,Hespanha J P ,Kriegam D J.Eigenfacesvs.fisherfaces:Recognition using class specific linear projec-tion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(7):711-720.

[2] He Xiaofei,Yan Shuicheng,Hu Yuxiao,et al.Face recognition using Laplacianfaces [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[3] Zhang H,Sun S,Jing Z,et al.Local structure based supervised feature extraction[J].Pattern Recognition,2006,39(8):1546-1550.

[4] 高全学,谢德燕,徐 辉,等.融合局部结构和差异信息的监督特征提取算法[J].自动化学报,2010,36(8):1107-1114.

[5] Cai Deng,He Xiaofei,Han Jiawei.Semi-supervised discriminant analysis[C]∥Proc of IEEE International Conference on Compu-ter Vision,Rio de Janeiro,Brazil,2007.

[6] 姜 伟,杨炳儒.半监督局部判别分析[J].计算机工程,2011,37(8):153-154,157.

[7] 谈 锐，陈秀宏.半监督的局部保留投影降维方法[J].计算机工程,2012,38(6):181-183.