Caltech Learning from Data 2 - Can machine really learn？

Learning真的能做到嗎？

一個unknown target function真的能靠有限的data input來逼近嗎？
這需要證明，要不然learning只是火雞的體重：一千天之前都是線性成長，一千天到了歸零，但是卻learn出了線性target function。

這其實是大哉問。我上了這麼多ML課程，只有caltech這個老師把這個大哉問問了出來，真的是很棒的課！！！！

機率實驗

從某個桶子內只有兩種顏色的球，抽中任一顏色的機率如下：

miu是未知常數，也就是說如果真的有一個underlying probability distribution的話，機器是否能infer或逼近這個miu?

定義sample = 從這個桶子拿N個球出來的此N個球
定義nu = 每次sample中紅球佔的比例，這是一個random number

如果獨立的多次sampling，能否nu可以infer or 逼近miu? YES
統計學證明：nu (sample frequency) 逼近miu (population frequency)的誤差epsilon，其機率跟N成exponential衰退：

所以N越大，nu和mu的誤差大於容忍區間epislon的機率越小！

但是事實上，這只是一半的故事，完整的公式如下：

哈！ 其實機率衰退的幅度雖然是exponentially，但是卻被epsilon^2 控制，我們一方面希望epsilon越小越好，但越小的epsilon又會減低negative exponential的威力，變成要更大的N。

此不等式稱為 Hoeffding's Inequality。

上面實驗與Machine learning關係？

其實很好類推。
我們要找出未知miu，相當於就是learning中要找出那個ideal target function，現在不是一個常數了，而是一個input vector mapping to output value的 UNKNOWN function:

不過上面的實驗中，桶子內的球抽出是呈現機率分布的，所以原本的learning diagram可以擴充如下：

用這個桶子的類比，桶子就是整個input space，每一個球就是input space中的特定一點。
如果把桶子內的球假設根據我們選的hypothesis function h來上色，如果h(x)和f(x)一致，則上綠色，反之上紅色，則對input space中所有的點來說，不同的h會把同一個input space中的所有點畫出不同的顏色：

所以每一個h其實都類比為對桶子內紅球頻率miu的猜測，透過sampling用nu來逼近或是說infer miu，這邊受惠於Hoeffing's Inequality，所以我們不需要真的知道miu（廢話）就能透過nu infer miu。

這些hypothesis組成了hypothesis set，learning過程其實就是一一比對這些hypothesis，看哪一組sampling最好。所謂的好當然就是紅球越少的越好，因為我們上色的根據是h(x) != f(x)的話，上紅色。不過這邊有個疑問，我們不知道f，要怎麼比對？

這就要用到Hoeffding's Inequality，見下段。

In sample performance and out of sample performance

這個從桶子裡面sampling的動作，其中紅球比例nu，其實在learning過程中實際上就是h判斷錯誤的比例，類比成in sample performance (error) E_in(h):

Hoeffding's Inequality可以改寫如下：

所以我們不需要知道f(x)，只要知道in sample error以及epsilon就能知道這個in sample error與out of sample error被bound在某個跟f(x)無關的數字，這樣就能知道h(x)的好壞。

Hoeffding's Inequality不適用於多次sampling

擲一個銅板10次 （相當從桶子中於做一次sampling)，全部都是 head的機率  = 0.5^10 ~= 0.1%

但是1000個銅板，一樣每個擲10次，出現至少一次全部是head的機率?
對每個銅板來說，擲出10個head的機率 = 0.5^10，所以擲不出10個head的機率 = 1-0.5^10
做了1000次（1000個銅板相當於1000次independent實驗）都擲不出10個head的機率 = (1-0.5^10)^1000

所以至少出現一次10個head的機率為 1 - (1 - 0.5^10)^1000 = 62.3%

做了一千次，至少有一次拿到滿分！！！！這就是機率的描述，做大量嘗試總會有一次狗屎運成功。

Hoeffding's Inequality只對任何一次sampling成立，如果是大量嘗試sampling，則需要修正如下：

假設我們最後挑選出的final hypothesis g，它的Hoefdding's Inequality一定小於等於其他hpothesis的Hoefdding's Inequality，所以worst case bounded by sum of all others:

簡單化減後：

這邊的intuition是：M越大代表你的model越複雜，結果反而in sample error跟out of sample error差距的可能性越大，似乎是指overfitting的問題？
靜待下回分解。