基于指数损失的PCA方法研究

摘要:主成分分析是模式识别理论中一种经典的特征提取方法,也是一种简单有效的维数约简方法,并在人脸识别等问题上获得了成功。该文主要从损失函数的角度研究了PCA问题,并提出一种基于指数损失的PCA方法。

关键词:特征提取;PCA;损失函数

中图分类号:TP18文献标识码:A文章编号:1009-3044(2010)18-5297-03

PCA-based Method of Index Losses

LU Gang

(Artillery Academy of P.L.A, Hefei 230031, China)

Abstract: Principal Component Analysis is a classical feature extraction method in pattern recognition theory and is also a simple and effective method for dimension reduction, which has been successfully applied to face recognition. The principal component analysis has been studied from the side of the loss function in this paper. The PCA algorithm that bases on the PCA algorithm for exponent-loss function has been raised.

Key words: feature extraction; PCA; loss function

损失函数实际隐含着对数据分布的假设,学习问题目标函数的多样化可能会更贴合实际数据。本文提出一种可以构造有效正交特征的基于指数损失函数的PCA方法。和PCA 方法一样,其最后得出的特征对降维,提高泛化性等都具有很大的价值,它也可以用到其它的学习算法中。考虑构建给定推断任务的正交特征。这些特征假设是相互正交的输入数据的线性组合,是通过数据的因数构建的,假设空间则是针对推断任务并根据损失函数而定义的。我们寻找一个小的特征的集合,这些特征跨过对一特殊推论任务起重要影响的那部分假设空间。

1 AnyBoost方法

本节从损失函数的角度研究了Boosting方法,这种方法将PCA方法中正交分量的性质与一般组合方法的灵活性结合了起来。其目标是建立一系列的正交特征或函数并通过损失函数来解释其响应。为此本文研究了AnyBoost方法并对其进行了改进。

Boosting算法构造的一组特征称为假设。一般地,针对回归问题,有y≈TC,对于分类问题,则有yTTC>0。

AnyBoost方法通过在假设空间做梯度下降构造了一个最优的假设的线性组合来拟合这个响应。设 为一实值函数(也就是假设)的集合。在T的范围内形成一线性函数空间。这个函数空间的内积可以定义为:

关于假设的线性组合, 可以写成Tc的形式,其中T表示这些假设,c表示它们的系数。需要找到一个要素t∈span(T)使损失函数l(y,f)近似最小化。AnyBoost方法通过在假设空间做梯度下降以达到这个目的。在此,l(y,Tc)=fl(y,Tc)表示在函数空间中损失函数的梯度。理想状态下,T的空间和y是一样的,但是这通常不是实际情形。因此需要极小化关于损失函数的线性泛函来拟合响应。

假设当前函数为f=Tc,则建立假设空间的下降方向ti+1。任何一个具有正内积和负梯度的函数(-l(y,Tc)Tti+1)一定是下降方向。在AnyBoost方法中,一个弱的学习算法就是用来建立一个在每次迭代中尽可能地接近有负梯度的最大内积的假设。通过添加入一个近似步长ci+1到假设,当前函数形式变为Tc+ci+1ti+1。此算法的停止标准有两种:一是弱学习机不能产生使下降方向收敛的弱假设,二是达到迭代最大数。

Anyboost算法的基本思想为:

Mason等人提出的AnyBoost方法是使用梯度下降的方法在选择一个在内积空间中的元素的线性组合,使得损失函数极小化。弱学习机的选择和求内积的极大化是等价的。

Anyboost算法的基本思想: 先假定:一类弱假设T,l(y,t)及梯度l(y,t),弱学习机寻找t∈T使uTt最大.

1)使f为一常数或作零假设

2)计算u1=-l(y,f)

3)令i=1到N

4)使tj∈argmaxt∈TuiTt

5)若-uiTt

6)选择ci以减小l(y,f+citi)

7)使f=tjcj

8)计算ui+1=-l(y,f)

9)结束上面i=1到N的循环

10)返回f。

研究者对其改进一般是改变这几个要素:步骤4中的弱学习机,损失函数及第6步中优化步长ci的方法等。

2 基于指数损失的PCA方法研究

在处理二分类问题中,AdaBoost算法中用到了指数损失函数。AdaBoost算法在每次迭代中更新数据点的权重,越困难的事例赋予越大的权重。这个算法可以理解为极小化指数损失泛函:

其中的响应yi∈{+1,-1},i=1,…,m

计算下降方向:

首先,将一恒定的弱假设添加到加法模型,然后通过优化

来确定恒定假设上的系数μy,其中c+为一正的数据点集,c-为一负的数据点集。通过这个简化,可以很容易地解出优化条件:

求:

下一步就要求函数的负梯度:

显然,在上式中对弱假设来说,“权重”在先前的迭代中起了关键作用,此时“权重”可以用公式表达为

通过加权产生新的响应变量,并用新的响应变量来拟合构造新的弱假设。在AdaBoost算法中,新的弱假设中相应的每个数据点都会被加权修正。

对函数的系数求解:

在每次迭代中,新的弱假设或者说隐含特征将被添加到模型当中来求取函数的系数c。对指数损失修改来极小化下面关于μy和c的损失函数:

为了简便起见,定义:

这样损失函数就可以简单地表示为:

设损失函数关于(μy,c)的梯度:

损失函数在此处的Hessian矩阵可以表示为:

因为yi∈{+1,-1}是针对二分类问题的,则Hessian矩阵可以写为:

因此,牛顿梯步为:

包含向量 的加权最小二乘问题决定了数据点的权重。自从μy和c得到递增式的优化,牛顿梯步才能从原来的最优值出发来减少迭代次数以达到收敛。实际上,很少的迭代数就可以满足要求了。总的来看,基于指数损失的PCA方法:

Loss-PCA算法基本思想是:

输入:样本X,响应y,隐性变量数目N

1) 计算。置。压缩映射:。

2) For i=1 to N

3) 计算最优解:wi=XiTui

4) 计算线性假设:,

5) 压缩映射:,

6) 通过修正的牛顿梯步来优化步长(uy,c)

7) 计算负梯度:

8) end

9) 最终特征:T(X)=(X-μX)TW(PTW)-1

10) 计算最初空间的系数:g=W(PTW)-1c

11) 最终函数:f(X)=(X-μX)Tg+μy

4 实验

对真实数据库的实验,首先采样采用算法对数据进行维数约简,最后采用k近邻法对测试样本进行分类。表1对Benchmark 数据库中的五个数据集Cancer、Diabetes, PCA方法和基于指数损失的PCA泛化性能(分类性能)的比较。

5 结论

从上述实验结果可以看出,基于指数损失的PCA泛化性能(分类性能)要比传统的PCA方法要好,进一步证明了指数损失的优越性。本文提出的基于指数损失的PCA方法进一步丰富了PCA方法的理论形式。

参考文献:

[1] Freund Y, Schapire R. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences, 1997,55(1):119-139.

[2] Johnson R A,Wichern D W. Applied Multivariate Statistical Analysis[M].Prentice Hall,1992.

[3] Wold H. Estimation of principal components and related models by iterative least squares[C]//Multivariate Analysis. New York: Academic Press, 1966: 391-420.

[4] Mason L, Baxter J, Bartlett P, et al. Boosting algorithms as gradient descent in function space[R]. Australian National University:RSISE,1999.

[5] Schapire R,Singer Y. Improved boosting algorithms using confiden cerated predictions[J].Machine Learning,1999(37):297-336.