2017年11月16日 星期四

Peak Balls from a Bin

罐子裡有100顆球,有0.4機率拿到紅色的球,其它為拿到綠色的球。從罐子裡取出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
-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

2017年9月26日 星期二

Definition of Dichotomy

上一篇,Max Number of Dichotomies,解釋了什麼是Dichotomy。本篇,再來看看台大的線上課程,Machine Learning Foundations,對於Dichotomy的定義


大家對此定義,是否感到困惑?式子左邊有h,為何右邊也有h?

這有點像是我們在唸文言文,有許多字是一字多義。尤其是「于」這個字,「煢煢僕夫,于彼冀方」這裡的「于」是「往」的意思。「婿立于門外」這裡的「于」是「於」的意思。當然,本人學問沒這麼大,這些例子是從網路上抓下來的。

又想到最近台灣的教育當局,要刪減文言文的比例,個人覺得不算是壞事,原因為何?待我另立篇說明之。學文言文有一個好處就是,不會執著於一個字只能有一個解釋,可以發揮想像力及推演能力,去理解一篇文章。

回到正題。這裡要說的是,左邊的h,指的是Dichotomy。而右邊的h,就是Hypothesis。

Hypothesis的定義

找到一個hypothesis,h,能區分平面上的3個點為 (+1為O,-1為X)

h(x1) = +1
h(x2) = +1
h(x3) = -1

換一個方式問,能區分平面上的3個點為 +1、+1、-1,的Hypothesis,有幾個?上一篇說明,有無限多個。

我們把所有能區分平面上的3個點為 +1、+1、-1,的Hypothesis,歸為一類,稱為Dichotomy,用符號h',表示之,以區分h。

h'(x1, x2, x3) = (h(x1), h(x2), h(x3)) = (+1, +1, -1)

於是,我們把無限多個Hypothesis,歸為一類,用一個Dichotomy表示。課程裡所提的,式子左邊的h,其實就是h'。因為課程用相同的符號h表達Dichotomy和Hypothesis,造成我們的困擾,有可能是因為我們文言文讀的不夠多的關係。

-Count

2017年9月25日 星期一

Max Number of Dichotomies

線上課程,Machine Learning Foundations,提到了 mH(N):

中文解釋為,在N個點裡,找出最大數量的 Dichotomy。數學式子定義如下,它是一個Dichotomy Set的Growth Function,裡面的H,代表Dichotomy Set。如何解釋它呢?


在解釋它之前,先了解什麼是Dichotomy。但在之前,還得先了解什麼是Hypothesis。所以要過好幾關,才能徹底了解此Growth Function。

先說,什麼是Hypothesis。

依照定義


意思是,給1個點x,輸出為+1 (用O表示) 或 -1 (用X表示),用來區別。我們可以用平面上,有3個點的2D perceptrons,來解釋。亦即,平面上有3個點,我們可以找到很多條線,來區分這3個點。一條線,就是一個 hypothesis,如下圖所示。


我們可以找到3條線,將x1與x2歸為+1類,x3歸為-1類。
h1(x1) = +1
h2(x1) = +1
h3(x1) = +1
h1(x2) = +1
h2(x2) = +1
h3(x2) = +1
h1(x3) = -1
h2(x3) = -1
h3(x3) = -1

當然不只這3條,會有無線多條。

什麼是Hypothesis Set?用數學式子定義如下


我們用上面的例子,來了解這個定義

H = {h1, h2, h3, …}

所以Hypothesis Set數量為
|H| = 無限多

因為我們不想處理無限多的hypothesis,所以想找一個方法,取代hypothesis,就是dichotomy。從上面的表格得知,用這3個hypothesis:h1、h2、h3,區分3個點的結果都是一樣的。所以我們可以將這3個hypothesis歸為一類,稱為dichotomy,用新的h1代表之,以取代舊的h1、h2、h3、……會有無限多的hypothesis。

h1(x1, x2, x3) = OOX

接下來,我們要探討,最多有幾個Dichotomy?

Dichotomy Set


H (x1, x2, …, xN) = {h1, h2, …}

請注意,這裡的H,指的是Dichotomy Set,而非Hypothesis Set。此Dichotomy Set最大的數量為
|H| <= 2N

我們回到原來用Growth Function表示Max Number of Dichotomies的式子



mH(N)的上限就是2N, 數學表示如下
mH(N) <= 2N

但實際上,對於2D Perceptrons而言,當N>=4,Dichotomies數量不會到達2N

我們用N=3,也就是3個點為例,用2D Perceptrons來看,會有幾個Dichotomy。我們用兩種情況,Case 1和Case 2,來算Dichotomy的數量。

Case 1是3個點不在同一條直線上,他的Dichotomy數量為8。Case 2是3個點剛好在一條直線上,他的Dichotomy數量為6。為何一個是8,一個是6?圖示如下:


這兩個Case,整理如下:
Case 1
Case 2
h1 (x1, x2, x3) = OOO
h2 (x1, x2, x3) = OOX
h3 (x1, x2, x3) = OXO
h4 (x1, x2, x3) = OXX
h5 (x1, x2, x3) = XOO
h6 (x1, x2, x3) = XOX
h7 (x1, x2, x3) = XXO
h8 (x1, x2, x3) = XXX
h1 (x1, x2, x3) = OOO
h2 (x1, x2, x3) = OOX
h4 (x1, x2, x3) = OXX
h5 (x1, x2, x3) = XOO
h7 (x1, x2, x3) = XXO
h8 (x1, x2, x3) = XXX
H (x1, x2, x3) = {
  h1, h2, h3, h4
  h5, h6, h7, h8
  }
H (x1, x2, x3) = {
  h1, h2, h4
  h5, h7, h8
  }
|H (x1, x2, x3)| = 8
|H (x1, x2, x3)| = 6

合併Case 1和Case 2

|H(x1, x2, x3)| = 8 or 6

將N=3的2 D Perceptrons,套用在下面這個式子


mH(3) = max(6, 8) = 8

這樣一來,對於max和H,是否能清楚了解?

至於,式子中的x1, x2, …, xN,代表什麼意思?

以N = 3來看,就是3個點。x1, x2, x3,代表平面上的任意3個點。這3個點的組合會有無限多個,我們僅拿2種代表性的3個點,來看。Case 1是取任意3個不在同一直線上的點,Case 2是取任意3個在同一直線上的點。當然,還有許多特殊的Case,如2個或3個點重疊,這種Case,不需要特別關注。

-Count

2017年8月2日 星期三

BAD Data in Multiple Hypotheses


上一篇,Machine Learning & Statistics,講到只有一個hypothesis的情況下, BAD Data出現的機率,可用下面這道公式算出來:

而且,我用一個例子,解釋這道公式:

罐子裡有20個彈珠,其中5個紅色,15個綠色。20個裡抓8個有幾種組合?機率各是多少?

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


從這張表,我們認為,D1, D2, 和D6都是BAD Data,把這3種BAD Data機率相加:

P(D1) + P(D2) + P(D6) = 0.4% + 5.4% + 5.1% = 10.9%

這就是針對於某一個hypothesis,h,而言,發生BAD Data的機率,就是一開始的這道公式,想要表達的意思。

以上,是復習上一篇的內容。

此外,上一篇,沒有提到,對某一組資料而言,BAD發生的機率是否夠小?

從我畫的這張表格當中,D1, D2, 和D6,這幾組BAD Data發生的機率,還算小:

P(D1) = 0.4%
P(D2) = 5.4%
P(D6) = 5.1%

全部加起來,為10.9%,也還可以接受。我們每一組樣本數為8,如果樣本數量更多的話,根據Hoeffding's Inequality,BAD Data發生的機率會更小。

上面這道式子,與這道式子

結合在一起,就是:

這道式子,白話一點,就是:只要樣本數量夠多,BAD Data發生的機率會變小。

教材裡,給的是5678組樣本。我相信,樣本可以有5678種組合,表示每一組樣本數量>=5678。這比我給的6組樣本,每組只有8筆而言,要大的多。所以教材BAD Data發生的機率會比我的,還要小很多。

所以,對於某一個hypothesis而言,只要樣本資料夠大,則BAD Data發生的機率會變小。

這又是什麼意思呢?還記得,我們判斷BAD Data的依據嗎?

|Ein(h)-Eout(h)| = ?

如果兩者的值相差太遠,那麼該樣本就是BAD Data。也就是用hypothesis求出樣本的錯誤率,和用同一個hypothesis求出母體的錯誤率,若這兩個錯誤率相差太遠,則稱BAD Data。所以,有些情況下,樣本的錯誤率,不能代表母體的錯誤率。好在,Hoeffding's Inequality告訴我們,只要樣本數量夠大,此情況發生的機率會很小。

所以對於Machine Learning而言,用某一個hypothesis,去檢驗樣本,只要樣本數量夠大,那麼該樣本的檢驗結果,相當於用同一個hypothesis去檢驗母體的結果。對於這一點,我們很有信心,信心從那來?就是Hoeffding's Inequality告訴我們的。

但實際上,Machine Learning是有許多hypothesis。接下來,要思考多個hypotheses的情況。我們的問題,就變成:


用 M 個 hypotheses,去檢驗樣本,只要樣本數量夠大,那麼該樣本的檢驗結果,是否相當於用相同 M 個 hypotheses去檢驗母體的結果?




教材導出了下面這道式子,這是M hypotheses的情況

和1個hypothesis比較:

我們發現,M 個 hypotheses式子,右邊多一個M。至於該式子的導出過程,請各位自行翻教材,我就不多說了。

寫這篇文章的目的,是希望能幫助大家從教材的迷宮裡,先抽離出來,以便提醒大家我們所要探討的問題,到底是什麼。了解我們想要解決的問題後,再去回頭去看教材裡的數學公式,會比較容易看得懂。

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

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