上節(jié)課橄浓，我們主要介紹了根據(jù)不同的設(shè)定吠谢，機(jī)器學(xué)習(xí)可以分為不同的類型。其中唯袄，監(jiān)督式學(xué)習(xí)中的二元分類和回歸分析是最常見的也是最重要的機(jī)器學(xué)習(xí)問題弯屈。本節(jié)課，我們將介紹機(jī)器學(xué)習(xí)的可行性恋拷，討論問題是否可以使用機(jī)器學(xué)習(xí)來解決资厉。
首先蔬顾，考慮這樣一個例子宴偿，如下圖所示湘捎，有3個label為-1的九宮格和3個label為+1的九宮格。根據(jù)這6個樣本窄刘，提取相應(yīng)label下的特征窥妇，預(yù)測右邊九宮格是屬于-1還是+1？結(jié)果是娩践，如果依據(jù)對稱性活翩，我們會把它歸為+1；如果依據(jù)九宮格左上角是否是黑色翻伺，我們會把它歸為-1材泄。除此之外，還有根據(jù)其它不同特征進(jìn)行分類吨岭，得到不同結(jié)果的情況拉宗。而且，這些分類結(jié)果貌似都是正確合理的辣辫，因為對于6個訓(xùn)練樣本來說旦事，我們選擇的模型都有很好的分類效果。
再來看一個比較數(shù)學(xué)化的二分類例子络它，輸入特征x是二進(jìn)制的族檬、三維的，對應(yīng)有8種輸入化戳，其中訓(xùn)練樣本D有5個单料。那么，根據(jù)訓(xùn)練樣本對應(yīng)的輸出y点楼，假設(shè)有8個hypothesis扫尖，這8個hypothesis在D上，對5個訓(xùn)練樣本的分類效果效果都完全正確掠廓。但是在另外3個測試數(shù)據(jù)上换怖，不同的hypothesis表現(xiàn)有好有壞。在已知數(shù)據(jù)D上蟀瞧，g≈f沉颂；但是在D以外的未知數(shù)據(jù)上，g≈f不一定成立悦污。而機(jī)器學(xué)習(xí)目的铸屉，恰恰是希望我們選擇的模型能在未知數(shù)據(jù)上的預(yù)測與真實結(jié)果是一致的，而不是在已知的數(shù)據(jù)集D上尋求最佳效果切端。
這個例子告訴我們彻坛，我們想要在D以外的數(shù)據(jù)中更接近目標(biāo)函數(shù)似乎是做不到的，只能保證對D有很好的分類結(jié)果。機(jī)器學(xué)習(xí)的這種特性被稱為沒有免費午餐（No Free Lunch）定理昌屉。NFL定理表明沒有一個學(xué)習(xí)算法可以在任何領(lǐng)域總是產(chǎn)生最準(zhǔn)確的學(xué)習(xí)器钙蒙。不管采用何種學(xué)習(xí)算法，至少存在一個目標(biāo)函數(shù)间驮，能夠使得隨機(jī)猜測算法是更好的算法躬厌。平常所說的一個學(xué)習(xí)算法比另一個算法更“優(yōu)越”，效果更好竞帽，只是針對特定的問題烤咧，特定的先驗信息，數(shù)據(jù)的分布抢呆，訓(xùn)練樣本的數(shù)目，代價或獎勵函數(shù)等笛谦。從這個例子來看抱虐，NFL說明了無法保證一個機(jī)器學(xué)習(xí)算法在D以外的數(shù)據(jù)集上一定能分類或預(yù)測正確，除非加上一些假設(shè)條件饥脑，我們以后會介紹恳邀。
從上一節(jié)得出的結(jié)論是：在訓(xùn)練集D以外的樣本上灶轰，機(jī)器學(xué)習(xí)的模型是很難谣沸，似乎做不到正確預(yù)測或分類的。那是否有一些工具或者方法能夠?qū)ξ粗哪繕?biāo)函數(shù)f做一些推論笋颤，讓我們的機(jī)器學(xué)習(xí)模型能夠變得有用呢乳附？
如果有一個裝有很多（數(shù)量很大數(shù)不過來）橙色球和綠色球的罐子，我們能不能推斷橙色球的比例u伴澄？統(tǒng)計學(xué)上的做法是赋除，從罐子中隨機(jī)取出N個球，作為樣本非凌，計算這N個球中橙色球的比例v举农，那么就估計出罐子中橙色球的比例約為v。
這種隨機(jī)抽取的做法能否說明罐子里橙色球的比例一定是v呢敞嗡？答案是否定的颁糟。但是從概率的角度來說，樣本中的v很有可能接近我們未知的u喉悴。下面從數(shù)學(xué)推導(dǎo)的角度來看v與u是否相近棱貌。
已知u是罐子里橙色球的比例，v是N個抽取的樣本中橙色球的比例粥惧。當(dāng)N足夠大的時候键畴，v接近于u。這就是Hoeffding’s inequality：
Hoeffding不等式說明當(dāng)N很大的時候，v與u相差不會很大起惕，它們之間的差值被限定在?之內(nèi)涡贱。我們把結(jié)論v=u稱為probably approximately correct(PAC)。
下面问词，我們將罐子的內(nèi)容對應(yīng)到機(jī)器學(xué)習(xí)的概念上來。機(jī)器學(xué)習(xí)中hypothesis與目標(biāo)函數(shù)相等的可能性嘀粱，類比于罐子中橙色球的概率問題激挪；罐子里的一顆顆彈珠類比于機(jī)器學(xué)習(xí)樣本空間的x；橙色的彈珠類比于h(x)與f不相等锋叨；綠色的彈珠類比于h(x)與f相等垄分；從罐子中抽取的N個球類比于機(jī)器學(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)錯誤的概率坐求，這也是機(jī)器學(xué)習(xí)能夠工作的本質(zhì)，即我們?yōu)樯对诓蓸訑?shù)據(jù)上得到了一個假設(shè)晌梨，就可以推到全局呢桥嗤？因為兩者的錯誤率是PAC的，只要我們保證前者小派任，后者也就小了砸逊。
這里我們引入兩個值Ein(h)和Eout(h)。Ein(h)表示在抽樣樣本中掌逛，h(x)與yn不相等的概率师逸；Eout(h)表示實際所有樣本中，h(x)與f(x)不相等的概率是多少豆混。
同樣篓像，它的Hoeffding’s inequality可以表示為：
該不等式表明，Ein(h)=Eout(h)也是PAC的皿伺。如果Ein(h)≈Eout(h)员辩，Ein(h)很小，那么就能推斷出Eout(h)很小鸵鸥，也就是說在該數(shù)據(jù)分布P下奠滑，h與f非常接近丹皱，機(jī)器學(xué)習(xí)的模型比較準(zhǔn)確。
一般地宋税，h如果是固定的摊崭，N很大的時候，Ein(h)≈Eout(h)杰赛，但是并不意味著g≈f呢簸。因為h是固定的，不能保證Ein(h)足夠小乏屯，即使Ein(h)≈Eout(h)根时，也可能使Eout(h)偏大。所以辰晕，一般會通過演算法A蛤迎，選擇最好的h，使Ein(h)足夠小含友，從而保證Eout(h)很小忘苛。固定的h，使用新數(shù)據(jù)進(jìn)行測試唱较，驗證其錯誤率是多少。
四召川、Connection to Real Learning
假設(shè)現(xiàn)在有很多罐子M個（即有M個hypothesis）南缓，如果其中某個罐子抽樣的球全是綠色，那是不是應(yīng)該選擇這個罐子呢荧呐？我們先來看這樣一個例子：150個人拋硬幣汉形，那么其中至少有一個人連續(xù)5次硬幣都是正面朝上的概率是
可見這個概率是很大的，但是能否說明5次正面朝上的這個硬幣具有代表性呢倍阐？答案是否定的概疆！并不能說明該硬幣單次正面朝上的概率很大，其實都是0.5峰搪。一樣的道理岔冀，抽到全是綠色求的時候也不能一定說明那個罐子就全是綠色球。當(dāng)罐子數(shù)目很多或者拋硬幣的人數(shù)很多的時候概耻，可能引發(fā)Bad Sample使套，Bad Sample就是Ein和Eout差別很大，即選擇過多帶來的負(fù)面影響鞠柄，選擇過多會惡化不好的情形侦高。
根據(jù)許多次抽樣的到的不同的數(shù)據(jù)集D，Hoeffding’s inequality保證了大多數(shù)的D都是比較好的情形（即對于某個h厌杜，保證Ein≈Eout）奉呛，但是也有可能出現(xiàn)Bad Data，即Ein和Eout差別很大的數(shù)據(jù)集D，這是小概率事件瞧壮。
也就是說登馒，不同的數(shù)據(jù)集Dn，對于不同的hypothesis馁痴，有可能成為Bad Data谊娇。只要Dn在某個hypothesis上是Bad Data，那么Dn就是Bad Data罗晕。只有當(dāng)Dn在所有的hypothesis上都是好的數(shù)據(jù)济欢，才說明Dn不是Bad Data，可以自由選擇演算法A進(jìn)行建模小渊。那么法褥，根據(jù)Hoeffding’s inequality，Bad Data的上界可以表示為連級（union bound）的形式：
其中酬屉，M是hypothesis的個數(shù)半等，N是樣本D的數(shù)量，?是參數(shù)呐萨。該union bound表明杀饵，當(dāng)M有限，且N足夠大的時候谬擦，Bad Data出現(xiàn)的概率就更低了切距，即能保證D對于所有的h都有Ein≈Eout，滿足PAC惨远，演算法A的選擇不受限制谜悟。那么滿足這種union bound的情況，我們就可以和之前一樣北秽，選取一個合理的演算法（PLA/pocket）葡幸，選擇使Ein最小的hm作為矩g，一般能夠保證g≈f贺氓，即有不錯的泛化能力蔚叨。
所以，如果hypothesis的個數(shù)M是有限的辙培，N足夠大缅叠，那么通過演算法A任意選擇一個矩g，都有Ein≈Eout成立虏冻；同時肤粱，如果找到一個矩g，使Ein≈0厨相，PAC就能保證Eout≈0领曼。至此鸥鹉，就證明了機(jī)器學(xué)習(xí)是可行的。
但是庶骄，如上面的學(xué)習(xí)流程圖右下角所示毁渗，如果M是無數(shù)個，例如之前介紹的PLA直線有無數(shù)條单刁，是否這些推論就不成立了呢灸异？是否機(jī)器就不能進(jìn)行學(xué)習(xí)呢？這些內(nèi)容和問題羔飞，我們下節(jié)課再介紹肺樟。
本節(jié)課主要介紹了機(jī)器學(xué)習(xí)的可行性逻淌。首先引入NFL定理么伯，說明機(jī)器學(xué)習(xí)無法找到一個矩g能夠完全和目標(biāo)函數(shù)f一樣。接著介紹了可以采用一些統(tǒng)計上的假設(shè)卡儒，例如Hoeffding不等式田柔，建立Ein和Eout的聯(lián)系，證明對于某個h骨望，當(dāng)N足夠大的時候硬爆，Ein和Eout是PAC的。最后擎鸠，對于h個數(shù)很多的情況摆屯，只要有h個數(shù)M是有限的，且N足夠大糠亩，就能保證Ein≈Eout，證明機(jī)器學(xué)習(xí)是可行的准验。
原文CSDN博客地址：
NTU林軒田機(jī)器學(xué)習(xí)基石課程學(xué)習(xí)筆記4 -- Feasibility of Learning
注明：
文章中所有的圖片均來自NTU林軒田《機(jī)器學(xué)習(xí)基石》課程赎线。
