非线性成分分析作为一个核的特征值问题

1、非线性成分分析作为一个核的特征值问题摘要我们用于一种新方法描述如何执行主成分分析非线性形式。通过对积分算子核函数的使用。通过一些相关的非线性映射输入空间，我们可以有效计算在高维特征空间的主成分组成部分；比如在16 *16的图像空间中所有可能的5个像素的乘积。这篇论文中我们给出了该方法的推导，连同由非线性与内核的方法形成的讨论，并且展现目前对模式识别的非线性特征提取的第一批实验结果。1 引入主成分分析是尽可能提取高维数据集的一种强大的配套技术.它很容易通过求解一个特征值问题或者用迭代算法来估计主成分；现有的文献（看Jolliffe(1986) and Diamataras & Kung

2、(1996)）。PCA是将我们所描述的数据的坐标系进行正交变换。用新的坐标值所表示的数据我们称为主成分。通常情况下,少数的主成分组足以说明数据的主要结构。这些少数的数据我们有时候叫做数据的因素及潜在变量。目前的主成分分析的推广工作，我们相对投射空间的主要成分而言，对输入空间中的变量或特征更感兴趣，因为它与输入变量时非线性相关的。其中包括对输入变量之间采取高层次的相关性得到的实例变量。在图像分析的情况下，这就相当于是对输入数据所张成的空间就行寻找主要成分。为了这个目的，我们在输入空间中依据核函数来表达特征空间中的点积。对于给出的任何一个算法我们都可以通过点积单独的被表示出来，也就是说，即使变量本

3、身没有明确的算法，我们也可以通过这个核函数组建不同的非线性函数。（Aizerman,Braverman,和 Rozonoer,1964；Boser,Guyon&Vapnik,1992）。尽管这个方法已被广泛的认知（Burges,1996）,它的对机器学习的用途不是很大，除了在支持向量机方面。（Vapnik,1995）在这篇论文中，我们给出了通过这种方法构造非线性函数的几个例子。第一个例子是主成分分析的非线性形式，我们将会给出方法的细节及实验结果（第2到4节），我们也将主要描绘出具体的算法（第7节）。在下一节中，我们首先回顾一下标准PCA的算法。为了能把它推广到非线性情况下，我们将用对应

4、的唯一的点积的方法将PCA算法公式化。在第3节中，我们将在特征空间中通过计算点积来讨论核方法。这两节主要是第4节的基础，第4节将提出对于非线性的PCA得核的基本算法。第5节中将讨论基本核PCA算法与其他推广的PCA算法的不同。在第6节中，我们将给出在模式识别的特征值提取中的核基本算法的一些第一次实验结果。然后在第7节将探讨关于核方法在其他领域的应用，将在第8节中对于探讨给出总结。最后，一些技术性的材料，对于论据不构成主要的线索我们将放入附录中。2 特种空间的PCA 给出一组以M为中心的观测值PCA算法对角化后的协方差矩阵为 （1）为了做这个，首先解决特征值问题 （2）对于特征值和且，对于V的值

5、必须依赖于的跨度，因此，（2）就等价于 (3)本节的其余部分是专门用来直接转换到非线性情况，为了在本论文中提出的方法做基础准备。我们应该现在就描述在空间F上的另一种点集的计算方法，它通过一个可能的非线性映射将输入空间映射到F空间 （4）F所代表的就是特征空间，维数可能非常的大，很可能是无限的。这里和下面的大写字母代表空间F中的元素而小写字母表示中的元素。接下来，我们做一个假设，我们将数据中心化，也就是说然后我们将返回数据点。用空间F的协方差矩阵 （5）_ 更精确地说，这个协方差矩阵也被定义为的期望；为了方便，我们应该通过一个有限的例子用同样的公式计算协方差矩阵来估计下(1)的极大似然率 （如果

6、F是无限维的空间，我们认为通过映射到将作为线性算子，我们必须找到个特征值以及 个特征向量满足 (6)和上面的讨论同理，V的解法也依赖于的跨度。对于我们，我们得到了两个有用过的结论：第一个我们得到下面的等价不等式 （7）第二，存在系数有 （8）结合（7）式和（8）式，我们得 （9）定义一个矩阵K （10）这就写成 （11）其中记为用通过作为向量的列。因为K是对称矩阵，它有一组可以长成整个空间的特征向量组成，即 （12）给出方程式（11）的所有的解法。我们记K为半正定的，它就相当于 （13）它是只对于所有的都有 （14）因此，K的特征值还都是正的，并且恰恰给出了方程式（11）的的解法。我们因此只需

7、对角化矩阵K。令记为特征值，并且是对应的特征向量的一组集，从而是第一个非零的特征值。我们根据需要将标准化那么对应的F中的向量也向被标准化，也就说 （15） 依赖于（8）式和（12）式，把转化成标准的形式： （16）为了提取主要成分，我们需要计算投影到F中的特征向量，（k=p,M）令X为测试点，任意一个F上的图像，有 （17）我们就称它为相应于的非线性主成分。总之，下面的步骤就需要计算主要成分：第一，计算用式子（10）定义的矩阵K的点积；第二步，计算它的特征向量以及在空间F中把它标准化；第三步，通过式子（17）计算讲测试点到特征向量上的投影。为了简单起见，上文中提出的假设指观察的结果都是集中的。

8、这个在输入空间很容易得到，但是在空间F上却很难得到，因为我们不能明确的计算出空间F的观察值的均值。然而，这有一种方法可以做到这一点，它会导致核基本PCA算法模式方程的轻微改变。（见附录A）在我们进行下一节之前，我们更需要严密的研究映射的角色，下面的观察是必要的。在矩阵计算中使用的映射可以是任意的非线性映射到可能的高维空间F。例如，在一个输入向量空间中的项目的所有n阶单项式。在那样的情况下，我们需要计算通过映射的输入向量的点积，而且是一个尽可能大的计算消耗。对于这个问题的解决，将在下一节给出描述，事实上这个方法我们只需要唯一计算（10）和（17）式中的映射模式的点积，我们根本不需要明确映射的模式

9、。_ 如果我们需要的映射不能将所有的观测值都映射成0，那么这样的一个p是永远存在的。 根据我们已经知道的结果（也就说Kirby&Sirovich,1990）PCA可以空过计算点积矩阵而不是方程式（1），然而，为了清楚和可拓展性的目地，（在目录A中我们可以考虑到在空间F中的数据都是被中心化了）我们给出更加细节的说明3 在特征值空间计算点积为了计算这个得点积形式，我们用一个核函数来表示它 （18）这样就使我们可以通过计算空间F中的点积的值而不需要找到映射。这个方法用于Boser,Guyou,&Vapnik(1992)在拓展Vapnik&Chervonenkis(1974)“

10、可推广的肖像”的超平面分离器到非线性支持向量机方面的应用。为了这个目的，他们将点积中所有情况都代替成一个预先选择的核函数。通过这种方式,Vapnik&Chervonenkis(1974)将这个有利的结果推广到了肖像识别的非线性情况。Aizerman，Braverman&Rozonoer(1964)叫F空间为“线性化空间”，并且用它依据隐函数分离的办法来根据输入空间的元素表达F中的元素之间的点积。如果空间F是高维的，我们想要为K找到一个封闭的形式来表达，为了更有效的计算。Aizerman et al.(1964)认为K是先天就选择的，不需要直接考虑对应的到F的映射。一个K的特殊选

11、择就对应一个点积，这个点积也对应一个适合的映射 （19）其中向X映射到向量，将X中的有序对对应所有可能的第n个结果。例如（Vapnik,1995），如果，那么得到与它等价的 （20）根据这个例子，我们很容易查证 （21）推广到一般，这个函数就是 （22） 对应的是输入空间坐标的第d个多项式的点积。如果X戴白是一个有像素值的图像，我们这样就能很容易的在任何d个像素生成的空间中运用假如我们能够单独依据点积计算，就不用明确的知道映射函数的形式。后者可能是一个非常高位的空间：尽管我们能想式子（20）那样确定出和映射到空间F上坐标的关系，但是中的图像通过映射到高维空间F下的维数仍然是，并且这样可能长到维

12、。例如，一个维的输入图像和一个多项式的阶是d=5 生成一个维数是 的空间。因此，通过(22)式中科核函数的形式是我们唯一的办法去考虑多元统计而不用考虑时间复杂性的合并增长问题。关于K函数对应的空间F的点积的一些广泛问题已经被Boser，Guyon,&Vapnik(1992)和Vapnik（1995）讨论过了：Mercer的定理，如果k是一个连续核的正的积分算子，我们就可以构建处一个到k作为点积的空间的映射，（更多细节见附录B）。 (18)式子用于解决我们的问题是简单的：我们将点积中所有情况都代替成一个预先选择的简单的核函数。这就是为什么我们不得将第2节中的问题公式化，某种程度上仅仅是利

13、用空间F上的点积的值。这个k的选择含蓄的决定了映射和特征空间F。 在附录B中，我们给出了常见的不同于（22）的其他的核函数的一些例子。4 核PCA4.1 算法为了完成图1中的PCA基本核算法，从现在开始叫做核PCA，虾米那的步骤开始被实现：第一，我们计算方程式（10）中的矩阵 (23)下面，我们解决（12）中的K的对角化问题，并且通过方程式（16）将特征向量正规化，使的系数如下：图示1：是PCA算法基本思想。在很多高维的特征空间F中，就像一个在输入空间的PCA，我们形成一个线性的PCA。因为F是有关于输入空间的非线性的（通过），在输入空间中恒定的映射到主要的特征向量上就形成了非线性了。既然我们

14、不能在输入空间中描绘出特征向量的原像，并不意味着它不存在。重要的是我们能不能找到一个准确的到F上的映射，而不是在输入空间中计算所有的k的核函数。为了通过核函数提取测试点x的一个主要成分，我们要计算方程式（17）中到特征向量上的映射 （24）如果我们用一个核函数来描述第三节，我们知道这个过程就是在一个高维的特征空间建立一个标准的PCA。除此之外，我们不需要再有更加复杂的计算在那个空间。4.2核PCA的性能如果我们使用一个满足第三节中条件的核函数，事实上我们就一组点集，i从1到M，在空间F而不是中。在F中，我们因此可以通过下面的性质得到PCA是一个正交基底的变换。（假设特征向量是按照特征值的大小升

15、序排列的）：·第一个主要成分q,也就是说。投影到特征向量，比其他q的正交方向有更多的协方差·由第一个q主成分在任意给定得代表观察的逼近误差是非常小的·这些主要成分是不相关的·这个代表的平均值是最小的·第一个q的主成分有最大的交换信息关于输入空间关于更多的细节，看Diamantratras&Kung（1996）为了将空间F上的PCA的性能转化到输入空间上，他们需要对特别选择的核函数进行研究。我们不打算对这个问题的细节讨论，而是在我们主成分分析的内核进行讨论。4.3降维以及特征及提取不像线性PCA，这个被提到的方法允许提取的一组主要成分超过

16、输入空间的维数，假设得到的观察值M超过的输入空间N的维数。线性PCA，他是基于的点积矩阵，能够找到至少N个非零个特征值，他们与协方差矩阵的N个非零的特征值是相同的。与此相反，核PCA可以找出到M个非零的特征值。事实阐明不可能形成基于的协方差矩阵的核PCA。4.4 计算的复杂性如第三节所提到的，一个5次单项式核作用到一个256维的输入空间可以生成一个维空间。看起来好像要想在它的空间上找主要成分时间很棘手的问题。然而，正如我们上面解释的，这不是问题。首先，如第二节中指出，我们不需要寻找空间F中的特征向量，只需要得到由空间F的向量生成的子空间。第二，我们不需要计算空间F中准_如果我们用一个核函数，当

17、然我们已经通过核函数得到特征值，得到甚至更多确的点积。正如我们所知道的用我们的方法在通过一个核函数输入空间中可以直接得到。这个核的主要成分分析就是一个通过在L个观察值的线性PCA于的点积矩阵的计算的比较。全部的计算复杂性并没有因为下面额外的附加消耗而改变：我们需要评估核函数而不是点积。如果k很简单的计算的话，如单项式的核函数，也就是说，这是它是微不足道的。而且，在这种情况下我们需要用大量的观测值,我们可能希望工作的算法是仅仅计算最大的特征值，相关的例子是通货紧缩的功率的测量方法（相关讨论参看Diamantaras&Kung.1996）另外，我们可以考虑通过计算M<例子的子矩阵来估

18、计点集矩阵，我们依旧从所有例子中提取主要成分（这种被我们一些实验中运用的方法在下边给出了说明）提取主成分的形式非常困难，在那里，我们每一次提取主成分都必须评估次（24），而不是仅仅像线性PCA一样评估一个点集。由于一些例子，例如，如果我们提取作为预处理步骤的主要成分分类，这个是不利的，即使有那些例子，我们可以加速通过模拟Burges（1996）在支持向量机的背景下提出的一种技术的方法，特别的，我们可以试着逼近每一个特征向量通过另一个向量 （25）在m 接近于一个先验结果通过希望的速度，并且，这是通过减少平法差 (26)关键点是这个方法可以不准确的处理高维空间F也可以运用。例如 （27）梯度与的

19、关系可以非常容易的在核函数条件中得到，可以通过标准梯度被最小化，当设原始矩阵就有可能获得最多N个向量一个确切的扩充（N是输入空间的维数）通过解决一个特征向量问题（Burges,1996）. 对于手写字符识别任务,这项技术导致通过50个因素在几乎不损失准确性来提速，产生了一个正式的艺术分类最后，我们指出尽管核主成分提取估计比它对应的线性更加昂贵，这个增加的输入可以在最后被恢复，在关于分类的实验是基于提取主成分，我们发现在非线性例子中，它是充分运用线性支持向量机来构造决定性的分界线，线性支持向量机虽然在分类速度上要比非线性的快的多，（后者要比可比神经网络慢（Burges&Schlkopf,

20、1996）.这个是由于支持向量决定了函数的事实（Boser,Guyon,&Vapnik,1992） （28）可以用单一的纵向量代入 (29)因此在最后进行分类可以被运作的极其快，主成份提取逐步执行的速度，另一方面，并因此这个分类器精确度速度交换，可以被控制通过我们提取的成分的数量，或者通过减少设置参量m4.5 解释性和变量的选择在PCA中，它有时候需要能够选择将子空间跨度映射到主成份提取的特殊轴，这个方法，它可能通过举例说明更加容易解释变量的选取，在非线性例子中，问题稍有不同：去获得解释性，我们希望找到那些基于F中PCA子空间的共轭函数4.6 改造仅仅进行基本的改造，标准的PCA允许改

21、造标准的,通过在确定的特征向量基中从中提取主成分（），的完整集合。、在核PCA这已不在可能，事实上可能发在F中的向量V在中没有了逆像，我们可以，即使发现了在中的向量z是映射的最接近于向量V的。为此，我们可以像Sec.44一样继续工作，并且写下在F中的距离在核函数矩阵中，同样，我们可以最大限度地降低它通过梯度降低。或者，我们可以用合适的复原方法对于基于内核的主成份的输入来确定改造的映射，首先这个对于数据的估计，我们可以用特定规矩的基向量类似于输入F中的特征向量在中的近似逆像。4.7多层次支持向量机通过第一次通过（24）式提取非线性主成份，然后训练支持向量机（Vapnik,1995）,我们可以在额

22、外的层次中构造典型支持向量机，通过元素提取的数量确定了第一个隐藏层的大小，将（24）式与支持向量机决策函数相结合。从而我们得到了典型的机器： （30）其中 这里，扩充系数是通过对标准支持向量机的计算的到的。已知不同的核函数和可以被运用于不同的层，同时知道这个可以提供高效率的方法在建立多变量的支持向量机，即，当时q机器映射，所有这些机器可能共享第一个包含数值昂贵的步骤的预处理层，然后是使用第二层的一个简单核。类似的考虑也适用于多层分类，在被构造的二进制分类器（可以共享一些预处理）。5 对于非线性PCA其他方法的比较）开始，对于非线性的例子它可能依赖于一般的线性PCA，或者选择适和估计主成份的迭代

23、方法，并利用一些部件的非线性去提取非线性特征。而不是给予这个领域的完整的评论，我们只是简单的描述三种途径，并且向Diamantaras & Kung （1996）的读者展示更详细的资料Hebbian Networks：由先驱工作者Oja创始（1982），一种的计算主成份的无监督神经网络典型算法被提出，相对于标准协方差矩阵对角化的方法，他们优势在于解决不稳定数据的案例，这些算法是相当通过增加非线性激活参变量来简单的构造函数变量，这些算法之后的提取特征就是作者提到的非线性主成份，与核PCA相比较，虽然，那些途径缺乏几何解释就像标准PCA在一个特征空间与输入空间的非线性相关性。并且很难理解他

24、们究竟是什么提取自动关联多层次感应器：考虑比输入小的有一个隐藏层的两层线性感应器，如果我们训练它像输出一样重复输入值(即把它应用于自动关联制作中)，然后激活隐藏的单元组成数据在低维空间的表示，与PCA密切相关（看例子Diamantaras&Kung，1996），推广到非线性领域，一种采用非线性激活功能和附加层。当然这种过程可以被认为是一种非线性PCA形式，应该强调的是，由此产生的解决非线性优化问题的网络培训构成，与获得可能性深陷的局部极小值，因此依赖于这样的结果与对训练的出发点。此外，在神经网络的实现的机器学习过程中通常存在这危险。非线性PCA神经算法的另一个问题是，成分提取的数量必须

25、事先被确定。这也是下面方法的情况，其中，虽然在明确提取什么样的非线性特征的清晰几何图片案例方面有优势。 主曲线：一个在输入空间中的几何解释方法是从用主曲线法（Hastie&Stuetzle,1989）. 这种方法反复估计一曲线（或曲面），其中捕获的数据结构,数据投射到曲线上（即映射到最接近的点），该算法试图找到一条性质曲线，该曲线上的每个点是所有数据点的平均值隐射到它上，可以证明，只有直线满足后者是主要成分，所以主曲线的确是后者的推广。计算主曲线，再次非线性优化问题必须被解决的。 核PCA: 核PCA是PCA意义上的一种非线性的推广，如果我们使用内核k（x,y）=(x·y)

26、,我们恢复原来的PCA.得到PCA的非线性形式，我们仅仅选择一个非线性核。此外，核PCA是一种在任意大（可能无限）维度的的特征空间中执行PCA的PCA算法的泛化。 与上面的方法比较，核PCA主要的优势是不涉及非线性优化，他本质上是一种线性代数学与标准PCA一样简单，此外，我们不需要提前指定我们想要提取成分的数量，神经的方法相比，核PCA如果我们需要处理大量的观测是不好用的。6.试验 在这节，我们提出了一个实验即我们使用核PCA提取主成分集。首先，我们应采取看一个简单的玩具例子，在此之后，我们描述了现实中的实验，我们试图评估通过分类任务提取的主要成分效用。图3：一个例子从MPI椅子数据库中提取的图像，左边为原始椅子图像，右边为缩减像素在16×16像素数据库中的图像6.1 玩具实验为了提供一些直觉关于怎样在输入空间中用FPCA，我们的实验表明用人工的2 - D的数据集，用1度至4度多项式核（参照图2）6.2 目标识别