上節(jié)課，我們主要介紹了根據(jù)不同的設(shè)定甸祭，機(jī)器學(xué)習(xí)可以分為不同的類型。其中褥影，監(jiān)督式學(xué)習(xí)中的二元分類和回歸分析是最常見的也是最重要的機(jī)器學(xué)習(xí)問題池户。本節(jié)課，我們將介紹機(jī)器學(xué)習(xí)的可行性凡怎，討論問題是否可以使用機(jī)器學(xué)習(xí)來解決校焦。

一、Learning is Impossible

首先统倒，考慮這樣一個(gè)例子寨典，如下圖所示，有3個(gè)label為-1的九宮格和3個(gè)label為+1的九宮格房匆。根據(jù)這6個(gè)樣本耸成，提取相應(yīng)label下的特征，預(yù)測右邊九宮格是屬于-1還是+1浴鸿？結(jié)果是井氢，如果依據(jù)對(duì)稱性，我們會(huì)把它歸為+1赚楚；如果依據(jù)九宮格左上角是否是黑色毙沾，我們會(huì)把它歸為-1。除此之外宠页，還有根據(jù)其它不同特征進(jìn)行分類左胞，得到不同結(jié)果的情況。而且举户，這些分類結(jié)果貌似都是正確合理的烤宙，因?yàn)閷?duì)于6個(gè)訓(xùn)練樣本來說，我們選擇的模型都有很好的分類效果俭嘁。

image.png

再來看一個(gè)比較數(shù)學(xué)化的二分類例子躺枕，輸入特征x是二進(jìn)制的、三維的，對(duì)應(yīng)有8種輸入拐云，其中訓(xùn)練樣本D有5個(gè)罢猪。那么，根據(jù)訓(xùn)練樣本對(duì)應(yīng)的輸出y叉瘩，假設(shè)有8個(gè)hypothesis膳帕，這8個(gè)hypothesis在D上，對(duì)5個(gè)訓(xùn)練樣本的分類效果效果都完全正確薇缅。但是在另外3個(gè)測試數(shù)據(jù)上危彩，不同的hypothesis表現(xiàn)有好有壞。在已知數(shù)據(jù)D上泳桦，g≈f汤徽；但是在D以外的未知數(shù)據(jù)上，g≈f不一定成立灸撰。而機(jī)器學(xué)習(xí)目的谒府，恰恰是希望我們選擇的模型能在未知數(shù)據(jù)上的預(yù)測與真實(shí)結(jié)果是一致的，而不是在已知的數(shù)據(jù)集D上尋求最佳效果梧奢。

image.png

這個(gè)例子告訴我們狱掂，我們想要在D以外的數(shù)據(jù)中更接近目標(biāo)函數(shù)似乎是做不到的，只能保證對(duì)D有很好的分類結(jié)果亲轨。機(jī)器學(xué)習(xí)的這種特性被稱為沒有免費(fèi)午餐（No Free Lunch）定理趋惨。NFL定理表明沒有一個(gè)學(xué)習(xí)算法可以在任何領(lǐng)域總是產(chǎn)生最準(zhǔn)確的學(xué)習(xí)器。不管采用何種學(xué)習(xí)算法惦蚊，至少存在一個(gè)目標(biāo)函數(shù)器虾，能夠使得隨機(jī)猜測算法是更好的算法。平常所說的一個(gè)學(xué)習(xí)算法比另一個(gè)算法更“優(yōu)越”蹦锋，效果更好兆沙，只是針對(duì)特定的問題，特定的先驗(yàn)信息莉掂，數(shù)據(jù)的分布葛圃，訓(xùn)練樣本的數(shù)目，代價(jià)或獎(jiǎng)勵(lì)函數(shù)等憎妙。從這個(gè)例子來看库正，NFL說明了無法保證一個(gè)機(jī)器學(xué)習(xí)算法在D以外的數(shù)據(jù)集上一定能分類或預(yù)測正確，除非加上一些假設(shè)條件厘唾，我們以后會(huì)介紹褥符。

二、Probability to the Rescue

從上一節(jié)得出的結(jié)論是：在訓(xùn)練集D以外的樣本上抚垃，機(jī)器學(xué)習(xí)的模型是很難喷楣，似乎做不到正確預(yù)測或分類的趟大。那是否有一些工具或者方法能夠?qū)ξ粗哪繕?biāo)函數(shù)f做一些推論，讓我們的機(jī)器學(xué)習(xí)模型能夠變得有用呢铣焊？

如果有一個(gè)裝有很多（數(shù)量很大數(shù)不過來）橙色球和綠色球的罐子逊朽，我們能不能推斷橙色球的比例u？統(tǒng)計(jì)學(xué)上的做法是曲伊，從罐子中隨機(jī)取出N個(gè)球惋耙，作為樣本，計(jì)算這N個(gè)球中橙色球的比例v熊昌，那么就估計(jì)出罐子中橙色球的比例約為v。

image.png

這種隨機(jī)抽取的做法能否說明罐子里橙色球的比例一定是v呢湿酸？答案是否定的婿屹。但是從概率的角度來說，樣本中的v很有可能接近我們未知的u推溃。下面從數(shù)學(xué)推導(dǎo)的角度來看v與u是否相近昂利。

已知u是罐子里橙色球的比例，v是N個(gè)抽取的樣本中橙色球的比例铁坎。當(dāng)N足夠大的時(shí)候蜂奸，v接近于u。這就是Hoeffding’s inequality：

P[|v?u|>?]≤2exp(?2?2N)
Hoeffding不等式說明當(dāng)N很大的時(shí)候硬萍，v與u相差不會(huì)很大扩所，它們之間的差值被限定在?之內(nèi)。我們把結(jié)論v=u稱為probably approximately correct(PAC)朴乖。

image.png

三祖屏、Connection to Learning

下面，我們將罐子的內(nèi)容對(duì)應(yīng)到機(jī)器學(xué)習(xí)的概念上來买羞。機(jī)器學(xué)習(xí)中hypothesis與目標(biāo)函數(shù)相等的可能性袁勺，類比于罐子中橙色球的概率問題；罐子里的一顆顆彈珠類比于機(jī)器學(xué)習(xí)樣本空間的x畜普；橙色的彈珠類比于h(x)與f不相等期丰；綠色的彈珠類比于h(x)與f相等；從罐子中抽取的N個(gè)球類比于機(jī)器學(xué)習(xí)的訓(xùn)練樣本D吃挑，且這兩種抽樣的樣本與總體樣本之間都是獨(dú)立同分布的钝荡。所以呢，如果樣本N夠大儒鹿，且是獨(dú)立同分布的化撕，那么，從樣本中h(x)≠f(x)的概率就能推導(dǎo)在抽樣樣本外的所有樣本中h(x)≠f(x)的概率是多少约炎。

image.png

映射中最關(guān)鍵的點(diǎn)是講抽樣中橙球的概率理解為樣本數(shù)據(jù)集D上h(x)錯(cuò)誤的概率植阴，以此推算出在所有數(shù)據(jù)上h(x)錯(cuò)誤的概率蟹瘾，這也是機(jī)器學(xué)習(xí)能夠工作的本質(zhì)，即我們?yōu)樯对诓蓸訑?shù)據(jù)上得到了一個(gè)假設(shè)掠手，就可以推到全局呢憾朴？因?yàn)閮烧叩腻e(cuò)誤率是PAC的，只要我們保證前者小喷鸽，后者也就小了众雷。

image.png

這里我們引入兩個(gè)值Ein(h)和Eout(h)。Ein(h)表示在抽樣樣本中做祝，h(x)與yn不相等的概率砾省；Eout(h)表示實(shí)際所有樣本中，h(x)與f(x)不相等的概率是多少混槐。

image.png

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

P[|Ein(h)?Eout(h)|>?]≤2exp(?2?2N)
該不等式表明，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很大的時(shí)候俄认，Ein(h)≈Eout(h)个少，但是并不意味著g≈f。因?yàn)閔是固定的眯杏，不能保證Ein(h)足夠小夜焦，即使Ein(h)≈Eout(h)，也可能使Eout(h)偏大岂贩。所以茫经，一般會(huì)通過演算法A，選擇最好的h萎津，使Ein(h)足夠小卸伞，從而保證Eout(h)很小。固定的h锉屈，使用新數(shù)據(jù)進(jìn)行測試荤傲，驗(yàn)證其錯(cuò)誤率是多少。

image.png

四颈渊、Connection to Real Learning

這里寫圖片描述

假設(shè)現(xiàn)在有很多罐子M個(gè)（即有M個(gè)hypothesis）遂黍，如果其中某個(gè)罐子抽樣的球全是綠色终佛，那是不是應(yīng)該選擇這個(gè)罐子呢？我們先來看這樣一個(gè)例子：150個(gè)人拋硬幣雾家，那么其中至少有一個(gè)人連續(xù)5次硬幣都是正面朝上的概率是

1?(3132)150>99%
可見這個(gè)概率是很大的铃彰，但是能否說明5次正面朝上的這個(gè)硬幣具有代表性呢？答案是否定的芯咧！并不能說明該硬幣單次正面朝上的概率很大牙捉，其實(shí)都是0.5。一樣的道理敬飒，抽到全是綠色求的時(shí)候也不能一定說明那個(gè)罐子就全是綠色球邪铲。當(dāng)罐子數(shù)目很多或者拋硬幣的人數(shù)很多的時(shí)候，可能引發(fā)Bad Sample无拗，Bad Sample就是Ein和Eout差別很大霜浴，即選擇過多帶來的負(fù)面影響，選擇過多會(huì)惡化不好的情形蓝纲。

根據(jù)許多次抽樣的到的不同的數(shù)據(jù)集D，Hoeffding’s inequality保證了大多數(shù)的D都是比較好的情形（即對(duì)于某個(gè)h晌纫，保證Ein≈Eout）税迷，但是也有可能出現(xiàn)Bad Data，即Ein和Eout差別很大的數(shù)據(jù)集D锹漱，這是小概率事件箭养。

image.png

也就是說，不同的數(shù)據(jù)集Dn哥牍，對(duì)于不同的hypothesis毕泌，有可能成為Bad Data。只要Dn在某個(gè)hypothesis上是Bad Data嗅辣，那么Dn就是Bad Data撼泛。只有當(dāng)Dn在所有的hypothesis上都是好的數(shù)據(jù)，才說明Dn不是Bad Data澡谭，可以自由選擇演算法A進(jìn)行建模愿题。那么，根據(jù)Hoeffding’s inequality蛙奖，Bad Data的上界可以表示為連級(jí)（union bound）的形式：

image.png

所以，如果hypothesis的個(gè)數(shù)M是有限的瓢宦，N足夠大碎连，那么通過演算法A任意選擇一個(gè)矩g，都有Ein≈Eout成立驮履；同時(shí)鱼辙，如果找到一個(gè)矩g，使Ein≈0玫镐，PAC就能保證Eout≈0倒戏。至此，就證明了機(jī)器學(xué)習(xí)是可行的恐似。

image.png

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

五忧陪、總結(jié)

本節(jié)課主要介紹了機(jī)器學(xué)習(xí)的可行性治笨。首先引入NFL定理，說明機(jī)器學(xué)習(xí)無法找到一個(gè)矩g能夠完全和目標(biāo)函數(shù)f一樣赤嚼。接著介紹了可以采用一些統(tǒng)計(jì)上的假設(shè)旷赖，例如Hoeffding不等式，建立Ein和Eout的聯(lián)系更卒，證明對(duì)于某個(gè)h等孵，當(dāng)N足夠大的時(shí)候，Ein和Eout是PAC的蹂空。最后俯萌，對(duì)于h個(gè)數(shù)很多的情況果录，只要有h個(gè)數(shù)M是有限的，且N足夠大咐熙，就能保證Ein≈Eout弱恒，證明機(jī)器學(xué)習(xí)是可行的。

注明：

文章中所有的圖片均來自臺(tái)灣大學(xué)林軒田《機(jī)器學(xué)習(xí)基石》課程棋恼。