機器學習裡不存在的免費午餐:No Free Lunch Theorems

不久之前參加了國內資料科學 / AI 的年度盛事,一方面有感於機器學習領域近年的飛速發展,另一方面覺得衍生的誤解與迷思幾乎也用同樣的速度在擴散,連 Facebook 的 AI 大神 Yann LeCun 在接受訪談的時候都明白表示希望大家不要再用魔鬼終結者的形象來解釋 AI ,因為這種印象完全是錯誤的。

無獨有偶地,一位業務經理人跟我說了好幾次,他覺得機器人馬上就要統一天下了云云,我好奇問他為什麼這麼覺得,對方回答,看看 AlphaGo 在圍棋領域的主宰力,如果把同樣的演算法拿來做別的事情,那人類有什麼希望呢?

啊哈!一個典型的模型「泛化」問題。

這位業務經理人的想法聽起來似乎很有道理:一個訓練到極致,聰明又複雜的演算法,可以用來解決各式各樣的問題,這正是多年前 AI /機器學習專家們開啟這個領域時的終極夢想,只要能找到最強最好的泛化演算法,就能夠輕易而大量地製造出各種人工智慧的應用。

有些幸運而又不幸運的是(取決於你站在誰的角度),數學定理早已證明最佳最好的泛用模型並不存在。這個對某些人而言有點討人厭的定理,也是本文的主題,有一點冷門,被稱為「沒有免費的午餐定理( No Free Lunch Theorems)」。

沒有免費的午餐定理 ( NFL, No Free Lunch Theorems ),這是什麼鬼東西?

NFL 定理跟美式足球聯盟搭不上邊,也不是真的跟午餐有關,它是 Wolpert & Macready 1997 年收錄在 IEEE 的一篇推導研究中「證明」的數學定理,至今累積近 6000 次引用。

數學「定理」不同於「理論」,只要條件滿足的情況下無論何時皆成立。而 NFL 所要描述的內容其實很簡單:「假如有一個黑盒子演算法能在特定的問題上表現優於其他演算法,則必定存在其他問題類型使得該演算法的表現差於其他演算法,在考慮各式各樣問題並重複多次之後最終沒有任何演算法的表現超越其他人」。

這條定理與因為名著《華爾街漫步》而廣為人知的「猴子隨機選股大勝專業經理人」研究在某個角度的意味相似,特定的演算法就像是經理人選擇的股票一樣,在大量試驗的平均結果之前人人平等,沒有任何演算法/選股組合可證明總是比較優越。

沒有免費午餐定理的基本數學形式, NFL Theorem #1 為:

No-Free-Lunch_Theorems_1

其中 a1, a2 分別代表不同的演算法,在考慮不同的成本函數 f 以及輸入樣本點 m 下產生 y 值的機率,最終以加總型式來通算演算法的整體績效。 NFL 的推導過程頗為複雜,但我們即使以不懂數學的角度來看也很快就能發現上述的式子中唯一個不同即是 a1 & a2 ,表示更換演算法對於最終的整體效能並無差別。

有些人可能腦筋轉得快,現代有很多演算法是進化型( Evolutionary )的算法,同一算法在不同的時間點對於結果值 y 會有不同的表現機率,使得上述的公式可能不滿足。Wolpert & Macready 考慮到這一點,也推導了時間相依的模型,結果定理仍然有效,它的變形版本, NFL Theorem #2 的數學形式如下,加入了時間相依因素 T:

No-Free-Lunch_Theorems_2

除此之外,兩位學者在論文中詳細的討論了各種情況,針對所有「答案」與「解法」集合空間為有限的問題, NFL 一律成立,而電腦演算法因為先天機器編碼組合的空間雖然很大但其實是有限數,因此全部都會符合 NFL 的描述。

再一次,猴子獲勝!如果以泛化模型為目標,閉著眼睛選一個演算法就可以了,換一個算法並不會有不同的結果。

NFL 的真正啟示

NFL 的存在,是否說明了機器學習或者深度學習沒有任何意義呢?當然不是這樣。

實務上在考慮「給定」的一個問題時,我們總是能夠找到一組最佳的演算法作為回應,例如在電腦圍棋領域的 AlphaGo。 NFL 的意義在於,如果我們在毫無所知的情況下把一個「表現優良」的演算法直接套用到其他問題時,不但不保證優良表現會延續,相反地極大可能比起閉起眼睛隨便挑一個還要差(因為給定一個演算法其泛化整體表現不可能大於平均值)!

也就是說,雖然 AlphaGo 的強大史無前例,但即使不考慮任何技術性細節,直接把超能演算法組合套用在其它問題的計算,也不太可能常常獲得所謂的「免費午餐」。

催生 NFL 理論的時代背景與今天有幾分相似:雨後春筍般湧現、號稱更加優秀的新算法與社會熱潮使得技術的本質遭到扭曲。

NFL 真正帶給我們的啟發是:盲目追求最佳演算法是沒有意義的,但是透過合理使用領域 & 專家知識在特定的議題上,我們將能得到超越(甚至大幅超越)隨機演算法平均的結果。

NFL 衍生討論裡面一個很重要的議題是在於 Priori 先驗資訊的角色(兩位作者都是貝氏統計專家),說的白話一點,實務上沒有人是真的閉著眼睛選擇演算法,而我們如何選擇什麼模型來對應什麼問題,這些知識和過程的火候就是「打敗隨機猴子」的主要方式。

而這個正好是快速發展的機器學習領域逐漸浮現的一大隱憂:越來越多號稱機器學習/深度學習/統計分析的專家與技術人員,並沒有充分理解手上使用的工具和方法真正在做的事情,而且對於這個一知半解的現狀感到過於安心,因此也就不可能有系統性的選擇正確的模型應用,以便在大多數時候擊敗那隻「看不見的猴子」。

R bloggers 網站兩年前刊出的一篇實作文章剛好可以呼應這裡說的問題,裡面用了便宜的 k-means 算法為對象說明了沒有足夠專家知識的 black-box 算法會產生的問題,有興趣的讀者可以研究一下。

如何買到「便宜的午餐」?

NFL 雖然乍看是一盆大冷水,還是有一些方法能夠幫助行業專家挑選合適的解決方案。為了方便底下的討論,請先想像一個由 n 個 solution(算法) 與 m 個 problem 構成的矩陣,每一個格子的值表示問題被解決的程度。

第一種購買「便宜午餐」的方式稱為「Restarting」,利用重複運算相同的演算法產生不同的結果,來擬似執行了多種 solution 的情況,並且從中分析給定的演算法  j ,是否有機會成為相對優良的泛化方案。

這種方式特別適合用於初始 & 過程隨機化的算法,因為這些算法每次運行都會得到不完全一樣的結果,因此可以被利用來突破 NFL 。

下方示意圖的 Scenario #1 中的紅色圈選區域表示正常情況下單一演算法對應每個問題的值,因為 NFL 的存在,想當然耳紅色區域中的數值會有高高低低。

當我們使用 Restarting 並同時考量所有結果數值時,命中的區域就隨之擴大成 Scenario #2 中的紅色區塊;對於一個 n-fold 的設計來說就能簡單取得 n 倍的空間。

No-Free-Lunch_Theorems_3_Restarting

接著要介紹的第二種方案,實際是兩種概念的組合:Ordinal Optimization 加上 Softened Goals。

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

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

當合併上面兩個概念之後,將能觀察到底下示意圖 Scenario #3 & #4 的空間改變,找到好解法(橘色區塊)的成本下降,同時機率上升:

No-Free-Lunch_Theorems_4_Order Optimization & Softened Goals

第三種途徑,則是現在廣泛被實作的 Ensemble Learning,這種技術的核心理念是透過多個演算法彼此獨立工作,最終以類似「投票」、「比稿」的方式來決定最終預測的結果值。

這種方法很像職業運動裡面組明星隊,問題也顯而易見:超級巨星組一隊就會拿冠軍嗎?答案是不一定,而判斷的標準還是回到前面說的,操作的專家對於模型的原理以及不同模型之間的關係有沒有足夠的理解。

「沒有免費午餐理論」的其他有趣議題

NFL 雖然論文發表較早,論文討論的內容卻還是頗能跟得上流行,對於以機器學習為基礎的資安攻防也給出了很正確的預言,那就是防禦成本將遠遠大於攻擊成本。

我們以一個簡單的防禦者 A / 攻擊者 B 對抗情境為例,將預期結果列出,就得到一個簡易的兩人賽局報償矩陣:

No-Free-Lunch_Theorems_5.1_Payoff Game

先看 Scenario #5 ,在原本的 NFL 中,我們要對抗的是各種問題,可以視之為攻擊者 B 集合 ,而人類專家所能得出的算法集合為防禦者 A 。在左邊的報償矩陣中可以發現,因為對於待解決的問題而言沒有是非好壞之分,因此人類專家(防禦者 A )只需考慮對自身有利的策略,不需分析對手的情況,因而有較多的機會可以取得理想的結果(紫色區塊)。

但在現代的資安攻防中, 例如 Scenario #6 ,代表攻擊者 B 的駭客就沒有這麼好心了,對駭客而言較好的策略是「以較強的手段攻擊對方較弱的地方」,而對於防禦者 A 而言,只有「以較強的防禦抵禦對手較弱的攻擊」才是比較有保障的策略,要找出好策略必須同時考量自己與對方的選擇,再加上實務中並不是所有的問題(資安風險)都能有實裝的防護措施,於是可被歸類為有效防禦的區域就相對小了。

對於防禦者而言,因為沒有「一勞永逸」的機器學習算法可以總是成功防禦所有的攻擊,因此需要準備許多不同的措施來因應;但是從攻擊者的角度來看,只要有單一算法能突破任一防禦者的防護,就算是成功了。這個理論性的描述在今天的資安攻防中基本上是對的。

另外一個有趣的想法則是, NFL 概念如果幾何化會是什麼樣子?

以一個三維空間為例:

No-Free-Lunch_Theorems_6_Geometric Example of NFL

 

其中延伸出去的 L 向量代表合適的「先驗」知識下選擇的算法結果,而 P 向量則是最佳化問題的本體。

你注意到 L/P 向量原點附近的圓錐體嗎?以相同原點為基準, NFL 所描述的多個隨機演算法將落於圓錐體的範圍之內。而如何決定一個固定的向量(算法)是否為最佳的數學做法,即是計算兩向量之間的內積,並找出內積最大者。

看得完你真是太厲害了,再挑戰一下吧?

(Visited 53 times, 44 visits today)

Wendell.Huang

科技公司嫌棄太活潑,消費品牌挑剔太沉悶…, 經常必須解釋自己在學什麼, 不小心就摔破對方眼鏡的業餘書呆子。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *