BAD Data in Multiple Hypotheses

上一篇，Machine Learning & Statistics，講到只有一個hypothesis的情況下， BAD Data出現的機率，可用下面這道公式算出來：

而且，我用一個例子，解釋這道公式：

罐子裡有20個彈珠，其中5個紅色，15個綠色。20個裡抓8個有幾種組合？機率各是多少？

我用MAC的Numbers App，做成以下這張表：

從這張表，我們認為，D1, D2, 和D6都是BAD Data，把這3種BAD Data機率相加：

P(D1) + P(D2) + P(D6) = 0.4% + 5.4% + 5.1% = 10.9%

這就是針對於某一個hypothesis，h，而言，發生BAD Data的機率，就是一開始的這道公式，想要表達的意思。

以上，是復習上一篇的內容。

此外，上一篇，沒有提到，對某一組資料而言，BAD發生的機率是否夠小？

從我畫的這張表格當中，D1, D2, 和D6，這幾組BAD Data發生的機率，還算小：

P(D1) = 0.4%

P(D2) = 5.4%

P(D6) = 5.1%

全部加起來，為10.9%，也還可以接受。我們每一組樣本數為8，如果樣本數量更多的話，根據Hoeffding's Inequality，BAD Data發生的機率會更小。

上面這道式子，與這道式子

結合在一起，就是：

這道式子，白話一點，就是：只要樣本數量夠多，BAD Data發生的機率會變小。

在教材裡，樣本的組合超過5678種，表示每一組樣本數量>=5678。這比我給的6組樣本，每組只有8筆而言，要大的多。所以教材BAD Data發生的機率會比我的，還要小很多。

所以，對於某一個hypothesis而言，只要樣本資料夠大，則BAD Data發生的機率會變小。

這又是什麼意思呢？還記得，我們判斷BAD Data的依據嗎？

|Ein(h)-Eout(h)| = ?

如果兩者的值相差太遠，那麼該樣本就是BAD Data。也就是用hypothesis求出樣本的錯誤率，和用同一個hypothesis求出母體的錯誤率，若這兩個錯誤率相差太遠，則稱BAD Data。所以，有些情況下，樣本的錯誤率，不能代表母體的錯誤率。好在，Hoeffding's Inequality告訴我們，只要樣本數量夠大，此情況發生的機率會很小。

所以對於Machine Learning而言，用某一個hypothesis，去檢驗樣本，只要樣本數量夠大，那麼該樣本的檢驗結果，相當於用同一個hypothesis去檢驗母體的結果。對於這一點，我們很有信心，信心從那來？就是Hoeffding's Inequality告訴我們的。

但實際上，Machine Learning是有許多hypothesis。接下來，要思考多個hypotheses的情況。我們的問題，就變成：

用 M 個 hypotheses，去檢驗樣本，只要樣本數量夠大，那麼該樣本的檢驗結果，是否相當於用相同 M 個 hypotheses去檢驗母體的結果？

all那一列的意思是，只要在這些hypothesis中，發生一次BAD，那就是BAD。

教材導出了下面這道式子，這是M hypotheses的情況

和1個hypothesis比較：

我們發現，M 個 hypotheses式子，右邊多一個M。至於該式子的導出過程，請各位自行翻教材，我就不多說了。

那麼，為何有M的式子，Ein與Eout用的參數是g？

我們知道，g是演算法從hypothesis set中，經過幾次之後，所找到的最好的解，Ein(g)為最小。最壞情況下，會經過幾次？|H| = M為M次。也就是，在M為有限的情況下，第m個h為g，這是最壞的情況。當這個情況發生時，演算法己經跑了M次了。而M次，很幸運地，都沒碰到BAD Data。

寫這篇文章的目的，是希望能幫助大家從教材的迷宮裡，先抽離出來，以便提醒大家我們所要探討的問題，到底是什麼。了解我們想要解決的問題後，再去回頭去看教材裡的數學公式，會比較容易看得懂。

-Count

這封郵件來自 Evernote。Evernote 是您專屬的工作空間，免費下載 Evernote

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