2017年7月8日 星期六

解釋 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

沒有留言:

張貼留言