2017年7月31日 星期一

BAD Sample & BAD Data

台大線上課程,Machine Learning Foundations,是一個非常好的機器學習教材。若只是為了整理教材,而寫部落格,那就有點畫蛇添足了,更何況網上已經有很多人為該教材整理出許多篇文章出來。

對我來說,比較值得做的事情,非整理教材,而是對於不清楚的部份解釋清楚,或是幫程度不夠的學生(包含我)搭一座橋梁。這有點像是中國古代學者,花一輩子的精力,對古老難懂的書寫註解,供往後的學者能更容易理解書中的內容一樣,我現在做的事情,就是對難懂的數學式子下註解,讓一般人能更容易了解,至少也能幫助自己了解。

該課程裡頭有一節,Connection to Real Learning,提到BAD Sample和BAD Data。現在,我為這兩個名詞,配合教材,仔細解釋一篇。

教材截圖如下:
BAD Sample (我的解釋)
  • 將h套用在Sample上面,完全沒有錯誤,以為h就是我想要找的g。可是,把h套用在來自於Population的Training Data,卻有1半的錯誤。這就是BAD Sample。

教材截圖:
BAD Data
  • 將h套用在Sample上面的錯誤率Ein(h),與h套用在Training Data上的錯誤率Eout(h),這兩個錯誤率相差太大,我們稱為對於h而言,為BAD Data。
  • BAD Sample是BAD Data的極端情況

教材截圖:



我的解釋如下:

PD [BAD D for h]
  • 對於h而言,遇到BAD Data的機率
D1, D2, …, D5678
  • 這裡是假設所有Sample的可能性為5678個
  • 如,罐子裡有20個彈珠,其中5個紅色,15個綠色。從罐子裡抓8個有幾種組合?機率各位多少?

教材截圖:
如何解釋這道式子?

本篇主要是解釋BAD Sample和BAD Data,至於這道式子,我會有另外一篇,Machine Learning & Statistics,解釋之。

-Count

這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月29日 星期六

Hoeffding's Inequality

台大的線上課程,Machine Learning Foundations,在談到Hoeffding's Inequality:


而且附了一道題目:


上一篇,A Question of Hoeffdign's Inequality,求出P <= 0.33。這個意思是: 誤差為0.3以上發生的機率,在樣本數量為10的情況下,小於等於0.33。

誤差 0.3 = |母體的錯誤機率 0.1 - 樣本的錯誤機率 0.4|  

我把不等式右邊的部份,畫成曲線圖,觀察到一件有趣的事情:


這裡的x,就是樣本數量N。從圖中,很明顯可以看出來,當x <= 3的時候,P > 1。問題是,機率怎麼可能大於1?所以,對於Hoeffding's Inequality而言,當樣本數很小的情況下,式子的右邊會超過1。遇到這種情況,我們就不要去管它,因為機率大於1,是不可能會發生的事情,雖然它還是滿足了Hoeffding's Inequality。

接下來,將Hoeffding's Inequality式子的右邊,對於不同的錯誤率0.1、0.3、0.5、1,共畫了4條曲線如下:



樣本數量為5的情況下:
  • P [誤差>0.1] <= 1.80…  (機率大於1的事情,此情況不會發生)
  • P [誤差>0.3] <= 0.81...
  • P [誤差>0.5] <= 0.16...
  • P [誤差>1] <= 0.00… (誤差不會超過1,此情況不會發生)

我想要表達的意思是,Hoeffding's Inequality只是一個不等式,在某些情況下,套用此不等式,是沒有太大意義。

我們知道:

誤差 = |母體的錯誤機率 - 樣本的錯誤機率|

結論:
  • 誤差介於0和1之間。用來表達樣本錯誤率和母體錯誤率相差的程度。0代表沒有差異。
  • 最低誤差設的愈小,樣本的錯誤率,和母體的錯誤率相差,大於最低的誤差,這件事情發生的機率就愈大。
  • 若最低誤差設的愈小,那麼所取的樣本數就要夠大。如此一來,樣本的錯誤率,和母體的錯誤率,就不會相差太大。我們把圖拉遠一點,就可以了解這句話的意思。


-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

A Question of Hoeffding's Inequality

台大的線上課程,Machine Learning Foundations,在講到Probability to the Rescue時,有一道小的題目,截圖如下:

正確答案是(3),如何求出?一開始,我不了解題目的意思。但從答案裡往回推敲,就了解了。解法如下:

題目的意思是,要把下面式子右邊,紅色框框裏的值求出來。我們可以將題目給的三個值0.1、0.4、10,標記在公式裡,看看會發生什麼事:

接下來,就是解不等式的過程:


所以 P <= 0.33,意思就是, 誤差為0.3以上發生的機率,在樣本數為10的情況下,小於等於0.33。

誤差 0.3 = |母體的錯誤機率 0.1 - 樣本的錯誤機率 0.4|  

我寫了另外一篇,Hoeffding's Inequality,對於此不等式,有更深入的探討。

教材還提到,真正的機率是0.05,這是什麼意思?這個意思是,在母體(Population)的錯誤機率0.4為已知的情況下,10個樣本(Sample)裡面錯誤的機率小於等於0.1的機率是多少?

用符號v表達樣本裡發生錯誤的機率,於是該問題,就寫成:

P [v <= 0.1] = ?

我們知道 N = 10,所以用符號#代表樣本裡面,發生錯誤的個數。因為樣本數N=10,所以v<=0.1的意思就是去關注樣本裡發生錯誤的個數為1或零,這樣就可以把上面的式子拆成下面這個式子:

P [v <= 0.1] = P [# = 1] + P [# = 0]

然後個別計算

P [# = 1] = ?
P [# = 0] = ?

如何計算?我們假設,母體的數量為100,於是這個問題,以下圖表示:



文字描述就是:罐子裡有100顆球,有0.4機率拿到紅色的球,其它為拿到綠色的球。從罐子裡取出10顆球,希望出現最多1顆紅色球的機率是多少?

就是從罐子取球問題,我會有另一篇,Pick Balls from a Bin,深入探討此問題。

高中學過排列組合的,就知道如何計算這個問題,下面的C是Combination:

P [#=1] = C (40, 1) * C (60, 9) / C (100, 10) = 0.03416...
P [#=0] = C (40, 0) * C (60, 10) / C (100, 10) = 0.00435...
P [v <= 0.1] = P [#=1] + P [#=0] = 0.03851…

教材說的值為0.05,問題出在那裡?我們把母體數設為 1000,然後再算一次看看:

P [#=1] = C (400, 1) * C (600, 9) / C (1000, 10) = 0.03970...
P [#=0] = C (400, 0) * C (600, 10) / C (1000, 10) = 0.00586...
P [v <= 0.1] = P [#=1] + P [#=0] = 0.04557…

該值0.04557...,四捨五入,取小數點後2位,就是0.05了。

我們可以試者把母體數設10000,再算一次看看。

P [#=1] = C (4000, 1) * C (6000, 9) / C (10000, 10) = 0.04025...
P [#=0] = C (4000, 0) * C (6000, 10) / C (10000, 10) = 0.00602...
P [v <= 0.1] = P [#=1] + P [#=0] = 0.04627…

若母體數量設為100000,則

P [v <= 0.1] = 0.04634

如何計算Combination,Google可以幫忙,如要用Google計算C (60, 10),要把它寫成:

60! / (10! * 50!) = 75394027566

但Google計算不了 C (600, 10)

各位可以改用Mac的Numbers所給的COMBIN函數,計算一下。使用Windows的Excel,應該可以找到相同的函數。

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月26日 星期三

No Free Lunch on Machine Learning

No Free Lunch (NFL),中文是,天下沒有白吃的午餐。數學上,它是一個定理:

「由於對所有可能函數的相互補償,最優化算法的性能是等價的。其含義是說沒有其他任何算法能夠比搜索空間的線性列舉或者純隨機搜索算法更優。」 (原文網址:https://kknews.cc/zh-tw/tech/xnp5p9.html)

NFL定理,在Machine Learning上的解釋為: (原文網址:https://kknews.cc/zh-tw/tech/xnp5p9.html
  1. 沒有學習器能夠比在所有可能的函數中比隨機猜測的結果更優。
  2. 也就是說每個學習器都必須包含一些數據之外的知識或者假設,才能夠將數據泛化。

我拿台大的Machine Learning Foundations (MLF) 線上課程裡的一個例子來解釋NFL。

下圖截取自課程裡的一節,Feasibility of Learning - Learning is Impossible,但我改了一下圖


上面是一個Training Samples,用符號D (Data) 表示。我們想透過ML (Machine Learning)的方法,找出一個規則。該規則g,可以推測剩下3個x值 {101, 110, 111} 所對應的y是多少。


我簡單畫一下ML的流程:
D: Data, Training Samples
H: Hypothesis Set
A: Algorithm
f: Unknown Target Function
g: Final Hypothesis

當然,MLF教材裡,有更漂亮的圖表達ML的流程。自己手繪的目的,只是為了理解並加深印象而已。ML的流程,在這就不多說了,請諸位自行去翻MLF教材。

這裡,主要是想借用ML的流程,解釋我們一開始的問題。

首先,我們知道,f是永遠未知的。對於這個問題而言,該f有幾種可能?
2^8 = 256

我們經由ML所得到的g,一定是在這256個f裡面的其中一個。

其實我們再深入思考,還可以發現,其實我們只要從8個裡面挑選一個就好了,為何?因為Training Samples的y已經縮減了f的可能性,如下圖:


ML在推導g的時候,除了需要D,還需要Hypothesis Set,H。假設我們想到兩個Hypothesis,h1和h2。

H = { h1, h2}
h1 = 若 x 只有1個bit為1,則y為X,否則為O
h2 = 對於前5筆x,遵循h1的規則,剩下3筆,就用猜的。

所以現在,經由ML,我們得到了g。接下來,就可以用g來推測剩下的3個x所對應的y為多少。

若g = h1:

y = g (101) = O
y = g (110) = O
y = g (111) = O 

這樣的推論,是否正確?其實無法知道。

就像買賣股票一樣,根據過往的經驗,我們覺得h1不錯,想用它做為g,來預測未來股票的漲跌,可是卻發現預測錯誤。如果真的用h1來判斷股票的買賣,可能就會虧錢。因為大家應該有玩股票的經驗,所以拿股票做為例子,大家比較能夠理解。

總而言之,f是未知的。就像股市所隱含神秘的規則,可能永遠不知道一樣。那麼,回到這個例子而言,我們用h1做為g來推測剩下3個x成功的機率是多少?符號表達這段話如下:

P [g(x) == f(x)] = 1/8
g (x) = h1 (x)
x is {101, 110, 111}

若g = h2:

現在用h2做為g來推測剩下3個x成功的機率是多少?

P [g(x) == f(x)] = 1/8
g (x) = h2 (x)
x is {101, 110, 111}

我們發現,不管是用h1和h2,機率都一樣。這代表什麼意思?這就是,我們花了一個月的時間,研究出自以為非常優秀的演算法A,所找到的非常好的假設h1,用它預測剩下3個x的準確率,與直接用h2亂猜的準確率,是一樣的。

這解釋了NLF on Machine Learning的第1條:「沒有學習器能夠比在所有可能的函數中比隨機猜測的結果更優」。

至於第2條:「也就是說每個學習器都必須包含一些數據之外的知識或者假設,才能夠將數據泛化」,該解釋,待另一篇說明之。

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

Why is the Final Hypothesis only one?

在學習 Machine Learning Foundations 線上課程,有一段,充滿疑惑。

下面這一段,是從 The Learning Problem - Component of Machine Learning,節錄的:

明明銀行在評量個人條件來決定核發信用卡,是有許多hypothesis組合在一起的。但這句話的意思是,只從h1、h2、h3中選擇其中一個最好的,做為g?可是實際上,最好的hypothesis,往往是這幾個基本的hypothesis組合在一起。例如:

h4 = h1 and h2 and h3

當我把內心的疑惑,寫出來之後,答案也就出來了。

那就是,這裡舉的例子,少列了一些用邏輯運算組合的hypothesis,如:

h4 = h1 and h2 and h3
h5 = h1 or h2 or h3
h6 = h1 and (h2 or h3)

所以,以實務經驗來看,最好的hypothesis,很可能會從這些組合的hypothesis裡面挑撰一個出來,做為g。當然,這又衍生另外一個問題,就是,這樣的hypothesis set, H有多大?

|H| = ?

課程後面,會提到一個公式

這裡的

M = |H|

意思就是,若H太大,會導致Bad Sample發生的機率變大。這種機率的問題,與上篇所提的,是同一類問題:
Coin Game Example in Machine Learning

這個公式,留待以後解釋。

總之,我的意思是,從h1、h2、h3經由邏輯運算所產生出來的hypothesis,剔掉重覆的之後,其數量應該是有限的,而且不會太多。

-Count





這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月22日 星期六

Coin Game Example in Machine Learning

下圖是一個機率問題,出自於Machine Learning Foundations的Connection to Real Learning。此問題,應該是在高中數學的機率範圍內,可以順便復習一下高中所學的機率。


我把上面這個問題,用機率符號P描述如下:

P(1個人丟銅板5次都是正面) = 1/32
P(150人至少有一個人丟銅板5次都是正面) =?

本身是程序員,喜歡用簡單變數名稱來代表一長串的事情,就用P1和P2分別代表如下:

P1 = P(1個人丟銅板5次都是正面) 
P2 = P(150人至少有一個人丟銅板5次都是正面)

所以該問題,改成如下:
P1 = 1/32, P2 = ?

計算P2:
P2 = 1 - P(150人沒有一個人丟銅板5次都是正面)

定義P3變數為:
P3 = P(150人沒有一個人丟銅板5次都是正面)

P2被改寫成:
P2 = 1- P3

計算P3:
P3 = P(1個人丟銅板5次皆非正面) ^ 150

定義P4變數為:
P4 = P(1個人丟銅板5次皆非正面)

P3被改寫成:
P3 = P4 ^ 150

計算P4:
P4 = 1 - P1

P3被改寫成:
P3 = P4^150 = (1 - P1)^150

P2被改寫成:
P2 = 1- P3 = 1 - (1-P1)^150

所以P2和P1的關係,就是:
P2 = 1 - (1 - P1)^150

我們知道P1 = 1/32,所以
P2 = 1 - (31/32)^150 = 99.1454% > 99%

畫圖表達推導過程:


公式:


一個簡單的問題,這樣搞,是否大費周章?為何不直接套用公式?現實世界的問題,往往超出教課書上所學的。所以學會如何推導公式的能力,比背公式還重要,尤其是對程序員而言。因為程序員所寫的程式,其實就是公式。

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月20日 星期四

Why PLA May Work - Step 2

上一篇,Why PLA May Work - Step 1,解釋了 min 的意思。本篇,解釋下面式子左邊的y-w-x涵意。


拿上一篇的圖例解釋:


t的意思,是代某一輪。如t=1,代表第1輪,t=2代表第2輪。
xn(t),代表第t輪所偵測到錯誤的點,而yn(t)代表該點是+1或-1。

下圖是假想第一輪的情況
在第一輪,我們肉眼看到有兩個錯誤的點:x1與x4。因為PLA每輪只取一個錯誤的點,所以我們只取x4來處理。其值y4 = -1。把這兩個值標記為x4(1)和y4(1),括號裡的1代表第1輪。為何說x4是錯誤的點?因為:

w4x4(1) = +1 
y4(1) = -1

sign (w4x4(1)) != y4(1)

x4和x1兩個點,那一個距離最後的那條藍色分割線最近?畫圖:

將x4和x1分別投影到wf向量上,然後比較投影向量的長度,長度愈短,表示離線愈近。我們用「目視」發覺x1離分割線最近。如何用數學式子表達?可以用向量內積。
向量內積的結果是有方向性的,所以各自乘上自己的y值,這樣一來,就確保左右兩邊的值都是正的,就相當於投影向量的長度了。

就像我們程序員,在寫程式時,有一個習慣。明明程式寫好了,跑起來沒問題,但還是想修改,為的是能適用在更多情況,我稱之為抽象化。所以,對上面這個式子抽象化,讓它符合所有x,就成為:


這個式子,除了表達適用於所有的點之外,還表達了兩件事情:
  • 所有的點,離分割線的距離都是大於零
  • 若n=1,就是x1的那一點,套用式子,就是等號。意思就是x1離分割線最近。

我們記得,PLA每輪只取一個錯誤的點處理,所以我們可以把「輪」的概念套用在上面這個式子。這樣一來,這道式子就更能表達出程式在運行PLA時的狀況。


這道式子,講白話一點,就是:
不管是第幾輪,每一輪所挑選的錯誤的那個x,與最終切割線的距離,和離切割線最近的那個x的距離,稱為最小距離相比,有兩種情況:
  • 距離 > 最小距離
  • 距離 = 最小距離
    • 兩個點是同一個點
    • 兩個點不同,但都是最小距離

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月16日 星期日

何為口服糖耐量試驗 (OGTT)?

當我們在做血糖檢查的時候(尤其是妊娠婦女的產檢),檢查前,除了要先空腹、抽血,還要喝下一杯難喝的葡萄糖,過兩個小時再抽血一次。其目的是要檢查血糖的變化是否為正常。這種檢查方式稱為OGTT。

相關名詞整理如下:
  • Diabetes Mellitus (DM) - 糖尿病
  • Fasting Blood Glucose (FBG) - 空腹血糖
  • Oral Glucose Tolerance Test (OGTT) - 口服糖耐量試驗
  • impaired Fasting Glucose (IFG) - 糖耐量異常
  • Impaired Glucose Tolerance (IGT) - 空腹血糖受損
  • Glycosylated Haemoglobin (HbA1c) - 糖化血紅蛋白

將兩次所測的血糖值,套用下表,可得知是否患糖尿病


這表格是什麼意義呢?我把表格的值,畫成下面幾張圖,會比較好解釋。

正常血糖者,用OGTT測試法的血糖變化


橫軸為時間。縱軸為血糖值,單位為mg/dl。藍色的線為糖尿病者的血糖變化。紫色的為正常血糖者的血糖變化。血糖變化,是從空腹(FBG),到OGTT喝下葡萄糖兩個小時後。

DM的血糖變化:FBG > 126, OGTT 2hrs > 200
Normal的血糖變化:FBG < 110, OGTT 2hrs < 140

IFG患者,用OGTT測試法的血糖變化


DM的血糖變化:FBG: 110~125, OGTT 2hrs < 140

IGT患者,用OGTT測試法的血糖變化


DM的血糖變化:FBG < 126, OGTT 2hrs > 140

結論

從這3張圖,可以比較DM、Normal、IFG、IGT的不同:
  • IGT患者對於糖的耐受度,不及IFG患者。
  • IFG患者的血糖,相比Normal,偏高,但不及DM。若OGTT 2hrs的血糖值越過140,就會被認定為IGT。
  • 正常血糖者,其血糖值,介於110與140之間
  • 糖尿病患的血糖值,空腹大於126,OGTT 2hrs時大於200。

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

糖尿病相關名詞解釋

最近在學習糖尿病的相關知識,對於糖尿病的測試方法,以及相關的英文專有名詞,整理如下。

專有名詞
  • Diabetes Mellitus (DM) - 糖尿病
  • Fasting Blood Glucose (FBG) - 空腹血糖
  • Oral Glucose Tolerance Test (OGTT) - 口服糖耐量試驗
  • impaired Fasting Glucose (IFG) - 糖耐量異常
  • Impaired Glucose Tolerance (IGT) - 空腹血糖受損
  • Glycosylated Haemoglobin (HbA1c) - 糖化血紅蛋白

糖尿病的英文全名,叫Diabetes Mellitus。另外一個和尿有關的病,叫Diabetes Insipidus尿崩。所以,用Diabetes稱呼糖尿病,是一般的說法。

糖尿病的區分
  • Normal Glucose Regulation 正常血糖水平
  • Pre-Diabetes 糖尿病前期
    • IGT
    • IFG
  • D2 - Diabetes Type 2 二型糖尿病
  • D1 - Diabetes Type 1 一型糖尿病
  • GD - Gestational Diabetes 妊娠型糖尿病

Pre-Diabetes是糖尿病的前期,有兩類IGT和IFG,後面會提。Pre-Diabetes不屬於糖尿病,但若不注意,有可能會到二期糖尿病D2。

糖尿病,可分為三類:D2 (二期糖尿病)、D1 (一期糖尿病)、與Gestational Diabetes(妊娠糖尿病)

Normal Glucose Regulation,就是血糖正常者。

正常人的胰臟內含兩種細胞,分別分秘兩種物質,胰島素和升糖素。升糖素就是升血糖用的。反之,胰島素是降血糖用的。一般我們在進食後的一兩個小時內,食物被腸道吸收後,血糖會升高,人體為了要平衡血糖,會督促胰臟分秘胰島素。胰島素會督促細胞,將血糖儲存在兩個地方,肌肉和肝臟,儲備能量。

如果平時吃太多會讓血糖升高的食物(不一定是甜食。果糖類的甜食,升高血糖有限),這樣一來,胰臟和細胞會交互影響:
  • 而細胞就會忙於應付胰島素給的命令,最後就會懶得去理它了,稱為胰島素阻抗。
  • 血糖降不下來,胰臟會一直分秘胰島素,導致太累,甚至發炎。

D1患者,先天上胰臟分泌不出胰島素,需要每天靠注射胰島素,來調節血糖。目前D1是無法根治的。

而不嚴重的D2,是有機會恢復到正常血糖水平。

GD只出現在妊娠婦女。

測量糖尿病的方法
  • 空腹血糖 (FBG) 測試
  • 隨機血糖測試
  • 糖耐量測試 (OGTT)
  • 糖化血色素 (HbA1c) 測試

我們知道,人一天血糖的變化,被兩種活動影響,進食和運動。進食會讓血糖升高,運動會使血糖降低。前三種方法是測量當時的血糖狀況。

第四種方法是測量糖化血色素的濃度,得知2~3個月的平均血糖狀況。其原理,有機會再和大家說明。

OGTT是測血糖的方法。它是在空腹的情況下,測量血糖值,然後喝下葡萄糖,過兩個小時,再測量血糖值。從兩次血糖的變化,可判斷是否為IGT, IFG, D2, GD

FBG有兩種涵意,一個是測試血糖的方法,另一個是OGTT在空腹時的血糖值。

FBG測量法,比OGTT方便的原因在於:只要測空腹時的血糖即可。不用喝葡萄糖,然後過兩個小時後再測一次。

何時情況下會用OGTT?
  1. 當 FBG有疑慮,需進一步確認。
  2. 妊娠婦女的血糖檢查。

關於OGTT、FBG、IFG、與IGT之間的關係,會有另一篇文章說明之。

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月13日 星期四

Why PLA May Work - Step 1

最近在看台大教授李軒田開的線上課程,Machine Learning Foundations,所以接下來的幾篇文章,將是我的學習筆記。

筆記,若只是將原來教材重新篇排整理,寫在blog上,是沒有太多的價值。何況李軒田的教材已經寫的夠好了。一個有價值的,應該是挖掘教材裡難懂的部份(至少對自己而言),想通了之後,把思路寫出來。除了讓自己將來能夠以此為基礎,做更深入的探討,並挖掘更多的東西之外,也期望別人若遇到同樣的問題,看了我的筆記之後,能夠對原始教材的理解有所幫助。

所以,各位在看我的學習筆記之前,請先去讀原始教材。

接下來,針對教材裡的 Why PLA may work,裡面的證明過程,有許多痛點,嘗試做一些解釋。其中一段,節錄如下:


一開始,對上面這個式子,有滿腹的疑惑。第一個問題是,min代表什麼意思?它的意思是 ,離分割線最近的點。舉一個例子如下


有6個點,分成兩組,紅和綠:

紅色:x1, x2, x3
綠色:x4, x5, x6

己經有一條線將這6個點分成兩邊,剛好一邊是紅色,另一邊是綠色。wf是這條線的法向量。

每一個點都和wf相乘的結果如下:

用sign函式整理一下:



我們先觀察紅色的3個點,發現x1是距離線最近的點。所以wf * x1的值是最小,而且會大於零:

0 < wf * x1 < wf * x2 < wf * x3

至於綠色的那3個點呢?肉眼看,就知道沒有一個點比x2更接近分割線。因為綠色的點與wf相乘,為負數,而綠色所對應的y也為負數,所以我們可以用下面這個式子表達所有6個點



那麼, min 是何意?下面的n又代表什麼?以這個例子來看,min下方的n為1,指的就是x1,這是因為x1離線最近,使得y、w、x相乘為最小,表達如下


為何 wf * x 愈小表示x離線愈近?這要從向量內積的幾何意義來解釋。這就留給下一篇:
Why PLA May Work - Step 2

-Count
這封郵件來自 Evernote。Evernote 是您專屬的工作空間,免費下載 Evernote

2017年7月10日 星期一

PLA 中 sign (w * x) 的幾何意義

這是PLA的演算法。節錄自,李軒田 - Machine Learning Foundations,



其中 sign (w * x),到底是什麼意思?因為w和x都是向量,可以從向量的角度來了解之。下圖有二組向量,紅色和綠色


紅色:x1, x2, x3
綠色:x4, x5, x6

希望用一條線來區分這兩組向量,它的法向量為w,我們可以觀察到一個現象:

w * x1 > 0
w * x2 > 0
w * x3 > 0
w * x4 < 0
w * x5 < 0
w * x6 < 0

這個意思就是,用w和x的內積,大於零或小於零,來區分紅色和綠色。用符號來表達,就是

sign (w * x) = +1 or -1

+1 ---> w * x > 0
-1 ---> w * x < 0

接下來,我們可以開始解釋PLA演算法的第一行



它的意思是,在第t輪,發現有一個點xn,被分在錯誤的一類yn。還是用圖說明比較清楚


圖中,藍色的那條切割線,沒有將 x1 與 x4 區分正確,也就是

w * x1 < 0
w * x4 > 0

用sign表達:

sign (w * x1) = -1 (should be +1) 
sign (w * x4) = +1 (should be -1)

這就是PLA演算法的第一行的解釋


這樣清楚了吧?

-Count

2017年7月8日 星期六

解釋 PLA 演算法

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

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需要3筆資料(-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

程式如何寫?這樣寫:

sign (w * x) != y

w = w + y * x

-Count