2017年7月29日 星期六

Hoeffding's Inequality

台大的線上課程,Machine Learning Foundations,在談到Hoeffding's Inequality:



這個不等式是拿來做什麼用的?舉下圖的罐子取球為例:



罐子裡有兩種顏色的彈珠,橘色和綠色。

橘色彈珠,以後稱為紅色,在Machine Learning,代表錯誤的資料。
綠色彈珠,在Machine Learning代表正確的資料。
mu = 紅色彈珠在罐子裡的機率。在Machine Learning代表母體資料的錯誤機率。
nu = 紅色彈珠在樣本裡的機率。在Machine Learning代表樣本資料的錯誤機率。

罐子裡的彈珠數量不明,紅色彈珠在罐子裡的機率mu也不明,要如何預測mu?我們可以從罐子裡取出N顆彈珠,看看紅色彈珠佔的比例nu為多少,就能推測mu。

根據經驗,N愈大,用nu就可以推測的mu,也就是N愈大,nu就愈接近mu,誤差就愈少。通常,因為成本考量,我們無法取得太多的樣本,所以就定義一個容忍度epsilon

epsilon >= |nu - mu|

意思就是希望 nu與mu的誤差,不要超過epsilon。用機率描述我們的需求,就是希望nu與mu的誤差超過epsilon,這件事情,發生的機率,愈少愈好。用數學式子表達就是:

P [|nu - mu| > epsilon]

這就是Hoeffding's Inequality,不等式左邊的意思。於是,計算P的方式,就要靠不等式的右邊:



P的值,是由N與epsilon決定的,我用Python畫成曲線圖:


Python程式碼如下:
[Hoeffding2.py]

發現N愈大,P就愈小。還發現當N <= 3的時候,P > 1。問題是,機率怎麼可能大於1?所以,對於Hoeffding's Inequality而言,當樣本數很小的情況下,式子的右邊會超過1。遇到這種情況,我們就不要去管它,因為機率大於1,是不可能會發生的事情,雖然它還是滿足了Hoeffding's Inequality。

這件事情也告訴了我們,從母體只取3個當做樣本,是沒有意義。

接下來看看,epsilon如何影響P。用4個epsilon:0.1、0.3、0.5、1,共畫了4條曲線如下:


很明顯,epsilon定的愈嚴,如0.1, P就愈大。定的愈寬,如0.5,P就愈小。

在樣本數量為5的情況下:

P [|nu - mu| > 0.1] <= 1.80… (機率大於1的事情,此情況不會發生)
P [
|nu - mu| > 0.3] <= 0.81

P [|nu - mu| > 0.5] <= 0.16
P [|nu - mu| > 1]   <= 0.00… (誤差不會超過1,此情況不會發生)
我想要表達的意思是,Hoeffding's Inequality是一個不等式,在樣本數量少,或誤差超過1的情況下,此不等式,沒有太大意義。

結論:
  • 容忍度epsilon設的愈嚴,樣本出現錯誤的機率,和母體出錯誤的機率,兩者相差超出epsilon,這件事情發生的機率就愈大。
  • epsilon設的愈小,那麼所取的樣本數N就要夠大。如此一來,樣本的錯誤率,和母體的錯誤率,就不會相差太大。我們把上圖拉遠一點,如下圖,就可以了解這句話的意思。
  • 最重要的一點,在母體的錯誤率mu不明的情況下,只要樣本數N夠大,在我們容許的範圍epsilon內,樣本的錯誤機率,可以代表母體的錯誤機率。

Python程式如下:
[Hoeffding.py]


-Count