您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 资本运营 > 非线性成分分析作为一个核的特征值问题
非线性成分分析作为一个核的特征值问题摘要我们用于一种新方法描述如何执行主成分分析非线性形式。通过对积分算子核函数的使用。通过一些相关的非线性映射输入空间,我们可以有效计算在高维特征空间的主成分组成部分;比如在16*16的图像空间中所有可能的5个像素的乘积。这篇论文中我们给出了该方法的推导,连同由非线性与内核的方法形成的讨论,并且展现目前对模式识别的非线性特征提取的第一批实验结果。1引入主成分分析是尽可能提取高维数据集的一种强大的配套技术.它很容易通过求解一个特征值问题或者用迭代算法来估计主成分;现有的文献(看Jolliffe(1986)andDiamataras&Kung(1996))。PCA是将我们所描述的数据的坐标系进行正交变换。用新的坐标值所表示的数据我们称为主成分。通常情况下,少数的主成分组足以说明数据的主要结构。这些少数的数据我们有时候叫做数据的因素及潜在变量。目前的主成分分析的推广工作,我们相对投射空间的主要成分而言,对输入空间中的变量或特征更感兴趣,因为它与输入变量时非线性相关的。其中包括对输入变量之间采取高层次的相关性得到的实例变量。在图像分析的情况下,这就相当于是对输入数据所张成的空间就行寻找主要成分。为了这个目的,我们在输入空间中依据核函数来表达特征空间中的点积。对于给出的任何一个算法我们都可以通过点积单独的被表示出来,也就是说,即使变量本身没有明确的算法,我们也可以通过这个核函数组建不同的非线性函数。(Aizerman,Braverman,和Rozonoer,1964;Boser,Guyon&Vapnik,1992)。尽管这个方法已被广泛的认知(Burges,1996),它的对机器学习的用途不是很大,除了在支持向量机方面。(Vapnik,1995)在这篇论文中,我们给出了通过这种方法构造非线性函数的几个例子。第一个例子是主成分分析的非线性形式,我们将会给出方法的细节及实验结果(第2到4节),我们也将主要描绘出具体的算法(第7节)。在下一节中,我们首先回顾一下标准PCA的算法。为了能把它推广到非线性情况下,我们将用对应的唯一的点积的方法将PCA算法公式化。在第3节中,我们将在特征空间中通过计算点积来讨论核方法。这两节主要是第4节的基础,第4节将提出对于非线性的PCA得核的基本算法。第5节中将讨论基本核PCA算法与其他推广的PCA算法的不同。在第6节中,我们将给出在模式识别的特征值提取中的核基本算法的一些第一次实验结果。然后在第7节将探讨关于核方法在其他领域的应用,将在第8节中对于探讨给出总结。最后,一些技术性的材料,对于论据不构成主要的线索我们将放入附录中。2特种空间的PCA给出一组以M为中心的观测值1,1,...,,,0MNkkkkxkMxRxPCA算法对角化后的协方差矩阵为11MTjjjCxxM(1)为了做这个,首先解决特征值问题vCv(2)对于0特征值和NvR0且11()MjjjCvxvxM,对于V的值必须依赖于1...Mxx的跨度,因此,(2)就等价于()()kkxvxCv1,...,kM(3)本节的其余部分是专门用来直接转换到非线性情况,为了在本论文中提出的方法做基础准备。我们应该现在就描述在空间F上的另一种点集的计算方法,它通过一个可能的非线性映射将输入空间映射到F空间:,NRFxX(4)F所代表的就是特征空间,维数可能非常的大,很可能是无限的。这里和下面的大写字母代表空间F中的元素而小写字母表示NR中的元素。接下来,我们做一个假设,我们将数据中心化,也就是说1()0Mkkx然后我们将返回数据点。用空间F的协方差矩阵11()(),MTjjjCxxM(5)_______1更精确地说,这个协方差矩阵也被定义为TXX的期望;为了方便,我们应该通过一个有限的例子用同样的公式计算协方差矩阵来估计下(1)的极大似然率(如果F是无限维的空间,我们认为通过映射XF到()(())jjxxX将()(()Tjjxx作为线性算子,我们必须找到0个特征值以及VF0个特征向量满足VCV(6)和上面的讨论同理,V的解法也依赖于1,...,()()Mxx的跨度。对于我们,我们得到了两个有用过的结论:第一个我们得到下面的等价不等式(())(())kkxVxCV1,...,kM(7)第二,存在系数(1,...,)iiM有1()MiiiVx(8)结合(7)式和(8)式,我们得1111(()())(()(())(()())MMMikiikjjiiijxxxxxxM1,...,kM(9)定义一个MM矩阵K()()ijjjKxx(10)这就写成2MKK(11)其中记为用通过1,...,M作为向量的列。因为K是对称矩阵,它有一组可以长成整个空间的特征向量组成,即MK(12)给出方程式(11)的所有的解法。我们记K为半正定的,它就相当于1,...,1,...,(()())(()())TMMxxxx(13)它是只对于所有的XF都有21,...,()(()())0MXFXxxX(14)因此,K的特征值还都是正的,并且恰恰给出了方程式(11)的M的解法。我们因此只需对角化矩阵K。令12,...,M记为特征值,并且1,...,M是对应的特征向量的一组集,从而p是第一个非零的特征值2。我们根据需要将,...,pM标准化那么对应的F中的向量也向被标准化,也就说()1kkVV,....,kpM(15)依赖于(8)式和(12)式,把,...,pM转化成标准的形式:,11(()())Mkkijjjijxx,1MkkijijijKkkKkkk(16)为了提取主要成分,我们需要计算投影到F中的特征向量kV,(k=p,…,M)令X为测试点,任意一个F上的图像()x,有1(())(()())MkkiiiVxxx(17)我们就称它为相应于的非线性主成分。总之,下面的步骤就需要计算主要成分:第一,计算用式子(10)定义的矩阵K的点积;3第二步,计算它的特征向量以及在空间F中把它标准化;第三步,通过式子(17)计算讲测试点到特征向量上的投影。为了简单起见,上文中提出的假设指观察的结果都是集中的。这个在输入空间很容易得到,但是在空间F上却很难得到,因为我们不能明确的计算出空间F的观察值的均值。然而,这有一种方法可以做到这一点,它会导致核基本PCA算法模式方程的轻微改变。(见附录A)在我们进行下一节之前,我们更需要严密的研究映射的角色,下面的观察是必要的。在矩阵计算中使用的映射可以是任意的非线性映射到可能的高维空间F。例如,在一个输入向量空间中的项目的所有n阶单项式。在那样的情况下,我们需要计算通过映射的输入向量的点积,而且是一个尽可能大的计算消耗。对于这个问题的解决,将在下一节给出描述,事实上这个方法我们只需要唯一计算(10)和(17)式中的映射模式的点积,我们根本不需要明确映射的模式。_______2如果我们需要的映射不能将所有的观测值都映射成0,那么这样的一个p是永远存在的。3根据我们已经知道的结果(也就说Kirby&Sirovich,1990)PCA可以空过计算点积矩阵,()ijijxx而不是方程式(1),然而,为了清楚和可拓展性的目地,(在目录A中我们可以考虑到在空间F中的数据都是被中心化了)我们给出更加细节的说明3在特征值空间计算点积为了计算这个得点积形式(()())xy,我们用一个核函数来表示它(,)(()())kxyxy(18)这样就使我们可以通过计算空间F中的点积的值而不需要找到映射。这个方法用于Boser,Guyou,&Vapnik(1992)在拓展Vapnik&Chervonenkis(1974)“可推广的肖像”的超平面分离器到非线性支持向量机方面的应用。为了这个目的,他们将点积中所有情况都代替成一个预先选择的核函数。通过这种方式,Vapnik&Chervonenkis(1974)将这个有利的结果推广到了肖像识别的非线性情况。Aizerman,Braverman&Rozonoer(1964)叫F空间为“线性化空间”,并且用它依据隐函数分离的办法来根据输入空间的元素表达F中的元素之间的点积。如果空间F是高维的,我们想要为K找到一个封闭的形式来表达,为了更有效的计算。Aizermanetal.(1964)认为K是先天就选择的,不需要直接考虑对应的到F的映射。一个K的特殊选择就对应一个点积,这个点积也对应一个适合的映射。一个特别有用的例子,它是由Poggio(1975.引理2.1)在多项式近似值的背景下对结果进行直接的推广:()(()()),dddxyCxCy(19)其中dC向X映射到向量()dCx,将X中的有序对对应所有可能的第n个结果。例如(Vapnik,1995),如果12(,)xxx,那么222121221()(,,,)Cxxxxxxx得到与它等价的2221212()(,,2)Cxxxxx(20)根据这个例子,我们很容易查证2121222221212121222((,)(,))(,,2)(,,2)()()TTTxxyyxxxxyyyyCxCy(21)推广到一般,这个函数就是(,)(,)dkxyxy(22)对应的是输入空间坐标的第d个多项式的点积。如果X戴白是一个有像素值的图像,我们这样就能很容易的在任何d个像素生成的空间中运用——假如我们能够单独依据点积计算,就不用明确的知道映射函数()dCx的形式。后者可能是一个非常高位的空间:尽管我们能想式子(20)那样确定出12xx和21xx映射到空间F上坐标的关系,但是NR中的图像通过映射到高维空间F下的维数仍然是(1)!!(1)!NppN,并且这样可能长到PN维。例如,一个1616维的输入图像和一个多项式的阶是d=5生成一个维数是1010的空间。因此,通过(22)式中科核函数的形式是我们唯一的办法去考虑多元统计而不用考虑时间复杂性的合并增长问题。关于K函数对应的空间F的点积的一些广泛问题已经被Boser,Guyon,&Vapnik(1992)和Vapnik(1995)讨论过了:Mercer的定理,如果k是一个连续核的正的积分算子,我们就可以构建处一个到k作为点积的空间的映射,(更多细节见附录B)。(18)式子用于解决我们的问题是简单的:我们将(()())xy点积中所有情况都代替成一个预先选择的简单的核函数(,)kxy。这就是为什么我们不得将第2节中的问题公式化,某种程度上仅仅是利用空间F上的点积的值。这个k的选择含蓄的决定了映射和特征空间F。在附录B中,我们给出了常见的不同于(22)的其他的核函数的一些例子。4核PCA4.1算法为了完成图1中的PCA基本核算法,从现在开始叫做核PCA,虾米那的步骤开始被实现:第一,我们计算方程式(10)中的矩阵,(())ijijijKkxy(23)下面,我们解决(12)中的K的对角化问题,并且通过方程式(16)将特征向量正规化,使n的系数如下:1,nnn图示1:是PCA算法基本思想。在很多高维的特征空间F中,就像一个在输入空间的PCA,我们形成一个线性的PCA。因为F是有关于输入空间的非线性的(通过),在输入空间中恒定的映射到主要的特征向量上就形成了非线性了。既然我们不能在输入空间中描绘出特征向量的原像,并不意味着它不存在。重要的是我们能不能找到一个准确的到F上的映射,而不是在输入空间中计算所有的k的核函数。为了通过核函数提取测试点x的一个主要成分,我们要计算方程式(17)中到特征向量上的映射,1()()(())MnnniiikPCxVxkxx(24)如果我们用一个核函数来描述第三节,我们知道这个过程就是在一个高维的特征空间建立一个标准
本文标题:非线性成分分析作为一个核的特征值问题
链接地址:https://www.777doc.com/doc-4388495 .html