- 《Understanding Machine Learning-From Theory to Algorithms》
- 第二章惜互，最后一段關(guān)于predictor 失敗的分析
一個(gè)upper bound的推導(dǎo)和理解
有了精度參數(shù)
, 我們就可以定義失敗的假設(shè) %7D(h_S)%3E%5Cepsilon)
. 我們有m個(gè)訓(xùn)練樣本)
，是通過采樣產(chǎn)生的蝠检，組成了樣本集合
虾宇。不同人/時(shí)間岖赋，采樣的結(jié)果是不一樣的摩梧，就有不同的樣本集合旁趟，比如有
. 這些樣本集合有多大概率產(chǎn)生失敗的predictor呢艰匙？記訓(xùn)練實(shí)例集為)
. 我們關(guān)心的是下面概率的上界限煞。
%7D(h_S)%3E%5Cepsilon%5C%7D))
#m-組實(shí)例采樣中 導(dǎo)致失敗預(yù)測器的 概率。
怎么算這個(gè)上界 upper bound?
- 引入bad hypothesis set的集合
%7D(h)%3E%5Cepsilon%5C%7D)
.
- 從bad hypothesis出發(fā)员凝，定義數(shù)據(jù)誤導(dǎo)集
%3D0%20%5C%7D)
也就是誤導(dǎo)集是依賴bad hypothesis的署驻，不同的
會有不同的誤導(dǎo)集，整個(gè)誤導(dǎo)集是所有bad hypothesis的并集健霹。
- 回到關(guān)注的問題中的集合
%7D(h_S)%3E%5Cepsilon%5C%7D)
, 這個(gè)集合等價(jià)于：
%7D(h)%3E%5Cepsilon%2CL_S(h)%3D0%5C%7D)
,繼續(xù)等價(jià)于：
%3D0%5C%7D)
旺上，子集關(guān)系就出來了：
%7D(h_S)%3E%5Cepsilon%5C%7D%5Csubseteq%20M)
, 這個(gè)集合只是誤導(dǎo)集的子集而已。
- 概率不等關(guān)系也就出來了：
%7D(h_S)%3E%5Cepsilon%5C%7D)%5Cleq%20D%5Em(M))
- 從第2點(diǎn)中可以看出
還是個(gè)并集糖埋。%3D0%5C%7D)
宣吱。利用聯(lián)合界的方式縮放：
%5Cleq%5Cmathop%7B%5CSigma%7D_%7Bh%5Cin%5Cmathcal%7BH%7D_B%7D%20D%5Em(%5C%7BS%7Cx%3AL_S(h)%3D0%5C%7D))
.
- 固定某個(gè)"bad"假設(shè)，展開：
%3D0%5C%7D)%3DD%5Em(%5C%7BS%7Cx%3A%5Cforall%20i%2C%20h(x_i)%3Df(x_i)%5C%7D)%3D%5Cmathop%7B%5CPi%7D_%7Bi%3D1%7D%5Em%20D(%5C%7Bx_i%3A%20h(x_i)%3Df(x_i)%5C%7D))
- 對于每個(gè)sample,
%3Df(x_i)%5C%7D)%3D1-L_%7B(D%2Cf)%7D(h)%5Cleq%201-%5Cepsilon%5Cleq%20e%5E%7B-%5Cepsilon%7D)
瞳别， 注意第6步中使用的bad hypothesis, 所以不等式成立征候。
- 所以整個(gè)的上界upper bound
%7D(h_S)%3E%5Cepsilon%5C%7D)%5Cleq%20%7C%5Cmathcal%7BH%7D%7Ce%5E%7B-%5Cepsilon%20m%7D)
說明：
- 假設(shè)空間很小
, 訓(xùn)練樣本量
只需要很少杭攻；但是由于實(shí)際問題的復(fù)雜性，
必須要很大(比如深度學(xué)習(xí))疤坝。為了控制這個(gè)upper bound, 就必然要求大的兆解，大數(shù)據(jù)量。
- 精度參數(shù)是一個(gè)要求指標(biāo)跑揉，精度需求越高锅睛，越小，實(shí)現(xiàn)相同的upper bound历谍， 就需要更大的现拒，數(shù)據(jù)量和精度有關(guān)系。通過數(shù)據(jù)增強(qiáng)提高分類精度望侈，這個(gè)公式也可以看出端倪印蔬。
- 算法理論分析的牛逼之處在于：給定少量的假設(shè)條件，就能夠分析出關(guān)鍵配置對性能影響關(guān)系甜无。
推論2.3
假設(shè) %7D%7B%5Cepsilon%7D)
%7D(h_S)%3E%5Cepsilon%5C%7D)%5Cleq%20%7C%5Cmathcal%7BH%7D%7Ce%5E%7B-%5Cepsilon%20m%7D%5Cleq%20%5Cdelta)
說明：在m足夠大的時(shí)候扛点，在獨(dú)立同分布的樣本集S上，最少以
的大概率保證
有效岂丘，即 %7D(h_S)%5Cleq%20%5Cepsilon)
.
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
