不要引用「沒有免費的午餐定理」了

雷鋒網 AI 科技評論按：「沒有免費的午餐定理」一度是機器學習界最常被談起的定理之一（真正長期被談起的自然是「更多的數據等於更好的表現」）。不過機器學習科學家 Andreas Mueller 最近撰文表示大家都引用錯定理了，其實事情比這更複雜，也有更深遠的啟示。

Andreas Mueller 是哥倫比亞大學數據科學研究院的助理研究科學家，也是《Introduction to machine learning with Python》一書的作者；他還是 scikit-learn 機器學習庫的核心開發者之一。

雷鋒網 AI 科技評論把他的這篇博客全文編譯如下。

首先一句話概括我這篇文章要說什麼：大家以後盡量不要再引用 Wolpert 的「沒有免費的午餐定理」了。如果你已經在哪裡引用過，那你很有可能用它支持了錯誤的結論。他的句話實際上想表達的是「你不可能在沒有假設的情況下從數據中學習」。

提出「沒有免費的午餐定理」這個概念的，實際上是 David H. Wolpert 的《The Lack of A Priori Distinctions Between Learning Algorithms》（https://www.mitpressjournals.org/doi/abs/10.1162/neco.1996.8.7.1341）這篇論文。機器學習領域裡有不少論文，它們經常被引用，但是沒什麼人認真讀過論文內容；這篇論文就是其中之一。大多數機器學習領域內的人提起這篇論文的時候都是想要說明「某個模型不可能在每個方面都是最好的」，或者「某個模型不會在每個方面都比另一個模型強」。但實際上這並不是 Wolpert 的這篇論文、這個定理真正想要表達的內容，所以大家未來不應該這樣引用這個定理，我會在下文里仔細說明這件事；以及，即便單獨考慮大眾想要說明的「某個模型不可能在每個方面都是最好的」，其實這個結論也是有問題的。

首先，據我所知至少有兩個定理都叫做「沒有免費的午餐」（no free lunch）。一個是 Wolpert 提出的，首次在《The Lack of A Priori Distinctions Between Learning Algorithms》論文里出現；另一個是 Shalev-Shwarz 和 Ben-David 提出的，在《Understanding Machine Learning》這本書里（這本書很棒，http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/）。Wolpert 還發表過一篇《No Free Lunch in Optimization》，不過我們只關注談監督學習的那個定理就好了。

《Understanding Machine Learning》里提出的那個定理和 Wolpert 的很不一樣，我的理解是， Shalev-Shwarz 和 Ben-David 兩人提出這個定理就是為了給「沒有免費的午餐」提出與 Wolpert 不同的、新的詮釋，而其實他們的定理內容是「某個模型不可能在每個方面都是最好的」，不過他們的表達方式非常具體。某種程度上說，他們描述這個定理的方式要比我們從現在的字面上所能感受到的要清晰明確得多。但我不太贊同他們用一個已有的名字來命名這個定理的做法。

Wolpert 最早的那篇論文的主要內容可以總結為「在這個定理的假設之下，任何兩個預測函數的泛化能力都是相同的」。這裡有兩個關鍵部分：假設和結論。

只看結論「任何兩個預測函數的泛化能力都是相同的」的話，經常會有人理解為類似「梯度提升不會總是最好的」這樣。但實際上它想說的是「梯度提升幾乎每次都能找到出現頻率最高的類」或者「神經網路幾乎每次都能預測到出現頻率最低的類」。顯然這和我們的機器學習實踐經驗是衝突的。但根據這個定理的說法，在泛化性質方面它就和你能找到的最好的模型一樣。所以這是怎麼回事？

理解這個定理的關鍵是理解定理中的假設。這個定理中的假設並不是機器學習研究中常用的那個「數據來自某個給定分布中的獨立同分布」假設，恰恰相反，Wolpert 假設數據是一個有限集，而且訓練和測試是獨立的、各自對應不同分布的數據。這個假設並非沒有合理之處，在實際中我們的數據總是有限的，而且我們希望看看模型在此前從未見過的新數據上表現如何。這樣的假設讓 Wolpert 能夠考慮到所有可能的數據集的情況。那麼，這個定理就是闡述在這個假設下、在所有可能的數據集上對比兩個演算法的表現。

雖然這個假設對於機器學習研究來說有一些合理之處，但其實問題也不小：

• 假設中說測試數據和訓練數據是統計不同的，也就是說測試數據和訓練數據根本沒什麼關係

• 數據標籤和數據特徵也沒有什麼關係（因為在考慮所有可能的標籤的平均情況）。

說成這樣以後，我們就能看出來這些假設對於任何預測建模都算不上有利。

那麼現在我們可以嘗試總結一下，或者重新表述一下 Wolpert 的「沒有免費的午餐定理」到底想要說什麼。單獨看結論得到的「每個模型在預測成員較少的那個分類時都有同樣的表現」可以理解為說「學習是不可能的」。再組合上我們對於他的假設的理解的話，就成了「如果訓練數據集和測試數據集沒有什麼關係，而且特徵和標籤之間也沒有什麼關係，那麼學習就是不可能的」。這聽起來簡直自然而然，不過也就和平時大家談論的「沒有免費的午餐定理」的內容大相徑庭。

也有一種對這個定理的解讀是「為了讓學習變得可能，你需要做出一些假設」。只不過，在這篇論文里 Wolpert 做出的假設恰恰是「訓練數據集和測試數據集沒有什麼關係，而且特徵和標籤之間也沒有什麼關係」，這樣一來學習反而變得不可能了。所以，如果你想要說明的觀點是「學習需要假設」的話，那你就不應該引用這一篇論文。

我對 Wolpert 的「沒有免費的午餐定理」的解讀

在我看來，這篇論文最大的意義是挑戰了獨立同分布假設。Wolpert 用很好的理由說明了為什麼他認為這個假設不怎麼妥當，以及為什麼機器學習理論需要探索其它的理論框架。尤其是，如果數據集容量是有限的，他就提出了一個確實值得考慮的情況。在這種情況下，獨立同分布假設會允許一個點同時出現在訓練集和測試集中，顯然這也就沒辦法討論泛化性了。那麼 Wolpert 提出訓練集和測試集沒有什麼聯繫，也就是合理的。

不過，他提出訓練集和測試集（以及標籤）是相互完全獨立的，這事還是有點奇怪的。我不確定他是否真的認為這是一個好的思考機器學習問題的框架。我猜測他提出這個的動機是希望整個領域重新考慮獨立同分布假設是否合理，並且嘗試尋找能夠更好地反映機器學習實踐的假設。如今許多年後回頭來看，我覺得很可惜，沒有更多的研究者沿著他的思路做更多的討論，而且他提出的定理也顯然被大批機器學習實踐者誤讀了。

在文章開頭我提到過還有另一個「沒有免費的午餐定理」。和 Wolpert 非常不同的是，它評價模型的時候使用了獨立同分布假設；在其它方面則有相似之處，在沒有其它額外假設的前提下，如果你只能看到一部分數據，那麼其餘的數據的標籤仍然是具有任意的可能的。所以，具體地來說，這個由 Shalev-Shwarz 和 Ben-David 提出的「沒有免費的午餐定理」的內容是，「對於任意一個指定的預測演算法，都會有它表現很糟糕的數據集，也就是說在這個數據集上別的學習者會有更好的表現」。不過這沒法阻擋有人提出「演算法 A 永遠都比演算法 B」好之類的說法，因為真正表現更好的那個演算法是無法實現的（它應當是那個無需查看數據就總能生成完全正確答案的演算法）。在這個思考框架里可以很輕鬆地證明，在一個不平衡的數據集中，預測出現頻率較高的類比預測頻率較低的類要更容易；而這個結論是無法在 Wolpert 的框架中得到的。

我覺得，不論你想要說明的結論是什麼，幾乎都不會需要引用 Wolpert 的論文。如果你想說明的是「有適當的假設就可以進行學習」，那你大概可以引用 Shalev-Shwarz 和 Ben-David 的那一整章的內容，我也不確定有沒有更正式的方法來引用。如果你非常想的話，你也可以引用 Wolpert，但我覺得這帶來的困惑要比幫助多多了。而如果你想說的是「對於有限數據來說，獨立同分布的假設也太奇怪了」，那你就一定要引用 Wolpert！

最後，如果你想要說的是「梯度提升不可能永遠比神經網路強，因為有沒有免費的午餐定理」，那在我看來你搞錯了，沒有任何證據可以支持這樣的陳述。我其實也不覺得在常用的機器學習演算法之間有任何的「總是更好」或者「總是更糟糕」的優劣關係，但我同時也沒聽說過有任何的機器學習理論能禁止這樣的事情發生（只要是在「學習是可行的」框架下討論）。

如果你對機器學習理論感興趣，Shalev-Shwarz 和 Ben-David 的那本書其實很棒。除此之外我還很喜歡 Mehryar Mohri, Afshin Rostamizadeh 和 Ameet Talwalkar 合著的《Foundations of Machine Learning》（https://cs.nyu.edu/~mohri/mlbook/）。我自己並不是一個做理論研究的人，但我覺得有一些理論基礎能在思考演算法的時候有一些好的思想框架。你想讀一讀 Wolpert 的那篇論文也不錯，雖然我覺得你的最大收穫會是了解他為什麼不喜歡獨立同分布假設，實際上論文中更多地是對機器學習理論的哲學的思考，而不是一般的機器學習理論討論。

via https://peekaboo-vision.blogspot.com/2019/07/dont-cite-no-free-lunch-theorem.html，雷鋒網 AI 科技評論編譯

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！