A Question of Hoeffding's Inequality

台大的線上課程，Machine Learning Foundations，在講到Probability to the Rescue時，有一道小的題目，截圖如下：

正確答案是(3)，如何求出？一開始，我不了解題目的意思。但從答案裡往回推敲，就了解了。解法如下：

題目的意思是，要把下面式子右邊，紅色框框裏的值求出來。我們可以將題目給的三個值0.1、0.4、10，標記在公式裡，看看會發生什麼事：

接下來，就是解不等式的過程：

所以 P <= 0.33，意思就是， 誤差超過容忍度epsilon 0.3以上發生的機率，在樣本數為10的情況下，小於等於0.33。

容忍度 0.3 = |母體的錯誤機率 0.4 - 樣本的錯誤機率 0.1|

容忍度的意思就是，我能容許的誤差，最多就是0.3。

也就是，在母體的錯誤機率為0.4的情況下，所取樣本的錯誤機率和母體的相差大於容忍度0.3，出現這種情況的機率，愈少愈好。

換句話說，在母體的錯誤機率為0.4，而容忍度為0.3的情況下，樣本的錯誤機率若是0.1是允許的，0.2也是允許的，但0不行。用下圖解釋，會比較清楚：

也就是說，若用Hoeffding's Inequality公式解這個問題，實際上是在算下面機率的總和。

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

我們發現，因為Hoeffding's Inequality實際上是在計算左右兩邊，所以右邊的 P[#=8] + P[#=9] + P[#=10]是多算出來的。

我寫了另外一篇，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，應該可以找到相同的函數。

以上計算P的方式，是在母體數量為己知的情況下。若母體數量是未知的，P能算出來嗎？這個問題，我在這一篇，Peak Balls from a Bin，有解釋。

-Count