支持向量分類(lèi)機(jī)原理講述課件

SupportVectorClassification數(shù)據(jù)挖掘中的新方法－支持向量分類(lèi)機(jī)原理位禮奎2016年6月SupportVectorClassification數(shù)提綱SVM有關(guān)概念介紹SVM分類(lèi)問(wèn)題的數(shù)學(xué)表示和推導(dǎo)簡(jiǎn)單的最優(yōu)分類(lèi)面廣義最優(yōu)分類(lèi)面非線性最優(yōu)分類(lèi)面提綱SVM有關(guān)概念介紹HistorySVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來(lái)，目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用。

HistorySVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，它傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法只有在樣本趨向無(wú)窮大時(shí)，其性能才有理論的保證。統(tǒng)計(jì)學(xué)習(xí)理論（STL）研究有限樣本情況下的機(jī)器學(xué)習(xí)問(wèn)題。SVM的理論基礎(chǔ)就是統(tǒng)計(jì)學(xué)習(xí)理論。傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法在進(jìn)行機(jī)器學(xué)習(xí)時(shí)，強(qiáng)調(diào)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。而單純的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化會(huì)產(chǎn)生“過(guò)學(xué)習(xí)問(wèn)題”，其推廣能力較差。推廣能力是指:將學(xué)習(xí)機(jī)器(即預(yù)測(cè)函數(shù),或稱(chēng)學(xué)習(xí)函數(shù)、學(xué)習(xí)模型)對(duì)未來(lái)輸出進(jìn)行正確預(yù)測(cè)的能力。傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法只有在樣本趨向無(wú)窮大時(shí)，其性能才有理論“過(guò)學(xué)習(xí)問(wèn)題”：某些情況下，當(dāng)訓(xùn)練誤差過(guò)小反而會(huì)導(dǎo)致推廣能力的下降。例如：對(duì)一組訓(xùn)練樣本(x,y),x分布在實(shí)數(shù)范圍內(nèi)，y取值在[0，1]之間。無(wú)論這些樣本是由什么模型產(chǎn)生的，我們總可以用y=sin(w*x)去擬合，使得訓(xùn)練誤差為0.“過(guò)學(xué)習(xí)問(wèn)題”：某些情況下，當(dāng)訓(xùn)練誤差過(guò)小反而會(huì)導(dǎo)致推廣能力根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)由經(jīng)驗(yàn)風(fēng)險(xiǎn)值和置信范圍值兩部分組成。而基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則的學(xué)習(xí)方法只強(qiáng)調(diào)了訓(xùn)練樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小誤差，沒(méi)有最小化置信范圍值，因此其推廣能力較差。Vapnik提出的支持向量機(jī)（SupportVectorMachine,SVM）以訓(xùn)練誤差作為優(yōu)化問(wèn)題的約束條件，以置信范圍值最小化作為優(yōu)化目標(biāo)，即SVM是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則的學(xué)習(xí)方法，其推廣能力明顯優(yōu)于一些傳統(tǒng)的學(xué)習(xí)方法。根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)由經(jīng)驗(yàn)風(fēng)險(xiǎn)值和置信范圍值由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問(wèn)題的求解，因此SVM的解是全局唯一的最優(yōu)解SVM在解決小樣本、非線性及高維模式識(shí)別問(wèn)題中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問(wèn)題的求解，因此SVM關(guān)于SVM思想：

通過(guò)某種事先選擇的非線性映射（核函數(shù)）將輸入向量映射到一個(gè)高維特征空間，在這個(gè)空間中尋找最優(yōu)分類(lèi)超平面。使得它能夠盡可能多的將兩類(lèi)數(shù)據(jù)點(diǎn)正確的分開(kāi)，同時(shí)使分開(kāi)的兩類(lèi)數(shù)據(jù)點(diǎn)距離分類(lèi)面最遠(yuǎn)。

途徑：

構(gòu)造一個(gè)約束條件下的優(yōu)化問(wèn)題，具體說(shuō)是一個(gè)帶線性不等式約束條件的二次規(guī)劃問(wèn)題(constrainedquadraticprograming),求解該問(wèn)題，構(gòu)造分類(lèi)超平面，從而得到?jīng)Q策函數(shù)。關(guān)于SVM思想：

通過(guò)某種事先選擇的非線性映射提綱SVM有關(guān)概念介紹SVM分類(lèi)問(wèn)題的數(shù)學(xué)表示和推導(dǎo)簡(jiǎn)單的最優(yōu)分類(lèi)面廣義最優(yōu)分類(lèi)面非線性最優(yōu)分類(lèi)面提綱SVM有關(guān)概念介紹分類(lèi)問(wèn)題的數(shù)學(xué)表示已知：訓(xùn)練集包含個(gè)樣本點(diǎn)：

說(shuō)明：是輸入指標(biāo)向量，或稱(chēng)輸入，或稱(chēng)模式，其分量稱(chēng)為特征，或?qū)傩?，或輸入指?biāo)；是輸出指標(biāo)，或輸出.問(wèn)題：對(duì)一個(gè)新的模式，推斷它所對(duì)應(yīng)的輸出是1還是-1.實(shí)質(zhì)：找到一個(gè)把上的點(diǎn)分成兩部分的規(guī)則.

2維空間上的分類(lèi)問(wèn)題)n維空間上的分類(lèi)問(wèn)題.分類(lèi)問(wèn)題的數(shù)學(xué)表示2維空間上的分類(lèi)問(wèn)題)n維根據(jù)給定的訓(xùn)練集其中，，尋找上的一個(gè)實(shí)值函數(shù)，用決策函數(shù)

判斷任一模式對(duì)應(yīng)的值.

可見(jiàn)，分類(lèi)學(xué)習(xí)機(jī)——構(gòu)造決策函數(shù)的方法(算法)，兩類(lèi)分類(lèi)問(wèn)題多類(lèi)分類(lèi)問(wèn)題線性分類(lèi)學(xué)習(xí)機(jī)非線性分類(lèi)學(xué)習(xí)機(jī)

分類(lèi)學(xué)習(xí)方法分類(lèi)學(xué)習(xí)方法SVM分類(lèi)問(wèn)題大致有三種：線性可分問(wèn)題、近似線性可分問(wèn)題、線性不可分問(wèn)題。SVM分類(lèi)問(wèn)題大致有三種：線性可分問(wèn)題、近似線性可分問(wèn)題、線

最大間隔原則最大間隔原則考慮圖1.2.1(a)——上的線性可分的分類(lèi)問(wèn)題.這里有許多直線能將兩類(lèi)點(diǎn)正確分開(kāi).如何選取和？簡(jiǎn)單問(wèn)題：設(shè)法方向已選定，如何選??？解答：選定平行直線極端直線和取和的中間線為分劃直線如何選取？對(duì)應(yīng)一個(gè)，有極端直線，稱(chēng)和之間的距離為“間隔”，顯然應(yīng)選使“間隔”最大的。

最大間隔法的直觀導(dǎo)出考慮圖1.2.1(a)——上的線性可分的分類(lèi)問(wèn)題.數(shù)學(xué)語(yǔ)言描述：給定適當(dāng)?shù)姆ǚ较蚝?，這兩條極端直線可表示為調(diào)整，使得令，則兩式可以等價(jià)寫(xiě)為與此相應(yīng)的分劃直線表達(dá)式:數(shù)學(xué)語(yǔ)言描述：調(diào)整，使得令，則兩式如何計(jì)算分劃間隔？考慮2維空間中極端直線之間的間隔情況求出兩條極端直線的距離：如何計(jì)算分劃間隔？求出兩條極端直線的距離：

原始問(wèn)題

原始問(wèn)題求解原始問(wèn)題？為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對(duì)偶問(wèn)題來(lái)求解對(duì)偶問(wèn)題

為原始問(wèn)題中與每個(gè)約束條件對(duì)應(yīng)的Lagrange乘子。這是一個(gè)不等式約束條件下的二次函數(shù)尋優(yōu)問(wèn)題，存在唯一解求解原始問(wèn)題？為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，我們轉(zhuǎn)化為對(duì)偶1.線性可分問(wèn)題計(jì)算，選擇的一個(gè)正分量,并據(jù)此計(jì)算事實(shí)上，的每一個(gè)分量都與一個(gè)訓(xùn)練點(diǎn)相對(duì)應(yīng)。而分劃超平面僅僅依賴(lài)于不為零的訓(xùn)練點(diǎn)，而與對(duì)應(yīng)于為零的那些訓(xùn)練點(diǎn)無(wú)關(guān)。稱(chēng)不為零的這些訓(xùn)練點(diǎn)的輸入為支持向量(SV)構(gòu)造分劃超平面,決策函數(shù)根據(jù)最優(yōu)解1.線性可分問(wèn)題計(jì)算2.近似線性可分問(wèn)題不要求所有訓(xùn)練點(diǎn)都滿足約束條件，為此對(duì)第個(gè)訓(xùn)練點(diǎn)引入松弛變量(SlackVariable),把約束條件放松到。

體現(xiàn)了訓(xùn)練集被錯(cuò)分的情況，可采用作為一種度量來(lái)描述錯(cuò)劃程度。兩個(gè)目標(biāo)：1.間隔盡可能大2.錯(cuò)劃程度盡可能小顯然，當(dāng)充分大時(shí)，樣本點(diǎn)總可以滿足以上約束條件。然而事實(shí)上應(yīng)避免太大，所以需在目標(biāo)函數(shù)對(duì)進(jìn)行懲罰（即“軟化”約束條件）2.近似線性可分問(wèn)題不要求所有訓(xùn)練點(diǎn)都滿足約束條件2.近似線性可分問(wèn)題因此，引入一個(gè)懲罰參數(shù)，新的目標(biāo)函數(shù)變?yōu)?

體現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn)，而則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù)實(shí)質(zhì)上是對(duì)經(jīng)驗(yàn)風(fēng)險(xiǎn)和表達(dá)能力匹配一個(gè)裁決。當(dāng)時(shí)，近似線性可分SVC的原始問(wèn)題退化為線性可分SVC的原始問(wèn)題。2.近似線性可分問(wèn)題因此，引入一個(gè)懲罰參數(shù)算法：(廣義)線性支持向量分類(lèi)機(jī)設(shè)已知訓(xùn)練集，其中2.選擇適當(dāng)?shù)膽土P參數(shù)，構(gòu)造并求解最優(yōu)化問(wèn)題3.計(jì)算，選擇的一個(gè)分量，并據(jù)此計(jì)算出4.構(gòu)造分劃超平面,決策函數(shù)求得算法：(廣義)線性支持向量分類(lèi)機(jī)設(shè)已知訓(xùn)練集3.非線性分劃例子:3.非線性分劃例子:3.非線性分劃設(shè)訓(xùn)練集，其中假定可以用平面上的二次曲線來(lái)分劃：現(xiàn)考慮把2維空間映射到6維空間的變換上式可將2維空間上二次曲線映射為6維空間上的一個(gè)超平面：3.非線性分劃設(shè)訓(xùn)練集3.非線性分劃可見(jiàn)，只要利用變換(2.3.4)，把所在的2維空間的兩類(lèi)輸入點(diǎn)映射到所在的6維空間，然后在這個(gè)6維空間中，使用線性學(xué)習(xí)機(jī)求出分劃超平面：最后得出原空間中的二次曲線：怎樣求6維空間中的分劃超平面？(線性支持向量分類(lèi)機(jī))3.非線性分劃可見(jiàn)，只要利用變換(2.3.4)，把3.非線性分劃需要求解的最優(yōu)化問(wèn)題其中3.非線性分劃需要求解的最優(yōu)化問(wèn)題其中3.非線性分劃在求得最優(yōu)化問(wèn)題的解后，得到分劃超平面其中最后得到?jīng)Q策函數(shù)或

線性分劃－>非線性分劃

代價(jià)：2維空間內(nèi)積－>6維空間內(nèi)積3.非線性分劃在求得最優(yōu)化問(wèn)題的解3.非線性分劃為此，引進(jìn)函數(shù)有比較(2.3.6)和(2.3.7)，可以發(fā)現(xiàn)這是一個(gè)重要的等式，提示6維空間中的內(nèi)積可以通過(guò)計(jì)算中2維空間中的內(nèi)積得到。3.非線性分劃為此，引進(jìn)函數(shù)有比較(2.3.6)和(2.3實(shí)現(xiàn)非線性分劃的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問(wèn)題得，而決策函數(shù)實(shí)現(xiàn)非線性分劃的思想給定訓(xùn)練集后，決策函數(shù)僅依賴(lài)于得實(shí)現(xiàn)非線性分劃的思想決策函數(shù)其中實(shí)現(xiàn)非線性分劃的思想決策函數(shù)其中核函數(shù)(核或正定核)定義設(shè)是中的一個(gè)子集。稱(chēng)定義在上的函數(shù)是核函數(shù)(正定核或核)，如果存在著從到某一個(gè)空間的映射使得其中表示中的內(nèi)積核函數(shù)(核或正定核)定義設(shè)是中的一個(gè)子集核函數(shù)的選擇多項(xiàng)式內(nèi)核徑向基函數(shù)內(nèi)核RBFSigmoind內(nèi)核目前研究最多的核函數(shù)主要有三類(lèi)：得到q階多項(xiàng)式分類(lèi)器每個(gè)基函數(shù)中心對(duì)應(yīng)一個(gè)支持向量，它們及輸出權(quán)值由算法自動(dòng)確定包含一個(gè)隱層的多層感知器，隱層節(jié)點(diǎn)數(shù)是