[ ML Foundation ] Section2 : Learning to Answer Yes/No - PLA (Part2)

Source From Here 
Introduction 
在 Part1 提到如果 Training Data 是 Linear Separable, 那你一定可以在進行 PLA 演算法正常的結束並找到 w 並正確地從 Training Data 找出 g(x)=y. 但如果 Training Data 不是 Linear Separable 或是 Training Data 中包含 Noise 時? 這時可以使用 Pocket Algorithm 來找出最好的 g: 
 

PLA - Pocket Algorithm 
這個演算法會比原先的 Cyclic 的方法慢, 但是保證一定能從 PLA 執行中正常結束. 其演算法步驟簡單說明如下: 

* Loop x 進行 Training
--- Random 從 x 中取出訓練資料, 利用現有的 w 進行預測 g'(x)=y
--- 如果w 預測錯誤, 則更新 w'=w, 並記錄累積的錯誤距離
* 比較上次 Loop 的累積錯誤距離與本次的累積錯誤距離
--- 上次 Loop 的累積錯誤距離 > 本次的累積錯誤距離: 繼續下次 Loop 的 Training 流程
--- 上次 Loop 的累積錯誤距離 < 本次的累積錯誤距離: 終止 PLA 訓練 (上次的 w 比本次的好)

使用與 Part1 同樣的 Training Data, 並透過 GML 套件中的 PLA 類別撰寫範例代碼如下: 

view plaincopy to clipboardprint?

1. package demo.classify  
2.   
3. import ml.classify.PLA  
4. import ml.classify.PLAClassify  
5. import ml.data.ui.DataInXYChart  
6.   
7. import org.jfree.ui.RefineryUtilities  
8.   
9. import flib.util.TimeStr  
10.   
11.   
12. // 1)　Prepare Training Data  
13. def x = [[1,7], [1,2], [1,4], [-1,3], [-4,-2], [-3,2], [3,-2], [-2, -11], [2.5, -15], [-1, -12], [1, 22]]  
14. def y = [1,1,1,-1,-1,-1,1, -1, 1, 1, -1]  
15.   
16. // 2) Training  
17. PLA pla = new PLA()  
18. PLAClassify cfy = pla.pocket(x, y)  // Or pla.cyclic(x, y)  
19. printf("\t[Info] Weighting Matrix(%d/%s):\n", cfy.loop, TimeStr.ToString(cfy.sp))  
20. cfy.w.eachWithIndex{v, i->printf("\t\tw[%d]=%s\n", i, v)}  
21.   
22.   
23. // 3) Predicting  
24. def t = [[1,3], [-4,1], [2,2], [3,6], [-1,9], [3, 39]]  
25. def r = [1, -1, 1, 1, -1, -1]  
26. def p = []  
27. t.eachWithIndex{ v, i->  
28.     e = cfy.classify(v)  
29.     printf("\t[Info] %s is classified as %d\n", v, e)  
30.     if(e==r[i]) p.add(e) // Correct  
31.     else p.add(3) // Miss  
32. }  
33. t.addAll(x)  
34. p.addAll(y)  
35.   
36. // 4) Show Predicting Result  
37. DataInXYChart demo = new DataInXYChart("Training Data", t, p, cfy.w)  
38. demo.pack();  
39. RefineryUtilities.centerFrameOnScreen(demo);  
40. demo.setVisible(true);  

使用 Cyclic 的方法執行結果如下: 
 

使用 Pocket 的方法執行結果如下: 
 

可以發現 Cyclic 的執行時間 (32ms) 比 Pocket 的方法快 (63ms); 但是 Pocket 找出的 w 可以正確的預測 Testing Data (沒有黃點出現)!