2 PAC學習框架 (page 21 22)

DoomNuo 2021-08-15 21:13:18 阅读数:821

本文一共[544]字,预计阅读时长:1分钟~
pac 框架 page

2.3 有限假設集的保證——不一致情形

在最一般的情况下,H 中可能沒有與標記訓練樣本一致的假設。這實際上是實踐中的典型案例,其中學習問題可能有些困難,或者概念類比學習算法使用的假設集更複雜。然而,在訓練樣本上具有少量錯誤的不一致假設可能是有用的,並且正如我們將看到的,可以從某些假設下的有利保證中受益。本節為這種不一致的情况和有限的假設集提供了學習保證。 為了在這種更一般的環境中獲得學習保證,我們將使用 Hoeffding 不等式(定理 D.1)或以下推論,它涉及單個假設的泛化誤差和經驗誤差。

推論2.1

固定  ϵ   >   0 \epsilon > 0  並讓  S S  錶示一個 i.i.d.大小為  m m  的樣本。然後,對於任何假設  h X     { 0 , 1 } h:X → \{0,1\} ,以下不等式成立:

P r S D m [ R ^ ( h ) R ( h ) ϵ ] e x p ( 2 m ϵ 2 ) ( 2.14 ) P r S D m [ R ^ ( h ) R ( h ) ϵ ] e x p ( 2 m ϵ 2 ) . ( 2.15 ) \begin{aligned} \underset {S D^m}{Pr}[\widehat R(h)-R(h)\ge\epsilon]&\le exp(-2m\epsilon ^2)(2.14)\\ \underset {S D^m}{Pr}[\widehat R(h)-R(h)\le -\epsilon]&\le exp(-2m\epsilon ^2).(2.15)\\ \end{aligned}

根據並集界限,這意味著以下兩側不等式:

P r S D m [ R ^ ( h ) R ( h ) ϵ ] 2 e x p ( 2 m ϵ 2 ) . ( 2.16 ) \underset {S D^m}{Pr}[\widehat R(h)-R(h)\ge\epsilon]\le 2exp(-2m\epsilon ^2).(2.16)

證明 結果緊跟定理D.1。 將 (2.16) 的右側設置為等於  δ δ  並求解  ϵ \epsilon 立即為單個假設產生以下界限。

推論 2.2 泛化界——單一假設

固定一個假設  h X     { 0 , 1 } h:X → \{0,1\} 。然後,對於任何  δ   >   0 δ > 0 ,以下不等式成立的概率至少為   1  −  δ  1 − δ

R ( h ) R ^ ( h ) + l o g 2 δ 2 m . ( 2.17 ) R(h)\le \widehat R(h)+\sqrt{\frac{log\frac{2}{δ}}{2m}}.(2.17)

下面的例子在一個簡單的例子中說明了這個推論。

示例2.6 拋硬幣

想象一下,拋一枚有偏向的硬幣,正面朝上的概率為  p p ,讓我們的假設成為總是猜測正面的那個。那麼真實錯誤率是  R ( h )   =   p R(h) = p  和經驗錯誤率  R ^ ( h ) = p ^ \widehat R(h)=\widehat p ,其中 p ^ \widehat p 是基於 i.i.d 抽取的訓練樣本的正面正面概率。因此,推論 2.2 以至少  1  −  δ 1 − δ  的概率保證。

p p ^ l o g 2 δ 2 m . ( 2.18 ) |p-\widehat p|\le\sqrt{\frac{log\frac{2}{δ}}{2m}}.(2.18)

因此,如果我們選擇   δ   =   0.02  δ = 0.02  並使用大小為  500 500  的樣本,概率至少為  98 % 98\% ,則 p ^ \widehat p 保證以下近似質量:

p p ^ l o g ( 10 ) 1000 0.048. ( 2.19 ) |p-\widehat p|\le\sqrt{\frac{log(10)}{1000}}\approx 0.048.(2.19)

當在樣本 S S 上進行訓練時,我們是否能輕易地應用推論2.2來限制學習算法返回的假設 h s h_s 的泛化誤差?不,因為 h s h_s 不是一個固定的假設,而是取决於所抽取的訓練樣本的隨機變量。還要注意,與固定假設的情况不同,對於固定假設,經驗誤差的期望值是泛化誤差(等式2.3),泛化誤差 R h S R(h_S) 是一個隨機變量,通常不同於期望值 E [ R ^ ( h S ) ] E[\widehat R(h_S)] ,後者是一個常數。因此,正如在一致情况下的證明一樣,我們需要導出一致收斂界,這是一個對所有假設 h H h∈ H 成立都具有很高概率的界。

版权声明:本文为[DoomNuo]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815211248044u.html