支持向量分類機(jī)原理

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

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

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

途徑：

構(gòu)造一個(gè)約束條件下的優(yōu)化問題，具體說是一個(gè)帶線性不等式約束條件的二次規(guī)劃問題(constrainedquadraticprograming),求解該問題，構(gòu)造分類超平面，從而得到?jīng)Q策函數(shù)。提綱SVM有關(guān)概念介紹SVM分類問題的數(shù)學(xué)表示和推導(dǎo)簡單的最優(yōu)分類面廣義最優(yōu)分類面非線性最優(yōu)分類面分類問題的數(shù)學(xué)表示已知：訓(xùn)練集包含個(gè)樣本點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

線性分劃－>非線性分劃

代價(jià)：2維空間內(nèi)積－>6維空間內(nèi)積3.非線性分劃為此，引進(jìn)函數(shù)有比較(2.3.6)和(2.3.7)，可以發(fā)現(xiàn)這是一個(gè)重要的等式，提示6維空間中的內(nèi)積可以通過計(jì)算中2維空間中的內(nèi)積得到。實(shí)現(xiàn)非線性分劃的思想給定訓(xùn)練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù)，一旦選定了函數(shù)，就可以求解最優(yōu)化問題得，而決策函數(shù)實(shí)現(xiàn)非線性分劃的思想決策函數(shù)其中核函數(shù)(核或正定核)定義設(shè)是中的一個(gè)子集。稱定義在