2017年7月29日 星期六

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

沒有留言:

張貼留言