2017年12月30日 星期六

Why PLA May Work - Step 4

上一篇文章提到


我用Python寫了一支PLA程式,執行結果如下:


這支程式從w0跑到w7,跑了7次,就找到了wf = w7。我們觀察到:

wfw0 < wfw1 < … < wfw7 

數學上,也證明了這個現象:


我們希望能從這現象,兩個向量的內積愈大,去推論兩個向量就愈靠近。

wf與wt的向量內積愈大,代表兩件事:
  1. wf與wt之間的夾角愈小
  2. wt的長度愈大 (wf長度固定)

所以,接下來,我們要證明,PLA,在每次修正錯誤後,Wt的長度變長的幅度,不會太大。

這裡借用台大的Machine Learning Foundations線上課程裡的一張圖,證明這件事情:


有了這道式子之後,我們想知道,隨者更正的次數的增加,wt的長度是如何變長的幅度:


我們發現,隨者t的增加,變長的幅度的上限,是以開根號的型式成長。

至於wf與wt兩個向量內積成長的幅度為何?


得知,內積成長的幅度,沒有上限,但不會小於t。

將這兩個式子擺在一起:


可以推論,wf與wt之間的夾角,會愈來愈小。也就是wt與wf愈來愈靠近。

-Count

沒有留言:

張貼留言