2019-03-08

ML——計(jì)算學(xué)習(xí)理論

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

泛化誤差：訓(xùn)練出的模型在除訓(xùn)練樣本外的新樣本集上的誤差竞川；

? ? ? ? ? ? ? ? ? ? ? ?? $E(h;D)=P_{x\sim D}(h(x)\neq y)$

經(jīng)驗(yàn)誤差：訓(xùn)練出的模型在訓(xùn)練集上的誤差。

? ? ? ? ? ? ? ? ? $\hat{E} (h;D)=\frac{1}{m} \sum\nolimits_{i=1}^m I(h(x_i)\neq y_i)$

本章后面部分將研究經(jīng)驗(yàn)誤差與泛化誤差間的逼近程度哪自，若h在數(shù)據(jù)集D上的經(jīng)驗(yàn)誤差為0茁帽，則稱h與D一致胆屿，否則稱其不一致腋逆。

Jensen不等式：對(duì)任意凸函數(shù)f(x)，有 $f(Ex)\geq Ef(x)$ 监嗜；

Hoeffding不等式：若 $x_1,x_2,...x_m$ 為m個(gè)獨(dú)立r.v.谐檀，且滿足 $0\leq x_i\leq 1$ ，則對(duì)任意 $\epsilon >0$ 裁奇，有

$P(\frac{1}{m}\sum_{i=1}^mx_i- \frac{1}{m}\sum_{i=1}^mE(x_i)\geq \epsilon )\leq exp(-2m\epsilon ^2)\\P(\vert \frac{1}{m}\sum_{i=1}^mx_i- \frac{1}{m}\sum_{i=1}^mE(x_i) \vert\geq \epsilon )\leq 2exp(-2m\epsilon ^2)$

McDiarmid不等式：若 $x_1,x_2,...x_m$ 為m個(gè)獨(dú)立r.v.桐猬，且對(duì)任意 $1\leq i\leq m$ ，函數(shù)f滿足：

$\mathop{\sup}_{x_1,...,x_m,x_{i}^, }\vert f(x_1,...,x_m)-f(x_1,...,x_{i-1} ,x_{i}^,,x_{i+1},...,x_m)\vert \leq c_i$

則對(duì)任意 $\epsilon >0$ 刽肠，有：

$P(f(x_1,...,x_m)-E(f(x_1,...,x_m))\geq \epsilon )\leq exp(\frac{-2\epsilon ^2}{\sum\nolimits_{i}c_{i}^2 } )\\P(\vert f(x_1,...,x_m)-E(f(x_1,...,x_m))\vert\geq \epsilon )\leq 2exp(\frac{-2\epsilon ^2}{\sum\nolimits_{i}c_{i}^2 } )$

PAC學(xué)習(xí)

PAC：概率近似正確课幕，以比較大的把握學(xué)得比較好的模型厦坛，即以較大的概率學(xué)得誤差滿足預(yù)設(shè)上限的模型；

概念c：從樣本空間X到標(biāo)記空間Y的映射乍惊，決定示例x的真實(shí)標(biāo)記y杜秸；

目標(biāo)概念c：對(duì)任何樣例(x,y)，有c(x)=y成立润绎；

概念類C：所學(xué)目標(biāo)概念構(gòu)成的集合撬碟；

假設(shè)空間H：給定學(xué)習(xí)算法L，考慮的所有可能概念的集合莉撇；

假設(shè)h：從樣本空間X到標(biāo)記空間Y的映射呢蛤，不確定的目標(biāo)概念；

可分（一致）：若目標(biāo)概念 $c\in H$ 棍郎，則H中存在假設(shè)能將所有示例按與真實(shí)標(biāo)記一致的方式完全分開(kāi)其障，稱該問(wèn)題對(duì)學(xué)習(xí)算法L是“可分的”。

不可分（不一致）：若 $c\notin H$ 涂佃，則H中不存在假設(shè)能將所有示例完全正確分開(kāi)励翼，稱該問(wèn)題對(duì)學(xué)習(xí)算法L是“不可分的”。

PAC辨識(shí)：學(xué)習(xí)算法L能以較大的概率（至少 $1-\delta$ ）學(xué)得目標(biāo)概念c的近似（誤差最多為 $\epsilon$ ）辜荠。

PAC可學(xué)習(xí)：m為從分布D中獨(dú)立同分布采樣得到的樣例數(shù)汽抚， $0<\epsilon ,\delta <1$ ，對(duì)所有分布D伯病，若存在學(xué)習(xí)算法L和多項(xiàng)式函數(shù)poly()造烁，使得對(duì)任何 $m\geq poly(1/\epsilon ,1/\delta ,size(x),size(c))$ ，L能從假設(shè)空間H中PAC辨識(shí)概念類C午笛，則稱概念類C對(duì)假設(shè)空間H而言是PAC可學(xué)習(xí)的惭蟋。

PAC學(xué)習(xí)算法：若學(xué)習(xí)算法L使概念C為PAC可學(xué)習(xí)的，且L的運(yùn)行時(shí)間也是多項(xiàng)式函數(shù) $poly(1/\epsilon ,1/\delta ,size(x),size(c))$ 药磺，則稱概念類C是高效PAC可學(xué)習(xí)的敞葛，稱L為概念類C的PAC學(xué)習(xí)算法。

假定學(xué)習(xí)算法L處理每個(gè)樣本的時(shí)間為常數(shù)与涡，則L的時(shí)間復(fù)雜度等價(jià)于樣本復(fù)雜度。對(duì)算法時(shí)間復(fù)雜度的關(guān)心轉(zhuǎn)化為對(duì)樣本復(fù)雜度的關(guān)心持偏。

樣本復(fù)雜度：滿足PAC學(xué)習(xí)算法L所需的 $m\geq poly(1/\epsilon ,1/\delta ,size(x),size(c))$ 中最小的m驼卖，稱為學(xué)習(xí)算法l的樣本復(fù)雜度。

若在PAC學(xué)習(xí)中假設(shè)空間和概念類完全相同H=C鸿秆，則稱為“恰PAC可學(xué)習(xí)”酌畜。但實(shí)際中研究的是假設(shè)空間與概念類不同的情形。一般而言卿叽，H越大桥胞，包含目標(biāo)概念的可能性越大恳守，但從中找出具體目標(biāo)概念的難度越大。 $\vert H \vert$ 有限時(shí)贩虾，稱H為“有限假設(shè)空間”催烘，否則為“無(wú)限假設(shè)空間”。

有限假設(shè)空間

可分情形

可分意味著目標(biāo)概念包含在算法的假設(shè)空間中缎罢，對(duì)于目標(biāo)概念伊群，在訓(xùn)練集D中的經(jīng)驗(yàn)誤差一定為0。一種簡(jiǎn)單的學(xué)習(xí)策略是：不斷剔除出現(xiàn)預(yù)測(cè)錯(cuò)誤的假設(shè)策精，保留經(jīng)驗(yàn)誤差為0的假設(shè)舰始。但由于訓(xùn)練規(guī)模有限，假設(shè)空間中可能有多個(gè)假設(shè)在D中經(jīng)驗(yàn)誤差為0咽袜，因此將問(wèn)題轉(zhuǎn)化為只要訓(xùn)練集D的規(guī)模能使學(xué)習(xí)算法L以概率 $1-\delta$ 找到目標(biāo)假設(shè)的 $\epsilon$ 近似即可丸卷。

D包含m個(gè)獨(dú)立同分布采樣得到的樣例，對(duì)某個(gè)輸出假設(shè)泛化誤差大于 $\epsilon$ 即 $E(h)>\epsilon$ 询刹，且在訓(xùn)練集上表現(xiàn)完美的概率谜嫉，即h與D表現(xiàn)一致的概率為：

$P((h(x_1)=y_1)\land...\land(h(x_m)=y_m) )=(1-P(h(x)\neq y))^m=(1-E(h))^m<(1-\epsilon )^m$

則所有這樣的假設(shè)出現(xiàn)的概率為：

$P((h\in H：E(h)>\epsilon \land \hat{E} (h)=0 )</p><p>令上式不大于<img class=$ 即：? ? ? ? ?? $\vert H \vert e^{-m\epsilon }\leq \delta$

可得：? ? ? ? ? ? ? ? ? ? ? ?? $m\geq \frac{1}{\epsilon } (ln\vert H \vert +ln\frac{1}{\delta } )$

因此，有限假設(shè)空間H都是PAC可學(xué)習(xí)的范抓，所需樣例數(shù)如上式骄恶。

不可分情形

不可分指的是目標(biāo)概念不存在于假設(shè)空間中，此時(shí)學(xué)習(xí)算法L無(wú)法學(xué)得目標(biāo)概念c的 $\epsilon$ 近似匕垫。但當(dāng)假設(shè)空間H給定時(shí)僧鲁，必存在一個(gè)泛化誤差最小的假設(shè)，找出此假設(shè)的 $\epsilon$ 近似亦可象泵。由此引申出“不可知學(xué)習(xí)”寞秃。

不可知PAC可學(xué)習(xí)：令m表示從分布D中獨(dú)立同分布采樣得到的樣例數(shù)， $0<\epsilon ,\delta <1$ 偶惠，對(duì)所有分布D春寿，若存在學(xué)習(xí)算法L和多項(xiàng)式函數(shù)poly()，使得對(duì)任何 $m\geq poly(1/\epsilon ,1/\delta ,size(x),size(c))$ 忽孽，L能從假設(shè)空間H中輸出滿足下式的假設(shè)h：

? ? ? ? ? ? ? ? ? ?? $P(E(h)-\mathop{\min}_{h^,\in H}E(h^,)\leq \epsilon )\geq 1-\delta$

則稱假設(shè)空間H是不可知PAC可學(xué)習(xí)的绑改。

由Hoeffding不等式知單個(gè)假設(shè)誤差概率如下：

$P(\hat{E} (h)-E(h)\geq \epsilon )\leq exp(-2m\epsilon ^2)\\ P(E(h)-\hat{E} (h)\geq \epsilon )\leq exp(-2m\epsilon ^2)\\ P(\vert E(h)-\hat{E} (h) \vert \geq \epsilon )\leq 2exp(-2m\epsilon ^2)$

對(duì)于假設(shè)空間的所有假設(shè)，出現(xiàn)泛化誤差與經(jīng)驗(yàn)誤差之差大于e的概率和為：

? ? ? ? $\sum_{h\in H} P(\vert E(h)-\hat{E} (h) \vert > \epsilon )\leq 2\vert H \vert exp(-2m\epsilon ^2)$

因此兄一，可令不等式右邊小于等于 $\delta$ 厘线，便可求出滿足泛化誤差與經(jīng)驗(yàn)誤差相差小于e所需最少樣本數(shù)，同時(shí)也可求出泛化誤差界出革。

$m\geq \frac{1}{2\epsilon^2 } (ln\vert H \vert +ln\frac{1}{\delta } )\\ P(\vert E(h)-\hat{E} (h) \vert \leq \sqrt{\frac{ln\vert H \vert +ln\frac{2}{\delta }}{2m} } )\geq 1-\delta$

VC維

現(xiàn)實(shí)學(xué)習(xí)任務(wù)面臨的常是無(wú)限假設(shè)空間造壮，欲對(duì)此情形的可學(xué)習(xí)性進(jìn)行研究，需度量假設(shè)空間的復(fù)雜度骂束，此時(shí)可考慮假設(shè)空間的VC維耳璧。

給定假設(shè)空間H和示例集成箫，H中每個(gè)假設(shè)都可對(duì)示例賦予標(biāo)記，標(biāo)記結(jié)果為： $h|_D=\left\{(h( x_1),h( x_2),...,h( x_m)) \right\}$

增長(zhǎng)函數(shù)：對(duì)所有 $m\in N$ 旨枯，假設(shè)空間的增長(zhǎng)函數(shù) $\Pi _H(m)$ 為：

$\Pi _H(m)=\mathop{\max}_{ \left\{ x_1,..x_m \right\}\subseteq X}\vert \left\{ h(x_1),...,h(x_m))|h\in H \right\} \vert$

增長(zhǎng)函數(shù)描述假設(shè)空間對(duì)示例所能賦予標(biāo)記的最大可能結(jié)果數(shù)蹬昌，比如說(shuō)現(xiàn)在數(shù)據(jù)集有兩個(gè)數(shù)據(jù)點(diǎn)，考慮一種二分類的情況召廷，可以將其分類成A或者B凳厢，則可能的值有：AA、AB竞慢、BA和BB先紫，所以這里增長(zhǎng)函數(shù)的值為4〕镏螅可能結(jié)果數(shù)越大遮精，該假設(shè)空間的表示能力越強(qiáng)“芰剩可利用增長(zhǎng)函數(shù)估計(jì)經(jīng)驗(yàn)函數(shù)與泛化誤差的關(guān)系：

對(duì)分：對(duì)二分類問(wèn)題本冲，H中的假設(shè)對(duì)示例賦予標(biāo)記的每種可能結(jié)果稱為對(duì)示例空間的一種對(duì)分（將示例集一分為二）。

打散：當(dāng)假設(shè)空間H作用于大小為m的樣本集D時(shí)劫扒，產(chǎn)生的對(duì)分?jǐn)?shù)量為 $2^m$ 檬洞，即 $\Pi _H(m)=2^m$ ，稱樣本集D被假設(shè)空間H打散沟饥。

上圖顯示添怔，二維空間中的三個(gè)點(diǎn)（不在一條直線上）可被平面上所有直線這個(gè)假設(shè)空間打散，此時(shí) $\Pi _H(m)=8=2^3$ 贤旷，但如下圖的四個(gè)點(diǎn)就不能被這個(gè)假設(shè)空間打散了广料，此時(shí) $\Pi _H(4)=14\neq 2^4$

break point：對(duì)于假設(shè)空間?H 的增長(zhǎng)函數(shù)? $\Pi _H(m)$ ，從 m=1 出發(fā)逐漸增大幼驶，當(dāng)增大到?k時(shí)艾杏，出現(xiàn)? $\Pi _H(m)<2^m$ 的情形，則說(shuō)?k是該假設(shè)空間的break point盅藻。即對(duì)于任何大小為 m(m≥k) 的數(shù)據(jù)集购桑，?H都沒(méi)有辦法打散它。eg當(dāng)假設(shè)空間?H定義為平面上所有直線時(shí)氏淑，其break point就為4勃蜘。

VC維：假設(shè)空間H的VC維是能被H打散的最大示例集的大小，即：

? ? ? ? ? ? ?? $VC(H)=max\left\{m: \Pi _H(m)=2^m \right\}$

根據(jù)此定義夸政，有?VC(H)=k?1，其中k是H的break point榴徐。VC維反映了函數(shù)集的學(xué)習(xí)能力守问，VC維越大匀归，能學(xué)到的模型越復(fù)雜。VC維的大小與學(xué)習(xí)算法無(wú)關(guān)耗帕，與數(shù)據(jù)集的具體分布無(wú)關(guān)穆端，與求解的目標(biāo)函數(shù)也無(wú)關(guān)，只與模型和假設(shè)空間有關(guān)仿便。另外体啰，實(shí)踐中有這樣一個(gè)規(guī)律：一般情況下，假設(shè)空間的VC維約等于假設(shè)自由變量的數(shù)目嗽仪。

周志華《機(jī)器學(xué)習(xí)》

https://blog.csdn.net/u011826404/article/details/73351162

https://tangshusen.me/2018/12/09/vc-dimension/

http://www.flickering.cn/machine_learning/2015/04/vc%E7%BB%B4%E7%9A%84%E6%9D%A5%E9%BE%99%E5%8E%BB%E8%84%89/

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

人面猴
序言：七十年代末荒勇，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子闻坚，更是在濱河造成了極大的恐慌沽翔，老刑警劉巖，帶你破解...
沈念sama閱讀 207,113評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件窿凤，死亡現(xiàn)場(chǎng)離奇詭異仅偎，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)雳殊，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,644評(píng)論 2贊 381
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)橘沥，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人夯秃，你說(shuō)我怎么就攤上這事座咆。” “怎么了寝并？”我有些...
開(kāi)封第一講書(shū)人閱讀 153,340評(píng)論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵箫措，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我衬潦，道長(zhǎng)斤蔓，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 55,449評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任镀岛，我火速辦了婚禮弦牡，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘漂羊。我一直安慰自己驾锰，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 64,445評(píng)論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布走越。她就那樣靜靜地躺著椭豫，像睡著了一般。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上赏酥，一...
開(kāi)封第一講書(shū)人閱讀 49,166評(píng)論 1贊 284
城市分裂傳說(shuō)
那天喳整，我揣著相機(jī)與錄音，去河邊找鬼裸扶。笑死框都，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的呵晨。我是一名探鬼主播魏保，決...
沈念sama閱讀 38,442評(píng)論 3贊 401
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼摸屠！你這毒婦竟也來(lái)了谓罗？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 37,105評(píng)論 0贊 261
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤餐塘，失蹤者是張志新（化名）和其女友劉穎妥衣，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體戒傻，經(jīng)...
沈念sama閱讀 43,601評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡税手，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,066評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了需纳。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片芦倒。...
茶點(diǎn)故事閱讀 38,161評(píng)論 1贊 334
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖不翩，靈堂內(nèi)的尸體忽然破棺而出兵扬，到底是詐尸還是另有隱情，我是刑警寧澤口蝠，帶...
沈念sama閱讀 33,792評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布器钟，位于F島的核電站，受9級(jí)特大地震影響妙蔗，放射性物質(zhì)發(fā)生泄漏傲霸。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,351評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一眉反、第九天我趴在偏房一處隱蔽的房頂上張望昙啄。院中可真熱鬧，春花似錦寸五、人聲如沸梳凛。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,352評(píng)論 0贊 19
一樁弒父案梳杏，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)韧拒。三九已至淹接，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間叛溢，已是汗流浹背蹈集。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,584評(píng)論 1贊 261
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留雇初，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,618評(píng)論 2贊 355
代替公主和親
正文我出身青樓减响，卻偏偏與公主長(zhǎng)得像靖诗，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子支示，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,916評(píng)論 2贊 344