淺談NFL定理
??NFL定義全稱，No Lunch Free沒有免費(fèi)的午餐定理，這是幫助我們理解算法性能的一個(gè)定理。你可能會覺得這個(gè)定理證明出來的結(jié)論或許是無稽之談，或許產(chǎn)生一種算法的無用論，但是事實(shí)并非如此。下面介紹的沒有免費(fèi)午餐定理的大部分內(nèi)容取自機(jī)器學(xué)習(xí)-周志華
??剛開始看到這個(gè)定理的時(shí)候你一定會覺得精深難懂，但是實(shí)際上確實(shí)只需要一些基礎(chǔ)的概率知識就能理解這條定理的基本內(nèi)容。
??介紹具體的證明過程之前，需要了解一些背景知識。在機(jī)器學(xué)習(xí)中，機(jī)器學(xué)習(xí)算法有成千上萬種，每種算法都有其獨(dú)到之處，都能達(dá)到我們想要的效果，但是往往效率或者正確率有差別，需要具體問題具體分析。
??實(shí)際上異常公平的一點(diǎn)是，假如一個(gè)算法針對問題X效率奇高，但是面對另一個(gè)具體問題Y時(shí)，效率非常低，甚至比不上一個(gè)在X問題上非常垃圾的算法B，這種現(xiàn)象是普遍存在的。
??從上面的圖來看，黑點(diǎn)代表訓(xùn)練集，白圈代表樣本空間除訓(xùn)練集之外的部分，甚至我們可以稱之為測試集。采用不同的算法針對相同的訓(xùn)練集訓(xùn)練，產(chǎn)生了A、B兩種不同的模型，圖a我們可以看到模型A針對測試集的泛化能力比B好很多，但是圖b的情況也是完全有可能出現(xiàn)的。所以針對不同的具體問題，算法的選擇也很重要，一個(gè)適合X問題的算法A，不一定普適于問題Y，甚至有可能在問題Y上A算法的表現(xiàn)不如“隨便亂猜”。
??憑什么這么說？
??上面公式1.1中定義了算法a在訓(xùn)練集X外的誤差，其中代表樣本空間，X代表訓(xùn)練集，I(·)表示如果·取值為幀，則I(·)為1，否則為0，也就是說當(dāng)假設(shè)h(x)產(chǎn)生的結(jié)果與f(x)一致時(shí)，不計(jì)入誤差，不一致時(shí)計(jì)入誤差。
??這部分表示對x預(yù)測結(jié)果的期望，也就等同于錯(cuò)誤率。如果不能理解，你可以考慮這樣一個(gè)問題，如果x取值1~10共十個(gè)數(shù)，我們采用算法A產(chǎn)生了假設(shè)h，有兩個(gè)h(x)的預(yù)測和實(shí)際的f(x)不一致，此時(shí)錯(cuò)誤率是多少呢，是，通過上面的公式(1)也可以計(jì)算出這個(gè)結(jié)果，每個(gè)x的取值概率為0.1，那么結(jié)果就是
。
??這部分明白之后，我們看,算法a可以產(chǎn)生不止一個(gè)假設(shè)h，每個(gè)假設(shè)出現(xiàn)的概率不同，這里定義為
??上面的公式表示，算法a在訓(xùn)練樣本X中，產(chǎn)生假設(shè)h的概率。
我們已經(jīng)知道一點(diǎn)是公式(1)表示的是假設(shè)h針對訓(xùn)練樣本集的誤差期望，那么結(jié)合公式(2)就產(chǎn)生了(1.1)的公式。
??因此公式（1.1）的意思就可以理解為，在訓(xùn)練集X上采用算法a產(chǎn)生的所有假設(shè)h的總誤差，從數(shù)學(xué)角度來說是個(gè)期望值，這里把這個(gè)期望值定義為誤差。
??接下來考慮一個(gè)二分類問題，也就是存在映射使得，這樣的映射函數(shù)有很多種，因此我們稱為假設(shè)這樣的映射函數(shù)為f，函數(shù)空間為
,然后我們按照所有的可能函數(shù)f對誤差進(jìn)一步求和，有
??上面的公式具備一些概率統(tǒng)計(jì)的基礎(chǔ)知識便能容易的推導(dǎo)出來，這里有個(gè)假設(shè)就是f是均勻分布的函數(shù)，均勻分布的函數(shù)從概率的角度來看會有一半與h（x）符合，一半與h（x）不符合，因此對函數(shù)空間乘以0.5。公式推導(dǎo)出來之后，我們會發(fā)現(xiàn)一個(gè)驚人的事情，就是算法a的總誤差與算法無關(guān)，也就是說即便我們采用隨便亂猜的算法b，最后得到的總誤差與a算法得到的總誤差沒什么不同。
??我們很容易想到，如果總誤差與算法無關(guān)，為什么還要設(shè)計(jì)那么多的算法，直接亂猜不久行了嘛？實(shí)際上，這種想法是錯(cuò)誤的，很多人簡單的去引用NFL定理，但是往往忘記了這個(gè)定理的前提，就是f是均勻分布的。但是實(shí)際情況并非如此，實(shí)際中各種建模的各種現(xiàn)象并非是均勻分布的，因此我們需要具體問題具體分析。
??總之，這個(gè)定理是讓我們意識到，討論算法的優(yōu)劣，泛化能力的強(qiáng)弱，都不能脫離實(shí)際的問題，要針對具體的問題具體地分析。
