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

沒有留言:

張貼留言