應該如何理解No Free Lunch Theorems for Optimization?

01-07

http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf
No free lunch in search and optimization

我聽來的故事是這樣的：（好幾個學者都是這麼說的）

有一段時間大家很喜歡做優化演算法的研究，灌了不少水。一般一個領域灌水是難免的，但是很多「外行」灌得過分了。比如，通過三個算例說明自己改進的演算法適用於多麼普適的問題集之類的論斷云云。後來如題主所見，David和William就啪啪啪打了眾人的臉。他們要說的是一件很簡單的事情：如果一個演算法對於某個類型的問題比另外的演算法效率高，那麼它一定不具有普適性（即一定存在另外一類問題使得這個演算法的效率低於隨機搜索）。

另外一篇文章比較好讀一些。Simple Explanation of the No-Free-Lunch Theorem and Its Applications, C. Y. Ho D. L. Pepine, Dec. 2002

過去，大家熱衷於研究更高效的優化方法。NFL卻告訴我們，沒有哪個演算法比其他演算法高效。但這並不是說這些研究沒有意義，因為在實際應用中，有些演算法就是明顯比另一些高效，這並不是錯覺。因為NFL的前提是考慮所有可能的目標函數，而實際生活中只會遇到其中極少一部分，這裡面是有free lunch的。

所以要說它的意義的話，不是說研究優化演算法沒有意義，而是提醒我們要轉換思路，從針對的問題集合（或者分布）出發去設計和改進演算法，而不是拍腦袋。

周志華老師的新書《機器學習》中，第一章1.4小節正好有一個完整的說明。從簡單的理論性證明、例子到解釋。因為第一章是樣章，網上恰巧可以找到這段內容。

http://www.tup.tsinghua.edu.cn/upload/books/yz/064027-01.pdf

我把最後的總結段落轉述過來：

NFL定理最重要的寓意，是讓我們清楚地認識到，脫離具體問題，空泛地談論」什麼學習演算法更好「毫無意義，因為若考慮所有潛在的問題，則所有的演算法一樣好. 要談論演算法的相對優劣，必須要針對具體問題；在某些問題上表現好的學習演算法，在另一問題上卻可能不盡如人意，學習演算法自身的歸納偏好與問題是否相配，往往會起到決定性作用.

以前寫論文的時候，如果一個演算法在一類問題上好用，其他問題上不好用，我會引用這篇文章。

所以，這文章最大的作用就是背黑鍋。

其實我壓根沒看懂過這篇文章，只知道是幾個物理的人寫的，公式推了一大堆。

這篇文章說白了就是世界上沒有全無敵的優化方法。

說明假如不知道用什麼演算法，就用猴子演算法，這樣起碼是所有演算法的平均水平