非線性成分分析作為一個核的特征值問題

1、非線性成分分析作為一個核的特征值問題摘要我們用于一種新方法描述如何執(zhí)行主成分分析非線性形式。通過對積分算子核函數(shù)的使用。通過一些相關(guān)的非線性映射輸入空間，我們可以有效計算在高維特征空間的主成分組成部分；比如在16 *16的圖像空間中所有可能的5個像素的乘積。這篇論文中我們給出了該方法的推導(dǎo)，連同由非線性與內(nèi)核的方法形成的討論，并且展現(xiàn)目前對模式識別的非線性特征提取的第一批實驗結(jié)果。1 引入主成分分析是盡可能提取高維數(shù)據(jù)集的一種強(qiáng)大的配套技術(shù).它很容易通過求解一個特征值問題或者用迭代算法來估計主成分；現(xiàn)有的文獻(xiàn)（看Jolliffe(1986) and Diamataras & Kung

2、(1996)）。PCA是將我們所描述的數(shù)據(jù)的坐標(biāo)系進(jìn)行正交變換。用新的坐標(biāo)值所表示的數(shù)據(jù)我們稱為主成分。通常情況下,少數(shù)的主成分組足以說明數(shù)據(jù)的主要結(jié)構(gòu)。這些少數(shù)的數(shù)據(jù)我們有時候叫做數(shù)據(jù)的因素及潛在變量。目前的主成分分析的推廣工作，我們相對投射空間的主要成分而言，對輸入空間中的變量或特征更感興趣，因為它與輸入變量時非線性相關(guān)的。其中包括對輸入變量之間采取高層次的相關(guān)性得到的實例變量。在圖像分析的情況下，這就相當(dāng)于是對輸入數(shù)據(jù)所張成的空間就行尋找主要成分。為了這個目的，我們在輸入空間中依據(jù)核函數(shù)來表達(dá)特征空間中的點(diǎn)積。對于給出的任何一個算法我們都可以通過點(diǎn)積單獨(dú)的被表示出來，也就是說，即使變量本

3、身沒有明確的算法，我們也可以通過這個核函數(shù)組建不同的非線性函數(shù)。（Aizerman,Braverman,和 Rozonoer,1964；Boser,Guyon&Vapnik,1992）。盡管這個方法已被廣泛的認(rèn)知（Burges,1996）,它的對機(jī)器學(xué)習(xí)的用途不是很大，除了在支持向量機(jī)方面。（Vapnik,1995）在這篇論文中，我們給出了通過這種方法構(gòu)造非線性函數(shù)的幾個例子。第一個例子是主成分分析的非線性形式，我們將會給出方法的細(xì)節(jié)及實驗結(jié)果（第2到4節(jié)），我們也將主要描繪出具體的算法（第7節(jié)）。在下一節(jié)中，我們首先回顧一下標(biāo)準(zhǔn)PCA的算法。為了能把它推廣到非線性情況下，我們將用對應(yīng)

4、的唯一的點(diǎn)積的方法將PCA算法公式化。在第3節(jié)中，我們將在特征空間中通過計算點(diǎn)積來討論核方法。這兩節(jié)主要是第4節(jié)的基礎(chǔ)，第4節(jié)將提出對于非線性的PCA得核的基本算法。第5節(jié)中將討論基本核PCA算法與其他推廣的PCA算法的不同。在第6節(jié)中，我們將給出在模式識別的特征值提取中的核基本算法的一些第一次實驗結(jié)果。然后在第7節(jié)將探討關(guān)于核方法在其他領(lǐng)域的應(yīng)用，將在第8節(jié)中對于探討給出總結(jié)。最后，一些技術(shù)性的材料，對于論據(jù)不構(gòu)成主要的線索我們將放入附錄中。2 特種空間的PCA 給出一組以M為中心的觀測值PCA算法對角化后的協(xié)方差矩陣為 （1）為了做這個，首先解決特征值問題 （2）對于特征值和且，對于V的值

5、必須依賴于的跨度，因此，（2）就等價于 (3)本節(jié)的其余部分是專門用來直接轉(zhuǎn)換到非線性情況，為了在本論文中提出的方法做基礎(chǔ)準(zhǔn)備。我們應(yīng)該現(xiàn)在就描述在空間F上的另一種點(diǎn)集的計算方法，它通過一個可能的非線性映射將輸入空間映射到F空間 （4）F所代表的就是特征空間，維數(shù)可能非常的大，很可能是無限的。這里和下面的大寫字母代表空間F中的元素而小寫字母表示中的元素。接下來，我們做一個假設(shè)，我們將數(shù)據(jù)中心化，也就是說然后我們將返回數(shù)據(jù)點(diǎn)。用空間F的協(xié)方差矩陣 （5）_ 更精確地說，這個協(xié)方差矩陣也被定義為的期望；為了方便，我們應(yīng)該通過一個有限的例子用同樣的公式計算協(xié)方差矩陣來估計下(1)的極大似然率 （如果

6、F是無限維的空間，我們認(rèn)為通過映射到將作為線性算子，我們必須找到個特征值以及 個特征向量滿足 (6)和上面的討論同理，V的解法也依賴于的跨度。對于我們，我們得到了兩個有用過的結(jié)論：第一個我們得到下面的等價不等式 （7）第二，存在系數(shù)有 （8）結(jié)合（7）式和（8）式，我們得 （9）定義一個矩陣K （10）這就寫成 （11）其中記為用通過作為向量的列。因為K是對稱矩陣，它有一組可以長成整個空間的特征向量組成，即 （12）給出方程式（11）的所有的解法。我們記K為半正定的，它就相當(dāng)于 （13）它是只對于所有的都有 （14）因此，K的特征值還都是正的，并且恰恰給出了方程式（11）的的解法。我們因此只需

7、對角化矩陣K。令記為特征值，并且是對應(yīng)的特征向量的一組集，從而是第一個非零的特征值。我們根據(jù)需要將標(biāo)準(zhǔn)化那么對應(yīng)的F中的向量也向被標(biāo)準(zhǔn)化，也就說 （15） 依賴于（8）式和（12）式，把轉(zhuǎn)化成標(biāo)準(zhǔn)的形式： （16）為了提取主要成分，我們需要計算投影到F中的特征向量，（k=p,M）令X為測試點(diǎn)，任意一個F上的圖像，有 （17）我們就稱它為相應(yīng)于的非線性主成分?？傊?，下面的步驟就需要計算主要成分：第一，計算用式子（10）定義的矩陣K的點(diǎn)積；第二步，計算它的特征向量以及在空間F中把它標(biāo)準(zhǔn)化；第三步，通過式子（17）計算講測試點(diǎn)到特征向量上的投影。為了簡單起見，上文中提出的假設(shè)指觀察的結(jié)果都是集中的。

8、這個在輸入空間很容易得到，但是在空間F上卻很難得到，因為我們不能明確的計算出空間F的觀察值的均值。然而，這有一種方法可以做到這一點(diǎn)，它會導(dǎo)致核基本PCA算法模式方程的輕微改變。（見附錄A）在我們進(jìn)行下一節(jié)之前，我們更需要嚴(yán)密的研究映射的角色，下面的觀察是必要的。在矩陣計算中使用的映射可以是任意的非線性映射到可能的高維空間F。例如，在一個輸入向量空間中的項目的所有n階單項式。在那樣的情況下，我們需要計算通過映射的輸入向量的點(diǎn)積，而且是一個盡可能大的計算消耗。對于這個問題的解決，將在下一節(jié)給出描述，事實上這個方法我們只需要唯一計算（10）和（17）式中的映射模式的點(diǎn)積，我們根本不需要明確映射的模式

9、。_ 如果我們需要的映射不能將所有的觀測值都映射成0，那么這樣的一個p是永遠(yuǎn)存在的。 根據(jù)我們已經(jīng)知道的結(jié)果（也就說Kirby&Sirovich,1990）PCA可以空過計算點(diǎn)積矩陣而不是方程式（1），然而，為了清楚和可拓展性的目地，（在目錄A中我們可以考慮到在空間F中的數(shù)據(jù)都是被中心化了）我們給出更加細(xì)節(jié)的說明3 在特征值空間計算點(diǎn)積為了計算這個得點(diǎn)積形式，我們用一個核函數(shù)來表示它 （18）這樣就使我們可以通過計算空間F中的點(diǎn)積的值而不需要找到映射。這個方法用于Boser,Guyou,&Vapnik(1992)在拓展Vapnik&Chervonenkis(1974)“

10、可推廣的肖像”的超平面分離器到非線性支持向量機(jī)方面的應(yīng)用。為了這個目的，他們將點(diǎn)積中所有情況都代替成一個預(yù)先選擇的核函數(shù)。通過這種方式,Vapnik&Chervonenkis(1974)將這個有利的結(jié)果推廣到了肖像識別的非線性情況。Aizerman，Braverman&Rozonoer(1964)叫F空間為“線性化空間”，并且用它依據(jù)隱函數(shù)分離的辦法來根據(jù)輸入空間的元素表達(dá)F中的元素之間的點(diǎn)積。如果空間F是高維的，我們想要為K找到一個封閉的形式來表達(dá)，為了更有效的計算。Aizerman et al.(1964)認(rèn)為K是先天就選擇的，不需要直接考慮對應(yīng)的到F的映射。一個K的特殊選

11、擇就對應(yīng)一個點(diǎn)積，這個點(diǎn)積也對應(yīng)一個適合的映射 （19）其中向X映射到向量，將X中的有序?qū)?yīng)所有可能的第n個結(jié)果。例如（Vapnik,1995），如果，那么得到與它等價的 （20）根據(jù)這個例子，我們很容易查證 （21）推廣到一般，這個函數(shù)就是 （22） 對應(yīng)的是輸入空間坐標(biāo)的第d個多項式的點(diǎn)積。如果X戴白是一個有像素值的圖像，我們這樣就能很容易的在任何d個像素生成的空間中運(yùn)用假如我們能夠單獨(dú)依據(jù)點(diǎn)積計算，就不用明確的知道映射函數(shù)的形式。后者可能是一個非常高位的空間：盡管我們能想式子（20）那樣確定出和映射到空間F上坐標(biāo)的關(guān)系，但是中的圖像通過映射到高維空間F下的維數(shù)仍然是，并且這樣可能長到維

12、。例如，一個維的輸入圖像和一個多項式的階是d=5 生成一個維數(shù)是 的空間。因此，通過(22)式中科核函數(shù)的形式是我們唯一的辦法去考慮多元統(tǒng)計而不用考慮時間復(fù)雜性的合并增長問題。關(guān)于K函數(shù)對應(yīng)的空間F的點(diǎn)積的一些廣泛問題已經(jīng)被Boser，Guyon,&Vapnik(1992)和Vapnik（1995）討論過了：Mercer的定理，如果k是一個連續(xù)核的正的積分算子，我們就可以構(gòu)建處一個到k作為點(diǎn)積的空間的映射，（更多細(xì)節(jié)見附錄B）。 (18)式子用于解決我們的問題是簡單的：我們將點(diǎn)積中所有情況都代替成一個預(yù)先選擇的簡單的核函數(shù)。這就是為什么我們不得將第2節(jié)中的問題公式化，某種程度上僅僅是利

13、用空間F上的點(diǎn)積的值。這個k的選擇含蓄的決定了映射和特征空間F。 在附錄B中，我們給出了常見的不同于（22）的其他的核函數(shù)的一些例子。4 核PCA4.1 算法為了完成圖1中的PCA基本核算法，從現(xiàn)在開始叫做核PCA，蝦米那的步驟開始被實現(xiàn)：第一，我們計算方程式（10）中的矩陣 (23)下面，我們解決（12）中的K的對角化問題，并且通過方程式（16）將特征向量正規(guī)化，使的系數(shù)如下：圖示1：是PCA算法基本思想。在很多高維的特征空間F中，就像一個在輸入空間的PCA，我們形成一個線性的PCA。因為F是有關(guān)于輸入空間的非線性的（通過），在輸入空間中恒定的映射到主要的特征向量上就形成了非線性了。既然我們

14、不能在輸入空間中描繪出特征向量的原像，并不意味著它不存在。重要的是我們能不能找到一個準(zhǔn)確的到F上的映射，而不是在輸入空間中計算所有的k的核函數(shù)。為了通過核函數(shù)提取測試點(diǎn)x的一個主要成分，我們要計算方程式（17）中到特征向量上的映射 （24）如果我們用一個核函數(shù)來描述第三節(jié)，我們知道這個過程就是在一個高維的特征空間建立一個標(biāo)準(zhǔn)的PCA。除此之外，我們不需要再有更加復(fù)雜的計算在那個空間。4.2核PCA的性能如果我們使用一個滿足第三節(jié)中條件的核函數(shù)，事實上我們就一組點(diǎn)集，i從1到M，在空間F而不是中。在F中，我們因此可以通過下面的性質(zhì)得到PCA是一個正交基底的變換。（假設(shè)特征向量是按照特征值的大小升

15、序排列的）：·第一個主要成分q,也就是說。投影到特征向量，比其他q的正交方向有更多的協(xié)方差·由第一個q主成分在任意給定得代表觀察的逼近誤差是非常小的·這些主要成分是不相關(guān)的·這個代表的平均值是最小的·第一個q的主成分有最大的交換信息關(guān)于輸入空間關(guān)于更多的細(xì)節(jié)，看Diamantratras&Kung（1996）為了將空間F上的PCA的性能轉(zhuǎn)化到輸入空間上，他們需要對特別選擇的核函數(shù)進(jìn)行研究。我們不打算對這個問題的細(xì)節(jié)討論，而是在我們主成分分析的內(nèi)核進(jìn)行討論。4.3降維以及特征及提取不像線性PCA，這個被提到的方法允許提取的一組主要成分超過

16、輸入空間的維數(shù)，假設(shè)得到的觀察值M超過的輸入空間N的維數(shù)。線性PCA，他是基于的點(diǎn)積矩陣，能夠找到至少N個非零個特征值，他們與協(xié)方差矩陣的N個非零的特征值是相同的。與此相反，核PCA可以找出到M個非零的特征值。事實闡明不可能形成基于的協(xié)方差矩陣的核PCA。4.4 計算的復(fù)雜性如第三節(jié)所提到的，一個5次單項式核作用到一個256維的輸入空間可以生成一個維空間。看起來好像要想在它的空間上找主要成分時間很棘手的問題。然而，正如我們上面解釋的，這不是問題。首先，如第二節(jié)中指出，我們不需要尋找空間F中的特征向量，只需要得到由空間F的向量生成的子空間。第二，我們不需要計算空間F中準(zhǔn)_如果我們用一個核函數(shù)，當(dāng)

17、然我們已經(jīng)通過核函數(shù)得到特征值，得到甚至更多確的點(diǎn)積。正如我們所知道的用我們的方法在通過一個核函數(shù)輸入空間中可以直接得到。這個核的主要成分分析就是一個通過在L個觀察值的線性PCA于的點(diǎn)積矩陣的計算的比較。全部的計算復(fù)雜性并沒有因為下面額外的附加消耗而改變：我們需要評估核函數(shù)而不是點(diǎn)積。如果k很簡單的計算的話，如單項式的核函數(shù)，也就是說，這是它是微不足道的。而且，在這種情況下我們需要用大量的觀測值,我們可能希望工作的算法是僅僅計算最大的特征值，相關(guān)的例子是通貨緊縮的功率的測量方法（相關(guān)討論參看Diamantaras&Kung.1996）另外，我們可以考慮通過計算M<例子的子矩陣來估

18、計點(diǎn)集矩陣，我們依舊從所有例子中提取主要成分（這種被我們一些實驗中運(yùn)用的方法在下邊給出了說明）提取主成分的形式非常困難，在那里，我們每一次提取主成分都必須評估次（24），而不是僅僅像線性PCA一樣評估一個點(diǎn)集。由于一些例子，例如，如果我們提取作為預(yù)處理步驟的主要成分分類，這個是不利的，即使有那些例子，我們可以加速通過模擬Burges（1996）在支持向量機(jī)的背景下提出的一種技術(shù)的方法，特別的，我們可以試著逼近每一個特征向量通過另一個向量 （25）在m 接近于一個先驗結(jié)果通過希望的速度，并且，這是通過減少平法差 (26)關(guān)鍵點(diǎn)是這個方法可以不準(zhǔn)確的處理高維空間F也可以運(yùn)用。例如 （27）梯度與的

19、關(guān)系可以非常容易的在核函數(shù)條件中得到，可以通過標(biāo)準(zhǔn)梯度被最小化，當(dāng)設(shè)原始矩陣就有可能獲得最多N個向量一個確切的擴(kuò)充（N是輸入空間的維數(shù)）通過解決一個特征向量問題（Burges,1996）. 對于手寫字符識別任務(wù),這項技術(shù)導(dǎo)致通過50個因素在幾乎不損失準(zhǔn)確性來提速，產(chǎn)生了一個正式的藝術(shù)分類最后，我們指出盡管核主成分提取估計比它對應(yīng)的線性更加昂貴，這個增加的輸入可以在最后被恢復(fù)，在關(guān)于分類的實驗是基于提取主成分，我們發(fā)現(xiàn)在非線性例子中，它是充分運(yùn)用線性支持向量機(jī)來構(gòu)造決定性的分界線，線性支持向量機(jī)雖然在分類速度上要比非線性的快的多，（后者要比可比神經(jīng)網(wǎng)絡(luò)慢（Burges&Schlkopf,

20、1996）.這個是由于支持向量決定了函數(shù)的事實（Boser,Guyon,&Vapnik,1992） （28）可以用單一的縱向量代入 (29)因此在最后進(jìn)行分類可以被運(yùn)作的極其快，主成份提取逐步執(zhí)行的速度，另一方面，并因此這個分類器精確度速度交換，可以被控制通過我們提取的成分的數(shù)量，或者通過減少設(shè)置參量m4.5 解釋性和變量的選擇在PCA中，它有時候需要能夠選擇將子空間跨度映射到主成份提取的特殊軸，這個方法，它可能通過舉例說明更加容易解釋變量的選取，在非線性例子中，問題稍有不同：去獲得解釋性，我們希望找到那些基于F中PCA子空間的共軛函數(shù)4.6 改造僅僅進(jìn)行基本的改造，標(biāo)準(zhǔn)的PCA允許改

21、造標(biāo)準(zhǔn)的,通過在確定的特征向量基中從中提取主成分（），的完整集合。、在核PCA這已不在可能，事實上可能發(fā)在F中的向量V在中沒有了逆像，我們可以，即使發(fā)現(xiàn)了在中的向量z是映射的最接近于向量V的。為此，我們可以像Sec.44一樣繼續(xù)工作，并且寫下在F中的距離在核函數(shù)矩陣中，同樣，我們可以最大限度地降低它通過梯度降低。或者，我們可以用合適的復(fù)原方法對于基于內(nèi)核的主成份的輸入來確定改造的映射，首先這個對于數(shù)據(jù)的估計，我們可以用特定規(guī)矩的基向量類似于輸入F中的特征向量在中的近似逆像。4.7多層次支持向量機(jī)通過第一次通過（24）式提取非線性主成份，然后訓(xùn)練支持向量機(jī)（Vapnik,1995）,我們可以在額

22、外的層次中構(gòu)造典型支持向量機(jī)，通過元素提取的數(shù)量確定了第一個隱藏層的大小，將（24）式與支持向量機(jī)決策函數(shù)相結(jié)合。從而我們得到了典型的機(jī)器： （30）其中 這里，擴(kuò)充系數(shù)是通過對標(biāo)準(zhǔn)支持向量機(jī)的計算的到的。已知不同的核函數(shù)和可以被運(yùn)用于不同的層，同時知道這個可以提供高效率的方法在建立多變量的支持向量機(jī)，即，當(dāng)時q機(jī)器映射，所有這些機(jī)器可能共享第一個包含數(shù)值昂貴的步驟的預(yù)處理層，然后是使用第二層的一個簡單核。類似的考慮也適用于多層分類，在被構(gòu)造的二進(jìn)制分類器（可以共享一些預(yù)處理）。5 對于非線性PCA其他方法的比較）開始，對于非線性的例子它可能依賴于一般的線性PCA，或者選擇適和估計主成份的迭代

23、方法，并利用一些部件的非線性去提取非線性特征。而不是給予這個領(lǐng)域的完整的評論，我們只是簡單的描述三種途徑，并且向Diamantaras & Kung （1996）的讀者展示更詳細(xì)的資料Hebbian Networks：由先驅(qū)工作者Oja創(chuàng)始（1982），一種的計算主成份的無監(jiān)督神經(jīng)網(wǎng)絡(luò)典型算法被提出，相對于標(biāo)準(zhǔn)協(xié)方差矩陣對角化的方法，他們優(yōu)勢在于解決不穩(wěn)定數(shù)據(jù)的案例，這些算法是相當(dāng)通過增加非線性激活參變量來簡單的構(gòu)造函數(shù)變量，這些算法之后的提取特征就是作者提到的非線性主成份，與核PCA相比較，雖然，那些途徑缺乏幾何解釋就像標(biāo)準(zhǔn)PCA在一個特征空間與輸入空間的非線性相關(guān)性。并且很難理解他

24、們究竟是什么提取自動關(guān)聯(lián)多層次感應(yīng)器：考慮比輸入小的有一個隱藏層的兩層線性感應(yīng)器，如果我們訓(xùn)練它像輸出一樣重復(fù)輸入值(即把它應(yīng)用于自動關(guān)聯(lián)制作中)，然后激活隱藏的單元組成數(shù)據(jù)在低維空間的表示，與PCA密切相關(guān)（看例子Diamantaras&Kung，1996），推廣到非線性領(lǐng)域，一種采用非線性激活功能和附加層。當(dāng)然這種過程可以被認(rèn)為是一種非線性PCA形式，應(yīng)該強(qiáng)調(diào)的是，由此產(chǎn)生的解決非線性優(yōu)化問題的網(wǎng)絡(luò)培訓(xùn)構(gòu)成，與獲得可能性深陷的局部極小值，因此依賴于這樣的結(jié)果與對訓(xùn)練的出發(fā)點(diǎn)。此外，在神經(jīng)網(wǎng)絡(luò)的實現(xiàn)的機(jī)器學(xué)習(xí)過程中通常存在這危險。非線性PCA神經(jīng)算法的另一個問題是，成分提取的數(shù)量必須

25、事先被確定。這也是下面方法的情況，其中，雖然在明確提取什么樣的非線性特征的清晰幾何圖片案例方面有優(yōu)勢。 主曲線：一個在輸入空間中的幾何解釋方法是從用主曲線法（Hastie&Stuetzle,1989）. 這種方法反復(fù)估計一曲線（或曲面），其中捕獲的數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)投射到曲線上（即映射到最接近的點(diǎn)），該算法試圖找到一條性質(zhì)曲線，該曲線上的每個點(diǎn)是所有數(shù)據(jù)點(diǎn)的平均值隱射到它上，可以證明，只有直線滿足后者是主要成分，所以主曲線的確是后者的推廣。計算主曲線，再次非線性優(yōu)化問題必須被解決的。 核PCA: 核PCA是PCA意義上的一種非線性的推廣，如果我們使用內(nèi)核k（x,y）=(x·y)

26、,我們恢復(fù)原來的PCA.得到PCA的非線性形式，我們僅僅選擇一個非線性核。此外，核PCA是一種在任意大（可能無限）維度的的特征空間中執(zhí)行PCA的PCA算法的泛化。 與上面的方法比較，核PCA主要的優(yōu)勢是不涉及非線性優(yōu)化，他本質(zhì)上是一種線性代數(shù)學(xué)與標(biāo)準(zhǔn)PCA一樣簡單，此外，我們不需要提前指定我們想要提取成分的數(shù)量，神經(jīng)的方法相比，核PCA如果我們需要處理大量的觀測是不好用的。6.試驗 在這節(jié)，我們提出了一個實驗即我們使用核PCA提取主成分集。首先，我們應(yīng)采取看一個簡單的玩具例子，在此之后，我們描述了現(xiàn)實中的實驗，我們試圖評估通過分類任務(wù)提取的主要成分效用。圖3：一個例子從MPI椅子數(shù)據(jù)庫中提取的圖像，左邊為原始椅子圖像，右邊為縮減像素在16×16像素數(shù)據(jù)庫中的圖像6.1 玩具實驗為了提供一些直覺關(guān)于怎樣在輸入空間中用FPCA，我們的實驗表明用人工的2 - D的數(shù)據(jù)集，用1度至4度多項式核（參照圖2）6.2 目標(biāo)識別