一個證明題
周志華《機器學習》第一章中，有一個關于“沒有免費的午餐”定理的題目，題目是這樣的：
假設樣本空間\(\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\)的“訓練集外誤差”：
\[E_{ote}(\mathcal{L}_a | X,f)=\sum_h \sum_{x\in \mathcal{X}-X} P(x)\ell({h(x),f(x)}) P(h|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\)按均勻分布求和為：
\[\begin{aligned} &\sum_f E_{ote}(\mathcal{L}_a | X,f) \\ =& \sum_f \sum_h \sum_{x\in \mathcal{X}-X} P(x)\ell({h(x),f(x)}) P(h|X, \mathcal{L}_a) \\ =& \sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a) \sum_f \ell({h(x),f(x)})\\ =& \sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a) \left( 2^{\vert\mathcal{X}\vert}\mathbb{I}(h(x)=1) (\dfrac{1}{2} \ell_1+\dfrac{1}{2} \ell_3) \right)\\ +& \sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a) \left( 2^{\vert\mathcal{X}\vert}\mathbb{I}(h(x)=0) (\dfrac{1}{2} \ell_2+\dfrac{1}{2} \ell_4) \right)\\ \end{aligned} \]上面最后一個等式是因為\(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\)，可將上式繼續化簡：
\[\begin{aligned} &\sum_f E_{ote}(\mathcal{L}_a | X,f) \\ =& 2^{\vert\mathcal{X}\vert-1}\sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a) \big((\ell_1+ \ell_3) \mathbb{I}(h(x)=1) +(\ell_2+\ell_4)(1-\mathbb{I}(h(x)=1)) \big)\\ =& 2^{\vert\mathcal{X}\vert-1} (\ell_2+\ell_4) \sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a)\cdot 1\\ +& 2^{\vert\mathcal{X}\vert-1} \sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a) (\ell_1+\ell_3-\ell_2-\ell_4)\mathbb{I}(h(x)=1)\\ =& 2^{\vert\mathcal{X}\vert-1} (\ell_2+\ell_4) \sum_{x\in \mathcal{X}-X} P(x) \\ +& 2^{\vert\mathcal{X}\vert-1} (\ell_1+\ell_3-\ell_2-\ell_4) \sum_{x\in \mathcal{X}-X} P(x) \sum_h P(h|X, \mathcal{L}_a)\mathbb{I}(h(x)=1) \end{aligned} \]上式中，第一部分\(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\)，將它們代入后得：
\[\sum_f E_{ote}(\mathcal{L}_a | X,f) = 2^{\vert\mathcal{X}\vert-1} \sum_{x\in \mathcal{X}-X} P(x) \]因此，它與\(\mathcal{L}_a\)無關，對于任意的\(\mathcal{L}_a\)和\(\mathcal{L}_b\)，它們的樣本外誤差的期望其實是相等的，這就是“沒有免費的午餐”定理（No Free Lunch Theorem，NFL），
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/196024.html
標籤：其他
上一篇：撰寫同時在PyTorch和Tensorflow上作業的代碼
下一篇：【ECCV 2020】GINet：Graph Interaction Network for Scene Parsing