0
雷鋒網(wǎng) AI 科技評論按：「沒有免費的午餐定理」一度是機器學習界最常被談起的定理之一（真正長期被談起的自然是「更多的數(shù)據(jù)等于更好的表現(xiàn)」）。不過機器學習科學家 Andreas Mueller 最近撰文表示大家都引用錯定理了，其實事情比這更復(fù)雜，也有更深遠的啟示。
Andreas Mueller 是哥倫比亞大學數(shù)據(jù)科學研究院的助理研究科學家，也是《Introduction to machine learning with Python》一書的作者；他還是 scikit-learn 機器學習庫的核心開發(fā)者之一。
雷鋒網(wǎng) AI 科技評論把他的這篇博客全文編譯如下。
首先一句話概括我這篇文章要說什么：大家以后盡量不要再引用 Wolpert 的「沒有免費的午餐定理」了。如果你已經(jīng)在哪里引用過，那你很有可能用它支持了錯誤的結(jié)論。他的句話實際上想表達的是「你不可能在沒有假設(shè)的情況下從數(shù)據(jù)中學習」。
提出「沒有免費的午餐定理」這個概念的，實際上是 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）這篇論文。機器學習領(lǐng)域里有不少論文，它們經(jīng)常被引用，但是沒什么人認真讀過論文內(nèi)容；這篇論文就是其中之一。大多數(shù)機器學習領(lǐng)域內(nèi)的人提起這篇論文的時候都是想要說明「某個模型不可能在每個方面都是最好的」，或者「某個模型不會在每個方面都比另一個模型強」。但實際上這并不是 Wolpert 的這篇論文、這個定理真正想要表達的內(nèi)容，所以大家未來不應(yīng)該這樣引用這個定理，我會在下文里仔細說明這件事；以及，即便單獨考慮大眾想要說明的「某個模型不可能在每個方面都是最好的」，其實這個結(jié)論也是有問題的。
首先，據(jù)我所知至少有兩個定理都叫做「沒有免費的午餐」（no free lunch）。一個是 Wolpert 提出的，首次在《The Lack of A Priori Distinctions Between Learning Algorithms》論文里出現(xiàn)；另一個是 Shalev-Shwarz 和 Ben-David 提出的，在《Understanding Machine Learning》這本書里（這本書很棒，http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/）。Wolpert 還發(fā)表過一篇《No Free Lunch in Optimization》，不過我們只關(guān)注談監(jiān)督學習的那個定理就好了。
《Understanding Machine Learning》里提出的那個定理和 Wolpert 的很不一樣，我的理解是， Shalev-Shwarz 和 Ben-David 兩人提出這個定理就是為了給「沒有免費的午餐」提出與 Wolpert 不同的、新的詮釋，而其實他們的定理內(nèi)容是「某個模型不可能在每個方面都是最好的」，不過他們的表達方式非常具體。某種程度上說，他們描述這個定理的方式要比我們從現(xiàn)在的字面上所能感受到的要清晰明確得多。但我不太贊同他們用一個已有的名字來命名這個定理的做法。
Wolpert 最早的那篇論文的主要內(nèi)容可以總結(jié)為「在這個定理的假設(shè)之下，任何兩個預(yù)測函數(shù)的泛化能力都是相同的」。這里有兩個關(guān)鍵部分：假設(shè)和結(jié)論。
只看結(jié)論「任何兩個預(yù)測函數(shù)的泛化能力都是相同的」的話，經(jīng)常會有人理解為類似「梯度提升不會總是最好的」這樣。但實際上它想說的是「梯度提升幾乎每次都能找到出現(xiàn)頻率最高的類」或者「神經(jīng)網(wǎng)絡(luò)幾乎每次都能預(yù)測到出現(xiàn)頻率最低的類」。顯然這和我們的機器學習實踐經(jīng)驗是沖突的。但根據(jù)這個定理的說法，在泛化性質(zhì)方面它就和你能找到的最好的模型一樣。所以這是怎么回事？
理解這個定理的關(guān)鍵是理解定理中的假設(shè)。這個定理中的假設(shè)并不是機器學習研究中常用的那個「數(shù)據(jù)來自某個給定分布中的獨立同分布」假設(shè)，恰恰相反，Wolpert 假設(shè)數(shù)據(jù)是一個有限集，而且訓練和測試是獨立的、各自對應(yīng)不同分布的數(shù)據(jù)。這個假設(shè)并非沒有合理之處，在實際中我們的數(shù)據(jù)總是有限的，而且我們希望看看模型在此前從未見過的新數(shù)據(jù)上表現(xiàn)如何。這樣的假設(shè)讓 Wolpert 能夠考慮到所有可能的數(shù)據(jù)集的情況。那么，這個定理就是闡述在這個假設(shè)下、在所有可能的數(shù)據(jù)集上對比兩個算法的表現(xiàn)。
雖然這個假設(shè)對于機器學習研究來說有一些合理之處，但其實問題也不小：
假設(shè)中說測試數(shù)據(jù)和訓練數(shù)據(jù)是統(tǒng)計不同的，也就是說測試數(shù)據(jù)和訓練數(shù)據(jù)根本沒什么關(guān)系
數(shù)據(jù)標簽和數(shù)據(jù)特征也沒有什么關(guān)系（因為在考慮所有可能的標簽的平均情況）。
說成這樣以后，我們就能看出來這些假設(shè)對于任何預(yù)測建模都算不上有利。
那么現(xiàn)在我們可以嘗試總結(jié)一下，或者重新表述一下 Wolpert 的「沒有免費的午餐定理」到底想要說什么。單獨看結(jié)論得到的「每個模型在預(yù)測成員較少的那個分類時都有同樣的表現(xiàn)」可以理解為說「學習是不可能的」。再組合上我們對于他的假設(shè)的理解的話，就成了「如果訓練數(shù)據(jù)集和測試數(shù)據(jù)集沒有什么關(guān)系，而且特征和標簽之間也沒有什么關(guān)系，那么學習就是不可能的」。這聽起來簡直自然而然，不過也就和平時大家談?wù)摰摹笡]有免費的午餐定理」的內(nèi)容大相徑庭。
也有一種對這個定理的解讀是「為了讓學習變得可能，你需要做出一些假設(shè)」。只不過，在這篇論文里 Wolpert 做出的假設(shè)恰恰是「訓練數(shù)據(jù)集和測試數(shù)據(jù)集沒有什么關(guān)系，而且特征和標簽之間也沒有什么關(guān)系」，這樣一來學習反而變得不可能了。所以，如果你想要說明的觀點是「學習需要假設(shè)」的話，那你就不應(yīng)該引用這一篇論文。
在我看來，這篇論文最大的意義是挑戰(zhàn)了獨立同分布假設(shè)。Wolpert 用很好的理由說明了為什么他認為這個假設(shè)不怎么妥當，以及為什么機器學習理論需要探索其它的理論框架。尤其是，如果數(shù)據(jù)集容量是有限的，他就提出了一個確實值得考慮的情況。在這種情況下，獨立同分布假設(shè)會允許一個點同時出現(xiàn)在訓練集和測試集中，顯然這也就沒辦法討論泛化性了。那么 Wolpert 提出訓練集和測試集沒有什么聯(lián)系，也就是合理的。
不過，他提出訓練集和測試集（以及標簽）是相互完全獨立的，這事還是有點奇怪的。我不確定他是否真的認為這是一個好的思考機器學習問題的框架。我猜測他提出這個的動機是希望整個領(lǐng)域重新考慮獨立同分布假設(shè)是否合理，并且嘗試尋找能夠更好地反映機器學習實踐的假設(shè)。如今許多年后回頭來看，我覺得很可惜，沒有更多的研究者沿著他的思路做更多的討論，而且他提出的定理也顯然被大批機器學習實踐者誤讀了。
在文章開頭我提到過還有另一個「沒有免費的午餐定理」。和 Wolpert 非常不同的是，它評價模型的時候使用了獨立同分布假設(shè)；在其它方面則有相似之處，在沒有其它額外假設(shè)的前提下，如果你只能看到一部分數(shù)據(jù)，那么其余的數(shù)據(jù)的標簽仍然是具有任意的可能的。所以，具體地來說，這個由 Shalev-Shwarz 和 Ben-David 提出的「沒有免費的午餐定理」的內(nèi)容是，「對于任意一個指定的預(yù)測算法，都會有它表現(xiàn)很糟糕的數(shù)據(jù)集，也就是說在這個數(shù)據(jù)集上別的學習者會有更好的表現(xiàn)」。不過這沒法阻擋有人提出「算法 A 永遠都比算法 B」好之類的說法，因為真正表現(xiàn)更好的那個算法是無法實現(xiàn)的（它應(yīng)當是那個無需查看數(shù)據(jù)就總能生成完全正確答案的算法）。在這個思考框架里可以很輕松地證明，在一個不平衡的數(shù)據(jù)集中，預(yù)測出現(xiàn)頻率較高的類比預(yù)測頻率較低的類要更容易；而這個結(jié)論是無法在 Wolpert 的框架中得到的。
我覺得，不論你想要說明的結(jié)論是什么，幾乎都不會需要引用 Wolpert 的論文。如果你想說明的是「有適當?shù)募僭O(shè)就可以進行學習」，那你大概可以引用 Shalev-Shwarz 和 Ben-David 的那一整章的內(nèi)容，我也不確定有沒有更正式的方法來引用。如果你非常想的話，你也可以引用 Wolpert，但我覺得這帶來的困惑要比幫助多多了。而如果你想說的是「對于有限數(shù)據(jù)來說，獨立同分布的假設(shè)也太奇怪了」，那你就一定要引用 Wolpert！
最后，如果你想要說的是「梯度提升不可能永遠比神經(jīng)網(wǎng)絡(luò)強，因為有沒有免費的午餐定理」，那在我看來你搞錯了，沒有任何證據(jù)可以支持這樣的陳述。我其實也不覺得在常用的機器學習算法之間有任何的「總是更好」或者「總是更糟糕」的優(yōu)劣關(guān)系，但我同時也沒聽說過有任何的機器學習理論能禁止這樣的事情發(fā)生（只要是在「學習是可行的」框架下討論）。
如果你對機器學習理論感興趣，Shalev-Shwarz 和 Ben-David 的那本書其實很棒。除此之外我還很喜歡 Mehryar Mohri, Afshin Rostamizadeh 和 Ameet Talwalkar 合著的《Foundations of Machine Learning》（https://cs.nyu.edu/~mohri/mlbook/）。我自己并不是一個做理論研究的人，但我覺得有一些理論基礎(chǔ)能在思考算法的時候有一些好的思想框架。你想讀一讀 Wolpert 的那篇論文也不錯，雖然我覺得你的最大收獲會是了解他為什么不喜歡獨立同分布假設(shè)，實際上論文中更多地是對機器學習理論的哲學的思考，而不是一般的機器學習理論討論。
via https://peekaboo-vision.blogspot.com/2019/07/dont-cite-no-free-lunch-theorem.html，雷鋒網(wǎng) AI 科技評論編譯
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
