第六章 The VC-Dimension

上一章介紹了講了EMR的誤差主要分為兩種，一種是approximation error，另一種是estimation error。其中approximation error衡量了所選擇假設h是不是適合這個問題，里面有沒有包含足夠的先驗知識。對于一個假設，如果要滿足PAC可學習的情況下，那么其estimation error需要被限制在一定的范圍之內(nèi)。

本章的目的是，能夠滿足PAC可學習的假設。之前的章節(jié)中提到過，有限假設集一定是PAC可學習的。

在無限假設集上怎么保證PAC可學習呢？

可以舉這么一個例子，使假設集\mathcal{H} = \{h_a:a\in R\}，h_a可以看作是一個值域區(qū)間從0-1上的函數(shù)，h_a(x) = \mathbb{I}_{[x<a]}表示當0<x<a時，ha(x) = 1，當x>a時，ha(x) = 0。

很明顯這個假設集是一個無限集，因為a可以取0-1中的任意數(shù)。

假設我們的最優(yōu)解是當a = a*時，這時候a*左右兩邊分別有一個對稱的bound，正好使得分別在這兩個bound之內(nèi)的數(shù)的概率被限制在epsilon之內(nèi)。

看到epsilon之后，立馬想到了PAC可學習性，那么在這里是怎么跟PAC建立聯(lián)系的呢？

在如上的例子中，如果我們給出了一個訓練集，給出兩個bound，使得最終的最優(yōu)假設的閾值在這兩個bound之內(nèi)，那么如果這兩個bound正好在a0和a1之內(nèi)的話，就能夠使得這個最優(yōu)假設的誤差小于epsilon。

利用這點經(jīng)過一系列的推導可以推出m_{\mathcal{H}}(\epsilon,\delta) \le \ulcorner log(2/\delta)/\epsilon\urcorner,也就是說在這種采樣復雜度的情況下，能夠使得一個無限集問題成為一個PAC可學習問題。

VC維

關(guān)于具體介紹VC維的內(nèi)容建議參考https://baike.baidu.com/item/vc維/2947135?fr=aladdin

= =

VC維主要主要衡量了假設集的學習能力，越大假設集空間越大，學習的復雜度也就越高。這個說起來很容易理解，但是在具體看這塊內(nèi)容數(shù)學推導時，有一種回到研一學習np問題的日子的感覺。確實是很硬核的知識點，理論推導以后有機會再啃書吧。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容