核扩展判定及核扩展方法

郑逢德,张鸿宾

(北京工业大学计算机学院,北京 100124)

核扩展判定及核扩展方法

郑逢德,张鸿宾

(北京工业大学计算机学院,北京 100124)

给出一种判定模式识别算法能否核扩展的方法,该方法具有不被算法具体形式所限制的优点.传统核扩展方法是通过将输入数据映射到特征空间,然后在特征空间运行原始算法,得到相应的核方法.给出另外一种核扩展策略,与传统核扩展方法具有等价性.分析及试验过程都表明,本文的核扩展方法具有可行性.

机器学习;模式识别;核方法;核扩展;KPCA

近年来核方法成为机器学习和模式识别领域中的热点,如 SVM[1]、KPCA[2]、KFDA[3-4],这些方法已成功应用于目标识别、文本分类、时间序列预测、基因图谱分析,在处理复杂数据中表现出它们的优点.虽然已经存在很多的核方法,但从原始线性算法转向核方法时都需要复杂的推导.这些核方法可以看作原始算法通过核技巧增加了处理非线性输入数据的能力,具体过程是:首先使用一个非线性变换,可将原始空间中的数据非线性地映射到某一个高维的特征空间中,在特征空间中利用一个已有线性算法,并且将它转化为仅涉及内积运算的优化问题,为了回避非线性映射的设计与具体形式,用满足 Mercer条件的核函数来代替内积运算,从而推导出一个与样本数有关、与样本维数无关的优化问题,最后求解优化问题,得到原始空间中的一个非线性判别函数或者回归函数,例如 SVM就可以看作最大化间隔分类器的核扩展[5].

并不是所有的算法都可以扩展为相应的核方法,对一个算法进行核扩展需要解决 2个问题:能否核扩展及如何核扩展.一个算法如果其最终输出只取决于输入数据的内积,则该算法可以进行核扩展.但许多算法并不能很明显地表示成输入数据内积的形式,判断它们能否被核扩展需要检查算法的内部过程,本文依据输入数据旋转不变性提出一种简单的判定方法.如何将一个算法扩展为相应的核方法,传统的做法是将输入数据的内积用核函数代替,得到的方法就是相应的核方法.Yang等[6]提出了KFD的一种等价方法:KPCA加上 LDA,KPCA是使用内积矩阵替换原始输入空间中的内积矩阵,然后基于核矩阵计算主分量.本文在此基础上提出了一种核扩展等价方法:即先对原始空间中的输入数据做 KPCA,得到非线性的特征,即特征空间中的主分量,然后将已有的线性算法作用于此主分量上.

1 核扩展的一种判定方法

一个算法的核扩展就是把该算法扩展到相应的核版本,核扩展一个算法的过程是:首先通过核函数把输入空间显式映射到特征空间,其次在相应特征空间使用原始算法.核方法采用一个映射 Φ:X→Φ(X)将数据映射到特征空间,优势在于并不需要知道该映射的形式,而只要知道输入数据的内积就可以.对一个算法进行核扩展就是使用核函数将输入空间的数据隐式映射到非线性的特征空间中,可以看出,如果一个算法的输出只取决于输入数据的内积,则该算法可以进行核扩展.一般算法本身并没有显式的表示成内积的形式来表示它的输出只与输入数据的内积有关,因此在推导相应核方法时需要用到较多的数学技巧.

核扩展过程中被表示成内积形式的线性算法可以通过选择一个核转变成非线性,这称为核技巧[2,7-8].这是一种非常有效的设计非线性算法的数学手段,很多研究人员利用核思想改造经典的线性算法,得到相应的基于核函数的非线性形式,并形象地称这一过程为线性算法的核化.令 xi,i=1,…,N表示一个算法的输入,算法 G具有可扩展能力,其输入应该是输入数据的内积矩阵 A=XTX,可以表示为

其中,X是输入数据形成的矩阵;O表示算法的输出.

一般来说,把一个算法进行核扩展就是直接把算法中的使用输入空间中内积的部分替换成特征空间中的内积.这是通过将输入数据的内积〈xi,xj〉替换成 k(xi,xj)=〈φ(xi),φ(xj)〉来完成的,其中 k为核函数,核矩阵,其中.所以核扩展后的算法 Gk和原始算法 G有如下关系:

这种方法在实际中有局限性,那就是需要显式的表达成内积的形式来表明它的输出只与输入数据的内积有关.

可以进行核扩展的算法其输出只与输入数据的内积有关,即其真正输入是 A.对 A进行特征值分解A=PDPT,令 Y=PD1/2,那么 Y可以通过 A得到一个唯一的解,且 A=YYT,容易发现 Y与 X只差一个旋转变换.

定理 1 假设 X是一个 n×p的矩阵,n是输入数据的个数,p是数据的维数.A=XXT,A的特征值分解为 A=PDPT,如果 p≤n,那么有 A=[QTX,0],否则[Y,0]=QTX,其中 QTQ=I,0表示一个零矩阵用来填补等式中剩余的位置以保证两边维数相等.

上述定理表明,输入数据 X和由 A得到的矩阵 Y基本上是一样的,只是相差一个旋转变换.这意味着,对于一个以矩阵 A作为输入的算法,其原始的输入数据可以不是唯一的,而是矩阵 Y的旋转变换后的集合.任何此集合里面的元素都可以看成是此算法的输入,因为它们都会得到相同的输入矩阵 A,即具有核扩展能力的算法的输出对输入的旋转变换具有不变性.另一方面,当一个算法的输出具有旋转不变性,那么原始输入 X与从 A导出的输入 Y对此算法是没有差别的,这个算法只是依赖于 A,因此可以得到核扩展的判定条件.

定理 2 一个算法能够核扩展的充分必要条件是这个算法的输出对算法的输入的旋转变换具有不变性.

2 核扩展方法

如何将一个算法扩展为相应的核方法,传统的做法是直接把算法中的使用输入空间中内积的部分替换成特征空间中的内积,得到的方法就是相应的核方法.一般来说,这种方法在实际使用中具有局限性,那就是需要显式的表达成内积的形式来表明它的输出只与输入数据的内积有关.Yang等[6]提出了 KFD的一种等价方法:KPCA加上 LDA,KPCA是使用内积矩阵替换原始输入空间中的内积矩阵,然后基于核矩阵计算主分量.本文在此基础上提出了一种核扩展等价方法:即先对原始空间中的输入数据做 KPCA,得到非线性的特征,然后将已有的线性算法作用于特征空间主分量上.KPCA首先将原始输入数据变换到特征空间,并取主成份,因此对一个算法进行核扩展可以先用 KPCA将特征空间降维,然后在由特征空间主成份张成的空间中运行原始算法,其算法等同于相应的核方法[9].

所有核方法都可以使用核函数来实现隐式的特征映射,下面的分析中,提出了核扩展和 KPCA的联系,这种联系表现为一种等价性,如下:

定理 3 算法的核扩展等价于先对输入数据做 KPCA处理,得到非线性的特征,即特征空间中的主分量,然后将算法作用于此分量上.

下面证明这 2种过程的等价性,要证明 2种算法的等价性,只需要证明这 2种算法的输出是相等的.

对于算法 G的核扩展 Gk,其过程是使用输入数据的核矩阵 K来替换原始内积 A作为算法的实际输入.

再考虑先做 KPCA后使用算法 G作用于特征空间的主分量这一过程.在做完 KPCA之后,算法 G的输入是特征空间中的数据的主分量.由于 G具有核扩展的能力,即 G的输出只是依赖于输入数据的内积矩阵,所以算法 G的输出只依赖于特征空间的数据的主分量的内积.其过程可以表示为

从 PCA与 KPCA的关系,有

其中 K是输入数据 X的核矩阵

这样就证明了过程 KPCA+G与 Gk的等价性.这种等价性的关键联系在于 KPCA的定理 3,即 KPCA形成新的内积矩阵——核矩阵 K,并且在特征空间中的计算主分量依然保持了此内积矩阵不变.

值得指出的是,本文提出的核扩展方法在有些情况下比传统的核化方法效率更高,设输入数据为 n个d维向量,在 KPCA实现过程中,需要求解核矩阵的特征值和特征向量,核矩阵是 n×n矩阵,计算复杂度为 O(n3),SVM的计算复杂度为 O(dn2),因此采用本文提出的方法去核化最大化间隔分类器得到 SVM,当样本数目小于样本维数时比传统的核化方法效率更高.

文献[3]对 KPCA+FDA与 KFD的等价性进行了论证,而且进行了相应的试验,文献[2]分别使用SVM和 KPCA+MMC两种方法在 USPS数据库上做手写数字识别,两种算法都达到了 4.0%的错误率.表1是本文在一些 UCI数据集上做的试验,可以看出本文提出的核扩展方法具有和传统核扩展相同的分率效果.

表 1 UCI数据集上的试验结果Table 1 The test result on UCI dataset

3 结束语

讨论了算法核扩展,即如何判定能否核扩展和如何进行核扩展,许多算法并不是很明显表示成输入数据内积的形式,判断它们能否被核扩展需要检查算法的内部过程,本文依据输入数据旋转不变性提出一种简单的判定方法,该方法具有不被算法具体形式所限制的优点.对算法进行核扩展,本文提出一种可行的核扩展策略,先对原始空间中的输入数据做 KPCA,得到非线性的特征,即特征空间中的主分量,然后将已有的线性算法作用于此主分量上,分析及试验过程都表明该核扩展方法具有可行性.

[1]VAPNIK V.The nature of statistical learning theory[M].New York:Springer,1995:70-85.

[2]SCHOLKOPF B,SMOLA A,MULLER K R.Nonlinear component analysis as a kernel eigenvalue problem[J].Neural Computation,1998,10(5):1299-1319.

[3]MIKA S,RATSCH G,WESTON J,et al.Fisher discriminant analysis with kernels[J].Proc IEEE Int'l Workshop Neural Networks for Signal Processing IX,1999,8:41-48.

[4]MIKA S,RATSCH G,SCHOLKOPF B,etal.Invariant feature extraction and classification in kernel spaces[C]∥Advances in Neural Information Processing Systems.Cambridge:MIT Press,1999:526-532.

[5]SHAWE-TAYLOR J,CRISTIANININ.Kernelmethods for pattern analysis[M].Cambridge:Cambridge University Press,2004:211-229.

[6]YANG J,FRANGI A F,YANG J Y,et al.KPCA pus LDA:a complete kernel fisher discriminant framework for feature extraction and recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(2):230-244.

[7]XU Y,SUN B,ZHANG C Y,et al.An implemention framework for kernel methods with high-dimensional patterns[C]∥Proceedings of the Fifth International Conference on Machine Learning and Cybernetics,Dalian:IEEEPress,2006:13-16.

[8]SCHOLKOPFB,MIKA S,KNIRSCH B,etal.Input space vs.feature space in kernel-based methods[J].IEEE Transactions on Neural Networks,1999,10(5):1000-1017.

[9]CHENW,ZHANG H.The condition of kernelizing an algorithm and an equivalence between kernel methods[C]∥Lecture Notes In Computer Science 4477,Berlin:Springer,2007:338-345.

(责任编辑 张 蕾)

The Condition of Kernelizing an Algorithm and Kernelizing Methods

ZHENG Feng-de,ZHANG Hong-bin
(College of Computer Science,Beijing University of Technology,Beijing 100124,China)

To kernelize an algorithm,there are two key points.That is,whether the algorithm can be kernelized and how to kernelize the algorithm if it can bekernelized.Generally it needs many mathematic skills to determine whether an algorithm can be kernelized.This paper provides a new determining condition for kernelization of algorithms.It has the advantage that it is not limited by the specific form of the algorithm.Traditional kernelizing methods are obtained through mapping the input data to the feature space and then running the algorithm in the feature space.This paper introduces another kernelizing method.The kernelizing method is equivalent to traditional kernelizing method through analysis and experiment.

machine learning;pattern recognition;kernelmethods;kernelization;KPCA

TP 273

A

0254-0037(2010)04-0554-04

2008-10-31.

国家自然科学基金资助项目(60775011).

郑逢德(1980—),男,河南延津人,博士生.