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

2017年12月29日 星期五

Why PLA May Work - Step 5

現在要證明PLA是可以停止的。台大的線上課程,Machine Learning Foundations,有證明的過程,但有一部份,是要是讓我們自己去想。還好,網路上,有人寫了完整的證明過程:


參考他的文章,我整理一下思路。WT是第T次修正的weight。將Wf與WT的單位向量做內積,得到以下結果。


我們知道,向量的內積,從幾何意義上來看,就是將一個向量,投影在另一個向量,若兩個向量的長度都是1,則投影的長度就是<=1。

我們想更進一步知道,若PLA若遇到線性可分的資料情況下,T的值,應該是有上限的:


也就是說,我們希望從兩個單位向量的內積,若能推導到

T <= 1/C

就表示T有一個上限。有上限,就表示PLA若遇到線性可分的資料情況,的確是會停止。

接下來,我們從之前推導的兩個式子:

Why PLA May Work - Step 4


求這兩個單位向量的內積的上限:



下面是推導的過程:



於是,我們得知,T有上限。就表示PLA若遇到線性可分的資料情況,的確是會停止。

-Count

2017年12月26日 星期二

Why PLA May Work - Step 3

現在解釋這道式子的由來:


教材裡,有該式子的推導過程。



結合上兩篇的文章,應該足以清楚了解


本篇,再深入了解一下此式子的幾何意義。此式子的左右兩邊是做向量的內積,向量的內積,就是在Wf上的投影,如下圖所示:


我們觀察到,w2在wf上的投影長度,大於w1在wf上的投影長度。真的是這樣嗎?Why?我們從wt+1是怎麼來的開始推導:


式子兩邊都對wf做內積:


我們認為,畫紅線的那一塊,一定是大於零。為何如此肯定?


那是因為一定會存在離切割線最近的點,投影在wf上的長度,也一定是最小,而且是大於零。


所以


我用Python寫了一支程式,跑的結果,也是如此。


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

w4w0 < w4w1 < w4w2 < w4w3 

-Count