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