2017年8月2日 星期三

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