降維算法(二)非線性降

1、1降維算法（二） 非線性降維一、 核技巧（Kernel method）二、等距映射(Isomap)2核函數(shù)發(fā)展歷史 早在1964年Aizermann等在勢函數(shù)方法的研究中就將該技術(shù)引入到機器學(xué)習(xí)領(lǐng)域，但是直到1992年Vapnik等利用該技術(shù)成功地將線性SVMs推廣到非線性SVMs時其潛力才得以充分挖掘。而核函數(shù)的理論則更為古老，Mercer定理可以追溯到1909年，再生核希爾伯特空間(ReproducingKernel Hilbert Space, RKHS)研究是在20世紀(jì)40年代開始的。 3n核方法的思想核方法核方法核方法的主要思想是基于這樣一個假設(shè)：“在低維空間中不能線性分割的點集，通

2、過轉(zhuǎn)化為高維空間中的點集時，很有可能變?yōu)榫€性可分的” ，例如下圖 左圖的兩類數(shù)據(jù)要想在一維空間上線性分開是不可能的，然而通過F(x)=(x-a)(x-b)把一維空間上的點轉(zhuǎn)化為右圖上的二維空間上，就是可以線性分割的了 4 如果直接把低維度的數(shù)據(jù)轉(zhuǎn)化到高維度的空間中，然后再去尋找線性分割平面，會遇到兩個大問題。n一是由于是在高維度空間中計算，導(dǎo)致curse of dimension問題；n二是非常的麻煩，每一個點都必須先轉(zhuǎn)換到高維度空間，然后求取分割平面的參數(shù)等等；怎么解決這些問題？ 答案是通過核方法（kernel method） 5 定義一個核函數(shù)K(x1,x2)= 其中x1和x2是低維度空間

3、中點（在這里可以是標(biāo)量，也可以是向量），(xi)是低維度空間的點xi轉(zhuǎn)化為高維度空間中的點的表示， 表示向量的內(nèi)積。 )(),(21xx注意：這里核函數(shù)K(x1,x2)的表達方式一般都不會顯式地寫為內(nèi)積的形式，即我們不關(guān)心高維度空間的形式。核函數(shù)巧妙地解決了上述的問題，在高維度中向量的內(nèi)積通過低維度的點的核函數(shù)就可以計算了。 核方法的原理6這里還有一個問題：“為什么我們要關(guān)心向量的內(nèi)積？”，一般地，我們可以把分類的問題分為兩類： 參數(shù)學(xué)習(xí)的形式和基于實例的學(xué)習(xí)形式。參數(shù)學(xué)習(xí)的形式參數(shù)學(xué)習(xí)的形式 就是通過一堆訓(xùn)練數(shù)據(jù)，把相應(yīng)模型的參數(shù)給學(xué)習(xí)出來，然后訓(xùn)練數(shù)據(jù)就沒有用了，對于新的數(shù)據(jù)，用學(xué)習(xí)出來的

4、參數(shù)即可以得到相應(yīng)的結(jié)論； 基于實例的學(xué)習(xí)基于實例的學(xué)習(xí)（又叫基于內(nèi)積的學(xué)習(xí)）則是在預(yù)測的時候也會使用訓(xùn)練數(shù)據(jù)，如KNN算法。而基于實例的學(xué)習(xí)一般就需要判定兩個點之間的相似程度，一般就通過向量的內(nèi)積來表達。從這里可以看出，核方法不是萬能的，它一般只針對基于實例的學(xué)習(xí)。 7n核函數(shù)的存在性判斷和如何構(gòu)造核函數(shù)的存在性判斷和如何構(gòu)造？ 既然我們不關(guān)心高維度空間的表達形式，那么怎么才能判斷一個函數(shù)是否是核函數(shù)呢？nMercer 定理定理：任何半正定的函數(shù)都可以作為核函數(shù)。所謂半正定的函數(shù)f(xi,xj)，是指擁有訓(xùn)練數(shù)據(jù)集合（x1,x2,.xn)，我們定義一個矩陣的元素aij = f(xi,xj)，

5、這個矩陣式n*n的，如果這個矩陣是半正定的，那么f(xi,xj)就稱為半正定的函數(shù)。 這個mercer定理不是核函數(shù)必要條件，只是一個充分條件，即還有不滿足mercer定理的函數(shù)也可以是核函數(shù)。 8n常見的核函數(shù)有高斯核，多項式核等等，在這些常見核的基礎(chǔ)上，通過核函數(shù)的性質(zhì)（如對稱性等）可以進一步構(gòu)造出新的核函數(shù)。9核函數(shù)設(shè)計和算法設(shè)計1）收集和整理樣本,并進行標(biāo)準(zhǔn)化；2）選擇或構(gòu)造核函數(shù)；3）用核函數(shù)將樣本變換成為核函數(shù)矩陣, 這 一步相當(dāng)于將輸入數(shù)據(jù)通過非線性函數(shù)映射到高維特征空間；4）在特征空間對核函數(shù)矩陣實施各種線性算法；5）得到輸入空間中的非線性模型。10等距映射（Isomap）n流

6、形學(xué)習(xí)算法 流形學(xué)習(xí)方法(Manifold Learning)，簡稱流形學(xué)習(xí)，自2000年在著名的科學(xué)雜志Science被首次提出以來，已成為信息科學(xué)領(lǐng)域的研究熱點。在理論和應(yīng)用上，流形學(xué)習(xí)方法都具有重要的研究意義 麻省理工學(xué)院計算機科學(xué)與人工智能實驗室的JoshTenenbaum教授 11n而非線性方法則是對線性方法的線性擴展，如主成分分析（Principal component analysis，PCA），多維尺度變換（Multidimensional scaling，MDS）等。 121314nIsomap的主要目標(biāo)是對于給定的高維流形，欲找到其對應(yīng)的低維嵌入，使得高維流形上數(shù)據(jù)點間的近鄰結(jié)構(gòu)在低維嵌入中得以保持。Isomap以MDS(Multidimensional Scaling)為計算工具，創(chuàng)新之處在于計算高維流形上數(shù)據(jù)點間距離時，不是用傳統(tǒng)的歐式距離，而是采用微分幾何中的測地線距離（或稱為曲線距離），并且找到了一種用實際輸入數(shù)據(jù)估計其測地線距離的算法（即圖論中的最小路徑逼近測地線距離)。 15流形學(xué)習(xí)的幾何圖示1617算法描述18Isomap的