西瓜書(shū) 第十二章 計(jì)算學(xué)習(xí)理論

這一章全是理論知識(shí)和公式，個(gè)人感覺(jué)有點(diǎn)難。這一章主要介紹了計(jì)算學(xué)習(xí)理論，即如何判斷一個(gè)算法能否得到目標(biāo)概念類(lèi)，針對(duì)一個(gè)算法得到的假設(shè)空間分為有限和無(wú)限，而有限分為兩種情形為可分和不可分；無(wú)限則需要研究它的vc維或Rademacher復(fù)雜度來(lái)進(jìn)行判斷分析。

12.1基礎(chǔ)知識(shí)

計(jì)算學(xué)習(xí)理論關(guān)于計(jì)算器學(xué)習(xí)的理論基礎(chǔ)，其目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)。

泛化誤差：學(xué)習(xí)器在整個(gè)樣本空間上的誤差。E(h;\mathbb{D})=P_{x\sim{\mathbb{D}}}(h(x)≠y)
經(jīng)驗(yàn)誤差：學(xué)習(xí)器在訓(xùn)練集上的誤差。\hat{E}(h;D)={\frac{1}{m}}\sum_{i=1}^mII(h(x_i)≠y_i)
因?yàn)镈是\mathbb{D}獨(dú)立同分布采樣，所以h 的經(jīng)驗(yàn)誤差的期望等于其泛化誤差。

不合disagreement：d(h_1,h_2)=P_{x\sim{\mathbb{D}}}(h_1(x)≠h_2(x))

常用不等式

Jensen不等式
Hoeffding不等式
McDiarmid不等式

常用不等式.PNG

12.2概率近似正確(PAC)學(xué)習(xí)

基礎(chǔ)定義

\cdot概念c：從樣本空間到標(biāo)記空間的映射。
\cdot目標(biāo)概念：對(duì)于任何樣例(x,y)，c(x)=y成立的c。
\cdot概念類(lèi)C：包含目標(biāo)概念的集合。
\cdot假設(shè)h：學(xué)習(xí)算法得出的從樣本空間到標(biāo)記空間的映射。
\cdot假設(shè)空間H：學(xué)習(xí)算法包含的所有假設(shè)的集合。

算法的可分與不可分

\cdot若目標(biāo)概念c∈H，則H中存在假設(shè)可以將所有示例按與真實(shí)標(biāo)記一致的方式完全分開(kāi)，稱(chēng)該問(wèn)題對(duì)學(xué)習(xí)算法L是“可分的”，亦稱(chēng)“一致的”。
\cdot若c?H，則H中不存在任何假設(shè)能將所有示例完全正確分開(kāi)，稱(chēng)該問(wèn)題對(duì)學(xué)習(xí)算法L是“不可分的”亦稱(chēng)“不一致的”。

PAC辨識(shí)

對(duì)0<\epsilon，\delta<1，所有c∈C和分布\mathbb{D}，若存在學(xué)習(xí)算法L，其輸出假設(shè)h∈H滿足P(E(h)≤\epsilon)≥1-\delta,
則稱(chēng)學(xué)習(xí)算法L能從假設(shè)空間H中PAC辨識(shí)概念類(lèi)C.

PAC可學(xué)習(xí)

將樣本考慮進(jìn)來(lái)，若樣本數(shù)量達(dá)到某一數(shù)量時(shí)，則算法總能PAC辨識(shí)概念類(lèi)，稱(chēng)為PAC可學(xué)習(xí)的。


PAC可學(xué)習(xí).png
PAC學(xué)習(xí)算法

連運(yùn)行時(shí)間也考慮進(jìn)來(lái)，當(dāng)運(yùn)行時(shí)間為多項(xiàng)式函數(shù)poly(1/{\epsilon},1/{\delta},size(x),size(c))，則稱(chēng)概念類(lèi)C是高效PAC學(xué)習(xí)可學(xué)習(xí)的，稱(chēng)L為概念類(lèi)C的PAC學(xué)習(xí)算法。
【注：size(\cdot)為復(fù)雜度】

樣本復(fù)雜度

滿足PAC學(xué)習(xí)算法L所需的m≥poly(1/{\epsilon},1/{\delta},size(x),size(c))中最小的m，稱(chēng)為學(xué)習(xí)算法L的樣本復(fù)雜度。

12.3有限假設(shè)空間

有限假設(shè)空間：|H|中假設(shè)有限。該假設(shè)空間可能包含有目標(biāo)概念稱(chēng)為可分情形，若假設(shè)空間沒(méi)有包含目標(biāo)概念則稱(chēng)為不可分情形。
無(wú)限假設(shè)空間：|H|中有無(wú)限個(gè)假設(shè)。該假設(shè)中一定有目標(biāo)概念。

可分情形

我們要如何從假設(shè)空間中學(xué)得目標(biāo)概念呢？
可以通過(guò)訓(xùn)練集來(lái)排除那些不符合的假設(shè)，直到只剩下一個(gè)假設(shè)時(shí)，它就是目標(biāo)概念。但是實(shí)際上我們可能得到多個(gè)經(jīng)驗(yàn)誤差為0的假設(shè)。這個(gè)時(shí)候就沒(méi)辦法進(jìn)一步區(qū)分了。所以我們需要越來(lái)越多的訓(xùn)練樣本才能更好的區(qū)分，如果訓(xùn)練樣本就是樣本集合，那么我們就一定可以得到目標(biāo)概念。

那么需要多少訓(xùn)練樣本才可以得到目標(biāo)概念有效近似呢？
對(duì)PAC學(xué)習(xí)來(lái)說(shuō)，只要訓(xùn)練集D的規(guī)模能使學(xué)習(xí)算法L以概率1-\delta找到目標(biāo)假設(shè)的\epsilon近似即可。

推導(dǎo)過(guò)程和結(jié)論.PNG

不可分情形

不可分情形說(shuō)明假設(shè)空間中并沒(méi)有目標(biāo)概念，但是我們卻可以找出其中泛化誤差最小的假設(shè)也不失為一個(gè)好的目標(biāo)，這就是不可知學(xué)習(xí)的來(lái)源。


推論定理.png

從上面的定理我們可以發(fā)現(xiàn)當(dāng)m較大時(shí)，h的經(jīng)驗(yàn)誤差非常接近其泛化誤差，所以對(duì)于有限的假設(shè)空間有：
定理.png
不可知PAC可學(xué)習(xí)

若存在學(xué)習(xí)算法L滿足P(E(h)-{\min_{h'∈H}E(h')≤{\epsilon}})≥1-\delta則稱(chēng)假設(shè)空間H是不可知可學(xué)習(xí)的。

當(dāng)學(xué)習(xí)算法的運(yùn)行時(shí)間也是多項(xiàng)式函數(shù)poly(1/{\epsilon},1/{\delta},size(x),size(c))，則稱(chēng)假設(shè)空間H是高效不可知PAC可學(xué)習(xí)的。

12.4VC維

對(duì)于無(wú)限的假設(shè)空間，要先研究其可學(xué)習(xí)性，需要度量假設(shè)空間的復(fù)雜度，而度量空間復(fù)雜度的常用方法是考慮空間的VC維。

增長(zhǎng)函數(shù)

假設(shè)h對(duì)D中示例的標(biāo)記結(jié)果為：h|_D=\{(h(x_1),h(x_2),...,h(x_m))\}對(duì)所有m∈\mathbb{N}，假設(shè)空間增長(zhǎng)函數(shù)為：\prod_H(m)=\max_{\{x_1,...,x_m\}\subseteq{\chi}}|\{(h(x_1),...,h(x_m))|h∈H\}|表示假設(shè)空間H對(duì)m個(gè)示例所能賦予標(biāo)記的最大可能結(jié)果數(shù)，值越大說(shuō)明該假設(shè)空間的表示能力越強(qiáng)。

對(duì)分和打散

盡管H中有無(wú)限個(gè)假設(shè)，但其對(duì)D中示例賦予標(biāo)記的可能結(jié)果是有限的。
\cdot對(duì)分：對(duì)二分類(lèi)問(wèn)題來(lái)說(shuō)，假設(shè)對(duì)D中示例賦予標(biāo)記的每種可能結(jié)果稱(chēng)為對(duì)D的一種對(duì)分。
\cdot打散：若假設(shè)空間H能實(shí)現(xiàn)示例集D上的所有對(duì)分，即{\prod}_H(m)=2^m，則稱(chēng)示例集D能被假設(shè)空間H“打散”。

VC維

\cdot假設(shè)空間H的VC維是能被H打散的最大示例集的大小，即VC(H)=max\{m:{\prod}_H(m)=2^m\}.
【注：并非所有的大小為d的示例集都能被假設(shè)空間打散】

\cdot增長(zhǎng)函數(shù)的上界與假設(shè)空間的VC維有關(guān)：

引理12.2.png

通過(guò)上面的式子可以得到增長(zhǎng)函數(shù)的上界：
若假設(shè)空間H的VC維為d，則對(duì)任意整數(shù)m≥d有

\cdot分布無(wú)關(guān)(數(shù)據(jù)獨(dú)立)性：VC維的泛化誤差只與樣例數(shù)目m有關(guān)，收斂速率為O(\frac{1}{\sqrt{m}})，與數(shù)據(jù)分布\mathbb{D}無(wú)關(guān)。
\cdot任何VC維有限的假設(shè)空間H都是(不可知)PAC可學(xué)習(xí)的。

12.5Rademacher復(fù)雜度

基于VC維的泛化誤差界是分布無(wú)關(guān)、數(shù)據(jù)獨(dú)立的，也就是對(duì)任何分布都成立，所以它得到的泛化誤差界比較的“松”的。
Rademacher復(fù)雜度是另一種刻畫(huà)空間復(fù)雜度的途徑，它在一定程度上考慮了數(shù)據(jù)分布。

Rademacher復(fù)雜度對(duì)h的經(jīng)驗(yàn)誤差進(jìn)行了一點(diǎn)小的改變，引入了Rademacher隨機(jī)變量。

Rademacher推導(dǎo)過(guò)程.PNG

經(jīng)驗(yàn)Rademacher復(fù)雜度衡量了函數(shù)空間與隨機(jī)噪聲在集合Z中的相關(guān)性。
定義12.8.png

基于Rademacher復(fù)雜度得到的關(guān)于函數(shù)空間F的泛化誤差界：
定義12.9.png

回歸問(wèn)題——基于Rademacher復(fù)雜度的泛化誤差界
回歸問(wèn)題泛化誤差界.png

二分類(lèi)問(wèn)題——基于Rademacher復(fù)雜度的泛化誤差界
二分類(lèi)問(wèn)題的泛化誤差.png

假設(shè)空間H的Rademacher復(fù)雜度與增長(zhǎng)函數(shù)的關(guān)系：
定理12.7.png

12.6穩(wěn)定性

穩(wěn)定性分析可以獲得宇算法有關(guān)的分析結(jié)果，主要考察算法在輸入發(fā)生變化時(shí)，輸出是否發(fā)生較大變化。

算法輸入的變化主要有以下兩種：
{\cdot}D^{\backslash{i}}表示移除D中第i個(gè)樣例得到的集合。
{\cdot}D^i表示替換D中第i樣例得到的集合。

關(guān)于假設(shè)L_D的幾種損失

三種損失.png

算法的均勻穩(wěn)定性

均勻穩(wěn)定性.png
對(duì)于損失函數(shù)，若學(xué)習(xí)算法L所輸出的假設(shè)滿足經(jīng)驗(yàn)損失最小化，則稱(chēng)為算法L滿足經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化(ERM)原則，簡(jiǎn)稱(chēng)算法是ERM的。
【注：經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化(ERM)原則{\hat{E(h)}=\min_{h'∈H}{\hat{E(h')}}}，即算法L輸出的假設(shè)h為假設(shè)空間中經(jīng)驗(yàn)誤差最小的假設(shè)】

穩(wěn)定性通過(guò)損失函數(shù)將學(xué)習(xí)算法和假設(shè)空間聯(lián)系起來(lái)，區(qū)別在于：
\cdot假設(shè)空間關(guān)注的是經(jīng)驗(yàn)誤差與泛化誤差，需要考慮到所有可能的假設(shè)：sup_{h∈H}|{\hat{E(h)}}-E(h)|;
\cdot穩(wěn)定性只關(guān)心當(dāng)前的輸出，只要當(dāng)前輸出滿足經(jīng)驗(yàn)損失最小即可：|{\hat{\varrho(L,D)}}-{\varrho}(L,\mathbb{D})|
若學(xué)習(xí)算法L是ERM且穩(wěn)定的，則假設(shè)空間H可學(xué)習(xí)。

參考：https://blog.csdn.net/cristianojason/article/details/79057977
https://blog.csdn.net/Julialove102123/article/details/79983545

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

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

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