這幾天跟著B站的視頻教程讀了《Learning From Data》這本書，找個(gè)地方總結(jié)下自己的理解。
為什么可以學(xué)習(xí)
做機(jī)器學(xué)習(xí)需要解決的第一個(gè)問題就是為什么機(jī)器學(xué)習(xí)是可行的？這個(gè)直覺上看起來沒啥可討論的問題，細(xì)化分析之后可以得出不少有趣的結(jié)論。
假設(shè)集合H，測試集誤差Ein和實(shí)際誤差Eout
機(jī)器學(xué)習(xí)的過程抽象起來就是從一個(gè)假設(shè)集合H中，根據(jù)測試數(shù)據(jù)上的誤差Ein，選取最合適的假設(shè)h的過程，這中間就涉及兩個(gè)主要問題：
如何保證Eout
我們只能在測試數(shù)據(jù)上進(jìn)行測試，得到測試誤差Ein，但是如何保證在真實(shí)數(shù)據(jù)上應(yīng)用這個(gè)假設(shè)時(shí)，Eout的大小也是可控的呢？如何選擇h
H的大小很可能是無限大，我們不可能把所有的假設(shè)都在測試數(shù)據(jù)上跑一遍，那么如何在有限的嘗試中選取合適的h呢？
如何保證Eout好像直覺上很簡單，如果保證測試數(shù)據(jù)是在真實(shí)數(shù)據(jù)中獨(dú)立隨機(jī)采樣到的，那么在測試數(shù)據(jù)上Ein和真實(shí)數(shù)據(jù)上的Eout的大小就有一個(gè)概率關(guān)系，也就是霍夫丁不等式：
是吧，看起來很簡單，Ein保證了，Eout就有保證了。但是我們忽略了一個(gè)過程，選擇最終的假設(shè)h時(shí)，我們是在H集合里選的，一般都是選擇Ein最小的那一個(gè)，這個(gè)過程會(huì)干擾Eout。
怎么理解呢，我們舉一個(gè)例子，假設(shè)我們需要預(yù)測一個(gè)有無限個(gè)球的罐子里，各種顏色球（紅黃藍(lán)）的比例，然后球一共有3種顏色，實(shí)際上各種顏色球的比例是1：1：1，實(shí)驗(yàn)方法是從罐子里取出3個(gè)球，來看哪種假設(shè)符合。
我們的假設(shè)集合本來只有兩個(gè)假設(shè)，紅黃藍(lán)1：1：1和全藍(lán)，全藍(lán)命中的概率只有(1/3)^3，很明顯全藍(lán)是個(gè)錯(cuò)誤的假設(shè)。
現(xiàn)在我們?yōu)榱恕案玫挠?xùn)練”，擴(kuò)充了假設(shè)集合，把全紅，全黃都加了進(jìn)來。結(jié)果呢反而導(dǎo)致出錯(cuò)的概率從(1/3)^3到了 (1/3)^3 * 3。
細(xì)品一下，測試數(shù)據(jù)總是有可能出現(xiàn)一些極端分布，會(huì)使得一些錯(cuò)誤假設(shè)Ein特別低，當(dāng)假設(shè)集合特別大的時(shí)候，每一個(gè)錯(cuò)誤假設(shè)都可能撞上對(duì)它來說match的數(shù)據(jù)分布，最終：
假設(shè)集合的增大，可以讓我們找到更低的Ein，但同時(shí)也導(dǎo)致Eout的范圍擴(kuò)大
VC維
實(shí)際上，Eout的擴(kuò)大和H的大小是正比的，這樣對(duì)于我們通常大小是無限的H來說，機(jī)器學(xué)習(xí)似乎失去了意義，當(dāng)假設(shè)集合太大時(shí)，我們總是可能選到一個(gè)正好在測試數(shù)據(jù)上表現(xiàn)特別好的“錯(cuò)誤假設(shè)”。為了解決這個(gè)問題，我們對(duì)假設(shè)進(jìn)行了分類，引入了VC維的概念。
VC維從某種程度上描述了某一個(gè)假設(shè)的“變化能力”，還是繼續(xù)剛才那個(gè)拿球的例子，因?yàn)椤叭S，全紅”的假設(shè)加入，導(dǎo)致我們出錯(cuò)概率變大，那么有一個(gè)做法就是繼續(xù)拿球，拿n個(gè)球，出錯(cuò)概率會(huì)變成 (1/3)^n * 3，隨著n變大，出錯(cuò)概率也會(huì)變小。但是如果我們的假設(shè)還包含“n-1:1:0", "n-2:1:1"這種呢？結(jié)果就是無論我們拿多少個(gè)球，總會(huì)有一個(gè)莫名其妙的假設(shè)正好撞上，最后稀里糊涂成為我們的最終假設(shè)。
所以雖然H是無限的，但我們?nèi)匀灰拗萍僭O(shè)的實(shí)際能力，比如我們規(guī)定，假設(shè)只能估計(jì)10個(gè)球內(nèi)紅黃藍(lán)的分布，這樣雖然10個(gè)球以內(nèi)怎么拿都會(huì)有一個(gè)奇葩假設(shè)能match，但是如果拿了10+K個(gè)球，多的K個(gè)球，每個(gè)球都是對(duì)假設(shè)集合的一個(gè)檢驗(yàn)。
限制假設(shè)的能力，有幾個(gè)辦法
一個(gè)是對(duì)假設(shè)進(jìn)行分析，找到它本身的能力范圍，就是VC維，如果假設(shè)的VC維不是無限的，那么增大采樣數(shù)據(jù)，就可以減小假設(shè)集合選出一個(gè)錯(cuò)誤假設(shè)的概率。
第二個(gè)就是強(qiáng)行約束我們模型的”能力“，當(dāng)模型的VC維太大時(shí)，我們可以得到很小的Ein，但是Eout會(huì)很大，就是我們常說的過擬合。過擬合常見的一個(gè)方案是增加regulator，regulator的作用方式是對(duì)模型參數(shù)增加一個(gè)限制，從某個(gè)角度看，就是限制了模型的表達(dá)能力，降低了其VC維。
