解釋 PLA 演算法

台大教授，李軒田開的線上課程，Machine Learning Foundations，講到PLA的演算法，兩行就可以搞定：

if (sign (w * x) != y)
    w = w + y * x

x是由兩個值(x1, x2)組合，對應在平面座標，代表某一個點。如何解釋 w * x 的原理？這個問題，畫成下面這張圖。

目的是希望畫出一條線，分割平面上的兩塊區域。一塊的值為+1，另一塊的值為-1。我們肉眼找到一條線可以區分這兩塊區域的線

x1 + x2 - 3 = 0

用倒推法思考，如何設計演算法，讓電腦獲得這條線？式子改寫成下面

h (x1, x2) = sign (-3 + x1 + x2)

sign的意思是，裡面的值，若大於0，則為+1，若小於0，則為-1。等於0，則為0。

(x1, x2)，是固定的一組資料，式子裡的係數，是機器最後找到的weight，(-3, 1, 1)。我們發現，每一個點有2筆資料(x1, x2)，而weight卻有3筆資料(-3, 1, 1)。為了演算法的簡潔，我們將式子改寫成：

h (x0, x1, x2) = sign (-3 * x0 + x1 + x2)

然後在將此式子符號化：

x0一直都是1。各位可以看得出來，這其實是三維空間的問題。圖示如下：

左邊是線性分割的問題，右邊是將問題轉為三維空間。用三維空間的角度，來解釋 w * x 會有些困難，所以我就想，把這個問題改成二維，比較好理解：

資料都在一條線上。這樣問題就變成，在線上取一個點(藍色)，區分線上的兩組資料。式子如下：

h (x1) = sign (-3 + x1)

我們發現，雖然每一個點，只有1筆資料(x1)，而weight需要2筆資料(-3, 1)表達，所以式子可以改寫為：

h (x0, x1) = sign (-3 * x0 + x1)

符號化就是：

各位可以看出來，這是一個二維空間的問題。現在，可以開始解釋 w * x，把問題畫成 x1-x0 平面座標圖：

為了配合 x1-x0 座標圖，我們把式子調整一下。若不這樣做，我們的座標圖就得畫成x0-x1。

圖中，很明顯可以看到，當 w=(1, -3)時，對3個點的內積：
w * (1, 1) = -2
w * (3, 1) = 0
w * (4, 1) = 1

各位有沒有注意到？w和(3, 1)剛好成為直角，所以w * (3, 1) = 0。該點剛好是一個分割的點。

w和(1, 1)的夾角大於90度，所以 w * (1, 1)  < 0，意思是 (1, 1) 位於-1的區域。
w和(4, 1)的夾角小於90度，所以 w * (4, 1) >0，意思是 (4, 1) 位於+1的區域。

這就是 w*x 在幾何上的意思。

也就是，我們往回推到最原始的，希望能找到合適的w，能滿足

一開始，機器隨便找到一個w = (4, -1)

發現於於兩個點而言：
w * (1, 1) = 3 > 0
w * (4, 1) = 15) > 0

都不滿足公式，而且夾角都小於90度。

所以，機器想要做的事情就是，希望調整w，使得對兩個點：
w * (1, 1) < 0 —— w於(1, 1)夾角 > 90
w * (4, 1) > 0 —— w於(4, 1)夾角 < 90

程式如何寫？這樣寫：

if (sign (w * x) != y)
    w = w + y * x

-Count