一個二分類下沒有免費午餐定理的題

• 2020 年 10 月 28 日
• 筆記
• 人工智慧, 千里路, 機器學習

一個證明題

周志華《機器學習》第一章中，有一個關於「沒有免費的午餐」定理的題目，題目是這樣的：

假設樣本空間\(\mathcal{X}\)和假設空間\(\mathcal{H}\)都是離散的，令\(P(h|X,\mathcal{L}_a)\)為演算法\(\mathcal{L}_a\)基於訓練數據\(X\)產生假設\(h\)的概率，令\(f\)代表真實目標函數。考查二分類問題，\(f\)可以是任何函數\(\mathcal{X} \mapsto \{0,1\}\)，函數空間為\(\{0,1\}^{\vert \mathcal{X} \vert}\)，假設\(f\)是均勻分布（即不管\(h(x)\)是什麼，都有一半的\(f\)對\(x\)的預測與\(h(x)\)不一致）。現在採用\(\ell(h(x),f(x))\)作為分類器的性能度量，考慮\(\mathcal{L}_a\)的「訓練集外誤差」：

試證明「沒有免費午餐定理」成立。

分析與解答

題目未給定\(\ell(h(x),f(x))\)的具體形式，但在二分類問題中，無非就4種情況。記\(\ell(1,1)=\ell_1\)，\(\ell(0,1)=\ell_2\)，\(\ell(1,0)=\ell_3\)，\(\ell(0,0)=\ell_4\)，它們都是常數。將\(\mathcal{L}_a\)的訓練集外誤差對所有\(f\)按均勻分布求和為：

上面最後一個等式是因為\(f\)是均勻分布，因此如果給定了\(h\)和\(x\)，不管\(h(x)\)是0還是1，都有一半的\(f\)會是\(f(x)=0\)，一半的\(f\)會是\(f(x)=1\)。

又因為\(\mathbb{I}(h(x)=1)+\mathbb{I}(h(x)=0)=1\)，可將上式繼續化簡：

上式中，第一部分\(2^{\vert\mathcal{X}\vert-1} (\ell_2+\ell_4) \sum_{x\in \mathcal{X}-X} P(x)\) 顯然與\(\mathcal{L}_a\)無關，第二部分則不然，需要再附加條件\(\ell_1+\ell_3-\ell_2-\ell_4=0\)才可以使整個式子與\(\mathcal{L}_a\)無關，在周志華的書中，並沒有加這個限制，可能是默認隱含了（因為加入這個條件很合理）。\(\blacksquare\)

特殊化情形

再來看在書正文中的例子，該例子將\(\ell(h(x),f(x))\)特殊化為二分類的錯誤率，即取\(\ell(h(x),f(x))=\mathbb{I}(h(x)\ne f(x))\)，對應到本文的設定中，有\(\ell_1=\ell_4=0\)，\(\ell_2=\ell_3=1\)，將它們代入後得：

因此，它與\(\mathcal{L}_a\)無關。對於任意的\(\mathcal{L}_a\)和\(\mathcal{L}_b\)，它們的樣本外誤差的期望其實是相等的。這就是「沒有免費的午餐」定理（No Free Lunch Theorem，NFL）。