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