When Can Machines Learn? ——part4
按例放上學(xué)習(xí)進(jìn)度:D
一亚兄、Learning is impossible呢蔫？
先從一個例子思考問題抖剿，給你6張圖片的資料瓢娜，你可以預(yù)測第7張屬于1還是-1嘛醇滥？
答案顯然是有很多種的黎比，比如，它是屬于+1的鸳玩，因為+1的都是對稱阅虫；
你也可以說它的屬于-1的，因為-1的圖形左上角第一個格子都是黑的不跟；
emmmm……
這……
對的颓帝，根本無法知道哪個才是想要的f.
再來看一個數(shù)學(xué)一點的例子:
現(xiàn)在給你5個資料，要你預(yù)測其他3個資料:P
在給的資料D里面窝革，g完全可以接近f购城，但是，在資料外呢?
有很多種可能虐译，根本不知道哪個才是想要的瘪板，也就是說，無法判斷g是不是靠近f的漆诽。然而侮攀，機器學(xué)習(xí)是想知道現(xiàn)有資料外的事，已經(jīng)有結(jié)果的事為啥還要預(yù)測厢拭，我們想要知道的是未知的事兰英。
這……
emmmm……
無法做到D以外的g接近f,這種特性稱為No Free Lunch(NFL)定理。
這個定理告訴我們蚪腐，關(guān)于某某學(xué)習(xí)算法可以在任何領(lǐng)域總是perfect是最準(zhǔn)確的學(xué)習(xí)器箭昵，那是不存在的！
解決方案是回季，利用統(tǒng)計學(xué)的一些假設(shè)家制，加上一些假設(shè)正林，問題似乎變得可以解決了呢:D
二、Probability to the rescue
先從一個球球問題來看:
現(xiàn)在有一個罐子里面放了一些球球颤殴，有橙色的和綠色的觅廓，球球超級多，你能預(yù)測出橙色球球的比例嘛涵但？
統(tǒng)計學(xué)給了一個解決方案杈绸，我先抓一把球球樣本，樣本orange比例為v,green就是1-v矮瘟。
現(xiàn)在假設(shè)罐子里的全部球球orange比例為u,那么green就是1-u瞳脓。
現(xiàn)在思考樣本可以代表罐子里的全部球球嘛？
當(dāng)然不可以!
v不等于u,比如澈侠，今天你歐氣爆滿劫侧，抓的全是green,那你可以說全部的球球都是green的嘛？顯然是不可以的:D
但是哨啃，在數(shù)學(xué)角度烧栋，概率角度來說，v是接近u的拳球！
下面用數(shù)學(xué)的方法來證明:
數(shù)學(xué)上有個Hoeffding's Inequality（霍夫丁不等式可以證明這個問題）:
設(shè)樣本中的orange比例為v
罐子里的orange比例為u
樣本大小為N
根據(jù)Hoeffding Inequality可以發(fā)現(xiàn)审姓，只要N足夠大（ps:exp()的意思是e的幾次方，看式子就知道N越大祝峻，總體越心隆），v是與u接近的莱找。
即只要樣本的數(shù)量足夠大画畅，樣本的比例是接近于罐子的比例的。
它們之間的差值在?之內(nèi)宋距。
我們把'v=u'這種結(jié)論稱為Probably Approximately Correct (PLA)。
這里需要說明一些特性：
- Hoeffding適用于所有的N和?
- 從上面的不等式可以看出症脂，與u無關(guān)谚赎，即我們不需要知道u
- 只要有足夠大的N或者足夠?qū)捤傻牟钪?，我們很可能可以得到v接近于u
總之诱篷，如果N足夠大壶唤，我們是可以通過已知的v去推斷出u的。
三棕所、Connection to learning
前面證明了球球的例子里v是可以推斷出u的闸盔，那么如果把球球的例子轉(zhuǎn)化到我們機器學(xué)習(xí)算法呢?
映射關(guān)系:
- orange比例（或者說概吧:D）=>固定的某條h=f
- 每個球球 => x,罐子=>X
- orange => h is wrong
- green => h is right
- N 個樣本 => 訓(xùn)練樣本D（就是喂給機器的資料D）
結(jié)論:如果N足夠大，且xn獨立同分布琳省，我們就可以從v推斷出u!
所以呢迎吵，現(xiàn)在我們的算法流程增加了一些部分:
- 從H中取一個固定h
- D（訓(xùn)練樣本）是從X來的躲撰，同時也用x去測驗h會不會接近f
- 用Eout(h)來代表我們不知道的那個東西，即f(或者說前面提到的罐子的所所有球球中orange的概率u)
- 用Ein(h)來代表N個樣本（即D）中的出錯率(或者說前面提到的橙色球球的概率v）
與v,u相同击费，對任何固定的h,將Eout(h)拢蛋，Ein(h)代入Hoeffding's Inequality中也是成立的。
和之前的球球問題一樣蔫巩，也具有如下特性：
- Hoeffding適用于所有的N和?
- 因為不取決于Eout(h)谆棱，所以我們不需要知道Eout(h),f和P都可以未知
- Ein(h)= Eout(h)是PAC的
還有一個問題需要考慮，上面的證明都是針對一個固定的h的圆仔，現(xiàn)在我們已經(jīng)可以確定對任何一個固定的h,當(dāng)樣本數(shù)據(jù)足夠大垃瞧，Ein(h)是接近Eout(h)的,那么,這樣就可以證明機器會學(xué)習(xí)了（g接近f）嘛？
當(dāng)A選擇了這個固定的h作為g時坪郭，上面的句子是成立的;
但是如果A是強制性選擇這個固定的h的个从，即A不考慮別的h就選這個fixed h時,上面的句子是錯誤的。因為截粗，說不定別的h更加優(yōu)秀（Ein(h)接近于0）信姓。所以，一般會通過A選擇最好的h绸罗，使Ein(h)足夠小意推，從而保證Eout(h)很小。固定的h珊蟀，使用新數(shù)據(jù)進(jìn)行測試菊值，驗證其錯誤率是多少。
流程如圖:
四育灸、Connection to real learning
現(xiàn)在有很多個h,其中有一個正好全部正確腻窒，那么，可以認(rèn)為罐子里的都是green嘛磅崭？
不行儿子！
從扔硬幣的例子也可以看出，當(dā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很遠(yuǎn)癌蓖，但是瞬哼，Ein很小（樣本出錯很少费坊，可是最后結(jié)果還是很差倒槐，這時候該怪樣本）
關(guān)于這部分再添加一些解釋好了:D
- 比如150個人每個人扔5次硬幣，至少一個人5次都是正面朝上的概率是大于99%的附井，但是讨越，單從一個人來看澎蛛，這個概率是1/32. => BAD D
- 比如我今天來扔個硬幣砾省，扔了5次，全是正面朝上鹰椒，這樣看起來好像正面朝上的概率是1沼死，但是其實還是1/2,Ein和Eout差值太大了 =>BAD sample
- 所以區(qū)別是着逐，比較的預(yù)期不一樣，BAD sample是說和yn不一樣意蛀，BAD D是直接和f(x)不一樣了耸别，前者是樣本里的，后者就是整體的了县钥。
根據(jù)許多次抽樣的到的不同的D秀姐，Hoeffding’s Inequality保證了大多數(shù)的D都是比較好的（即對于某個h，保證Ein≈Eout）若贮，但是也有可能出現(xiàn)BAD D(比如前面提到的150個人扔硬幣的例子省有，有一個人5次全是正面朝上在個人來看概率是很小的，1/32谴麦，機器對于這個固定的h,選擇了它蠢沿，但是它在整體來看是>99%的，是一個BAD D),這就是為什么說小概率事件在選擇多的情況下概率會變大匾效，惡化結(jié)果舷蟀。
- 不同的D，對于不同的h面哼，有可能成為BAD D
- 只要Dn在某個h上是BAD 雪侥，那么Dn就是BAD
- 只有當(dāng)Dn在所有的h上都是好的，才說明Dn不是BAD精绎，可以自由選擇A進(jìn)行建模
M是h的個數(shù)，N是樣本D的數(shù)量锌妻，?是參數(shù)代乃。
用Hoeffding和union bound可以推出:對于任意D,它是某些h的BAD D的概率為P,推導(dǎo)可得P與N成正比，與M成反比,即，M越小搁吓，N越大時原茅，我們越可以放心地在H中選擇錯誤率最小的h作為想要的g.
如果h的個數(shù)M是有限的，N足夠大堕仔，那么通過A任意選擇一個g擂橘，都有Ein≈Eout成立
如果找到一個g，使Ein≈0摩骨，PAC就能保證Eout≈0通贞。
這樣，就證明了機器學(xué)習(xí)是可行的恼五。
至此昌罩，我們現(xiàn)在證明了一個問題，即開篇講到的灾馒，如果是預(yù)測資料外的事茎用，結(jié)果那么多種，我怎么知道哪個才是想要的睬罗，現(xiàn)在我們有了一些假設(shè)條件轨功，那就是我們假設(shè)有Ein和Eout,是對出錯率的一種評估，現(xiàn)在只要我們選擇Ein最小的容达，就可以推出Eout(就是那個未知的東西的出錯率）也是最小的古涧，那么，此時的g就可以認(rèn)為是最優(yōu)秀的董饰，最接近于f的蒿褂。
但是，如上面的學(xué)習(xí)流程圖右下角所示卒暂，如果M是無數(shù)個啄栓，例如之前介紹的PLA直線有無數(shù)條，是否這些推論就不成立了呢也祠？(之后會處理:D)
五昙楚、Summary
總結(jié):
- 從一個圖片和二進(jìn)制例子告訴我們NFL定理，告訴我們ML無法做到g完全等于f
- 對于一個固定的h,用Hoeffding不等式引出Ein,Eout,證明了對于一個固定的h,當(dāng)N足夠大時诈嘿，Ein≈Eout是PAC的
- 對于multi-h情況下堪旧，用Hoeffding和union bound證明了只要M(h的個數(shù))是有限的，且N足夠大奖亚，Ein≈Eout是PAC的
- 最后淳梦，就證明了ML是可行的。
以上:D
注明:以上圖片都來自Cousera臺大林軒田老師的《機器學(xué)習(xí)基石》哦 QwQ
