SMO中啟發式選擇變量
在SMO算法中，我們每次需要選取一對α來進行優化，通過啟發式的選取我們可以更高效的選取待優化的變量使得目標函數下降的最快。
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
針對第一個α1和第二個α2 Platt SMO採取不同的啟發式手段。
第一個變量的選擇
第一個變量的選擇為外循環，與之前便利整個αα列表不同，在這裡我們在整個樣本集和非邊界樣本集間進行交替:
首先我們對整個訓練集進行遍歷, 檢查是否違反KKT條件，如果改點的αiαi和xi,yixi,yi違反了KKT條件則說明改點需要進行優化。
Karush-Kuhn-Tucker(KKT)條件是正定二次規劃問題最優點的充分必要條件。針對SVM對偶問題，KKT條件非常簡單:
在遍歷了整個訓練集並優化了相應的α後第二輪迭代我們僅僅需要遍歷其中的非邊界α. 所謂的非邊界α就是指那些不等於邊界0或者C的α值。 同樣這些點仍然需要檢查是否違反KKT條件並進行優化.
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
之後就是不斷地在兩個數據集中來回交替，最終所有的α都滿足KKT條件的時候，算法中止。
為了能夠快速選取有最大步長的α，我們需要對所有數據對應的誤差進行緩存，因此特地寫了個
SVMUtil
類來保存svm中重要的變量以及一些輔助方法:Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | classSVMUtil(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)foriinrange(self.m)] # 其他方法... ... |
下面為第一個變量選擇交替遍歷的大致代碼，相應完整的Python實現(完整實現見https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py):
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | while(it<max_iter): pair_changed=0 ifentire: foriinrange(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=[iforiinrange(svm_util.m) ifalphas[i]>0andalphas[i]<C] foriinnon_bound_indices: pair_changed+=examine_example(i,svm_util) ... ... |
第二個變量的選擇
SMO中的第二個變量的選擇過程為內循環，當我們已經選取第一個α1之後，我們希望我們選取的第二個變量α2優化後能有較大的變化。根據我們之前推導的式子
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
可以知道，新的α2的變化依賴於|E1−E2|, 當E1為正時， 那麼選擇最小的Ei作為E2，通常將每個樣本的Ei緩存到一個列表中，通過在列表中選擇具有|E1−E2|的α2來近似最大化步長。
有時候按照上述的啟發式方式仍不能夠是的函數值有足夠的下降，這是按下述步驟進行選擇:
在非邊界數據集上選擇能夠使函數值足夠下降的樣本作為第二個變量
如果非邊界數據集上沒有，則在整個數據僅上進行第二個變量的選擇
如果仍然沒有則重新選擇第一個α1
第二個變量選取的Python實現:
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | defselect_j(i,svm_util): ''' 通過最大化步長的方式來獲取第二個alpha值的索引. ''' errors=svm_util.errors valid_indices=[ifori,ainenumerate(svm_util.alphas)if0<a<svm_util.C] iflen(valid_indices)>1: j=-1 max_delta=0 forkinvalid_indices: ifk==i: continue delta=abs(errors[i]-errors[j]) ifdelta>max_delta: j=k max_delta=delta else: j=select_j_rand(i,svm_util.m) returnj |
KKT條件允許一定的誤差
在Platt論文中的KKT條件的判斷中有一個
tolerance
允許一定的誤差，相應的Python實現：Python
1 2 3 4 | r=E_i*y_i # 是否違反KKT條件 if(r<-tolerance andalpha<C)or(r>tolerance andalpha>0): ... |
關於Platt SMO的完整實現詳見:https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py
針對之前的數據集我們使用Platt SMO進行優化可以得到：
Python
1 2 | w=[0.8289668843516077,-0.26578914269411114] b=-3.9292583040559448 |
將分割線和支持向量可視化：
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
可見通過Platt SMO優化出來的支持向量與簡化版的SMO算法有些許不同。
使用遺傳算法優化SVM
由於最近自己寫了個遺傳算法框架，遺傳算法作為一個啟發式無導型的搜索算法非常易用，於是我就嘗試使用遺傳算法來優化SVM。
使用遺傳算法優化，我們就可以直接優化SVM的最初形式了也就是最直觀的形式:
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
順便再安利下自己的遺傳算法框架，在此框架的幫助下，優化SVM算法我們只需要寫幾十行的Python代碼即可。其中最主要的就是編寫適應度函數，根據上面的公式我們需要計算數據集中每個點到分割線的距離並返回最小的距離即可，然後放到遺傳算法中進行進化迭代。
遺傳算法框架GAFT項目地址: https://github.com/PytLab/gaft , 使用方法詳見README。
Ok， 我們開始構建種群用於進化迭代。
創建個體與種群
對於二維數據點，我們需要優化的參數只有三個也就是[w1,w2]和b, 個體的定義如下:
Python
1 2 3 | indv_template=GAIndividual(ranges=[(-2,2),(-2,2),(-5,5)], encoding='binary', eps=[0.001,0.001,0.005]) |
種群大小這裡取600，創建種群
Python
1 | population=GAPopulation(indv_template=indv_template,size=600).init() |
創建遺傳算子和GA引擎
這裡沒有什麼特別的，直接使用框架中內置的算子就好了。
Python
1 2 3 4 5 6 | 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初始形式描述出來就好了，只需要三行代碼:
Python
1 2 3 4 5 | @engine.fitness_register deffitness(indv): w,b=indv.variants[:-1],indv.variants[-1] min_dis=min([y*(np.dot(w,x)+b)forx,yinzip(dataset,labels)]) returnfloat(min_dis) |
開始迭代
這裡迭代300代種群
Python
1 2 | if'__main__'==__name__: engine.run(300) |
繪製遺傳算法優化的分割線
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | variants=engine.population.best_indv(engine.fitness).variants w=variants[:-1] b=variants[-1] # 分類數據點 classified_pts={'+1':[],'-1':[]} forpoint,label inzip(dataset,labels): iflabel==1.0: classified_pts['+1'].append(point) else: classified_pts['-1'].append(point) fig=plt.figure() ax=fig.add_subplot(111) # 繪製數據點 forlabel,pts inclassified_pts.items(): pts=np.array(pts) ax.scatter(pts[:,0],pts[:,1],label=label) # 繪製分割線 x1,_=max(dataset,key=lambdax:x[0]) x2,_=min(dataset,key=lambdax:x[0]) a1,a2=w y1,y2=(-b-a1*x1)/a2,(-b-a1*x2)/a2 ax.plot([x1,x2],[y1,y2]) plt.show() |
得到的分割曲線如下圖：
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
總結
本文對SVM的優化進行了介紹，主要實現了Platt SMO算法優化SVM模型，並嘗試使用遺傳算法框架GAFT對初始SVM進行了優化。
Python那些事——想知道機器學習算法嗎？Platt SMO值得你擁有！
相關推薦
