????????在前一篇筆記中介紹了一些機器學習中的基本概念猛计，其中提到了“模型”和“假設(shè)空間”的概念掩浙，也說過“統(tǒng)計學習首先要考慮的問題是學習什么樣的模型，模型確定了，模型的假設(shè)空間自然就確定了累盗，后面要做的就是從假設(shè)空間子搜索最優(yōu)的假設(shè)”。那么突琳，大家可能就會提出這樣的問題“哪一種模型能提出最好的假設(shè)空間若债，從而得到性能最好的假設(shè)函數(shù)？”或者“有沒有一個最強大的模型本今，使用它就可以解決所有的問題”或者更具體的“傳統(tǒng)的機器機器學習技術(shù)和現(xiàn)在正火熱的深度學習哪個更好？”主巍。答案很簡單：不結(jié)合具體的問題去比較哪個模型更好沒有意義冠息！接下來我們來看一個叫“沒有免費午餐”（NFL，No Free Lunch）的理論孕索，它會告訴我們?yōu)槭裁词沁@個答案逛艰。在接下來的討論中我們不區(qū)分模型、策略和算法搞旭，將它們統(tǒng)稱為“算法”或“機器學習算法”散怖，將由“算法”最終訓練出的最佳假設(shè)稱為“模型”。
????????首先看一個簡單例子（來源：周志華《機器學習》）：
????????假設(shè)我們有6個樣本點(xi, yi)組成的訓練集肄渗，分布如下圖：
????????假設(shè)我們選擇了兩種不同的機器學習算法La和Lb在這個訓練集上作訓練镇眷，它們各自搜索出了各自假設(shè)空間中最佳的假設(shè)函數(shù)A和B，對應上圖中的A和B兩條曲線翎嫡。那么對于A和B這兩個模型到底哪一個對未來的新的數(shù)據(jù)的預測更好呢欠动？
????????我們也許傾向于結(jié)構(gòu)更簡單的A。好吧惑申，如果我們的實際問題的數(shù)據(jù)分布如下圖所示具伍，那么A的性能的確比B好，A與訓練集外的樣本更一致圈驼，預測的比B準確：
上圖中人芽，白點為測試樣本，黑點為訓練樣本绩脆。
但是萤厅，現(xiàn)實的問題也有可能是這樣的：
在上面的這種情況下，B的性能比A好靴迫。
????????上面的例子說明了祈坠，不結(jié)合具體問題的情況下，對于一個學習算法La矢劲，若它在某個問題上比學習算法Lb好赦拘，則必然存在另一些問題，在那里Lb比La好芬沉。這個結(jié)論對任何算法都成立躺同，哪怕La是一個非常先進的算法阁猜，而Lb只是“隨機胡猜”算法。
????????周志華《機器學習》中給出了一個簡單的形式化的證明蹋艺，我會在其基礎(chǔ)上增加一些解釋來說明某些式子的意義剃袍。
周志華《機器學習》原文：
? ??????我解釋下為什么使用(1.1)式作為“訓練集之外的所有樣本上的誤差”。
????????首先捎谨，我們是這樣定義一個假設(shè)函數(shù)h對一個樣本點x的預測誤差的：預測值h(x)與真實值f(x)一致則誤差為0民效，不一致則誤差為1，即I(h(x)≠f(x))
? ? ? ? 由于x是一個隨機變量涛救，那么這個誤差值也是一個隨機變量畏邢，取值為0或1，其在訓練集之外的所有樣本上的期望可以看作假設(shè)函數(shù)h在訓練集之外的所有樣本上預測的錯誤率检吆，即：
????????我們就把這個錯誤率作為假設(shè)函數(shù)h在訓練集之外的所有樣本上的誤差舒萎。
????????然后，在算法La的假設(shè)空間中可能會存在多個假設(shè)函數(shù)與訓練集一致蹭沛，最終產(chǎn)生哪一個是有概率的（這一點我們在以后介紹具體算法時就會看到）臂寝，令算法La在訓練數(shù)據(jù)集X上產(chǎn)生某個假設(shè)h的概率為P(h|X, La)，那么摊灭，我們接下來要做的是定義算法La在“訓練集之外的所有樣本上的誤差”咆贬，而不只是La產(chǎn)生的一個假設(shè)h的誤差。
????????我們已經(jīng)定義了假設(shè)函數(shù)h在訓練集之外的所有樣本上的誤差帚呼，由于h是算法La以概率P(h|X, La)產(chǎn)生的素征，那么我們可以定義算法La的誤差為所有可能的h的誤差的期望，即：
????????上面的說明就是(1.1)是的含義了萝挤。
????????再解釋下(1.2)式的推導：
????????首先御毅，這里考慮的是二分類問題，而且假設(shè)真實目標函數(shù)f可以是任何輸入空間X到輸出空間{0, 1}的映射怜珍，那么整個函數(shù)空間的大小就應該是2^|X|端蛆。
????????然后，這里假設(shè)在整個函數(shù)空間中所有可能的目標函數(shù)f是均勻分布的（即所有真實的問題是均勻出現(xiàn)的）酥泛。
????????在二分類問題中今豆，對于一個樣本點x，假設(shè)函數(shù)h(x)的預測值要么是0要么是1柔袁，不妨假設(shè)為0呆躲，那么由于f是均勻分布的，所有將x映射為0的真實函數(shù)f的數(shù)量和所有將x映射為1的真實函數(shù)f的數(shù)量應該是一樣的捶索，那么插掂，在函數(shù)空間中就有一半數(shù)量的可能的f于假設(shè)函數(shù)h的預測不一致，于是就有：
等于
????????上面是對于NFL的簡化推導的說明。我們現(xiàn)在來看看這個NFL的結(jié)論辅甥。結(jié)論很有意思酝润，總誤差與學習算法無關(guān)，任意兩個學習算法它們的期望性能是相同的璃弄。既然所有學習算法的期望性能都和隨機胡猜差不多要销，那還有什么好學的？
????????我們需要注意到夏块，NFL定理有一個主要的前提：所有“問題”出現(xiàn)的機會相同疏咐，或所有問題同等重要。但實際情況并不是這樣脐供。很多時候浑塞，我們只關(guān)注自己正在試圖解決的問題（例如某個具體應用任務），希望為它找到一個解決方案患民，至于這個解決方案在別的問題缩举、甚至在相似的問題上是否為好方案垦梆，我們并不關(guān)心匹颤。所以，NFL定理最重要的寓意托猩，是讓我們清楚地認識到印蓖，脫離具體問題，空泛地談論“什么學習算法更好”毫無意義京腥，因為若考慮所有潛在的問題赦肃，則所有學習算法都一樣好。要談論算法的相對優(yōu)劣公浪，必須要針對具體的學習問題他宛；在某些問題上表現(xiàn)好的學習算法，在另一些問題上卻可能不盡如人意欠气。
????????可行的做法是厅各，針對我們要解決的問題，比較可能的模型的預測性能预柒，選出針對該問題最好的模型队塘。
????????最后，加一點我的理解宜鸯，不一定正確憔古，僅供參考。在《機器學習中》只對f按均勻分布算了誤差總和淋袖，其實我們可以算一下學習算法La在所有問題按均勻分布出現(xiàn)時的期望誤差鸿市，這個期望誤差其實就是學習算法La在均勻分布的所有問題上的不準確率，它的結(jié)果是：
????????其中X是樣本空間，D是訓練數(shù)據(jù)集灸芳，x∈X－D就是訓練集之外的所有樣本涝桅。式子中求和的部分是對x的概率求和，所以有E<=1/2, 也就是說這個不準確率是有上界的烙样。訓練數(shù)據(jù)集越小冯遂，這個不準確率越接近1/2，即當訓練數(shù)據(jù)不足時谒获，學習算法想給均勻出現(xiàn)的所有二分類問題提供一個通用的模型其準確率和瞎猜差不多接近一半一半蛤肌；但是如果能有充足的訓練數(shù)據(jù)，雖然學習算法之間的性能無法評估批狱，但是學出來的模型的準確率高于50%裸准，學習總比不學強。
