最新適用于初學(xué)者的模式識別核方法與支持向量機簡介

1、 夏夏 森森 （1）核函數(shù)方法簡介 早在1964年aizermann等在勢函數(shù)方法的研究中就將該技術(shù)引入到機器學(xué)習(xí)領(lǐng)域，但是直到1992年vapnik等利用該技術(shù)成功地將線性svms推廣到非線性svms時其潛力才得以充分挖掘。而核函數(shù)的理論則更為古老，mercer定理可以追溯到1909年，再生核希爾伯特空間(reproducingkernel hilbert space, rkhs)研究是在20世紀(jì)40年代開始的。（2）核函數(shù)方法原理 根據(jù)模式識別理論，低維空間線性不可分的模式通過非線性映射到高維特征空間則可能實現(xiàn)線性可分，但是如果直接采用這種技術(shù)在高維空間進行分類或回歸，則存在確定非線性映射

2、函數(shù)的形式和參數(shù)、特征空間維數(shù)等問題，而最大的障礙則是在高維特征空間運算時存在的“維數(shù)災(zāi)難”。采用核函數(shù)技術(shù)可以有效地解決這樣問題。 設(shè)x,zx,x屬于r（n）空間,非線性函數(shù)實現(xiàn)輸入間x到特征空間f的映射,其中f屬于r（m）,nm。根據(jù)核函數(shù)技術(shù)有： k(x,z) = 其中：為內(nèi)積,k(x,z)為核函數(shù)。從式可以看出，核函數(shù)將m維高維空間的內(nèi)積運算轉(zhuǎn)化為n維低維輸入空間的核函數(shù)計算，從而巧妙地解決了在高維特征空間中計算的“維數(shù)災(zāi)難”等問題，從而為在高維特征空間解決復(fù)雜的分類或回歸問題奠定了理論基礎(chǔ)。（3）核函數(shù)特點 核函數(shù)方法的廣泛應(yīng)用,與其特點是分不開的： 1）核函數(shù)的引入避免了“維數(shù)災(zāi)難

3、”,大大減小了計算量。而輸入空間的維數(shù)n對核函數(shù)矩陣無影響，因此，核函數(shù)方法可以有效處理高維輸入。 2）無需知道非線性變換函數(shù)的形式和參數(shù). 3）核函數(shù)的形式和參數(shù)的變化會隱式地改變從輸入空間到特征空間的映射，進而對特征空間的性質(zhì)產(chǎn)生影響，最終改變各種核函數(shù)方法的性能。 4）核函數(shù)方法可以和不同的算法相結(jié)合，形成多種不同的基于核函數(shù)技術(shù)的方法，且這兩部分的設(shè)計可以單獨進行，并可以為不同的應(yīng)用選擇不同的核函數(shù)和算法。（4）常見核函數(shù) 核函數(shù)的確定并不困難,滿足mercer定理的函數(shù)都可以作為核函數(shù)。常用的核函數(shù)可分為兩類，即內(nèi)積核函數(shù)和平移不變核函數(shù)，（5）核函數(shù)方法實施步驟 核函數(shù)方法是一種模

4、塊化(modularity)方法，它可分為核函數(shù)設(shè)計和算法設(shè)計兩個部分，具體為：1）收集和整理樣本,并進行標(biāo)準(zhǔn)化； 2）選擇或構(gòu)造核函數(shù)； 3）用核函數(shù)將樣本變換成為核函數(shù)矩陣,這一步相當(dāng)于將輸入數(shù)據(jù)通過非線性函數(shù)映射到高維特征空間；4）在特征空間對核函數(shù)矩陣實施各種線性算法；5）得到輸入空間中的非線性模型。顯然,將樣本數(shù)據(jù)核化成核函數(shù)矩陣是核函數(shù)方法中的關(guān)鍵。注意到核函數(shù)矩陣是ll的對稱矩陣，其中l(wèi)為樣本數(shù)。（6）核函數(shù)在模式識別中的應(yīng)用1）新方法。主要用在基于結(jié)構(gòu)風(fēng)險最小化(structural risk minimization,srm)的svm中。2）傳統(tǒng)方法改造。如核主元分析(ker

5、nel pca)、核主元回歸(kernel pcr)、核部分最小二乘法(kernel pls)、核fisher判別分析(kernel fisher discriminator, kfd)、核獨立主元分析(kernel independent component analysis,kica)等，這些方法在模式識別等不同領(lǐng)域的應(yīng)用中都表現(xiàn)了很好的性能。vc維維 vc維維：對于一個指示函數(shù)（即只有0和1兩種取值的函數(shù)）集，如果存在h個樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個樣本打散，函數(shù)集的vc維就是能夠打散的最大樣本數(shù)目。 如果對任意的樣本數(shù)，總有函數(shù)能打散它們，

6、則函數(shù)集的vc維就是無窮大。 一般而言,vc維越大, 學(xué)習(xí)能力就越強,但學(xué)習(xí)機器也越復(fù)雜。 目前還沒有通用的關(guān)于計算任意函數(shù)集的vc維的理論,只有對一些特殊函數(shù)集的vc維可以準(zhǔn)確知道。 n維實數(shù)空間中線性分類器和線性實函數(shù)的vc維是n+1。 學(xué)習(xí)機器的實際風(fēng)險由兩部分組成: 訓(xùn)練樣本的經(jīng)驗風(fēng)險 置信范圍(同置信水平有關(guān),而且同學(xué)習(xí)機器的vc維和訓(xùn)練樣本數(shù)有關(guān)。 在訓(xùn)練樣本有限的情況下,學(xué)習(xí)機器的vc維越高,則置信范圍就越大,導(dǎo)致實際風(fēng)險與經(jīng)驗風(fēng)險之間可能的差就越大。 在設(shè)計分類器時, 不但要使經(jīng)驗風(fēng)險最小化,還要使vc維盡量小,從而縮小置信范圍,使期望風(fēng)險最小。(ln(2 / ) 1) ln(

7、 /4)( )( )emphn hrrn 結(jié)構(gòu)風(fēng)險最小化 傳統(tǒng)機器學(xué)習(xí)方法中普遍采用的經(jīng)驗風(fēng)險最小化原則在樣本數(shù)目有限時是不合理的,因此，需要同時最小化經(jīng)驗風(fēng)險和置信范圍。 統(tǒng)計學(xué)習(xí)理論提出了一種新的策略,即把函數(shù)集構(gòu)造為一個函數(shù)子集序列,使各個子集按照vc維的大小排列;在每個子集中尋找最小經(jīng)驗風(fēng)險,在子集間折衷考慮經(jīng)驗風(fēng)險和置信范圍,取得實際風(fēng)險的最小。這種思想稱作結(jié)構(gòu)風(fēng)險最小化(structural risk minimization)，即srm準(zhǔn)則。實現(xiàn)srm原則的兩種思路 在每個子集中求最小經(jīng)驗風(fēng)險,然后選擇使最小經(jīng)驗風(fēng)險和置信范圍之和最小的子集。 設(shè)計函數(shù)集的某種結(jié)構(gòu)使每個子集中都能

8、取得最小的經(jīng)驗風(fēng)險,然后只需選擇適當(dāng)?shù)淖蛹怪眯欧秶钚?則這個子集中使經(jīng)驗風(fēng)險最小的函數(shù)就是最優(yōu)函數(shù)。支持向量機方法實際上就是這種思路的實現(xiàn)。多核學(xué)習(xí)方法 人們對核方法的關(guān)注,得益于支持向量機(support vector machine,svm)理論的發(fā)展和應(yīng)用,核函數(shù)的采用使得線性的svm很容易推廣到非線性的svm.其核心在于利用相對簡單得多的核函數(shù)運算,既避免了特征空間中復(fù)雜的內(nèi)積計算,又避免了特征空間(學(xué)習(xí)機器)本身的設(shè)計。 多核學(xué)習(xí)方法是當(dāng)前核機器學(xué)習(xí)領(lǐng)域的一個新的熱點.核方法是解決非線性模式分析問題的一種有效方法,但在一些復(fù)雜情形下,由單個核函數(shù)構(gòu)成的核機器并不能滿足諸如 ： 數(shù)

9、據(jù)異構(gòu)或不規(guī)則、樣本規(guī)模巨大、樣本不平坦分布等實際的應(yīng)用需求,因此將多個核函數(shù)進行組合,以獲得更好的結(jié)果。svm廣義最優(yōu)分類面 假定訓(xùn)練數(shù)據(jù) 可以被一個超平面分開 我們進行正歸化 此時分類間隔等于 使最大間隔最大等價于使 最小11( ,),.,( ,), 1, 1nllx yx yxr y rbrwbxwn, 0).() 1,1,.,iiyw xbil2w2w 最優(yōu)分類面問題可以表示成約束優(yōu)化問題 minimize subject to211( )()22() 1,1,.,iiwww wyw xbilsvm多類的情況 svm本質(zhì)上是兩類分類器. 常用的svm多值分類器，利用線性判別函數(shù)設(shè)計多類

10、分類器有多種方法。例如可以把k類問題轉(zhuǎn)化為k個兩類問題，其中第i 個問題是用線性判別函數(shù)把屬于ci類與不屬于ci類的點分開。更復(fù)雜一點的方法是用k(k-1)/2個線性判別函數(shù)，把樣本分為k個類別，每個線性判別函數(shù)只對其中的兩個類別分類。svm訓(xùn)練算法訓(xùn)練算法傳統(tǒng)的利用標(biāo)準(zhǔn)二次型優(yōu)化技術(shù)解決對偶問題的方法,是svm訓(xùn)練算法慢及受到訓(xùn)練樣本集規(guī)模制約的主要原因。目前已提出了許多解決方法和改進算法,主要是從如何處理大規(guī)模樣本集的訓(xùn)練問題、提高訓(xùn)練算法收斂速度等方面改進。主要有：分解方法、修改優(yōu)化問題法、增量學(xué)習(xí)法、幾何方法等分別討論。svm分類算法分類算法 訓(xùn)練好svm分類器后,得到的支持向量被用來構(gòu)成決策分類面。對于大規(guī)模樣本集問題,svm訓(xùn)練得到的支持向量數(shù)目很大,則進行分類決策時的計算代價就是一個值得考慮的問題。 解決方法如：縮減集(reduced set) svm方法，采用縮減集代替支持向量集,縮減集中的向量不是支持向量,數(shù)目比支持向量少,但它們在分類決策函數(shù)中的形式與支持向量相同。svm方法的特點 svm 的最終決策函數(shù)只由少數(shù)的支持向量所確定,計算的復(fù)雜性取決于支持向量的數(shù)目,而