Why PLA May Work - Step 4

上一篇文章提到

Why PLA May Work - Step 3

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

這支程式從w₀跑到w₇，跑了7次，就找到了w_f = w₇。我們觀察到：

w_fw0 < w_fw1 < … < w_fw7 

數學上，也證明了這個現象：

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

w_f與w_t的向量內積愈大，代表兩件事：

1. w_f與w_t之間的夾角愈小
2. w_t的長度愈大 (w_f長度固定)

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

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

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

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

至於w_f與w_t兩個向量內積成長的幅度為何？

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

將這兩個式子擺在一起：

可以推論，w_f與w_t之間的夾角，會愈來愈小。也就是w_t與w_f愈來愈靠近。

-Count

Why PLA May Work - Step 5

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

Perceptron Learning Algorithm (PLA)

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

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

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

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

T <= 1/C

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

接下來，我們從之前推導的兩個式子：

Why PLA May Work - Step 4

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

下面是推導的過程：

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

-Count

Why PLA May Work - Step 3

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

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

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

Why PLA May Work - Step 1

Why PLA May Work - Step 2

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

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

式子兩邊都對wf做內積：

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

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

所以

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

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

w₄w₀ < w₄w₁ < w₄w₂ < w₄w₃ 

-Count