核擴展判定及核擴展方法

鄭逢德,張鴻賓

(北京工業(yè)大學計算機學院,北京 100124)

核擴展判定及核擴展方法

鄭逢德,張鴻賓

(北京工業(yè)大學計算機學院,北京 100124)

給出一種判定模式識別算法能否核擴展的方法,該方法具有不被算法具體形式所限制的優(yōu)點.傳統(tǒng)核擴展方法是通過將輸入數(shù)據(jù)映射到特征空間,然后在特征空間運行原始算法,得到相應(yīng)的核方法.給出另外一種核擴展策略,與傳統(tǒng)核擴展方法具有等價性.分析及試驗過程都表明,本文的核擴展方法具有可行性.

機器學習;模式識別;核方法;核擴展;KPCA

近年來核方法成為機器學習和模式識別領(lǐng)域中的熱點,如 SVM[1]、KPCA[2]、KFDA[3-4],這些方法已成功應(yīng)用于目標識別、文本分類、時間序列預(yù)測、基因圖譜分析,在處理復(fù)雜數(shù)據(jù)中表現(xiàn)出它們的優(yōu)點.雖然已經(jīng)存在很多的核方法,但從原始線性算法轉(zhuǎn)向核方法時都需要復(fù)雜的推導(dǎo).這些核方法可以看作原始算法通過核技巧增加了處理非線性輸入數(shù)據(jù)的能力,具體過程是:首先使用一個非線性變換,可將原始空間中的數(shù)據(jù)非線性地映射到某一個高維的特征空間中,在特征空間中利用一個已有線性算法,并且將它轉(zhuǎn)化為僅涉及內(nèi)積運算的優(yōu)化問題,為了回避非線性映射的設(shè)計與具體形式,用滿足 Mercer條件的核函數(shù)來代替內(nèi)積運算,從而推導(dǎo)出一個與樣本數(shù)有關(guān)、與樣本維數(shù)無關(guān)的優(yōu)化問題,最后求解優(yōu)化問題,得到原始空間中的一個非線性判別函數(shù)或者回歸函數(shù),例如 SVM就可以看作最大化間隔分類器的核擴展[5].

并不是所有的算法都可以擴展為相應(yīng)的核方法,對一個算法進行核擴展需要解決 2個問題:能否核擴展及如何核擴展.一個算法如果其最終輸出只取決于輸入數(shù)據(jù)的內(nèi)積,則該算法可以進行核擴展.但許多算法并不能很明顯地表示成輸入數(shù)據(jù)內(nèi)積的形式,判斷它們能否被核擴展需要檢查算法的內(nèi)部過程,本文依據(jù)輸入數(shù)據(jù)旋轉(zhuǎn)不變性提出一種簡單的判定方法.如何將一個算法擴展為相應(yīng)的核方法,傳統(tǒng)的做法是將輸入數(shù)據(jù)的內(nèi)積用核函數(shù)代替,得到的方法就是相應(yīng)的核方法.Yang等[6]提出了KFD的一種等價方法:KPCA加上 LDA,KPCA是使用內(nèi)積矩陣替換原始輸入空間中的內(nèi)積矩陣,然后基于核矩陣計算主分量.本文在此基礎(chǔ)上提出了一種核擴展等價方法:即先對原始空間中的輸入數(shù)據(jù)做 KPCA,得到非線性的特征,即特征空間中的主分量,然后將已有的線性算法作用于此主分量上.

1 核擴展的一種判定方法

一個算法的核擴展就是把該算法擴展到相應(yīng)的核版本,核擴展一個算法的過程是:首先通過核函數(shù)把輸入空間顯式映射到特征空間,其次在相應(yīng)特征空間使用原始算法.核方法采用一個映射 Φ:X→Φ(X)將數(shù)據(jù)映射到特征空間,優(yōu)勢在于并不需要知道該映射的形式,而只要知道輸入數(shù)據(jù)的內(nèi)積就可以.對一個算法進行核擴展就是使用核函數(shù)將輸入空間的數(shù)據(jù)隱式映射到非線性的特征空間中,可以看出,如果一個算法的輸出只取決于輸入數(shù)據(jù)的內(nèi)積,則該算法可以進行核擴展.一般算法本身并沒有顯式的表示成內(nèi)積的形式來表示它的輸出只與輸入數(shù)據(jù)的內(nèi)積有關(guān),因此在推導(dǎo)相應(yīng)核方法時需要用到較多的數(shù)學技巧.

核擴展過程中被表示成內(nèi)積形式的線性算法可以通過選擇一個核轉(zhuǎn)變成非線性,這稱為核技巧[2,7-8].這是一種非常有效的設(shè)計非線性算法的數(shù)學手段,很多研究人員利用核思想改造經(jīng)典的線性算法,得到相應(yīng)的基于核函數(shù)的非線性形式,并形象地稱這一過程為線性算法的核化.令 xi,i=1,…,N表示一個算法的輸入,算法 G具有可擴展能力,其輸入應(yīng)該是輸入數(shù)據(jù)的內(nèi)積矩陣 A=XTX,可以表示為

其中,X是輸入數(shù)據(jù)形成的矩陣;O表示算法的輸出.

一般來說,把一個算法進行核擴展就是直接把算法中的使用輸入空間中內(nèi)積的部分替換成特征空間中的內(nèi)積.這是通過將輸入數(shù)據(jù)的內(nèi)積〈xi,xj〉替換成 k(xi,xj)=〈φ(xi),φ(xj)〉來完成的,其中 k為核函數(shù),核矩陣,其中.所以核擴展后的算法 Gk和原始算法 G有如下關(guān)系:

這種方法在實際中有局限性,那就是需要顯式的表達成內(nèi)積的形式來表明它的輸出只與輸入數(shù)據(jù)的內(nèi)積有關(guān).

可以進行核擴展的算法其輸出只與輸入數(shù)據(jù)的內(nèi)積有關(guān),即其真正輸入是 A.對 A進行特征值分解A=PDPT,令 Y=PD1/2,那么 Y可以通過 A得到一個唯一的解,且 A=YYT,容易發(fā)現(xiàn) Y與 X只差一個旋轉(zhuǎn)變換.

定理 1 假設(shè) X是一個 n×p的矩陣,n是輸入數(shù)據(jù)的個數(shù),p是數(shù)據(jù)的維數(shù).A=XXT,A的特征值分解為 A=PDPT,如果 p≤n,那么有 A=[QTX,0],否則[Y,0]=QTX,其中 QTQ=I,0表示一個零矩陣用來填補等式中剩余的位置以保證兩邊維數(shù)相等.

上述定理表明,輸入數(shù)據(jù) X和由 A得到的矩陣 Y基本上是一樣的,只是相差一個旋轉(zhuǎn)變換.這意味著,對于一個以矩陣 A作為輸入的算法,其原始的輸入數(shù)據(jù)可以不是唯一的,而是矩陣 Y的旋轉(zhuǎn)變換后的集合.任何此集合里面的元素都可以看成是此算法的輸入,因為它們都會得到相同的輸入矩陣 A,即具有核擴展能力的算法的輸出對輸入的旋轉(zhuǎn)變換具有不變性.另一方面,當一個算法的輸出具有旋轉(zhuǎn)不變性,那么原始輸入 X與從 A導(dǎo)出的輸入 Y對此算法是沒有差別的,這個算法只是依賴于 A,因此可以得到核擴展的判定條件.

定理 2 一個算法能夠核擴展的充分必要條件是這個算法的輸出對算法的輸入的旋轉(zhuǎn)變換具有不變性.

2 核擴展方法

如何將一個算法擴展為相應(yīng)的核方法,傳統(tǒng)的做法是直接把算法中的使用輸入空間中內(nèi)積的部分替換成特征空間中的內(nèi)積,得到的方法就是相應(yīng)的核方法.一般來說,這種方法在實際使用中具有局限性,那就是需要顯式的表達成內(nèi)積的形式來表明它的輸出只與輸入數(shù)據(jù)的內(nèi)積有關(guān).Yang等[6]提出了 KFD的一種等價方法:KPCA加上 LDA,KPCA是使用內(nèi)積矩陣替換原始輸入空間中的內(nèi)積矩陣,然后基于核矩陣計算主分量.本文在此基礎(chǔ)上提出了一種核擴展等價方法:即先對原始空間中的輸入數(shù)據(jù)做 KPCA,得到非線性的特征,然后將已有的線性算法作用于特征空間主分量上.KPCA首先將原始輸入數(shù)據(jù)變換到特征空間,并取主成份,因此對一個算法進行核擴展可以先用 KPCA將特征空間降維,然后在由特征空間主成份張成的空間中運行原始算法,其算法等同于相應(yīng)的核方法[9].

所有核方法都可以使用核函數(shù)來實現(xiàn)隱式的特征映射,下面的分析中,提出了核擴展和 KPCA的聯(lián)系,這種聯(lián)系表現(xiàn)為一種等價性,如下:

定理 3 算法的核擴展等價于先對輸入數(shù)據(jù)做 KPCA處理,得到非線性的特征,即特征空間中的主分量,然后將算法作用于此分量上.

下面證明這 2種過程的等價性,要證明 2種算法的等價性,只需要證明這 2種算法的輸出是相等的.

對于算法 G的核擴展 Gk,其過程是使用輸入數(shù)據(jù)的核矩陣 K來替換原始內(nèi)積 A作為算法的實際輸入.

再考慮先做 KPCA后使用算法 G作用于特征空間的主分量這一過程.在做完 KPCA之后,算法 G的輸入是特征空間中的數(shù)據(jù)的主分量.由于 G具有核擴展的能力,即 G的輸出只是依賴于輸入數(shù)據(jù)的內(nèi)積矩陣,所以算法 G的輸出只依賴于特征空間的數(shù)據(jù)的主分量的內(nèi)積.其過程可以表示為

從 PCA與 KPCA的關(guān)系,有

其中 K是輸入數(shù)據(jù) X的核矩陣

這樣就證明了過程 KPCA+G與 Gk的等價性.這種等價性的關(guān)鍵聯(lián)系在于 KPCA的定理 3,即 KPCA形成新的內(nèi)積矩陣——核矩陣 K,并且在特征空間中的計算主分量依然保持了此內(nèi)積矩陣不變.

值得指出的是,本文提出的核擴展方法在有些情況下比傳統(tǒng)的核化方法效率更高,設(shè)輸入數(shù)據(jù)為 n個d維向量,在 KPCA實現(xiàn)過程中,需要求解核矩陣的特征值和特征向量,核矩陣是 n×n矩陣,計算復(fù)雜度為 O(n3),SVM的計算復(fù)雜度為 O(dn2),因此采用本文提出的方法去核化最大化間隔分類器得到 SVM,當樣本數(shù)目小于樣本維數(shù)時比傳統(tǒng)的核化方法效率更高.

文獻[3]對 KPCA+FDA與 KFD的等價性進行了論證,而且進行了相應(yīng)的試驗,文獻[2]分別使用SVM和 KPCA+MMC兩種方法在 USPS數(shù)據(jù)庫上做手寫數(shù)字識別,兩種算法都達到了 4.0%的錯誤率.表1是本文在一些 UCI數(shù)據(jù)集上做的試驗,可以看出本文提出的核擴展方法具有和傳統(tǒng)核擴展相同的分率效果.

表 1 UCI數(shù)據(jù)集上的試驗結(jié)果Table 1 The test result on UCI dataset

3 結(jié)束語

討論了算法核擴展,即如何判定能否核擴展和如何進行核擴展,許多算法并不是很明顯表示成輸入數(shù)據(jù)內(nèi)積的形式,判斷它們能否被核擴展需要檢查算法的內(nèi)部過程,本文依據(jù)輸入數(shù)據(jù)旋轉(zhuǎn)不變性提出一種簡單的判定方法,該方法具有不被算法具體形式所限制的優(yōu)點.對算法進行核擴展,本文提出一種可行的核擴展策略,先對原始空間中的輸入數(shù)據(jù)做 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—),男,河南延津人,博士生.