免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開(kāi)APP
userphoto
未登錄

開(kāi)通VIP,暢享免費(fèi)電子書(shū)等14項(xiàng)超值服

開(kāi)通VIP
一個(gè)二分類(lèi)下沒(méi)有免費(fèi)午餐定理的題

一個(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)練集外誤差”:

\[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) \]

試證明“沒(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\)均勻分布求和為:

\[\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} \]

上面最后一個(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):

\[\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\)無(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\),將它們代入后得:

\[\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\)無(wú)關(guān)。對(duì)于任意的\(\mathcal{L}_a\)\(\mathcal{L}_b\),它們的樣本外誤差的期望其實(shí)是相等的。這就是“沒(méi)有免費(fèi)的午餐”定理(No Free Lunch Theorem,NFL)。

本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶(hù)發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊舉報(bào)。
打開(kāi)APP,閱讀全文并永久保存 查看更多類(lèi)似文章
猜你喜歡
類(lèi)似文章
一般回歸問(wèn)題、線(xiàn)性回歸與模型的正確設(shè)定
EM算法深度解析
張益唐對(duì)于素?cái)?shù)間隔有限研究概述
數(shù)海拾貝
YangCan: 那些年,我們一起追的EB | 統(tǒng)計(jì)之都
你傻ell勞勞碌碌
更多類(lèi)似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服