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

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,於是這個問題,以下圖表示:


高中學過排列組合的,就知道如何計算這個問題,下面的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