Machine Learning 共筆 Week 4

上一周探討了各種不同面向的機器學習後，今天要探討的是Learning做不到的事情:

1. Two controversial answer: 當一個問題有不只一種答案，在這種狀況下無法收斂 Model是學不到東西的
2. No free lunch: general purpose的algorithm是不存在的，應該根據假設與背景知識去設計優化，畢竟各種演算法的設計與現實資料情境往往都存在一定程度的傾斜

我們真正想要做的其實就是對這個未知的 f 做一個推論，這邊帶出一個國中時期生物課就教過的捉放法:

如果想要估計一個群體的總數，隨機抓一個固定數量做上標記，下一次再抓一個固定數量並算出有做標記的比例藉此估算出這個群體的總數

這樣的動作在統計學上稱為隨機抽樣，雖然說這種方式有一定的誤差，但這樣的誤差是非常小並且有一個數學定理可以算出這個範圍 這個重要的定理就是 Hoeffding’s Inequality

這個定理告訴我們捉放法得出的分布與真實母體的分布差異大於某一個定值e的機率小於一個只由e與抓取的樣本總數N有關，也就是說當樣本總數夠多時，樣本與實際的誤差會越小 → Probably Approximately Correct(PAC)

這個定理巧妙的部分就在於加了e之後，我們就可以在不需要知道真實母體數量的前提下知道這個捉放法偏離真實分布的機率不會高到哪裡去

知道 Hoeffding’s Inequality 的用法後回過頭來看我們在ML遇到的問題：我們有一個從母體隨機選出的資料集，要怎麼證明如果演算法在這個資料集裡面表現的好，在真實母體下也能表現的一樣好呢?

我們先講母體比喻成一個罐子裡有很多顆橘色和綠色的球，其中橘色代表演算法預測錯誤，綠色代表演算法預測正確，如此一來我們想要知道的事情就是在這個罐子裡橘色球的比例 (也就是演算法在母體的錯誤率)

事情變得很簡單，從 Hoeffding’s Inequality 我們可以知道

1. 每次抓出來的Data Set 是有可能表現的不好 (不好的意思是指與母體分布差異太大)，但這個機率是非常小的
2. 抓一把出來算橘色球的比例 (演算法在樣本表現的錯誤率)與罐子裡橘色球的比例是 PAC

當樣本的錯誤率很接近母體的錯誤率而且這個錯誤率很小，我們就可以說這個演算法在母體的表現是好的

但現實狀況是我們的 Hypothesis 不會只有一個也不會強迫演算法只能選固定的Hypothesis，如果真的這麼做了通常表現也不會太好，我們只能說不夠接近 f ，我們其實只是在做 verification

為了讓大家了解這個詭異的困境，在影片中舉了一個例子，讓教室內的150人同時擲硬幣五次，一定有人出現五次都是正面，但不代表那個人擲出正面的機率比大家高所以 Hoeffding’s Inequality 用在 Real Learning 的正確姿勢應該是:

找出任意一個 Hypothesis 出現 bad sample 機率有多小並且只受到 M, N,e 的影響