人工智能經(jīng)典電子書5.支持向量機-SMO算法實現(xiàn)

SMO算法內(nèi)容提要線性可分支持向量機線性不可分支持向量機支持向量機回歸實現(xiàn)策略多分類報告內(nèi)容SVM簡介求解算法-SMO優(yōu)化算法多分類問題系統(tǒng)演示SeparatingSurface:A+A-SVM算法特點SVM有如下主要幾個特點：(1)非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射；(2)對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊際的思想是SVM方法的核心；(3)支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定作用的是支持向量。因此，模型需要存儲空間小，算法魯棒性強；(4)無序任何前提假設(shè)，不涉及概率測度；(1)SVM算法對大規(guī)模訓(xùn)練樣本難以實施由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的計算（m為樣本的個數(shù)），當(dāng)m數(shù)目很大時該矩陣的存儲和計算將耗費大量的機器內(nèi)存和運算時間。針對以上問題的主要改進有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、張學(xué)工的CSVM以及O.L.Mangasarian等的SOR算法(2)用SVM解決多分類問題存在困難經(jīng)典的支持向量機算法只給出了二類分類的算法，而在數(shù)據(jù)挖掘的實際應(yīng)用中，一般要解決多類的分類問題?？梢酝ㄟ^多個二類支持向量機的組合來解決。主要有一對多組合模式、一對一組合模式和SVM決策樹；再就是通過構(gòu)造多個分類器的組合來解決。主要原理是克服SVM固有的缺點，結(jié)合其他算法的優(yōu)勢，解決多類問題的分類精度。如：與粗集理論結(jié)合，形成一種優(yōu)勢互補的多類問題的組合分類器。問題提出線性可分的分類問題：（令黑色的點=-1，白色的點=+1）所以當(dāng)有一個新的點x需要預(yù)測屬于哪個分類的時候，我們用sgn(f(x))，就可以預(yù)測了，sgn表示符號函數(shù)，當(dāng)f(x)>0的時候，sgn(f(x))=+1,當(dāng)f(x)<0的時候sgn(f(x))=–1。+1-1我們怎樣才能取得一個最優(yōu)的劃分直線f(x)呢？最大距離MaximumMarginal選擇使得間隙最大的函數(shù)作為分割平面是由很多道理的，比如說從概率的角度上來說，就是使得置信度最小的點置信度最大（聽起來很拗口），從實踐的角度來說，這樣的效果非常好，等等。最大距離f(x)=wx+b=0wx+b=1wx+b=-1(x,y)M目標(biāo)函數(shù)：等價于：因為單調(diào)，并且為了計算方便：求解問題數(shù)據(jù)集合：優(yōu)化目標(biāo)：x，y為已知數(shù)求解建立拉格朗日公式：求偏導(dǎo)數(shù)：求解：對偶問題求解將兩式帶回L(w,b,a)得到對偶問題的表達式求解問題數(shù)據(jù)集合：優(yōu)化目標(biāo)：x，y為已知數(shù)核函數(shù)線性不可分的情況我們可以為分錯的點加上一點懲罰，對一個分錯的點的懲罰函數(shù)就是這個點到其正確位置的距離：軟間隔C-SVMC是一個由用戶去指定的系數(shù)，表示對分錯的點加入多少的懲罰，當(dāng)C很大的時候，分錯的點就會更少，但是過擬合的情況可能會比較嚴(yán)重，當(dāng)C很小的時候，分錯的點可能會很多，不過可能由此得到的模型也會不太正確軟支持向量機求解構(gòu)造拉格朗日公式：求偏導(dǎo)數(shù)：求解問題數(shù)據(jù)集合：優(yōu)化目標(biāo)：其中C為人為設(shè)定，x，y為已知數(shù)問題？實際上在處理大型問題時，由于存儲和計算兩方面的要求，這些算法往往會失效。這些算法都要存儲與訓(xùn)練集相應(yīng)的核矩陣，然而存儲核矩陣所需要的內(nèi)存是隨著訓(xùn)練集中訓(xùn)練點數(shù)L的平凡增長的。例如，當(dāng)訓(xùn)練點數(shù)目超過4000時，存儲核函數(shù)矩陣需要多達128兆。求解方法：坐標(biāo)上升法固定除之外的所有參數(shù)，這時W可看作只是關(guān)于的函數(shù)，那么直接對求導(dǎo)優(yōu)化即可?？梢酝ㄟ^更改優(yōu)化順序來使W能夠更快地增加并收斂。如果W在內(nèi)循環(huán)中能夠很快地達到最優(yōu)，那么坐標(biāo)上升法會是一個很高效的求極值方法。問題？固定以外的所有參數(shù)，那么將不再是變量（可以由其他值推出），因為問題中規(guī)定了因此，我們最少一次需要選取兩個參數(shù)做優(yōu)化，比如

和，此時可以由和其他參數(shù)表示出來。=>SMO算法SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對線性SVM和數(shù)據(jù)稀疏時性能更優(yōu)。第一步選取一對參數(shù)，選取方法使用啟發(fā)式方法（Maximalviolatingpair）。第二步，固定除被選取的參數(shù)之外的其他參數(shù)，確定W極值。SMO算法設(shè)我們選取了初始值滿足了問題中的約束條件。接下來，我們固定其余參數(shù)，這樣W就是和的函數(shù)。并且和滿足條件：由于其余參數(shù)都是已知固定，因此為了方便，可將等式右邊標(biāo)記成實數(shù)值。SMO算法進而其中：目標(biāo)函數(shù)：求偏導(dǎo)：帶入w,v：求得：參數(shù)的求解最終參數(shù)的解為：其中：和？a的取值范圍當(dāng)a1和a2異號時，也就是一個為1，一個為-1時，他們可以表示成一條直線，斜率為1。如下圖：橫軸是

，縱軸是

，

和

既要在矩形方框內(nèi)，也要在直線上，因此同理，當(dāng)和同號時a2a1CCa1-a2=E(0,-E)(C,C-E){{參數(shù)求解參數(shù)計算：參數(shù)b計算：？b的求解設(shè)在界內(nèi)，則有，帶入上式得：兩邊同乘以，得b的求解在界內(nèi)，則在界內(nèi)，則、都在界內(nèi)，則情況1和情況2的B值相等，任取一個；都不在界內(nèi)，則取值為情況1和情況2之間的任意值。問題？算法如何終止？對于SMO算法，其中的兩個參數(shù)如何選擇呢？隨機？啟發(fā)式規(guī)則一個自然的想法是那些違反KKT最嚴(yán)重的點，他們對間距貢獻最大，因此可以通過該啟發(fā)規(guī)則來完成調(diào)整參數(shù)的選取。（并且此種啟發(fā)規(guī)則