[[206589]]

前言

之前實(shí)現(xiàn)了簡(jiǎn)單的SMO算法來(lái)優(yōu)化SVM的對(duì)偶問(wèn)題，其中在選取α的時(shí)候使用的是兩重循環(huán)通過(guò)完全隨機(jī)的方式選取，具體的實(shí)現(xiàn)參考《機(jī)器學(xué)習(xí)算法實(shí)踐-SVM中的SMO算法》。

本文在之前簡(jiǎn)化版SMO算法的基礎(chǔ)上實(shí)現(xiàn)了使用啟發(fā)式選取α對(duì)的方式的Platt SMO算法來(lái)優(yōu)化SVM。另外由于最近自己也實(shí)現(xiàn)了一個(gè)遺傳算法框架GAFT，便也嘗試使用遺傳算法對(duì)于SVM的原始形式進(jìn)行了優(yōu)化。

• 對(duì)于本文算法的相應(yīng)實(shí)現(xiàn)，參考:https://github.com/PytLab/MLBox/tree/master/svm
• 遺傳算法框架GAFT項(xiàng)目地址: https://github.com/PytLab/gaft

正文

SMO中啟發(fā)式選擇變量

在SMO算法中，我們每次需要選取一對(duì)α來(lái)進(jìn)行優(yōu)化，通過(guò)啟發(fā)式的選取我們可以更高效的選取待優(yōu)化的變量使得目標(biāo)函數(shù)下降的最快。

針對(duì)第一個(gè)α1和第二個(gè)α2 Platt SMO采取不同的啟發(fā)式手段。

第一個(gè)變量的選擇

第一個(gè)變量的選擇為外循環(huán)，與之前便利整個(gè)αα列表不同，在這里我們?cè)谡麄€(gè)樣本集和非邊界樣本集間進(jìn)行交替:

首先我們對(duì)整個(gè)訓(xùn)練集進(jìn)行遍歷, 檢查是否違反KKT條件，如果改點(diǎn)的αiαi和xi,yixi,yi違反了KKT條件則說(shuō)明改點(diǎn)需要進(jìn)行優(yōu)化。

Karush-Kuhn-Tucker(KKT)條件是正定二次規(guī)劃問(wèn)題最優(yōu)點(diǎn)的充分必要條件。針對(duì)SVM對(duì)偶問(wèn)題，KKT條件非常簡(jiǎn)單:

在遍歷了整個(gè)訓(xùn)練集并優(yōu)化了相應(yīng)的α后第二輪迭代我們僅僅需要遍歷其中的非邊界α. 所謂的非邊界α就是指那些不等于邊界0或者C的α值。 同樣這些點(diǎn)仍然需要檢查是否違反KKT條件并進(jìn)行優(yōu)化.

之后就是不斷地在兩個(gè)數(shù)據(jù)集中來(lái)回交替，最終所有的α都滿足KKT條件的時(shí)候，算法中止。

為了能夠快速選取有最大步長(zhǎng)的α，我們需要對(duì)所有數(shù)據(jù)對(duì)應(yīng)的誤差進(jìn)行緩存，因此特地寫(xiě)了個(gè)SVMUtil類(lèi)來(lái)保存svm中重要的變量以及一些輔助方法: 

下面為第一個(gè)變量選擇交替遍歷的大致代碼，相應(yīng)完整的Python實(shí)現(xiàn)(完整實(shí)現(xiàn)見(jiàn)https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py):  

第二個(gè)變量的選擇

SMO中的第二個(gè)變量的選擇過(guò)程為內(nèi)循環(huán)，當(dāng)我們已經(jīng)選取第一個(gè)α1之后，我們希望我們選取的第二個(gè)變量α2優(yōu)化后能有較大的變化。根據(jù)我們之前推導(dǎo)的式子   

可以知道，新的α2的變化依賴于|E1−E2|, 當(dāng)E1為正時(shí)， 那么選擇最小的Ei作為E2，通常將每個(gè)樣本的Ei緩存到一個(gè)列表中，通過(guò)在列表中選擇具有|E1−E2|的α2來(lái)近似最大化步長(zhǎng)。

有時(shí)候按照上述的啟發(fā)式方式仍不能夠是的函數(shù)值有足夠的下降，這是按下述步驟進(jìn)行選擇:

在非邊界數(shù)據(jù)集上選擇能夠使函數(shù)值足夠下降的樣本作為第二個(gè)變量

如果非邊界數(shù)據(jù)集上沒(méi)有，則在整個(gè)數(shù)據(jù)僅上進(jìn)行第二個(gè)變量的選擇

如果仍然沒(méi)有則重新選擇第一個(gè)α1

第二個(gè)變量選取的Python實(shí)現(xiàn): 

KKT條件允許一定的誤差

在Platt論文中的KKT條件的判斷中有一個(gè)tolerance允許一定的誤差，相應(yīng)的Python實(shí)現(xiàn)： 

關(guān)于Platt SMO的完整實(shí)現(xiàn)詳見(jiàn):https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py

針對(duì)之前的數(shù)據(jù)集我們使用Platt SMO進(jìn)行優(yōu)化可以得到：  

將分割線和支持向量可視化：

可見(jiàn)通過(guò)Platt SMO優(yōu)化出來(lái)的支持向量與簡(jiǎn)化版的SMO算法有些許不同。

使用遺傳算法優(yōu)化SVM

由于最近自己寫(xiě)了個(gè)遺傳算法框架，遺傳算法作為一個(gè)啟發(fā)式無(wú)導(dǎo)型的搜索算法非常易用，于是我就嘗試使用遺傳算法來(lái)優(yōu)化SVM。

使用遺傳算法優(yōu)化，我們就可以直接優(yōu)化SVM的最初形式了也就是最直觀的形式:  

順便再安利下自己的遺傳算法框架，在此框架的幫助下，優(yōu)化SVM算法我們只需要寫(xiě)幾十行的Python代碼即可。其中最主要的就是編寫(xiě)適應(yīng)度函數(shù)，根據(jù)上面的公式我們需要計(jì)算數(shù)據(jù)集中每個(gè)點(diǎn)到分割線的距離并返回最小的距離即可，然后放到遺傳算法中進(jìn)行進(jìn)化迭代。

遺傳算法框架GAFT項(xiàng)目地址: https://github.com/PytLab/gaft , 使用方法詳見(jiàn)README。

Ok， 我們開(kāi)始構(gòu)建種群用于進(jìn)化迭代。

創(chuàng)建個(gè)體與種群

對(duì)于二維數(shù)據(jù)點(diǎn)，我們需要優(yōu)化的參數(shù)只有三個(gè)也就是[w1,w2]和b, 個(gè)體的定義如下:  

種群大小這里取600，創(chuàng)建種群  

創(chuàng)建遺傳算子和GA引擎

這里沒(méi)有什么特別的，直接使用框架中內(nèi)置的算子就好了。  

適應(yīng)度函數(shù)

這一部分只要把上面svm初始形式描述出來(lái)就好了，只需要三行代碼: 

開(kāi)始迭代

這里迭代300代種群 

繪制遺傳算法優(yōu)化的分割線 

 

得到的分割曲線如下圖：

完整的代碼詳見(jiàn): https://github.com/PytLab/MLBox/blob/master/svm/svm_ga.py

總結(jié)

本文對(duì)SVM的優(yōu)化進(jìn)行了介紹，主要實(shí)現(xiàn)了Platt SMO算法優(yōu)化SVM模型，并嘗試使用遺傳算法框架GAFT對(duì)初始SVM進(jìn)行了優(yōu)化。