機器學習演算法實踐-Platt SMO和遺傳演算法優化SVM

01-24

前言

之前實現了簡單的SMO演算法來優化SVM的對偶問題，其中在選取 $alpha$ 的時候使用的是兩重循環通過完全隨機的方式選取，具體的實現參考《機器學習演算法實踐-SVM中的SMO演算法》。

本文在之前簡化版SMO演算法的基礎上實現了使用啟發式選取 $alpha$ 對的方式的Platt SMO演算法來優化SVM。另外由於最近自己也實現了一個遺傳演算法框架GAFT，便也嘗試使用遺傳演算法對於SVM的原始形式進行了優化。

對於本文演算法的相應實現，參考:https://github.com/PytLab/MLBox/tree/master/svm
遺傳演算法框架GAFT項目地址: https://github.com/PytLab/gaft

正文

SMO中啟發式選擇變數

在SMO演算法中，我們每次需要選取一對 $alpha$ 來進行優化，通過啟發式的選取我們可以更高效的選取待優化的變數使得目標函數下降的最快。

針對第一個 $alpha_1$ 和第二個 $alpha_2$ Platt SMO採取不同的啟發式手段。

第一個變數的選擇

第一個變數的選擇為外循環，與之前便利整個 $alpha$ 列表不同，在這裡我們在整個樣本集和非邊界樣本集間進行交替:

首先我們對整個訓練集進行遍歷, 檢查是否違反KKT條件，如果改點的 $alpha_i$ 和 $x_1$ , $y_i$ 違反了KKT條件則說明改點需要進行優化。
Karush-Kuhn-Tucker(KKT)條件是正定二次規劃問題最優點的充分必要條件。針對SVM對偶問題，KKT條件非常簡單: $egin{cases} alpha_i = 0 Longleftrightarrow y_i(w^{T}x_i + b) ge 1 \ alpha_i = C Longleftrightarrow y_i(w^{T}x_i + b) le 1 \ 0 < alpha_i < C Longleftrightarrow y_i(w^{T}x_i + b) = 1 end{cases}$
在遍歷了整個訓練集並優化了相應的αα後第二輪迭代我們僅僅需要遍歷其中的非邊界αα. 所謂的非邊界 $alpha$ 就是指那些不等於邊界0或者C的 $alpha$ 值。同樣這些點仍然需要檢查是否違反KKT條件並進行優化.

之後就是不斷地在兩個數據集中來回交替，最終所有的 $alpha$ 都滿足KKT條件的時候，演算法中止。

為了能夠快速選取有最大步長的 $alpha$ ，我們需要對所有數據對應的誤差進行緩存，因此特地寫了個SVMUtil類來保存svm中重要的變數以及一些輔助方法:

class SVMUtil(object): """ Struct to save all important values in SVM. """ def __init__(self, dataset, labels, C, tolerance=0.001): self.dataset, self.labels, self.C = dataset, labels, C self.m, self.n = np.array(dataset).shape self.alphas = np.zeros(self.m) self.b = 0 self.tolerance = tolerance # Cached errors ,f(x_i) - y_i self.errors = [self.get_error(i) for i in range(self.m)] # 其他方法......

下面為第一個變數選擇交替遍歷的大致代碼，相應完整的Python實現(完整實現見https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py):

while (it < max_iter): pair_changed = 0 if entire: for i in range(svm_util.m): pair_changed += examine_example(i, svm_util) print("Full set - iter: {}, pair changed: {}".format(i, pair_changed)) else: alphas = svm_util.alphas non_bound_indices = [i for i in range(svm_util.m) if alphas[i] > 0 and alphas[i] < C] for i in non_bound_indices: pair_changed += examine_example(i, svm_util) ......

第二個變數的選擇

SMO中的第二個變數的選擇過程為內循環，當我們已經選取第一個 $alpha_1$ 之後，我們希望我們選取的第二個變數 $alpha_2$ 優化後能有較大的變化。根據我們之前推導的式子 $alpha_{2}^{new, unclipped} = alpha_{2}^{old} + frac{y_{2}(E_{1} - E_{2})}{eta}$ 可以知道，新的 $alpha_2$ 的變化依賴於 $lvert E_1 - E_2 vert$ , 當 $E_1$ 為正時，那麼選擇最小的 $E_i$ 作為 $E_2$ ，通常將每個樣本的 $E_i$ 緩存到一個列表中，通過在列表中選擇具有 $lvert E_1 - E_2 vert$ 的 $alpha_2$ 來近似最大化步長。

有時候按照上述的啟發式方式仍不能夠是的函數值有足夠的下降，這是按下述步驟進行選擇:

在非邊界數據集上選擇能夠使函數值足夠下降的樣本作為第二個變數
如果非邊界數據集上沒有，則在整個數據僅上進行第二個變數的選擇
如果仍然沒有則重新選擇第一個 $alpha_1$

第二個變數選取的Python實現:

def select_j(i, svm_util): """ 通過最大化步長的方式來獲取第二個alpha值的索引. """ errors = svm_util.errors valid_indices = [i for i, a in enumerate(svm_util.alphas) if 0 < a < svm_util.C] if len(valid_indices) > 1: j = -1 max_delta = 0 for k in valid_indices: if k == i: continue delta = abs(errors[i] - errors[j]) if delta > max_delta: j = k max_delta = delta else: j = select_j_rand(i, svm_util.m) return j

KKT條件允許一定的誤差

在Platt論文中的KKT條件的判斷中有一個tolerance允許一定的誤差，相應的Python實現：

r = E_i*y_i# 是否違反KKT條件if (r < -tolerance and alpha < C) or (r > tolerance and alpha > 0): ...

關於Platt SMO的完整實現詳見:https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py

針對之前的數據集我們使用Platt SMO進行優化可以得到：

w = [0.8289668843516077, -0.26578914269411114]b = -3.9292583040559448

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

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

使用遺傳演算法優化SVM

由於最近自己寫了個遺傳演算法框架，遺傳演算法作為一個啟發式無導型的搜索演算法非常易用，於是我就嘗試使用遺傳演算法來優化SVM。

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

$arg max limits_{w, b} { min limits_{n} (y_{i} cdot (w^{T}x + b)) cdot frac{1}{lVert w Vert} }$

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

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

Ok，我們開始構建種群用於進化迭代。

創建個體與種群

對於二維數據點，我們需要優化的參數只有三個也就是 $[w_1, w_2]$ 和 $b$ , 個體的定義如下:

indv_template = GAIndividual(ranges=[(-2, 2), (-2, 2), (-5, 5)], encoding="binary", eps=[0.001, 0.001, 0.005])

種群大小這裡取600，創建種群

population = GAPopulation(indv_template=indv_template, size=600).init()

創建遺傳運算元和GA引擎

這裡沒有什麼特別的，直接使用框架中內置的運算元就好了。

selection = RouletteWheelSelection()crossover = UniformCrossover(pc=0.8, pe=0.5)mutation = FlipBitBigMutation(pm=0.1, pbm=0.55, alpha=0.6)engine = GAEngine(population=population, selection=selection, crossover=crossover, mutation=mutation, analysis=[ConsoleOutput, FitnessStore])

適應度函數

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

@engine.fitness_registerdef fitness(indv): w, b = indv.variants[: -1], indv.variants[-1] min_dis = min([y*(np.dot(w, x) + b) for x, y in zip(dataset, labels)]) return float(min_dis)

開始迭代

這裡迭代300代種群

if "__main__" == __name__: engine.run(300)

繪製遺傳演算法優化的分割線

variants = engine.population.best_indv(engine.fitness).variantsw = variants[: -1]b = variants[-1]# 分類數據點classified_pts = {"+1": [], "-1": []}for point, label in zip(dataset, labels): if label == 1.0: classified_pts["+1"].append(point) else: classified_pts["-1"].append(point)fig = plt.figure()ax = fig.add_subplot(111)# 繪製數據點for label, pts in classified_pts.items(): pts = np.array(pts) ax.scatter(pts[:, 0], pts[:, 1], label=label)# 繪製分割線x1, _ = max(dataset, key=lambda x: x[0])x2, _ = min(dataset, key=lambda x: x[0])a1, a2 = wy1, y2 = (-b - a1*x1)/a2, (-b - a1*x2)/a2ax.plot([x1, x2], [y1, y2])plt.show()

得到的分割曲線如下圖：

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

總結

本文對SVM的優化進行了介紹，主要實現了Platt SMO演算法優化SVM模型，並嘗試使用遺傳演算法框架GAFT對初始SVM進行了優化。

參考

Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines