2017年11月21日 星期二

Hoeffding's Inequality & Machine Learning

前面幾篇,介紹了統計學的Hoeffding's Inequality概念,並以罐子取彈珠為例:


本篇,將統計學,應用在機器學習上,這樣罐子取彈珠,是一樣的問題。


D = 樣本
f(xn) = yn

機器學習的目的,就是將 f 找出來。可是在母體的資料量很大,或不明確的情況下,我們只能從樣本裡推敲 f。所以會先用一個hypothesis h,來推導。如何驗證我們的h是否接近f?直接拿樣本檢測即可,檢測方式如下:


這裡有一個問題就是,用h檢測樣本,是否和用相同的h檢測母體,這兩個結果是否接近?講白一點,就是希望樣本的檢測結果,可以代表母體。也就是說,若找到一個h,用來檢驗樣本,發現錯誤率非常小,那麼我們就可以認為,拿同樣的h,檢驗母體,發生的錯誤的機率也會非常小。

我們把上面那兩個式子,改用機率表達如下:





於是,我們的問題,就和罐子取彈珠,是一樣的問題。這個問題就是:
「到底用h檢測樣本的結果,是否可以代表母體?」

這問題,可以用 Hoeffding's Inequality解釋:


在Machine Learning Foundations教材裡,用下面這張表格,解釋這個現象。

D1, D2, … D5678, … 為將所有可能的樣本列舉出來。所以:
|D1| = |D2| = … = |D5678| = N
N = 樣本所包含元素的數量。

BAD的意思是,若某個樣本
|Ein(h) - Eout(h)| > epsilon

也就是此樣本用h的檢測結果,其錯誤率,和用相同的h檢測母體的結果,相差太遠,則稱此樣本為BAD。

我們把所有為BAD的樣本發生的機率加起來,就是下面這道式子。


下面這道式子,其實就是Hoeffding's Inequality


現在,我把這件事情,用罐子取彈珠這個例子,可以解釋更清楚一點。


  • Marble in Bin: 罐子裡彈珠數,不知道
    • 相當於Objects in Population,不知道
  • R (Red): 罐子裡紅色彈珠數,不知道
    • 相當於 h(x) != f(x) 在Population發生的次數,不知道
  • G (Green): 罐子裡綠色彈珠數,不知道
    • 相當於 h(x) == f(x) 在Population發生的次數,不知道
  • mu = 紅色彈珠佔罐子裡彈珠40%
    • 相當於 Eout(h),即h(x) != f(x)在Population的機率為40%
  • Marbels in Sample:樣本彈珠的數量為10
    • 相當於Objects in Sample的數量為10    
  • epsilon:就是容忍度

在N = 10的情況下,所有可能的樣本組合為2^10 = 1024。我將這些樣本分成11類,如下表:


  • R = 樣本裡紅色彈珠的數量。
    • 相當於 h(x) != f(x)在樣本發生的次數
  • G = 樣本裡綠色彈珠的數量。
    • 相當於 h(x) == f(x)在樣本發生的次數
  • N = 在樣本裡,紅色彈珠的數量為R,綠色彈珠的數量為G的情況下,有幾種排列方式
    • 相當於樣本裡,發生h(x) != f(x)與h(x) == f(x)這兩種情況,有幾種排列方式
  • P(D) = 在某一組樣本D裡,出現紅色彈珠的數量為R,綠色彈珠的數量為G,的機率
    • 相當於樣本裡,h(x) != f(x)的發生數量與h(x) == f(x)的發生數量,此情況出現的機率
  • nu = 紅色彈珠出現在樣本的機率。
    • 相當於 Ein(h)
  • |nu - mu| = |母體有錯誤資料的機率 - 樣本有錯誤資料的機率|
    • 相當於|Ein(h) - Eout(h)|
  • Is Bad? = V。表示:誤差 |nu = mu| > 容忍度 epsilon。
    • 相當於|Ein(h) - Eout(h)| > epsilon

所以,機器學習裡,用hypothesis檢驗樣本這個過程,可類比為彈珠取樣,請參考:Explain Hoeffding's Inequality with Python

-Count

沒有留言:

張貼留言