文章原創(chuàng),最近更新：2018-07-25

學(xué)習(xí)鏈接:
4-3 Connection to Learning
4-4 Connection to Real Learning

學(xué)習(xí)參考鏈接:
1、臺灣大學(xué)林軒田機器學(xué)習(xí)基石課程學(xué)習(xí)筆記4 -- Feasibility of Learning
2、《機器學(xué)習(xí)基石》學(xué)習(xí)筆記<4>

1.Connection to Learning

那么如何通過抽彈珠這個例子跟我們的Learning相聯(lián)系呢？

下面，我們將罐子的內(nèi)容對應(yīng)到機器學(xué)習(xí)的概念上來。機器學(xué)習(xí)中hypothesis與目標函數(shù)相等的可能性，類比于罐子中橙色球的概率問題；

• 罐子里的一顆顆彈珠類比于機器學(xué)習(xí)樣本空間的x；
• 橙色的彈珠類比于h(x)與f不相等；
• 綠色的彈珠類比于h(x)與f相等；
• 從罐子中抽取的N個球類比于機器學(xué)習(xí)的訓(xùn)練樣本D，且這兩種抽樣的樣本與總體樣本之間都是獨立同分布的。

所以呢，如果樣本N夠大，且是獨立同分布的，那么，從樣本中h(x)≠f(x) 的概率就能推導(dǎo)在抽樣樣本外的所有樣本中h(x)≠f(x)的概率是多少。

映射中最關(guān)鍵的點是講抽樣中橙球的概率理解為樣本數(shù)據(jù)集D上h(x)錯誤的概率，以此推算出在所有數(shù)據(jù)上h(x)錯誤的概率，這也是機器學(xué)習(xí)能夠工作的本質(zhì)，即我們?yōu)樯对诓蓸訑?shù)據(jù)上得到了一個假設(shè)，就可以推到全局呢？因為兩者的錯誤率是PAC的，只要我們保證前者小，后者也就小了。

所以呢，現(xiàn)在我們的算法流程增加了一些部分:

• 從H中取一個固定h
• D（訓(xùn)練樣本）是從X來的，同時也用x去測驗h會不會接近f
• 用Eout(h)來代表我們不知道的那個東西，即f(或者說前面提到的罐子的所所有球球中orange的概率u)
• 用Ein(h)來代表N個樣本（即D）中的出錯率(或者說前面提到的橙色球球的概率v）

備注
Ein(h)表示在抽樣樣本中，h(x)與yn不相等的概率；
Eout(h)表示實際所有樣本中，h(x)與f(x)不相等的概率是多少。

與v,u相同，對任何固定的h,將Eout(h)，Ein(h)代入Hoeffding's Inequality中也是成立的。和之前的球球問題一樣，也具有如下特性：

• Hoeffding適用于所有的N和?
• 因為不取決于Eout(h)，所以我們不需要知道Eout(h),f和P都可以未知
• Ein(h)= Eout(h)是PAC的

同樣，它的Hoeffding’s inequality可以表示為：

還有一個問題需要考慮，上面的證明都是針對一個固定的h的，現(xiàn)在我們已經(jīng)可以確定對任何一個固定的h,當樣本數(shù)據(jù)足夠大，Ein(h)是接近Eout(h)的,那么,這樣就可以證明機器會學(xué)習(xí)了（g接近f）嘛？

但是如果A是強制性選擇這個固定的h的，即A不考慮別的h就選這個fixed h時,上面的句子是錯誤的。因為，說不定別的h更加優(yōu)秀（Ein(h)接近于0）。所以，一般會通過A選擇最好的h，使Ein(h)足夠小，從而保證Eout(h)很小。固定的h，使用新數(shù)據(jù)進行測試，驗證其錯誤率是多少。

備用:一般地，h如果是固定的，N很大的時候，Ein(h)≈Eout(h)，但是并不意味著g≈f。因為h是固定的，不能保證Ein(h)足夠小，即使Ein(h)≈Eout(h)，也可能使Eout(h)偏大。

測試練習(xí):

答案是2.

2.Connection to Real Learning

假設(shè)現(xiàn)在有很多罐子M個（即有M個hypothesis,相當于有很多個h），如果其中某個罐子抽樣的球全是綠色，那是不是應(yīng)該選擇這個罐子呢？

不行！
從扔硬幣的例子也可以看出，當選擇多了以后，會惡化BAD sample,也就是說，Ein和Eout的差值很大。最簡單的扔硬幣的例子，雖然可能有的人扔了10次都是正面，但是我們不能說正面的概率就是1，概率還是0.5。這個例子中10次就足以造成BAD sample.

• BAD sample: Ein 和Eout的差值很大
• BAD Data for One h:Eout(h)和Ein(h)差值很大，比如，Eout很大，離f很遠，但是，Ein很?。颖境鲥e很少，可是最后結(jié)果還是很差，這時候該怪樣本）

我們先來看這樣一個例子：150個人拋硬幣，那么其中至少有一個人連續(xù)5次硬幣都是正面朝上的概率是

單從一個人來看，正面朝上的概率是1/32

• 比如我今天來扔個硬幣，扔了5次，全是正面朝上，這樣看起來好像正面朝上的概率是1，但是其實還是1/2,Ein和Eout差值太大了 =>BAD sample
• 所以區(qū)別是，比較的預(yù)期不一樣，BAD sample是說和yn不一樣，BAD D是直接和f(x)不一樣了，前者是樣本里的，后者就是整體的了。

可見這個概率是很大的，但是能否說明5次正面朝上的這個硬幣具有代表性呢？答案是否定的！并不能說明該硬幣單次正面朝上的概率很大，其實都是0.5。一樣的道理，抽到全是綠色求的時候也不能一定說明那個罐子就全是綠色球。當罐子數(shù)目很多或者拋硬幣的人數(shù)很多的時候，可能引發(fā)Bad Sample，Bad Sample就是E(in)和E(out)差別很大，即選擇過多帶來的負面影響，選擇過多會惡化不好的情形。

根據(jù)許多次抽樣的到的不同的數(shù)據(jù)集D，Hoeffding’s inequality保證了大多數(shù)的D都是比較好的情形（即對于某個h，保證E(in)≈E(out))，但是也有可能出現(xiàn)Bad Data，即E(in)和E(out)差別很大的數(shù)據(jù)集D，這是小概率事件。

也就是說，不同的數(shù)據(jù)集D(n),對于不同的hypothesis，有可能成為Bad Data。只要D(n)在某個hypothesis上是Bad Data，那么D(n)就是Bad Data。只有當D(n)在所有的hypothesis上都是好的數(shù)據(jù)，才說明D(n)不是Bad Data，可以自由選擇演算法A進行建模。那么，根據(jù)Hoeffding’s inequality，Bad Data的上界可以表示為連級（union bound）的形式：

如果h的個數(shù)M是有限的，N足夠大，那么通過A任意選擇一個g，都有Ein≈Eout成立
如果找到一個g，使Ein≈0，PAC就能保證Eout≈0。

這樣，就證明了機器學(xué)習(xí)是可行的。

但是，如上面的學(xué)習(xí)流程圖右下角所示，如果M是無數(shù)個，例如之前介紹的PLA直線有無數(shù)條，是否這些推論就不成立了呢？是否機器就不能進行學(xué)習(xí)呢？這些內(nèi)容和問題，我們下節(jié)課再介紹。

測試題目:

答案是1

3.總結(jié)

總結(jié)內(nèi)容如下:

• 從一個圖片和二進制例子告訴我們NFL定理，告訴我們ML無法做到g完全等于f
• 對于一個固定的h,用Hoeffding不等式引出Ein,Eout,證明了對于一個固定的h,當N足夠大時，Ein≈Eout是PAC的
• 對于multi-h情況下，用Hoeffding和union bound證明了只要M(h的個數(shù))是有限的，且N足夠大，Ein≈Eout是PAC的
• 最后，就證明了ML是可行的。