周志華《機(jī)器學(xué)習(xí)》第一章中,有一個(gè)關(guān)于“沒(méi)有免費(fèi)的午餐”定理的題目,題目是這樣的:
假設(shè)樣本空間\(\mathcal{X}\)和假設(shè)空間\(\mathcal{H}\)都是離散的,令\(P(h|X,\mathcal{L}_a)\)為算法\(\mathcal{L}_a\)基于訓(xùn)練數(shù)據(jù)\(X\)產(chǎn)生假設(shè)\(h\)的概率,令\(f\)代表真實(shí)目標(biāo)函數(shù)。考查二分類(lèi)問(wèn)題,\(f\)可以是任何函數(shù)\(\mathcal{X} \mapsto \{0,1\}\),函數(shù)空間為\(\{0,1\}^{\vert \mathcal{X} \vert}\),假設(shè)\(f\)是均勻分布(即不管\(h(x)\)是什么,都有一半的\(f\)對(duì)\(x\)的預(yù)測(cè)與\(h(x)\)不一致)?,F(xiàn)在采用\(\ell(h(x),f(x))\)作為分類(lèi)器的性能度量,考慮\(\mathcal{L}_a\)的“訓(xùn)練集外誤差”:
試證明“沒(méi)有免費(fèi)午餐定理”成立。
題目未給定\(\ell(h(x),f(x))\)的具體形式,但在二分類(lèi)問(wèn)題中,無(wú)非就4種情況。記\(\ell(1,1)=\ell_1\),\(\ell(0,1)=\ell_2\),\(\ell(1,0)=\ell_3\),\(\ell(0,0)=\ell_4\),它們都是常數(shù)。將\(\mathcal{L}_a\)的訓(xùn)練集外誤差對(duì)所有\(f\)按均勻分布求和為:
上面最后一個(gè)等式是因?yàn)?span id="fu8ihs5fyo3" class="math inline">\(f\)是均勻分布,因此如果給定了\(h\)和\(x\),不管\(h(x)\)是0還是1,都有一半的\(f\)會(huì)是\(f(x)=0\),一半的\(f\)會(huì)是\(f(x)=1\)。
又因?yàn)?span id="fu8ihs5fyo3" class="math inline">\(\mathbb{I}(h(x)=1)+\mathbb{I}(h(x)=0)=1\),可將上式繼續(xù)化簡(jiǎn):
上式中,第一部分\(2^{\vert\mathcal{X}\vert-1} (\ell_2+\ell_4) \sum_{x\in \mathcal{X}-X} P(x)\) 顯然與\(\mathcal{L}_a\)無(wú)關(guān),第二部分則不然,需要再附加條件\(\ell_1+\ell_3-\ell_2-\ell_4=0\)才可以使整個(gè)式子與\(\mathcal{L}_a\)無(wú)關(guān),在周志華的書(shū)中,并沒(méi)有加這個(gè)限制,可能是默認(rèn)隱含了(因?yàn)榧尤脒@個(gè)條件很合理)。\(\blacksquare\)
再來(lái)看在書(shū)正文中的例子,該例子將\(\ell(h(x),f(x))\)特殊化為二分類(lèi)的錯(cuò)誤率,即取\(\ell(h(x),f(x))=\mathbb{I}(h(x)\ne f(x))\),對(duì)應(yīng)到本文的設(shè)定中,有\(\ell_1=\ell_4=0\),\(\ell_2=\ell_3=1\),將它們代入后得:
因此,它與\(\mathcal{L}_a\)無(wú)關(guān)。對(duì)于任意的\(\mathcal{L}_a\)和\(\mathcal{L}_b\),它們的樣本外誤差的期望其實(shí)是相等的。這就是“沒(méi)有免費(fèi)的午餐”定理(No Free Lunch Theorem,NFL)。
聯(lián)系客服