基于全局不相关的多流形学习

彭永康，李 波

(1.武汉科技大学 计算机科学与技术学院，湖北 武汉 430065；2.武汉科技大学智能信息处理与实时工业系统湖北省重点实验室，湖北 武汉 430065)

0 引 言

在人脸识别[1]任务中，特征提取是其中非常关键的一环，主要的目的是为了降维，提取出关键的特征信息。在过去几十年中，很多针对高维数据降维的算法被相继提出，维数约减算法可分为线性方法和非线性方法两类[2]。典型的线性方法有无监督的主成分分析(principal component analysis，PCA)和有监督的线性判别分析(linear discriminant analytics，LDA)[3]。代表性的非线性算法如流形学习，有拉普拉斯特征映射[4](laplacian eigenmaps，LE)算法，但是LE算法在泛化能力上表现不是很好，换句话说，测试数据使用训练数据得到的投影矩阵计算其低维空间映射时是不容易得到的，这个问题也叫作out-of-sample问题。针对这个问题，张量化[5]、核化[6]、线性化[7]等技术相继出现来处理这个问题。相对于LE算法，局部保持投影[8](locally preserving projections，LPP)算法计算成本低并且在聚类能力上表现良好。但是以上的LPP算法和LE算法都是基于样本的局部结构而没有考虑样本的非局部结构信息，之后Yang等提出了一个非监督判别投影算法[9](unsupervised discriminant projection，UDP)，不仅注意了样本的局部结构信息，还将样本的非局部结构信息考虑进去。

以上的流形学习算法是基于点到点之间的距离，有以下缺陷，其一，使用点到点之间的距离学习样本点的几何结构信息有限，其二，抗干扰能力不强，容易受到噪声的干扰。针对以上问题，近邻线性组合的方法包括近邻特征线[10](nearest feature line，NFL)和近邻特征场[11](nearest feature plane，NFP)相继被提出。点到特征线的距离和点到特征空间的距离相较于点到点之间的距离，可以挖掘出更多的判别信息，加强算法的判别能力。但是基于点到特征空间的距离依然容易受到噪声的干扰，无法充分学习样本点的局部判别信息。为了解决以上算法的缺陷，提出特征空间到特征空间距离，可以更好学习样本之间的结构信息，同时提升算法的鲁棒性，减少噪声对算法判别能力的干扰。

通过特征抽取得到的判别信息很大程度上会存在一定的信息冗余，即判别特征向量是统计相关的。为了减少其冗余度，使判别特征是全局不相关的，将不相干约束应用于特征空间到特征空间距离度量学习，可以减少判别信息的相关性，提高算法的判别能力。

本文提出一个基于全局不相关的多流形学习算法(UFDML)。①使用特征空间到特征空间的距离，并使异类特征空间距离最大。②提出一个不相关约束应用于该算法之上，使得抽取的特征是全局不相关的。通过对LDA，LPP，UDP等算法的比较，本文提出的方法在ORL，Yale，AR人脸库中的识别率是优于其它算法的。

1 点到特征空间距离

根据参考文献[12,13]，点到特征空间的距离则可以由如下定义为

(1)

(2)

(3)

2 基于不相关的多流形学习算法

2.1 特征空间距离

(4)

同样的方式，样本点xj在它的近邻特征空间的投影点可以表示为

(5)

所以，空间到空间的距离(S2S distance)可以定义为如下所示

(6)

用矩阵的形式表达，则S2S距离矩阵可以表示为

(7)

这里T是一个索引矩阵，并且矩阵的元素满足以下的公式

(8)

2.2 特征空间多流形度量

(9)

这里

(10)

这里Pij的取值为：当xi，xj属于异类最近邻样本点，则记作1，否则记作0。

本算法的目的是为了找到一个最优的线性转化，Y=WTX，通过该线性转化可以使得异类之间的距离最大，所以寻求的投影点应是样本点在异类特征空间的投影点，即上式可以变化成如下所示

(11)

M=TTT

(12)

结合式(11)、式(12)，上式可以改写成以下的形式

(13)

WXT(Dii-MI)XWT=WXTLXWT

(14)

这里L是一个拉普拉斯矩阵L=D-M。

2.3 不相关分析

特征抽取算法在人脸识别中扮演着非常重要的角色，但是，通过特征抽取所得到的特征往往含有重叠的判别信息，而在特征抽取算法中加入统计不相关的这个特性可以很好消除判别信息的冗余。但是很多算法往往忽视了这个性质，本文提出的算法在基于特征空间距离进行特征抽取的同时，加入了不相关约束，使得抽取的判别特征信息是统计不相关的。

由前文可得到，对于训练样本，判别分析可以由如下的变化得到

(15)

但是由该式得到的特征分量是统计相关的，即

(16)

只有该等式等于0时，特征分量yi和yj是统计不相关的，但是式(15)并不能保证得到的特征分量是统计不相关，当提取出的特征分量是统计相关的，存在着冗余信息，不利于信息的提取和最终的分类。

2.4 基于全局不相关的多流形学习框架

基于以上的问题，本文提出了一个基于全局不相关的多流形学习的框架，使得异类样本之间距离尽可能的大，样本点经过线性转化后得到的投影向量是全局不相关的。在式(15)的基础上，添加一个不相关约束，使得到的判别特征是全局不相关的，并且异类样本之间的距离尽可能的大。

提出的不相关约束要满足抽取的特征Y=WTX，其中任意两个特征向量yi，yj(i≠j)，是全局不相关的，这样可以得到

(17)

这里Wi,Wj是代表矩阵W中不同的俩列，St则是代表训练样本的全局散度矩阵，可以表示为

(18)

(19)

等式(17)和等式(19)整理得以下式子

WTStW=I

(20)

这里的N指训练样本点个数。

将该不相关约束添加到等式中，则我们最终得到的优化函数如下所示

(21)

对这个优化函数进行求解，通过拉格朗日乘子法，即

(22)

对其求偏导数，则得到以下的形式

(23)

令其等于0，则得到

XLXTW=λStW

(24)

这样，等式(24)求解可以等价于求解其广义特征分解问题，则得到的特征向量组成的矩阵是所要求的最优化的特征转换矩阵W。

2.5 算法流程

在上述的理论基础上，本文提出的UFDML算法步骤见表1。

表1 基于全局不相关的多流形学习算法步骤

3 实验和分析

为了对本文提出的方法进行验证，将本文提出的UFDML算法与相关的经典算法进行实验结果比较，比较的方法包括UDP，LPP，LDA算法。实验的数据库则选用AR，ORL，Yale这3个广泛使用的标准人脸数据库，以此对本文所提出算法的有效性和实用性进行评估。

3.1 数据集描述

Yale数据集中共计165张人脸图片，分别为15个人在相似背景下的不同光照条件和表情的人脸图片。实验中，图像样本被处理成64×64的大小。

ORL数据集共计400幅灰度图像，分别为40个人在不同时间下拍摄完成的，每个人的人脸图像的表情变化丰富。实验中，图像样本被处理成64×64的大小[14]。

AR数据集共计4000多幅图像，分别为70名男性人脸图像样本和56名女性人脸图像样本。其中图像的拍摄都是在不同的光照环境下拍摄完成的，表情也各不相同。

表2列出AR，ORL，Yale数据集的详细信息。

表2 AR，ORL，Yale数据集信息

3.2 AR，ORL，Yale数据集上不同方法的效果比对

在AR，ORL，Yale数据集对比实验中，我们用本文提出的UFDML算法跟其它算法进行比较，实验结果验证了算法的有效性。实验过程中，先通过各算法对原始高维数据进行降维，最后使用KNN分类器得到识别结果。

对于每个数据集，选取每个算法10次中的最高识别准确率作为最终识别结果。识别结果如下。

如表3所示，在这个实验中，训练样本n随机的选中为每类6,7,8个，并且每种算法重复训练10次，得到每个算法最大识别率和与之对应的最佳维度。从实验结果可以看出，本文提出的算法在训练样本选中6,7,8个时，得到的识别率都是优于其它3种算法的。

表3 UDP,LPP,UFDML,LDA在AR数据集上的识别结果

如表4所示，每一类图像中随机选中4,5,6个作为训练样本，其余的作为测试样本，重复10次得到每个算法最大识别率和最佳维度。从实验结果可以看出，本文提出的算法在训练样本选中4,5,6个时，本文提出的算法的识别能力优于其它算法。

表4 UDP,LPP,UFDML,LDA在ORL数据集上的识别结果

如表5所示，训练样本n随机的选中为每类6,7,8个并重复训练10次，得到每个算法最大识别率和对应维度。从实验结果可以看出，本文提出的算法在训练样本选中6,7,8个时，得到的识别率都是优于其它3种算法的，并且实验得到的识别率在分别划分为6,7,8个训练样本时，算法的识别率是相对稳定的。

4 结束语

为了解决传统流形学习算法中判别特征信息不够充足，易受到噪声影响和判别特征冗余的问题，本文提出了一种基于全局不相关的多流形学习算法(UFDML)。该算法首先通过特征空间到特征空间距离来代替传统的点到点之间的距离，学习一个基于特征空间距离的判别矩阵，使得异类样本点之间的距离尽可能的大，同时，加入了一个不相关的约束条件使判别特征统计不相关，最终得到最优的投影矩阵。UFDML算法有以下优点，其一，能够更好地学习样本点局部结构信息和抗噪声干扰能力强，二是经过该算法抽取的特征向量是统计不相关的，这样可以降低其冗余度，样本点在低维空间的分类能力得到提高。在ORL，AR，Yale人脸数据库上的实验结果验证了UFSDML算法的有效性和鲁棒性。不足的是，与其它流形学习算法相比，本文提出的算法在计算时间上不如其它算法，因为计算投影点所造成的迭代花费时间过多，下一步的研究方向将考虑如何有效降低算法的时间复杂度。

表5 UDP,LPP,UFDML,LDA在Yale数据集上的识别结果