cctg: NFL(No Free Lunch Theorems) 沒有免費的午餐定理

2019/7/29

NFL(No Free Lunch Theorems) 沒有免費的午餐定理

在認識或瞭解 machine learing 或 AI 的概念後，通常會想到，如果能有一個可以處理所有問題的 AI，那麼就可以解決所有問題，那就能省去大量人力，大家都不用工作了。這是一個尋找 AI 的通用演算法的問題，只要能有一個超強的演算法，那就能很快地製造出符合不同需求的 AI 機器人。

但是在尋找這個演算法以前，我們要先知道，已經有人用了數學的方法，證明了並不存在一個能一統天下的 AI 演算法模型，這就是 NFL(No Free Lunch Theorems) 沒有免費的午餐定理。

NFL 定理 www.no-free-lunch.org 有兩個，一個是 No Free Lunch for Supervised Machine Learning (WOLPERT, David H., 1996. The lack of a priori distinctions between learning algorithms. Neural Computation, 8(7), 1341–1390.)，一個是 No Free Lunch for Search/Optimization (WOLPERT, David H., and William G. MACREADY, 1997. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82.)。

實際上在了解到這個定理的概念後，我們要知道，在不考慮具體問題的情況下，沒有任何一個算法比另一個算法更優，甚至直接胡亂猜測還會更好。我們無法去討論哪一個演算法比較好，但如果針對某個具體的特定的問題，確實可找到表現比較好的機器學習演算法，但這個演算法，卻無法解決其他的問題。換句話說，不同的問題，就可以找到最適當的演算法，而每個演算法，都有各自適用的問題。

也可以說如果我們對要解決的問題一無所知，且並假設其分佈完全隨機且平等，那麼任何演算法的預期性能都是相似的。在某個領域、特定假設下表現卓越的演算法，不一定在另一個領域也能是最厲害的。正因如此，我們才需要研究和發明更多的機器學習算法來處理不同的假設和數據，也就是處理不同的問題。

華爾街漫步是一本投資指南，其中廣為人知的「隨機漫步理論」研究，也就是說一隻矇著眼睛的猴子，對著眾多股票隨意擲飛鏢，所挑選出來的投資組合，也會跟專家挑的組合一樣好，猴子隨機選股大勝專業經理人。就像是 NFL 有著類似的概念，特定的演算法就像是經理人選擇的股票一樣，沒有任何演算法/選股組合可以證明，他的選股策略比較厲害。

NFL for Machine Learning 有兩條規則

沒有一個機器學習演算法，在所有可能的函數中，能夠比隨機猜測的結果更好。
每個機器學習演算法都必須包含一些數據之外的知識或者假設，才能夠將數據一般化。

要用什麼策略選擇一個適當的演算法？

想像一個由 n 個 solution(算法) 與 m 個 problem 構成的矩陣，每一個格子的值表示問題被解決的程度。

Restarting

重複運算相同的演算法，會產生不同的結果，得到多個 solution，然後分析某個演算法，看看是否為相對較優良的演算法。這種方式特別適合用於初始 & 過程隨機化的算法，因為這些演算法每次執行都會得到不完全一樣的結果。
Ordinal Optimization + Softend Goals

因為計算 n x m 矩陣實際上每個格子裡面的「值」，可能是很複雜的向量/矩陣等需要耗費大量資源來處理。為了簡化計算的負擔， Ordinal Optimization 只考慮 A 算法是否比 B 算法好，而不管兩者之間的差距有多大。

Softened Goals 則是常見的取捨法則：放棄追求「最最最好」的解法，轉而追求「足夠好」的方式。
Ensemble Learning

透過多個演算法彼此獨立工作，最終以類似「投票」、「比稿」的方式來決定最終預測的結果值。