No Free Lunch on Machine Learning

No Free Lunch (NFL)，中文是，天下沒有白吃的午餐。數學上，它是一個定理：

「由於對所有可能函數的相互補償，最優化算法的性能是等價的。其含義是說沒有其他任何算法能夠比搜索空間的線性列舉或者純隨機搜索算法更優。」 (原文網址：https://kknews.cc/zh-tw/tech/xnp5p9.html)

NFL定理，在Machine Learning上的解釋為： (原文網址：https://kknews.cc/zh-tw/tech/xnp5p9.html

1. 沒有學習器能夠比在所有可能的函數中比隨機猜測的結果更優。
2. 也就是說每個學習器都必須包含一些數據之外的知識或者假設，才能夠將數據泛化。

我拿台大的Machine Learning Foundations (MLF) 線上課程裡的一個例子來解釋NFL。

下圖截取自課程裡的一節，Feasibility of Learning - Learning is Impossible，但我改了一下圖

上面是一個Training Samples，用符號D (Data) 表示。我們想透過ML (Machine Learning)的方法，找出一個規則。該規則g，可以推測剩下3個x值 {101, 110, 111} 所對應的y是多少。

我簡單畫一下ML的流程：

D: Data, Training Samples

H: Hypothesis Set

A: Algorithm

f: Unknown Target Function

g: Final Hypothesis

當然，MLF教材裡，有更漂亮的圖表達ML的流程。自己手繪的目的，只是為了理解並加深印象而已。ML的流程，在這就不多說了，請諸位自行去翻MLF教材。

這裡，主要是想借用ML的流程，解釋我們一開始的問題。

首先，我們知道，f是永遠未知的。對於這個問題而言，該f有幾種可能？

2^8 = 256

我們經由ML所得到的g，一定是在這256個f裡面的其中一個。

其實我們再深入思考，還可以發現，其實我們只要從8個裡面挑選一個就好了，為何？因為Training Samples的y已經縮減了f的可能性，如下圖：

ML在推導g的時候，除了需要D，還需要Hypothesis Set，H。假設我們想到兩個Hypothesis，h1和h2。

H = { h1, h2}

h1 = 若 x 只有1個bit為1，則y為X，否則為O

h2 = 對於前5筆x，遵循h1的規則，剩下3筆，就用猜的。

所以現在，經由ML，我們得到了g。接下來，就可以用g來推測剩下的3個x所對應的y為多少。

若g = h1：

y = g (101) = O

y = g (110) = O

y = g (111) = O 

這樣的推論，是否正確？其實無法知道。

就像買賣股票一樣，根據過往的經驗，我們覺得h1不錯，想用它做為g，來預測未來股票的漲跌，可是卻發現預測錯誤。如果真的用h1來判斷股票的買賣，可能就會虧錢。因為大家應該有玩股票的經驗，所以拿股票做為例子，大家比較能夠理解。

總而言之，f是未知的。就像股市所隱含神秘的規則，可能永遠不知道一樣。那麼，回到這個例子而言，我們用h1做為g來推測剩下3個x成功的機率是多少？符號表達這段話如下：

P [g(x) == f(x)] = 1/8

g (x) = h1 (x)

x is {101, 110, 111}

若g = h2：

現在用h2做為g來推測剩下3個x成功的機率是多少？

P [g(x) == f(x)] = 1/8

g (x) = h2 (x)

x is {101, 110, 111}

我們發現，不管是用h1和h2，機率都一樣。這代表什麼意思？這就是，我們花了一個月的時間，研究出自以為非常優秀的演算法A，所找到的非常好的假設h1，用它預測剩下3個x的準確率，與直接用h2亂猜的準確率，是一樣的。

這解釋了NLF on Machine Learning的第1條：「沒有學習器能夠比在所有可能的函數中比隨機猜測的結果更優」。

至於第2條：「也就是說每個學習器都必須包含一些數據之外的知識或者假設，才能夠將數據泛化」，該解釋，待另一篇說明之。

-Count

這封郵件來自 Evernote。Evernote 是您專屬的工作空間，免費下載 Evernote