PLA(perceptron learning algorithm)更新會不會停？
剛上完林軒田機器學習基石第二講，對於線性可分情況下，更新次數有上限的推導，還是不太理解，查了李航的統計機器學習的書，過程比較詳細，紀錄一下。
前提：
假設數據是線性可分，存在一條向量長度為||w_opt^||=1的超平面（以二維來講就是一條線）w_opt^．x_opt^ = w_opt．x + b_opt = 0，可將資料完全分開，代表圈圈在一邊，叉叉在另外一邊。對所有的點i = 1~N，存在 r > 0
yi（w_opt^．xi^）= yi（w_opt．xi + b_opt） (1)
r > 0 代表點不會在線上，因為等於零就是訓練出來的這條線。
2. 在每一個點，都有以下等式
yi（w_opt^．xi^）= yi（w_opt．x + b_opt）> 0 (2)
每個點都不在線上，且分類正確（r > 0），正正得正，或是負負得正。
所以存在最小距離 = min{ yi(w_opt．x+b_opt) } ，也代表著，
yi（w_opt^．xi^）= yi（w_opt．x + b_opt） (3)
證明
(1) 以平面來說，某個點（Px, Py）到ax+by+c=0直線的距離是
|a Px + b Py +c|／square root(square(a) + square(b))
(2) w^ = ０開始，如果分類錯誤，就更新權重，也就是旋轉目前的分類線，w_k-1^ = (w_k-1, b_k-1)
分類錯誤時，yi(w_k-1^．xi ^) = yi(w_k-1．xi + b_k-1) < 0 (4)
更新權重時，η(learning rate)
w_k =w_k-1 + ηyixi
b_k = b_k-1 + ηyi
等於 w_k^ = w_k-1^ + ηyixi^ (5)
由(3)、(5)推導，可得出ｘ
w_k^．w_opt^ = w_k-1^．w_opt^ + ηyixi^．w_opt^
≥w_k-1^．w_opt^ + ηr
一層一層的推導，就會得出以下公式(6)
w_k^．w_opt^
≥w_k-1^．w_opt^ + ηr
≥ w_k-2^．w_opt^ + ηr +ηr
≥ kηr
因為最一開始的w0^=0開始，最初項w_0^．w_opt^ = 0，往前推幾次，就有幾個η ，就是kη
由(4)、(5)推導，
square(||w_k^||) =square( (w_k-1^ + ηyixi^))
= square(|| w_k-1^||) + 2ηyixi^．w_k-1^ + square(η||xi^||)
(因為y = 1 or -1，平方後等於1，固可省略)
square(||w_k^||) = square(w_k-1^ + ηyixi^)
≤square(|| w_k-1^||) ＋ square(η||xi^||)
≤ square(|| w_k-1^||) ＋ square(ηR)
≤square(|| w_k-2^||) ＋ square(ηR) ＋ square(ηR)
≤k．square(ηR) (7)
1. 依據(4)公式 yixi^．w_k-1^ ≤0，所以移除此項，會小於原本的等式)
2. 因為最一開始的w_0^=0開始，最初項w^．w^ = 0，後我們把max||xi^||用另外一個符號R代替，代表最遠的向量單位，往前推幾次，就有幾個square(ηR)，就是k．square(ηR)。
依據公式(6)、(7)
kη w_k^．w_opt^ =||w_k^|| ||w_opt^||cosθ (cosθ值為 0 到 1)
≤||w_k^|| ||w_opt^||（||w_opt^||為1）= ||w_k^||≤
square_root(k) ηR
square(kr)≤ square(R)，最後得出ｋ ≤square(R/r)，證明了更新次數是存在上限的，只要數據是線性可分。
1. 單位向量Wiki
2. 餘弦cosθ wiki
