非线性二维主成分分析方法

2022-01-23高宇夏志明刘欢

纯粹数学与应用数学 2021年4期

高宇,夏志明,刘欢

(1.西北大学数学学院,陕西西安 710127;2.西安交通大学数学与统计学院,陕西西安 710049)

1 引言

随着社会的快速发展和信息的加速流动,数据这一生产要素正在迅速扩大.自2012年以来,“大数据”一词被越来越多地提及,各行各业产生的海量数据已经成为经济社会的新石油.学术研究者及商业缔造者通过对数据的共享和交叉互用,实现其学术及经济价值的最大化.然而这些数据数量众多,种类繁杂,因此如何以最小的成本对其进行传输和存储是社会各大领域需要思考的问题.在这种背景下,“数据压缩”再一次吸引了广大研究者们的目光.它是指在有损或无损压缩的前提下,删减数据中包含的冗余信息,进而提高有效信息的占比,减少同等信息量下数据的存储空间.早在19世纪,就有相关研究者做了大量工作,特别是在机器学习、计算机视觉和信息检索领域[1-6].因此,用于“数据压缩”的手段和工具有很多,但这些方法难易程度不一,其中有一类操作简单且应用广泛的方法是主成分分析类方法.这类方法的基本思想是在保证数据投影变异性最大的前提下,沿着特定方向将数据投影到一个低维空间中,而方差则作为度量投影变异性的指标,以此达到用较少空间存储较多信息的目的.前辈们一直在该领域探索前进,这类方法也在逐渐发展完善.

主成分分析(Principal Component Analysis,PCA)是该类方法中最原始、最经典的一种.文献[7]最先引入这一概念,随后文献[8]将这一情形推广到随机向量.其数据压缩能力在文献[9]中得以展示.简单的结构及有效的压缩能力使得主成分分析得到了众多领域的普遍认可,其中值得一提的是其在计算机视觉领域做出的贡献.在该领域,研究者们关注如何处理图像,致力于挖掘PCA应用于人脸识别的潜能.在文献[10-11]中,PCA首次被用于人脸识别.文献[12]提出了著名的特征脸方法.自此,PCA在人脸识别领域引起了广泛关注,并逐渐发展成为该领域最成功的方法之一.同样被用于人脸识别的还有主成分分析的一些变种,包括独立分量分析(Independent Component Analysis,ICA)和核主成分分析(kernel Principal Component Analysis)[13-15].寻找投影变异性最大的方向并沿着这些方向进行投影是PCA的核心目标,可以借助“K-L变换”或“Hotelling变换”构造一组标准正交的方向,而这组方向恰好是样本协方差矩阵的特征向量,详见文献[16],文献[17]详述了张量数据的主成分分析方法.具体来说,对于给定的样本X∈Rm,PCA往往被定义为Z=UX[18-19],其中U为正交投影矩阵,Z为投影后所得向量.

PCA是一种基于向量数据构造的压缩方法,但在现实生活中很多数据以矩阵形式存在.将矩阵拉直为向量是一种普遍的做法,但不可否认的是,在拉直过程中原有数据结构会被割裂,这可能会导致结构中隐含信息的丢失.除此之外,拉直后向量维数的增加会导致“维数诅咒”(Curse of dimension).文献[20]也曾表示PCA无法捕捉投影方向的不变性.针对PCA的这些局限,文献[21]提出了一种基于矩阵数据建立的数据压缩方法—二维主成分分析(Two-dimensional PCA,2DPCA).该方法在投影前无需将矩阵转化为向量,从而规避了矩阵向量化导致的信息损失及“维数诅咒”.与PCA类似,对于给定的样本A∈Rm×n,2DPCA被表示为Z2D=AU2D,其中U2D为投影矩阵,Z2D为投影后所得矩阵.

2DPCA弥补了PCA的不足,有着深刻的应用场景,如掌纹识别[22]、图像去噪[23]及图像降维[24]等.其通过对原始数据做单侧投影实现了数据压缩的目的,但同时却忽视了数据沿另一侧压缩的可能性.譬如,矩阵数据右乘投影矩阵,则列结构得以压缩,但行结构却并未发生改变.这样的压缩方式一方面会限制模型的压缩性能,另一方面会造成压缩后行列信息之间的不平衡.文献[25]发表广义主成分分析方法(GPCA)解决了这一问题并在次年提出了对应的改进算法—矩阵的广义低秩近似(GLRAM)[26].对于给定的样本A∈Rm×n,GPCA通过双边投影矩阵UL∈Rr×l1和UR∈Rc×l2实现对数据两个方向的同时压缩,并记压缩后的样本ZG=UTLAUR.

如果从优化视角出发考虑PCA、2DPCA及GPCA,这些方法均属于“平方损失最小”准则下的拟合问题[16].而在相同复杂度下,非线性方法相比于线性压缩方法而言,具有更强的拟合能力.尽管主成分分析类方法从未停止发展的脚步,但不论是PCA,2DPCA还是GPCA,都属于线性压缩方法.为此,也曾有专家、学者提出了一系列非线性主成分分析方法,如多层感知器、核主成分分析方法[27]以及自编码器[28]等.多层感知器最初是为了克服感知机无法解决线性不可分问题而提出的一种设想,随着反向传播算法的提出,该方法突破了发展瓶颈,解决了隐层的权值训练问题,但该方法解释性不强;核主成分分析方法则是先将数据映射到高维特征空间中,再对数据进行主成分分析以实现降维,无疑在高维特征空间中,数据更容易被划分,但在这个过程中,核函数没有显式表达式;自编码器是在1985年,由 David H.等人在玻尔兹曼机上进行了首次尝试,与大多数神经网络模型一样,该方法可解释性弱,编码与解码过程类似于黑箱操作.因此,本文将基于二维主成分分析方法,探索一种可以自由变换压缩方向且具有显式表达式的非线性数据压缩方法—非线性二维主成分分析(Two-Dimensional Nonlinear Principal Component Analysis,2DNPCA),并从网络模型角度对方法进行直观地解释.

本文剩余部分的结构组织如下:第二节中首先描述了非线性二维主成分分析的核心思想,紧接着建立了该方法所对应的可解释网络模型;第三节中推导了基于梯度下降法所设计的形变反向传播算法并证明了其收敛性;第四节中呈现了基于ORL数据库公开数据集进行的数值实验结果;第五节则在总结全文的基础上,提出了方法可改进之处及未来的工作重心.本文所涉及的所有证明均在附录中给出.

2 非线性二维主成分分析方法

2.1 核心思想

该方法延续了主成分分析类方法的一般做法,即通过特定的投影矩阵对数据进行压缩.在此基础上,每次投影之后通过引入激活函数对数据进行二次变换,在尽可能保留有效信息的原则下提高模型的压缩能力.而引入什么样的激活函数,需要根据数据特征而定.比如,对于一张像素值位于0-255之间的黑白照片而言,假设出现了像素值为负的异常点,想要将其就近修正,此时可以选择Sigmoid函数,将负值点赋为一个无限接近于0的正数;另外,由于Sigmoid函数值域的特殊性,此文中省略数据归一化的步骤.

因此,对于一个给定的黑白图片样本A∈Rr×c,非线性二维主成分被定义为

其中,f(i)(·),i=1,2为被选择的激活函数.在深度学习领域,Sigmoid函数是一个被广泛使用的激活函数,该函数可以将变量映射到(0,1)之间,呈现为S型曲线,具有单调递增性和可微性.鉴于Sigmoid函数的优越性与普适性,本文取

当然,根据具体需求不同,也可以选择其他类型的激活函数,比如Sgn函数,ReLU函数等.U(1)∈Rr×l1为行维度所对应的投影矩阵,实现行方向信息的压缩;类似地,U(2)∈Rc×l2为实现列方向压缩所对应的列投影矩阵.为了达到数据压缩的目的,往往令l1＜r,l2＜c.对于给定的n个大小为r×c的样本,原始情况下n*r*c的存储空间需要被占用,按照上述方式压缩后所需的存储空间则变为n*l1*l2+r*l1+c*l2.衡量数据压缩成功与否的重要标志之一为数据是否可以在一个误差可接受的范围内被重构,若U(1),U(2)为正交矩阵,f(1),f(2)为可逆函数,则原始数据可以按照如下步骤被完全复原:

但如果对模型加入过多假设,则会增加模型的计算复杂度,削弱模型的可推广性.因此,考虑如下过程:

不妨直接令g(1),g(2)与f(1),f(2)保持一致,设为Sigmoid函数,使用过程中根据任务的不同,g(1),g(2)也可以被替换为其他激活函数.上述整个过程称为前向传播,执行前向传播过程便得到重构数据ˆA,而ˆA与A之间的差异将被作为衡量方法压缩性能的重要指标之一.

2.2 网络结构

提及非线性数据压缩方法,自编码器是极具代表性的一种.而非线性二维主成分分析作为一种非线性数据压缩方法,是否可以从网络的角度去理解？答案是肯定的.在这一节中,将建立一个特殊的网络模型以诠释该方法,也将指出其与自编码器的不同之处.根据前向传播过程,本文得到一个包含三个隐层的网络模型,图1展示了最终的模型结构.按照自编码器的定义方式,该结构可以视为由编码器及解码器两部分组成,其中输入层及第一、二隐层构成编码器;第二、三隐层及输出层构成解码器.观察模型不难发现,一个基于形变的子隐层在第一、三隐层的内部被引入,称之为形变子层,它的引入使得网络可以灵活改变数据的压缩维度.除此之外,不同于一般网络的黑箱性,该网络是基于非线性二维主成分分析所构建,因此网络中的各隐层各节点都有其存在的实际意义及显示表达.

图1 非线性二维主成分分析的网络结构

接下来将对参数进行求解.

3 参数估计及其形变反向传播算法

问题(11)是一个无约束最优化问题,通常使用最优化方法来求解,梯度下降法是其中极具代表性的一种.该方法的思想是沿着当前点的梯度反方向寻找新的迭代点,直到抵达某个局部最小值.对于凸优化问题而言,局部最优即为全局最优,这一结论的成立已经得到证明;然而对于如问题(11)的非凸优化问题,会出现多个局部最优解的情况.目前包含梯度下降法在内的大多数优化算法都无法保证一定能使得计算结果收敛到全局最优,但实验部分的结果表明本文所设计的算法能够得到一个较优的解.另外,梯度下降法虽适用于大多数情境,但它的一些变种,比如:批量梯度下降法、小批量梯度下降法及随机梯度下降法等在数据集较大的情况下能够取得优异的表现.因此,根据数据集的大小以及实际需要可以选择恰当的算法以取得更优的性能.考虑到本文所用数据集较小,故选用梯度下降法.

根据梯度下降法的步骤,对于一个包含有n个样本点A(1),···,A(n)的数据集,在每一个样本点上按照如下方式更新参数:

其中f(·)为目标函数,η为学习率,也被称为步长.结合(11)式易得

在第二节所建立的网络结构中,直接计算损失函数关于投影矩阵的导数是非常困难的,而根据(1)-(10)式,利用复合函数求导的链式法则有

因此,可以将问题转化为损失函数关于节点向量的求导.若记

表1 形变反向传播算法

其中k为任意正数.

根据定理结果可知:当学习率充分小时,参数序列会无限靠近最优解,且在欧几里得度量(Euclidean Metric)下,收敛速率为参数估计值与最优解之间距离平方的倒数.

注:由于证明过于繁琐,因此该定理涉及的证明及引理均在附录中给出.

4 数值实验

4.1 数据集简介

数值实验将基于Olivetti Research Laboratory(ORL)人脸数据库展开,该数据库于1992年 4月至1994年4月由英国剑桥Olivetti实验室创建,是一个在人脸识别领域非常著名的公开数据集.数据集共包含40个文件夹,每个文件夹对应一个人,每个人有10张人脸图像,共400张.这些照片是在不同时间、不同光照条件以及不同的面部表情(睁眼或闭眼,微笑或不微笑)及面部细节(是否佩戴眼镜)下拍摄的,所有图像均在较暗的均匀背景下采集,且为正面拍摄,只有极少数存在稍微的侧偏.这些图像以PGM格式储存,是高为112,宽为92的灰度图像.在后续实验中,所有图像被缩放为高、宽均为90的灰度图作为样本参与实验.实验共分为两个部分:第一部分验证算法的收敛性;第二部分检验方法的压缩性能.

4.2 算法收敛性实验

在实验开始前,需确定压缩后行、列各自的尺寸.为了叙述简洁,在下文中用基底对来称呼每一个给定的行、列组合,比如压缩后的行尺寸为a,列尺寸为b,则称(a,b)为一个基底对.希望算法在所有的基底对上都能快速收敛,一个稳妥的检验办法是遍历所有基底对,观察RMSRE是否能最终平稳.对于90×90的矩阵数据而言,共需遍历8100组基底对,这无疑会耗费大量的时间,并且在实际压缩过程中,压缩后的尺寸应尽可能小,因此考虑以下选取方式:每个方向在3到50之间每间隔2取1个值,即按照3,6,9,···的方式等间距取值.如此每个方向上有16种选择,仅需遍历256组基底对即可.这样的选择方式大大减少了实验的总次数且能保证所选择的基底对是具有代表性的.

最终实验结果如图2所示,其中横坐标表示迭代次数,纵坐标表示RMSRE的值,每一条不同颜色的曲线对应一组不同的基底对,共256条曲线.观察图形不难看出,大部分曲线都能在20次迭代前出现拐点并稳定于某个值附近,剩余的曲线也最终趋于平稳,此实验结果表明形变反向传播算法是收敛的.

图2 不同基底对下RMSRE的变化情况

4.3 压缩性能对比实验

该实验将通过对比非线性二维主成分分析与PCA,2DPCA及GPCA在ORL数据集上的压缩效果来说明模型的压缩性能,而压缩性能的比较通常会涉及重构误差及压缩程度这两个对立的指标,关于度量重构误差的指标在算法收敛性实验部分已经给出,在此再引入一个用于衡量压缩程度大小的指标:压缩率(compression ratio,CR).通俗来讲,压缩率被定义为

接下来将分别给出上述四种方法所对应压缩率的具体表达式.通过引言可知,PCA及2DPCA对矩阵数据进行单侧投影,而GPCA及本文方法执行双侧投影,因此这些方法压缩率的表达式在形式上不同.

在第一个子实验中,随机抽选10组不同的基底对展开实验,以各自的CR值作为横坐标,对应的RMSRE值作为纵坐标得到图3所示实验结果,图例中用2DNPCA表示非线性二维主成分分析.观察图形可以看出黑色实线始终位于黑色虚线下方,这意味着在同等压缩程度下,非线性二维主成分分析方法所对应的RMSRE始终小于GPCA所对应的RMSRE,也就是说本文方法的压缩性能优于GPCA.另外可以看出,在压缩率小于160时,两条曲线都呈现出上升趋势,即误差随着压缩率的逐渐增大而增大,这是符合认知的;但在160之后两条曲线的变化则不再规律,并且呈现出大致相似的变化趋势,因此有充足的理由认为这种变化是压缩本身而非某一种方法所拥有的属性.对此进行深入思考后,认为这种变化是由于矩阵数据的“各向异性”[16]所造成的,所谓“各向异性”就是高阶数据在不同方向上所包含的信息量不同.在同一压缩率下,对于矩阵数据而言对应着不止一种压缩方案,如果沿着数据信息量较大的方向进行过度压缩,则会导致重构误差的增大,反之误差则会变小.因此,沿着数据的哪个方向进行多大程度的压缩是一个值得思考的问题,作者正在进行相关方面的研究工作并且已经有实验证明在不同方向上确实存在相对应的较优压缩程度.

图3 GPCA及2DNPCA的压缩性能对比

在第二个子实验中将展示由四种方法重构所得的人脸图像.与算法收敛性实验类似,在每次实验前都需预先确定基底对.为了保证对其他方法的公平,先设定 PCA及2DPCA选取的特征数为m,将m设置为GPCA及2DNPCA压缩后其中一个方向的尺寸,再将另一个方向的尺寸压缩为d,如此可以保证本文方法是在同等或较为苛刻的条件下与其他方法进行比较.实验发现:不同基底对下,实验结果非常相似,出于文章篇幅的考虑,本文只挑选一组作为展示,所挑选的这组对比图(图4)是在m=8,d=26的情况下所得到的.

图4 重构人脸图像对比

图4中第一行为原始图像,接下来依次为由PCA,2DPCA,GPCA及2DNPCA所对应的重构人脸图.观察图像可以发现,由PCA重构所得图像的清晰度显著差于其他三种方法,而另外三种方法对应图像的清晰度则没有明显差异.为了得到一个确切的结论,计算三种方法对应的重构误差依次为:5.9850,5.9221以及5.7681.重构误差越小,则意味着与原始图像之间的差异越小,这就说明除了原始图像所在行,剩余四行的清晰度依次递增.基于此,得出本文方法的压缩性能优于PCA,2DPCA及GPCA的结论.

5 结论

本文基于二维主成分分析提出一种非线性矩阵压缩方法—非线性二维主成分分析法,该方法通过引入激活函数对投影后数据进行变换,从而实现数据的非线性压缩;同时,本文从网络角度出发建立了对应的可解释网络模型,模型通过在特定位置加入形变子层对压缩方向进行改变,进而实现矩阵数据两个维度的同时压缩,PCA,2DPCA及GPCA等方法也可从该角度获得直观解释;除此之外,本文设计了模型的“形变反向传播算法”并给出了收敛性证明.数值实验则基于ORL数据库的公开数据集展开,实验结果表明:非线性二维主成分分析的压缩性能优于线性主成分分析类方法PCA,2DPCA及GPCA.

在数值实验中,本文采取遍历的方式确定每个方向上数据被压缩后的尺寸,但这样的方式不够简洁,因此作者致力于开展相关方面的研究工作且已经取得不错的实验结果;另外“形变反向传播算法”是基于梯度下降法而设计的,但在样本量非常大的情况下,小批量梯度下降法及随机梯度下降法都是更佳的选择.

附录A

定理 A.1对于损失函数(11)及网络模型图1,有以下结论成立: