《非线性成分分析作为一个核的特征值问题》由会员分享，可在线阅读，更多相关《非线性成分分析作为一个核的特征值问题（20页珍藏版）》请在金锄头文库上搜索。
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 为中心的观测值 1,1.,0MNkkkxxR
5、xPCA 算法对角化后的协方差矩阵为（1）1MTjCx为了做这个，首先解决特征值问题（2）v对于 特征值和 且 ，对于 V 的值0NR01()MjjjCvxv必须依赖于 的跨度，因此， （2）就等价于1.Mx(3)()()kkvxv,.本节的其余部分是专门用来直接转换到非线性情况，为了在本论文中提出的方法做基础准备。我们应该现在就描述在空间 F 上的另一种点集的计算方法，它通过一个可能的非线性映射将输入空间映射到 F 空间 :,NRF（4）xXF 所代表的就是特征空间，维数可能非常的大，很可能是无限的。这里和下面的大写字母代表空间 F 中的元素而小写字母表示中的元素。NR接下来，我们做一个假设
6、，我们将数据中心化，也就是说 1()0Mkkx然后我们将返回数据点。用空间 F 的协方差矩阵（5）1(),MTjjjCx_1更精确地说，这个协方差矩阵也被定义为 TX的期望；为了方便，我们应该通过一个有限的例子用同样的公式计算协方差矩阵来估计下(1)的极大似然率（如果 F 是无限维的空间，我们认为通过映射 到XF()jjxX将 作为线性算子，我们必须找到 个特征值以及 ()Tjjx0个特征向量V0满足 (6)VC和上面的讨论同理，V 的解法也依赖于 的跨度。对于我1,.()Mx们，我们得到了两个有用过的结论：第一个我们得到下面的等价不等式（7）()()kkxVxCV1,.第二，存在系数 有1,
7、.iM（8）1()iiix结合（7）式和（8）式，我们得1 11()()()()MMMiki ikjjii i jxxxx （9）,.定义一个 矩阵 K（10）()ijjjx这就写成 （11）2MK其中 记为用通过 作为向量的列。因为 K 是对称矩阵，它有1,.一组可以长成整个空间的特征向量组成，即（12）给出方程式（11）的所有 的解法。我们记 K 为半正定的，它就相当于1,. 1,.()()()()TMMxx（13）它是只对于所有的 都有XF（14）21,.()()()0MxX因此，K 的特征值还都是正的，并且恰恰给出了方程式（11）的的解法。我们因此只需对角化矩阵 K。令 记为特征值，M
8、 12,.M并且 是对应的特征向量的一组集，从而 是第一个非零的特1,. p征值 。我们根据需要将 标准化那么对应的 F 中的向量也向2 ,.pM被标准化，也就说（15） ()1kV,.p依赖于（8）式和（12）式，把 转化成标准的形式：M,1()()kijjjijx,1MkijiijKkk （16）k为了提取主要成分，我们需要计算投影到 F 中的特征向量 ，kV（k=p,M）令 X 为测试点，任意一个 F 上的图像 ，有()x（17）1()(MkkiiiVx我们就称它为相应于 的非线性主成分。总之，下面的步骤就需要计算主要成分：第一，计算用式子（10）定义的矩阵 K 的点积； 第二步，计算它
9、的特征向量以及在3空间 F 中把它标准化；第三步，通过式子（ 17）计算讲测试点到特征向量上的投影。为了简单起见，上文中提出的假设指观察的结果都是集中的。这个在输入空间很容易得到，但是在空间 F 上却很难得到，因为我们不能明确的计算出空间 F 的观察值的均值。然而，这有一种方法可以做到这一点，它会导致核基本 PCA 算法模式方程的轻微改变。（见附录 A）在我们进行下一节之前，我们更需要严密的研究映射 的角色，下面的观察是必要的。在矩阵计算中使用的映射 可以是任意的非线性映射到可能的高维空间 F。例如，在一个输入向量空间中的项目的所有 n 阶单项式。在那样的情况下，我们需要计算通过映射的输入向量
10、的点积，而且是一个尽可能大的计算消耗。对于这个问题的解决，将在下一节给出描述，事实上这个方法我们只需要唯一计算（10）和（17）式中的映射模式的点积，我们根本不需要明确映射的模式。_2如果我们需要的映射 不能将所有的观测值都映射成 0，那么这样的一个 p是永远存在的。 3根据我们已经知道的结果（也就说 Kirby&Sirovich,1990）PCA 可以空过计算点积矩阵 ,()ijx而不是方程式（1） ，然而，为了清楚和可拓展性的目地， （在目录 A 中我们可以考虑到在空间 F 中的数据都是被中心化了）我们给出更加细节的说明3 在特征值空间计算点积为了计算这个得点积形式 ，我们用一个核函数来表
11、示它()(xy（18）, )ky这样就使我们可以通过计算空间 F 中的点积的值而不需要找到映射。这个方法用于 Boser,Guyou,&Vapnik(1992)在拓展Vapnik&Chervonenkis(1974)“可推广的肖像”的超平面分离器到非线性支持向量机方面的应用。为了这个目的，他们将点积中所有情况都代替成一个预先选择的核函数。通过这种方式,Vapnik&Chervonenkis(1974)将这个有利的结果推广到了肖像识别的非线性情况。Aizerman，Braverman&Rozonoer(1964)叫 F 空间为“线性化空间” ，并且用它依据隐函数分离的办法来根据输入空间的元素表达
12、 F 中的元素之间的点积。如果空间 F 是高维的，我们想要为 K 找到一个封闭的形式来表达，为了更有效的计算。Aizerman et al.(1964)认为 K 是先天就选择的，不需要直接考虑对应的 到 F 的映射。一个 K 的特殊选择就对应一个点积，这个点积也对应一个适合的映射 。一个特别有用的例子，它是由 Poggio（1975.引理2.1）在多项式近似值的背景下对结果进行直接的推广： （ 19）()()(),dddxyCxy其中 向 X 映射到向量 ，将 X 中的有序对对应所有可能的第dCdn 个结果。例如（Vapnik,1995 ） ，如果 ，那么12(,)x22121(),)xx得到
13、与它等价的22112(),)Cxx（20）根据这个例子，我们很容易查证（21）2121122(,),)(,)()TTTxyxyC推广到一般，这个函数就是（22）(,)(,)dkxy对应的是输入空间坐标的第 d 个多项式的点积。如果 X 戴白是一个有像素值的图像，我们这样就能很容易的在任何 d 个像素生成的空间中运用假如我们能够单独依据点积计算，就不用明确的知道映射函数 的形式。后者可能是一个非常高位的空间：尽管我()dCx们能想式子（20）那样确定出 和 映射到空间 F 上坐标的关系，12x1但是中的图像通过映射 到高维空间 F 下的维数仍然是 ，并NR(1)!Np且这样可能长到 维。例如，一
14、个 维的输入图像和一个多项PN16式的阶是 d=5 生成一个维数是 的空间。因此，通过(22) 式中科0核函数的形式是我们唯一的办法去考虑多元统计而不用考虑时间复杂性的合并增长问题。关于 K 函数对应的空间 F 的点积的一些广泛问题已经被Boser，Guyon,&Vapnik(1992)和 Vapnik（1995）讨论过了：Mercer的定理，如果 k 是一个连续核的正的积分算子，我们就可以构建处一个到 k作为点积的空间的映射， （更多细节见附录 B） 。(18)式子用于解决我们的问题是简单的：我们将 点()(xy积中所有情况都代替成一个预先选择的简单的核函数 。这就是,k为什么我们不得将第
15、2 节中的问题公式化，某种程度上仅仅是利用空间 F 上的点积的值。这个 k 的选择含蓄的决定了映射 和特征空间 F。在附录 B 中，我们给出了常见的不同于（22）的其他的核函数的一些例子。4 核 PCA4.1 算法为了完成图 1 中的 PCA 基本核算法，从现在开始叫做核 PCA，虾米那的步骤开始被实现：第一，我们计算方程式（10）中的矩阵(23),()ijijiKkxy下面，我们解决（12）中的 K 的对角化问题，并且通过方程式（16）将特征向量正规化，使 的系数如下：n1,nn图示 1：是 PCA 算法基本思想。在很多高维的特征空间 F 中，就像一个在输入空间的 PCA，我们形成一个线性的 PCA。因为 F 是有关于输入空间的非线性的（通过 ） ，在输入空间中恒定的映射到主要的特征向量上就形成了非线性了。既然我们不能在输入空间中描绘出特征向量的原像，并不意味着它不存在。重要的是我们能不能找到一个准确的到 F 上的映射，而不是在输入空间中计算所有的 k 的核函数。为了通过核函数提取测试点 x 的一个主要成分，我们要计算方程式（17）中到特征向量上的映射
