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