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

沒有留言:

張貼留言