2017年12月30日 星期六

Why PLA May Work - Step 4

上一篇文章提到


我用Python寫了一支PLA程式,執行結果如下:


這支程式從w0跑到w7,跑了7次,就找到了wf = w7。我們觀察到:

wfw0 < wfw1 < … < wfw7 

數學上,也證明了這個現象:


我們希望能從這現象,兩個向量的內積愈大,去推論兩個向量就愈靠近。

wf與wt的向量內積愈大,代表兩件事:
  1. wf與wt之間的夾角愈小
  2. wt的長度愈大 (wf長度固定)

所以,接下來,我們要證明,PLA,在每次修正錯誤後,Wt的長度變長的幅度,不會太大。

這裡借用台大的Machine Learning Foundations線上課程裡的一張圖,證明這件事情:


有了這道式子之後,我們想知道,隨者更正的次數的增加,wt的長度是如何變長的幅度:


我們發現,隨者t的增加,變長的幅度的上限,是以開根號的型式成長。

至於wf與wt兩個向量內積成長的幅度為何?


得知,內積成長的幅度,沒有上限,但不會小於t。

將這兩個式子擺在一起:


可以推論,wf與wt之間的夾角,會愈來愈小。也就是wt與wf愈來愈靠近。

-Count

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

2017年12月26日 星期二

Why PLA May Work - Step 3

現在解釋這道式子的由來:


教材裡,有該式子的推導過程。



結合上兩篇的文章,應該足以清楚了解


本篇,再深入了解一下此式子的幾何意義。此式子的左右兩邊是做向量的內積,向量的內積,就是在Wf上的投影,如下圖所示:


我們觀察到,w2在wf上的投影長度,大於w1在wf上的投影長度。真的是這樣嗎?Why?我們從wt+1是怎麼來的開始推導:


式子兩邊都對wf做內積:


我們認為,畫紅線的那一塊,一定是大於零。為何如此肯定?


那是因為一定會存在離切割線最近的點,投影在wf上的長度,也一定是最小,而且是大於零。


所以


我用Python寫了一支程式,跑的結果,也是如此。


這支程式從w0跑到w4,跑了5次,就找到了wf = w4。我們觀察到:

w4w0 < w4w1 < w4w2 < w4w3 

-Count

2017年11月22日 星期三

Machine Learning & Statistics

本篇主要的目的是總結Machine Learning Foundations教材。在教材的迷宮中,我把目光拉遠一點,看看到底機器學習的目的是什麼?為何機器學習需要用到統計學的觀念?

機器學習,簡單一句話,就是從已知的,找到一個合適的假設hypothesis,用它來預測未知的。而在統計學裡,樣本是已知的,母體是未知,所以機器學習攀上了統計學的原因在此。

機器學習的過程,是從許多hypothesis裡,挑出最好的。在這過程中,會遇到三個主要問題:

  1. 如何檢驗hypothesis?
  2. 如何挑選hypothesis?
  3. 檢驗挑選hypothesis都在樣本裡做,為何能代表在母體裡檢驗挑選hypothesis?

1. 如何檢驗某個hypothesis?

我們只能從已知的樣本資料,去驗證某個hypothesis。已知的樣本資料如下:



D = Sample
|D| = N
1 <= n <= N

樣本資料有一個特性,就是對所有xn而言 yn = f (xn)。但我們不知道f長什麼樣子。我們只能想辦法去推測它。所以找到一個hypothesis,h。用樣本資料去檢驗h。檢驗方式如下:


這就用樣本檢驗h的方法。若發生錯誤的次數愈少,就是好的h。

2. 如何挑選hypothesis?

我們可以設計一套演算法,如PLA,每次找到的hypothesis,發生錯誤的機率愈來愈少。之前發表PLA相關文章:
解釋 PLA 演算法
PLA 中 sign (w * x) 的幾何意義
Why PLA May Work - Step 1
Why PLA May Work - Step 2

3.為何從樣本裡挑選hypothesis的過程,可相當程度代表從母體挑選hypothesis

對一個hypothesis,h而言,只要樣本資料夠大,用樣本檢驗h,發生錯誤的機率,相當於用母體檢驗h,發生錯誤的機率。這個現象,可以用Hoeffding's Inequality解釋。我在之前的幾篇文章有提過:
Explain Hoeffding's Inequality with Python
Hoeffding's Inequality & Machine Learning

上面這句話,用數學式子表達如下:

用樣本檢驗h,發生錯誤的機率:

用母體檢驗h,發生錯誤的機率:

樣本資料夠大,這兩個錯誤的機率會非常接近,因為遵循Hoeffding's Inequality:

對於某個h而言,定義BAD Data如下:


有了BAD Data的定義之後,就可以將上面的Hoeffding's Inequality,簡化為以下這個式子:

用下面表格,會比較好理解這個式子:

D1, D2, … D5678, … 為將所有可能的樣本列舉出來。所以:
|D1| = |D2| = … = |D5678| = N
N = 樣本資料的數量。

簡單來講就是,若是樣本數量夠大,那麼發生BAD Data的機率就愈少,這是因為Hoeffding Inequality。

在只有一個hypothesis的情況下,只要樣本數量夠大,那麼樣本檢驗h的結果,相當於用母體檢驗的結果。問題是,機器學習的過程,會用到好幾個hypothesis,用樣本檢驗這些hypothesis的結果,是否就相當於用母體檢驗這些hypothesis的結果?我們希望的答案是YES,不然,機器學習是沒有用的。在Machine Learning Foundations教材裡,有答案YES的推導過程。教材裡用下面表格視覺化此問題:


總共有M個hypothesis。用樣本與母體檢驗這M個hypothesis,發生BAD Data的機率為:

請參考:BAD Data in Multiple Hypotheses

我們發現,在原來的Hoeffding's Inequality,多乘了一個M。接下來要分析,M為機器學習帶來那些影響:

Case 1 - M為無限大

  • 如此一來,機器學習就不用談了,因為從樣本學到的東西,無法套用在母體,永遠學不會

Case 2 - M愈大
  • 好處:更多的hypothesis,容易找到錯誤率最小的
  • 壞處:發生BAD Data的機率愈大
Case 3 - M愈小
  • 好處:發生BAD Data的機率愈小
  • 壞處:更少的hypothesis,難找到錯誤率最小的
Case 1是我們面對最大的問題。因為之前提到的PLA,若將每條直線視為hypothesis,會有無限多個hypothesis。所以我們要將無限的hypothesis,轉換為有限的dichotomy。這就是為何Machine Learning Foundations,會有很大的篇幅說明dichotomy的原因。也可以參考之前談過dichotomy的文章:

Definition of Dichotomy
Max Number of Dichotomies

至於Case 2和Case 3,在教材裡,就是Trade-off on M。以後有機會再為大家解釋。

-Count

2017年11月21日 星期二

Hoeffding's Inequality & Machine Learning

前面幾篇,介紹了統計學的Hoeffding's Inequality概念,並以罐子取彈珠為例:


本篇,將統計學,應用在機器學習上,這樣罐子取彈珠,是一樣的問題。


D = 樣本
f(xn) = yn

機器學習的目的,就是將 f 找出來。可是在母體的資料量很大,或不明確的情況下,我們只能從樣本裡推敲 f。所以會先用一個hypothesis h,來推導。如何驗證我們的h是否接近f?直接拿樣本檢測即可,檢測方式如下:


這裡有一個問題就是,用h檢測樣本,是否和用相同的h檢測母體,這兩個結果是否接近?講白一點,就是希望樣本的檢測結果,可以代表母體。也就是說,若找到一個h,用來檢驗樣本,發現錯誤率非常小,那麼我們就可以認為,拿同樣的h,檢驗母體,發生的錯誤的機率也會非常小。

我們把上面那兩個式子,改用機率表達如下:





於是,我們的問題,就和罐子取彈珠,是一樣的問題。這個問題就是:
「到底用h檢測樣本的結果,是否可以代表母體?」

這問題,可以用 Hoeffding's Inequality解釋:


在Machine Learning Foundations教材裡,用下面這張表格,解釋這個現象。

D1, D2, … D5678, … 為將所有可能的樣本列舉出來。所以:
|D1| = |D2| = … = |D5678| = N
N = 樣本所包含元素的數量。

BAD的意思是,若某個樣本
|Ein(h) - Eout(h)| > epsilon

也就是此樣本用h的檢測結果,其錯誤率,和用相同的h檢測母體的結果,相差太遠,則稱此樣本為BAD。

我們把所有為BAD的樣本發生的機率加起來,就是下面這道式子。


下面這道式子,其實就是Hoeffding's Inequality


現在,我把這件事情,用罐子取彈珠這個例子,可以解釋更清楚一點。


  • Marble in Bin: 罐子裡彈珠數,不知道
    • 相當於Objects in Population,不知道
  • R (Red): 罐子裡紅色彈珠數,不知道
    • 相當於 h(x) != f(x) 在Population發生的次數,不知道
  • G (Green): 罐子裡綠色彈珠數,不知道
    • 相當於 h(x) == f(x) 在Population發生的次數,不知道
  • mu = 紅色彈珠佔罐子裡彈珠40%
    • 相當於 Eout(h),即h(x) != f(x)在Population的機率為40%
  • Marbels in Sample:樣本彈珠的數量為10
    • 相當於Objects in Sample的數量為10    
  • epsilon:就是容忍度

在N = 10的情況下,所有可能的樣本組合為2^10 = 1024。我將這些樣本分成11類,如下表:


  • R = 樣本裡紅色彈珠的數量。
    • 相當於 h(x) != f(x)在樣本發生的次數
  • G = 樣本裡綠色彈珠的數量。
    • 相當於 h(x) == f(x)在樣本發生的次數
  • N = 在樣本裡,紅色彈珠的數量為R,綠色彈珠的數量為G的情況下,有幾種排列方式
    • 相當於樣本裡,發生h(x) != f(x)與h(x) == f(x)這兩種情況,有幾種排列方式
  • P(D) = 在某一組樣本D裡,出現紅色彈珠的數量為R,綠色彈珠的數量為G,的機率
    • 相當於樣本裡,h(x) != f(x)的發生數量與h(x) == f(x)的發生數量,此情況出現的機率
  • nu = 紅色彈珠出現在樣本的機率。
    • 相當於 Ein(h)
  • |nu - mu| = |母體有錯誤資料的機率 - 樣本有錯誤資料的機率|
    • 相當於|Ein(h) - Eout(h)|
  • Is Bad? = V。表示:誤差 |nu = mu| > 容忍度 epsilon。
    • 相當於|Ein(h) - Eout(h)| > epsilon

所以,機器學習裡,用hypothesis檢驗樣本這個過程,可類比為彈珠取樣,請參考:Explain Hoeffding's Inequality with Python

-Count

2017年11月18日 星期六

Explain Hoeffding's Inequality with Python

在上一篇,Hoeffding's Inequality,解釋這此不等式的使用方法。本篇用MAC Numbers App及Python幫大家了解這道公式的由來,這對我們日後深入了解Machine Learning,可能會有很大的幫助。


我們假設一種情況是,罐子裡彈珠數量未知,但知道紅色彈珠佔40% (mu),剩下的為綠色。從罐子裡取出一顆彈珠,再放回罐子 (Sampling with Replacement),這樣取放10次裡面,出現紅色彈珠的機率nu與紅色彈珠佔罐子40%,這兩者相差,超出容忍度epsilon 0.3的機率,其上限為多少?

此問題,用圖表示,會比較清楚:



這條線從0到1,表示機率。綠色的O表示容許的機率nu。紅色的X表示不容許的機率nu。我們將紅色彈珠視為一筆錯誤的資料,那麼母體有40%的資料是錯誤的,所以若樣本裡面,若有0.4機率的資料是錯誤的,那麼這個樣本就可以代表母體。但實際情況是,樣本裡發生錯誤資料的機率,不見得剛好是0.4,所以我們就定一個範圍epsilon = 0.3為我們容許的誤差範圍。

接下來,我們想算出,在樣本數量為10的情況下,出現紅色球 (錯誤資料)的機率P。有兩種方法:

方法一:用Hoeffding's Inequality
此法不需要知道,紅色彈珠在母體的機率mu,與紅色彈珠在樣本的機率nu。只要知道樣本的數量N與容忍度epsilon,就可以馬上算出P。

方法二:將上圖的紅叉標示的機率加總:

P = P[#=0] + P[#=8] + P[#=9] + P[#=10] = 0.0183

我將方法二的計算過程,寫在MAC的Numbers App或Windows的Excel,並顯示結果。

我用MAC的Numbers App 做成下面這張表:


  • Marble: 罐子裡彈珠數,不知道
  • R (Red): 罐子裡紅色彈珠數,不知道。紅色彈珠可視為一筆錯誤的資料
  • G (Green): 罐子裡綠色彈珠數,不知道。綠色彈珠可視為一筆正確的資料
  • mu = 紅色彈珠佔罐子裡彈珠40%
  • Samples = 樣本數量
  • epsilon = 容忍度。若將紅色彈珠視為錯誤資料,那麼|母體有錯誤資料的機率 - 樣本有錯誤資料的機率|<= epsilon為我們許,epsilon為容許的誤差上限,簡稱容忍度。

第二張表:


  • R = 樣本裡紅色彈珠的數量
  • G = 樣本裡綠色彈珠的數量
  • N = 在樣本裡,紅色彈珠的數量為R,綠色彈珠的數量為G的情況下,有機種排列方式
  • P(D) = 在某一組樣本D裡,出現紅色彈珠的數量為R,綠色彈珠的數量為G,的機率
  • nu = 紅色彈珠出現在樣本的機率
  • |nu - mu| = |母體有錯誤資料的機率 - 樣本有錯誤資料的機率|
  • Is Bad? = V。表示:誤差 |nu = mu| > 容忍度 epsilon

從彈珠罐取放彈珠10次(Sampling with Replacement),10次裡面出現紅色綠色彈珠,有11種情況,分別是D1, D2, …, D11。於是我們用高中學過的排列組合,將這個問題,拆成11個獨立的小問題:
  • D1:出現10個紅色的,及0個綠色的,
  • D2:出現9個紅色的,及1個綠色的。
  • D3:出現8個紅色的,及2個綠色的。
  • D4:出現7個紅色的,及3個綠色的。
  • D5:出現6個紅色的,及4個綠色的。
  • D6:出現5個紅色的,及5個綠色的。
  • D7:出現4個紅色的,及6個綠色的。
  • D8:出現3個紅色的,及7個綠色的。
  • D9:出現2個紅色的,及8個綠色的。
  • D10:出現1個紅色的,及9個綠色的。
  • D11:出現0個紅色的,及10個綠色的。
有了所有小問題的R和G之後,我們就可以計算每個小問題發生的機率。例如,求D3發生的機率的公式為:

其它小問題的機率。我將此公式,套用在Numbers,就可以很快算出來,如:

N:D2
FACT是Numbers提供的公式。如 FACT (3) = 3! = 6

P(D):D2

我們發現,把所有小問題的機率加起來,剛好為100% = P(D):Sum格子。更加驗證了,這個大問題,剛好拆解成11個小問題,而且不會漏掉。

用方法一和方法二,所算出來的P,分別為0.33與0.0183,這有些差異。問題出在那兒?問題出在樣本數量不夠大。如果樣本數量愈大,這個差異就愈小。如何說明?

先不用數學證明這個現象。取而代之,我寫了一支Python程式,解釋這個現象。Python程式,計算出下面的結果:


在樣本為10的情況下,此Python的結果,和用Mac Numers的結果是一樣的。

此程式接下來也畫了下面這張圖,樣本數N從10逐一增加到30,用方法一和方法二所計算的P,隨者N愈大,這兩個P就愈小,而且愈接近。


總結上圖所發現的幾件事情:
  1. 當樣本數量夠大,方法二算出來的P,會接近方法一,由Hoeffding's Inequality算出來的P。所以Hoeffding's Inequality是此問題的上限。
  2. 不管是用方法一,還是方法二,樣本數量都要夠大,這樣我們不希望看到的機率P,就會愈小。
Python程式如下:
[InferHoeffding.py]


-Count