PAD-learnable的 定義:?
P(Rs(h(x))>=?)<=δ
* 存在對應(yīng)的其中是樣本的數(shù)量抒痒，代表樣本的分布代表樣本空間
* 存在對應(yīng)的Dm,其中,m是樣本的數(shù)量，D代表樣本的分布.Dm代表樣本空間.
如何理解: 用概率學(xué)的理論解釋, 就是R(x) （錯誤樣本）可以控制在一定的概率范圍內(nèi). 在m 個樣本中隨機取m * epsilon 次袁串，至少有一次錯誤的可能性小于delta.
c(x): 規(guī)則定義空間,需要學(xué)習(xí)的空間
h(x): 假設(shè)空間, 學(xué)習(xí)到的空間
將c(x) 具象化: 如果是一個矩形區(qū)域，落在矩形區(qū)域內(nèi)的點為1靶累，否則為0. 可以推導(dǎo)得出該c(x) 是否是PAC-learning可學(xué)習(xí)的敏释，以及在什么情況下可學(xué)習(xí).
假設(shè)R1(x)為h(x) 假設(shè)空間， R(x)為定義空間晤硕，ri(x) 為h(x) 外且在c(x)內(nèi)的4個矩形內(nèi)的點.
也就是說：所有的樣本都掉入了誤差區(qū)域悼潭。?
因為誤差區(qū)域又是一個矩形c(x),?可以通過嵌套的方式得出：P(R(ri))>=?
4(1-?m/4)^m<=4exp(??m/4)[較常用的不等式]
最終可以得出結(jié)論: 如果要保證PAC-learning: 需要滿足:
m>=4/?log(δ/4)
這也揭示了機器學(xué)習(xí)達到一定的性能, 需要的樣本量與定義空間之間的關(guān)系.
另一個例子:
如果c(x) 不是矩形區(qū)域，而是圓形區(qū)域會怎樣呢舞箍，這是本書的練習(xí)題舰褪，可以證明為PAC-learning的，滿足
m>=1/?log(δ)
證明如下:
假設(shè)R(x)為定義空間, R1(x)為假設(shè)空間h(x), r(x) 為R1(x) 外且在R(x) 內(nèi)的r(x)環(huán)形內(nèi)的點.
P(Rs(R(x))>=?)=P(R1(x)∩r1=Φ)=P(r1)
由于r1為環(huán)形區(qū)域,面積小于圓形區(qū)域.
有P(r1)<(1??)m<=exp(?m?) 故有:m>=1/?log(δ)
下面討論c(x)定義空間的學(xué)習(xí)邊界.
有限邊界定義空間
何為有限邊界疏橄，可以這么理解, 就是有N個函數(shù)定義的規(guī)則空間. 前提占拍，N個規(guī)則空間都是滿足PAC-learning的.
比如有N個矩形，N個圓, c(x) 可以用N個函數(shù)定義出來. 這里我們用|H|表示函數(shù)的數(shù)量. 那么捎迫，滿足什么條件晃酒，就可以 PAC-learning，條件是:
m>=1/?(log|H|+log1/δ)
根據(jù)公式看一下窄绒，樣本空間的大小取決于這定義空間有多復(fù)雜(|H|), 以及需要多高的準(zhǔn)確率(epsilon越小贝次，準(zhǔn)確率越高), 可以假設(shè)，當(dāng)|H|無限大時, PAC-learning就不可達到了.
證明方法就是這|H|個規(guī)則空間的疊加.
c(x)的表示
本書中用一個例子展示出一個concept集的表示對于學(xué)習(xí)的重要性彰导。這里列舉了K-CNF 庫克公式的例子.
怎么理解K-CNF公式呢蛔翅？先給出K-CNF的定義:
假設(shè)concept可以由k組表示得到，u0?k. 那么就可以寫成∪u0?k.
對于一個單獨的位谋，又可以表示為ui,1∩...∩ui,nk.
每個ui都有一組單獨的特征組合.
因此就有K?CNF的公式:
如果假設(shè)ui,ni 又是一組新的bool表達式而不是數(shù)值山析，那么有點樹模型的感覺：
有k顆數(shù)，取每棵樹的最大值. 而每顆數(shù)都有n個分支倔幼，所有滿足n個分支的盖腿，就滿足concept集合.
