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

Use Python to Emulate Sampling with Replacement

罐子裡有100顆球,紅色的球佔40%,綠色的球佔60%。從罐子裡取出10顆球,希望出現最多1顆紅色球的機率是多少?

這是一個Sampling with Replacement(放回取樣)問題,在Peak Balls from a Bin,我們用簡單的機率公式,可以算出來:

P [# = 0] = 0.6^10 = 0.006
P [# = 1] = 0.6^9 * 0.4 * 10
P [v <= 0.1] = P [# = 0] + P [# = 1] = 0.046…

本篇,我用Python給定不同的母體數量,100、1000、10000、100000,模擬這個Sampling with Replacement。

程式碼如下:
[SamplingWithReplacement.py]



[Result]
執行結果如下:

There are 100 balls in the bin. (40 red balls, 60 green balls)
Select %d balls from the bin with replacement.
Times of replacement               = 10000
Number of red balls in the sample  = 348
Probability                        = 0.034800

There are 1000 balls in the bin. (400 red balls, 600 green balls)
Select %d balls from the bin with replacement.
Times of replacement               = 10000
Number of red balls in the sample  = 469
Probability                        = 0.046900

There are 10000 balls in the bin. (4000 red balls, 6000 green balls)
Select %d balls from the bin with replacement.
Times of replacement               = 10000
Number of red balls in the sample  = 473
Probability                        = 0.047300

There are 100000 balls in the bin. (40000 red balls, 60000 green balls)
Select %d balls from the bin with replacement.
Times of replacement               = 10000
Number of red balls in the sample  = 438
Probability                        = 0.043800

我們發現,母體數量愈大,Probability趨近於一個極限值,大概在0.046附近。

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

2017年11月16日 星期四

Peak Balls from a Bin

罐子裡有100顆球,紅色的球佔40%,綠色的球佔60%。從罐子裡取出10顆球,希望出現最多1顆紅色球的機率是多少?

這個問題,可以用下圖表示:




此問題,有兩種解法:
  1. 不放回取樣 (Sampling without Replacement)
  2. 放回取樣 (Sampling with Replacement)

Sampling without Replace

在上一篇,A Question of Hoeffding's Inequality,計算機率的方式,是用Sampling without Replace。本篇,用Python程式觀察,當母體(Population)數量變大的情況下,所要球的機率是否有極限值?

Bin3.py (from Gist)

執行結果:

prob (100, 0.4)    = 0.038515760543954836
prob (1000, 0.4)   = 0.045571401459545594
prob (10000, 0.4)  = 0.04627879605450445
prob (100000, 0.4) = 0.04634954100183593


上圖看來,當Population夠大的情況下,似乎 prob = 0.0463...是極限了。我們先觀察有這個現象,如何用數學證明,待我研究完後,再給大家參考。

Sampling with Replacements

如從罐子每取出一顆,馬上放回,那麼這個機率,就很好計算,解釋如下:


因為取球再放回去,每次都是獨立事件,所以計算10次都是綠色球的機率,就是將每次取球為綠色的機率0.6自乘10次:

P [# = 0] = 0.6^10 = 0.006

10次裡面,只有1次為紅色球的機率,就是先球9次為為綠色的機率 (0.6^9),再乘上1次為紅色的機率 (0.4)。因為不確定紅色的球會出現在第幾次,但有10個可能出現的位置,所以再乘上10:

P [# = 1] = 0.6^9 * 0.4 * 10

最後將兩個機率加起來,就得到最後的值

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

用Sampling with Replacements方法的好處是:
  1. 不需要考慮母體的大小
  2. 計算方式簡單
  3. 當母體數量夠大,其結果接近Sampling without Replacement
下一篇,Use Python to Emulate Sampling with Replacement,用Python模擬這個問題。

-Count

2017年11月7日 星期二

Why use Bounding Function

我們有了Hypothesis Set的Growth Function,為何還要定義一個Bounding Function呢?

這是因為我們想用Bounding Function對Hypothesis Set分類,就像之前我們用Dichotomy將Hypothesis歸類,Definition of Dichotomy,目的是一樣。

複習一下4種Hypothesis Set (圖片來源:Machine Learning Foundations)



我們發現,不同的Hypothesis Set,有各自的Growth Function。有的Hypothesis Set甚至尚未找到Growth Function,如2D perceptrons。如果Growth Function的樣子長的不一樣,甚至有些不知道它的樣子,我們要如何用簡單的方法,來描述Growth Function的特性?

程序員的思考方式是,花繁為簡,整理出下面表格




第1行為Perceptron的名稱。第2行為每個Perceptron的Breakpoint。第3行為每個Perceptron的成長函數。我們知道前面4個Perceptron的成長函數,最後一個2D Perceptrons的成長函數,不知道,但肯定不會超過2N

第4行,我們希望用一個簡單的方法來代替成長函數。就是用演算法所學的Big O,並且用k標示break point。

第5行,就是將第4行的描述,用Bouding Function表達。Positive Intervals和1D Perceptrons,雖然O裡的內容不一樣,但都以表達為 B(N, 3)。因為它的Bounding的原故。

如此一來,問題就簡化為,不管Perceptron長什麼樣子,只要知道它的Breakpoint在那裡,我們就可以用Bounding Function來表達它的上限。

-Count

2017年9月27日 星期三

The Growth Functions of the Four Hypothesis Sets

台大的線上課程,Machine Learning Foundations,對於以下4種Hypothesis Sets,尋找他們的Growth Functions及Break Points。


對於Postitive Rays、Postitive Intervals、及Convex Sets而言,都可以找到它們的Growth Function,mH(N)。但對於2D Perceptrons而言,就不容易找到mH(N),但可以找到它的上限:

mH(N) < 24, N >= 4

這裡的N = 4,就是此Growth Function的Break Point。

我用Python,將Positive Rays、Postitive Intervals、及Convex Sets,這3種Growth Function畫出折線圖出來。對於2D Perceptrons,因為找不到它的Growth Function,但手繪紅色那條線段,它是介於2D Perceptrons和Convex Set的中間。


橫軸N代表平面上的N個點。縱軸代表最大Dichotomies的數量。每一條折線,代表每一種Hypothesis Set的Growth Function,分別說明如下:
  • Convex Set。不管N有多大,找不到Break Point。
  • Positive Rays。當N = 2時,出現Break Point。
  • Positive Intervals。當N = 3時,出現Break Point。
  • 至於2D Perceptron呢?會在N = 4時,在紅色線上的那一綠色的點,就是BreakPoint。
Python程式如下


-Count