2017年5月26日 星期五

[perceptron, T] 計算 perceptron 的學習收斂

為何 Wf 和 Wt 的內積是根號 T + 常數?
井民全, Jing, mqjing@gmail.com
Google doc: This Document

有關 perceptron 收斂問題的推導, 我想很多人早就知道了. 我只是有興趣把它推導一次, 記錄一下過程.

Page 14


使用遞迴算出 t 次更新 W 後, 目標線 與預測線 的相似程度, 即計算內積
做法:
根據 pp. 14,  
其中 .
是目標 weight.
=>
t = 1

t = 2

t =3

第 t 次
--------- (1)

Page 15

使用遞迴算出 t 次更新 W 後, 預測線 的長度變更, upper bound
做法:

t = 0,

t = 1,


t = 2,


第 t 次

-------- (2)



計算內積

令


做法如下

     代入 (1)   


                        
                                  
         
由 (2) 得知,
, 因為 不是 (+1) 就是 (-1), 所以 =1.
                 --------------------(3)



代入 (3)

                         
                                                     


所以, 若執行 T 次的 update, 目標線 與預測線 的相似程度, 即內積的結果




    --------------------(4)
           --------------------(5)




Page 16

計算收斂次數 T 的 upper bound

=> 由 (5) T 次 update W 後, 目標線 與預測線 的單位向量的內積, 如下


而 內積的最大值 ＝ 1, 所以


因此 T 的 upper bound 為
             
             


Appendix



Reference


at