引言

談到機器學習一個非常著名的定理，那就不得不提 No Free Lunch 定理了。該定理核心思想是沒有一種通用的學習算法可以在各種任務中都有很好的表現，需要對具體問題進行具體的分析。從原理出發去理解 AI 算法可以能夠對 AI 相關的問題有更深刻的認識，像這種基于嚴格數學證明推導出的結論，尤其值得重視。翻閱了大量的相關材料力求讓該定理的證明過程更加完整（需要注意的是該定理核心證明步驟中用到了一個修改版本的馬爾可夫不等式），相關的材料列在文末。

No Free Lunch 定理證明

定理 1（No Free Lunch）：假定 是一個在域 的二分類任務中任意一個機器學習算法，其損失函數為 損失。令 是一個大小為 的訓練集，存在域 中的分布 ，則有：

• 存在一個函數 ，且有 。

• 對于子列 ，則概率不等式 成立。

證明：

（1）令 表示域 中大小為 的一個子集。主要的證明思路是只利用數據集 一半的數據樣本點并不能給出剩下一半數據點的信息。假定 表示數據集 到標簽集合 所有可能的函數集合，且 表示的是函數集合的基數，其中 ，。對于 中每一個函數假設，令 是 中的分布：

進而可知存在函數 ，在數據分布 上則有 。（2）主要證明的關鍵在于即對任意的學習算法 有：

首先從 中采樣出 個樣本構造一個訓練集，其中采樣出的樣本可以重復，進而可知有 中可能的樣本序列。令這些樣本序列分別表示為 。_

402 Payment Required

表示的是函數 在樣本序列 中的數據集合，則有：

又因為

402 Payment Required

，所以則有：

現固定 ，令 ，，其中 是剩余沒有采樣的樣本數。對于每一個函數 ， 有：

所以

對于給定的 ，因為 是所有可能函數映射的基數，所以總有成對存在的 有：

進而則有：

根據馬爾可夫不等式的修改版可知，給定一個隨機變量 ，給定一個常數 ，進而則有：

馬爾可夫不等式為：

利用馬爾可夫不等可知：

No Free Lunch和先驗知識

訓練一個分類器的時候經常會用到一些先驗知識，那 No Free Lunch 定理與先驗知識有什么關系呢？考慮一個 ERM（Empirical Risk Minimization）分類器，其所有分類映射 組成了集合 。這類映射集合 缺乏先驗知識，則根據 No Free Lunch 定理可知，給定一個學習算法，會在一些學習任務中學習失敗，所以可以推知，該類學習算法 不是 PAC（Probably Approximately Correct）學習的。

定義1（PAC）：如果一個學習算法集合 是 PAC 學習的，存在一個計數函數 。一個學習算法對于任意的 ，任意的在域 中的分布 和任意的打標函數 ，則有該類學習算法數 ，并存在一個學習算法 ，滿足以下概率公式：

根據 PAC 學習的定義和 No Free Lunch 定理可知，則有如下推論：

推論 1：令 是一個無限域集， 是所有 的函數集合，則 不是 PAC 可學習的。

證明：該推論可以利用反證法來證明。假定 是 PAC 可學習的。選取 和 。通過 PAC 的定義可知，一定存在學習算法 ，其數量為 ，對于任意在 上生成的數據分布，如果對于一些函數 ，使得 ，并且當 在采樣出 個樣本的數據集合 上，有：

然后由 No Free Lunch 定理可知，當 ，對于每一個學習算法，存在分布 使得：

所以出現矛盾。

那要如何防止這種失敗？通過使用對特定學習任務的先驗知識，可以避免 No Free Lunch 定理所預見的風險，從而避免在學習該任務時那些導致失敗的分布的出現，所以可知先驗知識主要通過限制學習算法類? 的范圍。

誤差分解

令 是一個 映射，則可以 誤差可以由如下公式表示：

誤差分解為兩部分，一個是近似誤差，另一個是估計誤差。

• 近似誤差：近似誤差是一種歸納偏差，它不取決于訓練樣本集的大小，而是由所由訓練出的分類器的映射所決定。增大映射的范圍可以減小近似誤差。在可實現性假設下，近似誤差為零。然而，在不可知論的情況下，近似誤差可能很大。

• 估計誤差：近似誤差和 ERM 預測值所獲得的誤差之間的差值。估計誤差的產生是因為經驗風險（即訓練誤差）只是對真實風險的估計，因此最小化經驗風險的預測器只是最小化真實風險的預測器的估計。這種估計的質量取決于訓練分類器的訓練集大小以及復雜性。

由于目標是將總損失降至最低，因此就需要面臨著一種權衡，稱為偏差-復雜性權衡。一方面，分類器集合 越大（模型的容量過大，自由度過高）會減少近似誤差，但同時可能會增加估計誤差，因為豐富的 可能會導致過度擬合。

反之，一個非常小的集合（即模型容量不夠大，或者沒有涵蓋到真實的目標函數）會減少估計誤差，但可能會增加近似誤差，或者換句話說，可能會導致擬合不足。No Lunch Theorem 定理指出，沒有通用的學習算法，每個學習算法都必須被指定完成某項任務，并使用有關該任務的一些先驗知識。

參考文獻

[1] https://www.youtube.com/watch?v=DxaK8OSnxvE&list=UUaJUsUVO8sj71H5gCVgh7sw&index=41

[2]?https://www.youtube.com/watch?v=wilz_c07ImI&list=UUaJUsUVO8sj71H5gCVgh7sw&index=40

[3]?https://en.wikipedia.org/wiki/No_free_lunch_theorem

[4]?https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學術熱點剖析、科研心得或競賽經驗講解等。我們的目的只有一個，讓知識真正流動起來。

📝?稿件基本要求：

? 文章確系個人原創作品，未曾在公開渠道發表，如為其他平臺已發表或待發表的文章，請明確標注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發送，要求圖片清晰，無版權問題

? PaperWeekly 尊重原作者署名權，并將為每篇被采納的原創首發稿件，提供業內具有競爭力稿酬，具體依據文章閱讀量和文章質量階梯制結算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請備注即時聯系方式（微信），以便我們在稿件選用的第一時間聯系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長按添加PaperWeekly小編

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

·

總結

以上是生活随笔為你收集整理的机器学习著名定理之—No Free Lunch定理详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。