老師提供了一個情境題給大家思考一下
如果今天我們手上有許多罐的彈珠，如圖一所示
裏面的橘色與綠色彈珠的比例不盡然相同
假設我們目前使用的假設模型h，剛好百分之百符合某一罐的分佈狀況，我們要不要採用???
(這時候就應該要有警覺，我們採用的標準是什麼?)
圖一、不同罐彈珠
換另一個情況來作說明，老師嘗試讓大家用另一個角度看同一個問題
如果今天150位修課的同學，同時丟五次銅板
其中一位剛好丟出五次正面，剛好跟手上的資料分佈狀況相同
請問他的擲銅板技術特別好嗎???
由圖三的Ans結果可以看到簡單的計算式
即使使用正反面出現機率相同的硬幣，當N變大的時候，150個硬幣中的其中一個硬幣
丟出5次都正面這種異端狀況，經計算發現出現的機率會 > 99% !
如果選到這種取樣資料，造成Ein與Eout差距很大，會讓我們的決策結果變得更糟!!!
我們在這邊稱呼它為BAD的取樣資料
圖二、圖一的簡化情形-銅板實驗
霍夫丁能夠保證的事情是這些取樣的結果是不好的(BAD)的機率很低
並且，在將這些情況的機率都加起來之後，這些不好的情況發生機率很小(samll)
圖三、不同實驗組BAD資料的示意圖
當如果有許多個hypotheses，我們該怎麼選擇 hypotheses h，
讓我們的演算法能夠自由的(可以想成隨機的)進行選擇(意思就是每個h都能夠被採用)?
重點在，如果A採用的 h 在D1到Dn，如果有其中一組的表現是BAD
則該hypotheses便不能夠使用
在這麼多組資料中，只有D1126使用了所有的hypotheses h1 到 hm
都沒有出現 Ein 與 Eout 相差過遠的 BAD 資料組
因此，D1126這個資料組可以被選來當作實驗資料組
圖四、資料與假設模型之間的關係
今天有很多筆不同的資料(D1到DM)與假設模型(h1到hM)之間的關係，按照聯集的觀念
把個別所有人M筆資料的機率不等式加起來，就是總BAD資料的機率不等式
已下是結合霍夫丁不等式的數學式推導，可以知道會產生BAD資料的邊界(Bound)是多少
以及與邊界和資料筆數的關係為何。
圖五、結合霍夫丁不等式之推導
--------------------------------------------------------------------------------------------
小結
經過了前面的這些努力
在假設模型庫H有限的情況，而且資料足夠的情況底下
我的Ein(取樣資料的誤差) 與 Eout(剩餘資料的誤差)，在不管採用哪個hypotheses g
我的 Ein 與 Eout 都會非常接近。
如果今天我的學習演算法A選了一個假設模型g，使得Ein最小而且約等於零
透過上述統計上的假設，可以知道學習這件事情是可能的
這時終於可以開始進行學習的動作。
--------------------------------------------------------------------------------------------
後記 :
Q : 有關於Ein 和 Eout這一切的推論都是從霍夫丁不等式出發
難道霍夫丁不等式就一定是正確的嗎?
沒有留言:
張貼留言