西瓜書(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

最后編輯于：2020.04.09 00:26:31

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市罩驻，隨后出現(xiàn)的幾起案子穗酥，更是在濱河造成了極大的恐慌，老刑警劉巖，帶你破解...
沈念sama閱讀 219,270評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件砾跃，死亡現(xiàn)場(chǎng)離奇詭異骏啰，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)抽高，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,489評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)判耕，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人翘骂，你說(shuō)我怎么就攤上這事壁熄。” “怎么了碳竟？”我有些...
開(kāi)封第一講書(shū)人閱讀 165,630評(píng)論 0贊 356
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵草丧，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我莹桅，道長(zhǎng)昌执，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,906評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任诈泼，我火速辦了婚禮仙蚜，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘厂汗。我一直安慰自己委粉，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,928評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布娶桦。她就那樣靜靜地躺著贾节，像睡著了一般。火紅的嫁衣襯著肌膚如雪衷畦。梳的紋絲不亂的頭發(fā)上栗涂，一...
開(kāi)封第一講書(shū)人閱讀 51,718評(píng)論 1贊 305
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音祈争，去河邊找鬼斤程。笑死，一個(gè)胖子當(dāng)著我的面吹牛菩混，可吹牛的內(nèi)容都是我干的忿墅。我是一名探鬼主播，決...
沈念sama閱讀 40,442評(píng)論 3贊 420
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼沮峡，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼疚脐！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起邢疙，我...
開(kāi)封第一講書(shū)人閱讀 39,345評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤棍弄，失蹤者是張志新（化名）和其女友劉穎望薄，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體呼畸，經(jīng)...
沈念sama閱讀 45,802評(píng)論 1贊 317
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡痕支，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,984評(píng)論 3贊 337
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了蛮原。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片采转。...
茶點(diǎn)故事閱讀 40,117評(píng)論 1贊 351
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖瞬痘，靈堂內(nèi)的尸體忽然破棺而出故慈，到底是詐尸還是另有隱情，我是刑警寧澤框全，帶...
沈念sama閱讀 35,810評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布察绷，位于F島的核電站，受9級(jí)特大地震影響津辩，放射性物質(zhì)發(fā)生泄漏拆撼。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,462評(píng)論 3贊 331
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一喘沿、第九天我趴在偏房一處隱蔽的房頂上張望闸度。院中可真熱鬧，春花似錦蚜印、人聲如沸莺禁。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,011評(píng)論 0贊 22
一樁弒父案窄赋，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)哟冬。三九已至，卻和暖如春忆绰，著一層夾襖步出監(jiān)牢的瞬間浩峡，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,139評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工错敢，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留翰灾，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,377評(píng)論 3贊 373
代替公主和親
正文我出身青樓稚茅，卻偏偏與公主長(zhǎng)得像纸淮，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子峰锁，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,060評(píng)論 2贊 355

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