機器學(xué)習(xí)必將會設(shè)計算法的優(yōu)化問題，主要是實現(xiàn)Platt SMO算法，那么，下面本文對SVM的優(yōu)化進行了介紹，主要實現(xiàn)了Platt SMO算法優(yōu)化SVM模型，并嘗試使用遺傳算法框架GAFT對初始SVM進行了優(yōu)化。

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

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

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

　　第一個變量的選擇

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

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

　　Karush-Kuhn-Tucker（KKT）條件是正定二次規(guī)劃問題最優(yōu)點的充分必要條件。針對SVM對偶問題，KKT條件非常簡單：

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

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

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

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

　　第二個變量的選擇

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

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

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

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

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

　　如果仍然沒有則重新選擇第一個α1

　　第二個變量選取的Python實現(xiàn)：

　　KKT條件允許一定的誤差

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

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

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

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

　　可見通過Platt SMO優(yōu)化出來的支持向量與簡化版的SMO算法有些許不同。

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

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

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

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

　　遺傳算法框架GAFT項目地址： https://github.com/PytLab/gaft ， 使用方法詳見README。

　　Ok， 我們開始構(gòu)建種群用于進化迭代。

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

　　對于二維數(shù)據(jù)點，我們需要優(yōu)化的參數(shù)只有三個也就是［w1，w2］和b， 個體的定義如下：

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

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

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

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

　　這一部分只要把上面svm初始形式描述出來就好了，只需要三行代碼：

　　開始迭代

　　這里迭代300代種群

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

　　得到的分割曲線如下圖：