一個(gè)證明題

周志華《機(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）。