機器學(xué)習(xí)相關(guān)介紹:沒有免費午餐定理

一、沒有免費午餐定理

1995年，D.H.Wolpert等人提出沒有免費午餐定理（No Free Lunch Theorem）。該定理具體描述為：任何一個預(yù)測函數(shù)，如果在一些訓(xùn)練樣本上表現(xiàn)好，那么必然在另一些訓(xùn)練樣本上表現(xiàn)不好，如果不對數(shù)據(jù)在特征空間的先驗分布有一定假設(shè)，那么表現(xiàn)好與表現(xiàn)不好的情況一樣多。因此，沒有一個機器學(xué)習(xí)算法在任何情況下表現(xiàn)均優(yōu)。

二、未假設(shè)先驗分布的預(yù)測

假設(shè)一臺計算機只有兩個存儲單元，并假設(shè)計算機的存儲單元不是屬于第一類就是屬于第二類。當已知一個存儲單元屬于第一類，預(yù)測另一個存儲單元的類別。該預(yù)測問題可能包含兩種情況：

（1）第一個和第二個存儲單元均屬于第一類。

（2）第一個存儲單元屬于第一類，第二個存儲單元屬于第二類。

若沒有假設(shè)兩種情況的先驗概率分布（即默認兩種情況先驗概率相同），則兩種情況出現(xiàn)的概率相同。此時，無論預(yù)測第二個存儲單元屬于哪種類別，正確或錯誤預(yù)測的概率均為50%。

當假設(shè)計算機的存儲單元為三個或三個以上時，正確或錯誤預(yù)測每個存儲單元的概率均為50%（如圖一所示，圖一中圓圈代表第一類，叉代表第二類）。

圖一，圖片來源：中國慕課大學(xué)《機器學(xué)習(xí)概論》 因此，即使增加已知存儲單元類別的個數(shù)，正確或錯誤預(yù)測每個未知存儲單元的概率也為50%。

圖片來源：中國慕課大學(xué)《機器學(xué)習(xí)概論》 綜上，可得到推論：無論計算機的存儲單元有多少，無論已知多少個類別信息，如果默認各種情況先驗概率相同，正確預(yù)測的概率均為50%。即默認各種情況先驗概率相同的情況下，所有的機器學(xué)習(xí)算法與隨機猜測的結(jié)果相同。 三、假設(shè)先驗分布的預(yù)測 如圖二所示，如果預(yù)測圖中問號處的圖形，則多數(shù)人可能預(yù)測偏上的問號是圈，偏下的問號是叉。該預(yù)測與所有流行的機器學(xué)習(xí)算法做出的預(yù)測相同。

圖二，圖片來源：中國慕課大學(xué)《機器學(xué)習(xí)概論》 機器學(xué)習(xí)算法偏向做出上述預(yù)測的原因是開發(fā)人員在設(shè)計機器學(xué)習(xí)算法時假設(shè)：在特征空間上距離接近的樣本屬于同一類別的概率更高?；诖思僭O(shè)，圖二中問號處圖形的各種情況先驗概率不同。偏上的問號是圓圈的先驗概率高，是叉的先驗概率低；偏下的問號是叉的先驗概率高，是圓圈的先驗概率低。

四、先驗假設(shè)是否準確的討論 先驗假設(shè)不一定準確，下文舉例說明。

例一：假設(shè)明天太陽會照常升起。該假設(shè)基于人們數(shù)千次或數(shù)萬次看見太陽升起，基于過去的書籍中對太陽升起的多次記錄，基于如萬有引力的論證，并通過類比推廣得出。此種方式得出的假設(shè)不能保證基于該假設(shè)的預(yù)測結(jié)果準確率達到100%。


例二：圖二的預(yù)測中，如果圓圈代表花朵，叉代表蜜蜂，那么偏上的問號處可能是蜜蜂，該蜜蜂落入花叢中，并通知其他蜜蜂到此地采蜜。

圖片來源：中國慕課大學(xué)《機器學(xué)習(xí)概論》

審核編輯 ：李倩