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

一、沒有免費(fèi)午餐定理

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

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

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

（1）第一個(gè)和第二個(gè)存儲(chǔ)單元均屬于第一類。

（2）第一個(gè)存儲(chǔ)單元屬于第一類，第二個(gè)存儲(chǔ)單元屬于第二類。

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

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

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

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

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

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

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


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

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

審核編輯 ：李倩