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