支持向量機(jī)SMO算法

支持向量機(jī)（五）SMO算法11SMO優(yōu)化算法（Sequentialminimaloptimization）SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對線性SVM和數(shù)據(jù)稀疏時(shí)性能更優(yōu)。有關(guān)SMO最佳的資料就是他本人寫的《SequentialMinimalOptimizationAFastAlgorithmforTrainingSupportVectorMachines》了。我拜讀了一下，下面先說講義上對此辦法的總結(jié)。首先回到我們前面始終懸而未解的問題，對偶函數(shù)最后的優(yōu)化問題：要解決的是在參數(shù)上求最大值W的問題，至于和都是已知數(shù)。C由我們預(yù)先設(shè)定，也是已知數(shù)。按照坐標(biāo)上升的思路，我們首先固定除以外的全部參數(shù)，然后在上求極值。等一下，這個(gè)思路有問題，由于如果固定以外的全部參數(shù)，那么將不再是變量（能夠由其它值推出），由于問題中規(guī)定了因此，我們需要一次選用兩個(gè)參數(shù)做優(yōu)化，例如和，此時(shí)能夠由和其它參數(shù)表達(dá)出來。這樣回帶到W中，W就只是有關(guān)的函數(shù)了，可解。這樣，SMO的重要環(huán)節(jié)以下：意思是，第一步選用一對和，選用辦法使用啟發(fā)式辦法（背面講）。第二步，固定除和之外的其它參數(shù)，擬定W極值條件下的，由表達(dá)。SMO之因此高效就是由于在固定其它參數(shù)后，對一種參數(shù)優(yōu)化過程很高效。下面討論具體辦法：假設(shè)我們選用了初始值滿足了問題中的約束條件。接下來，我們固定，這樣W就是和的函數(shù)。并且和滿足條件：由于都是已知固定值，因此為了方面，可將等式右邊標(biāo)記成實(shí)數(shù)值。當(dāng)和異號時(shí)，也就是一種為1，一種為-1時(shí)，他們能夠表達(dá)成一條直線，斜率為1。以下圖：橫軸是，縱軸是，和既要在矩形方框內(nèi)，也要在直線上，因此，同理，當(dāng)和同號時(shí)，，然后我們打算將用表達(dá)：然后反代入W中，得展開后W能夠表達(dá)成。其中a,b,c是固定值。這樣，通過對W進(jìn)行求導(dǎo)能夠得到，然而要確保滿足，我們使用表達(dá)求導(dǎo)求出來的，然而最后的，要根據(jù)下面狀況得到：這樣得到后，我們能夠得到的新值。下面進(jìn)入Platt的文章，來找到啟發(fā)式搜索的辦法和求b值的公式。這邊文章使用的符號表達(dá)有點(diǎn)不太同樣，但是實(shí)質(zhì)是同樣的，先來熟悉一下文章中符號的表達(dá)。文章中定義特性到成果的輸出函數(shù)為與我們之前的實(shí)質(zhì)是一致的。原始的優(yōu)化問題為：求導(dǎo)得到：通過對偶后為：s.t.這里與W函數(shù)是同樣的，只是符號求反后，變成求最小值了。和是同樣的，都表達(dá)第i個(gè)樣本的輸出成果（1或-1）。通過加入松弛變量后，模型修改為：由公式（7）代入（1）中可知，這個(gè)過程和之前對偶過程同樣。重新整頓我們規(guī)定的問題為：與之對應(yīng)的KKT條件為：這個(gè)KKT條件闡明，在兩條間隔線外面的點(diǎn)，對應(yīng)前面的系數(shù)為0，在兩條間隔線里面的對應(yīng)為C，在兩條間隔線上的對應(yīng)的系數(shù)在0和C之間。將我們之前得到L和H重新拿過來：之前我們將問題進(jìn)行到這里，然后說將用表達(dá)后裔入W中，這里將代入中，得其中這里的和代表某次迭代前的原始值，因此是常數(shù)，而和是變量，待求。公式（24）中的最后一項(xiàng)是常數(shù)。由于和滿足下列公式由于的值是固定值，在迭代前后不會(huì)變。那么用s表達(dá)，上式兩邊乘以時(shí)，變?yōu)椋浩渲写耄?4）中，得這時(shí)候只有是變量了，求導(dǎo)如果的二階導(dǎo)數(shù)不不大于0（凹函數(shù)），那么一階導(dǎo)數(shù)為0時(shí)，就是極小值了。假設(shè)其二階導(dǎo)數(shù)為0（普通成立），那么上式化簡為：將w和v代入后，繼續(xù)化簡推導(dǎo)，得（推導(dǎo)了六七行推出來了）我們使用來表達(dá)：普通狀況下目的函數(shù)是正定的，也就是說，能夠在直線約束方向上求得最小值，并且。那么我們在（30）兩邊都除以能夠得到這里我們使用表達(dá)優(yōu)化后的值，是迭代前的值，。與之前提到的同樣不是最后迭代后的值，需要進(jìn)行約束：那么在特殊狀況下，可能不為正，如果核函數(shù)K不滿足Mercer定理，那么目的函數(shù)可能變得非正定，可能出現(xiàn)負(fù)值。即使K是有效的核函數(shù)，如果訓(xùn)練樣本中出現(xiàn)相似的特性x，那么仍有可能為0。SMO算法在不為正值的狀況下仍有效。為確保有效性，我們能夠推導(dǎo)出就是的二階導(dǎo)數(shù)，，沒有極小值，最小值在邊沿處取到（類比），時(shí)更是單調(diào)函數(shù)了，最小值也在邊沿處獲得，而的邊沿就是L和H。這樣將和分別代入中即可求得的最小值，對應(yīng)的還是也能夠懂得了。具體計(jì)算公式以下：至此，迭代關(guān)系式出了b的推導(dǎo)式以外，都已經(jīng)推出。b每一步都要更新，由于前面的KKT條件指出了和的關(guān)系，而和b有關(guān)，在每一步計(jì)算出后，根據(jù)KKT條件來調(diào)節(jié)b。b的更新有幾個(gè)狀況：來自羅林開的ppt這里的界內(nèi)指，界上就是等于0或者C了。前面兩個(gè)的公式推導(dǎo)能夠根據(jù)和對于有的KKT條件推出。這樣全部參數(shù)的更新公式都已經(jīng)介紹完畢，附加一點(diǎn)，如果使用的是線性核函數(shù)，我們就能夠繼續(xù)使用w了，這樣不用掃描整個(gè)樣本庫來作內(nèi)積了。w值的更新辦法為：根據(jù)前面的公式推導(dǎo)出。12SMO中拉格朗日乘子的啟發(fā)式選擇辦法終于到了最后一種問題了，所謂的啟發(fā)式選擇辦法重要思想是每次選擇拉格朗日乘子的時(shí)候，優(yōu)先選擇樣本前面系數(shù)的作優(yōu)化（論文中稱為無界樣例），由于在界上（為0或C）的樣例對應(yīng)的系數(shù)普通不會(huì)更改。這條啟發(fā)式搜索辦法是選擇第一種拉格朗日乘子用的，例如前面的。那么這樣選擇的話，與否最后會(huì)收斂?？尚业氖荗suna定理告訴我們只要選擇出來的兩個(gè)中有一種違反了KKT條件，那么目的函數(shù)在一步迭代后值會(huì)減小。違反KKT條件不代表，在界上也有可能會(huì)違反。是的，因此在給定初始值=0后，先對全部樣例進(jìn)行循環(huán)，循環(huán)中碰到違反KKT條件的（不管界上還是界內(nèi)）都進(jìn)行迭代更新。等這輪過后，如果沒有收斂，第二輪就只針對的樣例進(jìn)行迭代更新。在第一種乘子選擇后，第二個(gè)乘子也使用啟發(fā)式辦法選擇，第二個(gè)乘子的迭代步長大致正比于，選擇第二個(gè)乘子能夠最大化。即當(dāng)為正時(shí)選擇負(fù)的絕對值最大的，反之，選擇正值最大的。最后的收斂條件是在界內(nèi)（）的樣例都能夠遵照KKT條件，且其對應(yīng)的只在極小的范疇內(nèi)變動(dòng)。至于如何寫具體的程序，請參考JohnC.Platt在論文中給出的偽代碼。13總結(jié)這份SVM的講義重點(diǎn)概括了SVM的基本概念和基本推導(dǎo)，中規(guī)中矩卻又讓人醍醐灌頂。起初讓我最頭疼的是拉格朗日對偶和SMO，后來逐步明白拉格朗日對偶的重要作用是將w的計(jì)算提前并消除w，使得優(yōu)化函數(shù)變?yōu)槔窭嗜粘俗拥膯我粎?shù)優(yōu)化問題。而SMO里面迭代公式的推導(dǎo)也著實(shí)讓我耗費(fèi)了不少時(shí)間。對比這樣復(fù)雜的推導(dǎo)過程，SVM的思想確實(shí)那么簡樸。它不再像logistic回歸同樣企圖去擬合樣本點(diǎn)（中間加了一層sigmoid函數(shù)變換），而是就在樣本中去找分隔線，為了評判哪條分界限更加好，引入了幾何間隔最大化的目的。之后全部的推導(dǎo)都是去解決目的函數(shù)的最優(yōu)化上了。在解決最優(yōu)化的過程中，發(fā)現(xiàn)了w能夠由特性向量內(nèi)積來表達(dá)，進(jìn)而發(fā)現(xiàn)了核函數(shù)，僅需要調(diào)節(jié)核函數(shù)就能夠?qū)⑻匦赃M(jìn)行低維到高維的變換，在低維上進(jìn)行計(jì)算，實(shí)質(zhì)成果體現(xiàn)在高維上。由于并不是全部的樣本都可分，為了確保SVM的通用性，進(jìn)行了軟間隔的解決，造成的成果就是將優(yōu)化問題變得更加復(fù)