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

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

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

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

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

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

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

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

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

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

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