p267 - p292
今天一定要早睡！= =
這一章挺枯燥的= =

第12章 計(jì)算學(xué)習(xí)理論

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

計(jì)算學(xué)習(xí)理論研究的是關(guān)于通過(guò)“計(jì)算”來(lái)進(jìn)行“學(xué)習(xí)”的理論
即關(guān)于機(jī)器學(xué)習(xí)的理論基礎(chǔ)
目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)，并根據(jù)分析結(jié)果指導(dǎo)算法設(shè)計(jì)。

泛化誤差 vs 經(jīng)驗(yàn)誤差 數(shù)學(xué)定義（p267）
若樣本符合獨(dú)立同分布，則經(jīng)驗(yàn)誤差的期望等于其泛化誤差。

定義泛化誤差的上界：稱為誤差參數(shù)

對(duì)任意兩個(gè)映射，可通過(guò)其“不合”來(lái)度量他們之間的差別（見(jiàn)p267）

給出了三個(gè)常用不等式
Jensen不等式、Hoeffding不等式、McDiarmid不等式。
見(jiàn)p268

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

PAC：概率近似正確學(xué)習(xí)理論。

PAC學(xué)習(xí)給出了一個(gè)抽象刻畫機(jī)器學(xué)習(xí)能力的框架。

學(xué)習(xí)算法是否“可分”？

給出了幾個(gè)定義：
定義12.1 PAC辨識(shí)
定義12.2 PAC可學(xué)習(xí)
定義12.3 PAC學(xué)習(xí)算法
定義12.4 樣本復(fù)雜度

12.3 有限假設(shè)空間

12.3.1 可分

可分意味著目標(biāo)概念c屬于假設(shè)空間H
得到一個(gè)結(jié)論：
有限假設(shè)空間H都是PAC可學(xué)習(xí)的。

12.3.2 不可分情形

當(dāng)c不屬于H時(shí)，學(xué)習(xí)算法是無(wú)法學(xué)得目標(biāo)概念c的ε近似。
但是當(dāng)假設(shè)空間H給定時(shí)， 其中必存在一個(gè)泛化誤差最小的假設(shè)。
找到這個(gè)假設(shè)也是個(gè)不錯(cuò)的選擇。
這稱為“不可知學(xué)習(xí)”

12.4 VC維

現(xiàn)實(shí)中任務(wù)大多是無(wú)限假設(shè)空間。
如實(shí)數(shù)中的所有區(qū)間。
這時(shí)需要度量假設(shè)空間的復(fù)雜度，用到的是"VC維“

概念1.增長(zhǎng)函數(shù)

表示假設(shè)空間H對(duì)m個(gè)示例所能賦予標(biāo)記的最大可能結(jié)果數(shù)。

概念2.對(duì)分

H中的假設(shè)對(duì)D中示例賦予標(biāo)記的每種可能結(jié)果稱為對(duì)D的一種"對(duì)分"

概念3.打散

若假設(shè)空間H能實(shí)現(xiàn)示例集D上的所有對(duì)分，則稱D能被H打散。

大概念.VC維

H的VC維是能被H打散的最大示例集的大小。
VC維的定義與數(shù)據(jù)分布D無(wú)關(guān)！

p275的兩個(gè)例子。很形象。
例12.1 實(shí)數(shù)域中的區(qū)間[a,b]
例12.2 二維實(shí)平面上的線性劃分

p275-278一堆定理。
定理12.4 任何VC維有限的假設(shè)空間H都是不可知PAC可學(xué)習(xí)的。

12.5 Rademacher復(fù)雜度

VC維不考慮數(shù)據(jù)分布，使得普適。但對(duì)于特殊情況就很不好。

Rademacher復(fù)雜度，另一種刻畫假設(shè)空間復(fù)雜度的途徑。
它在一定程度上考慮了數(shù)據(jù)分布。
p279 - 284

12.6 穩(wěn)定性

基于12.4和12.5來(lái)推到泛化誤差界，所得到的結(jié)果都和具體的學(xué)習(xí)算法無(wú)關(guān)。
但在另一方面，若希望獲得與算法有關(guān)的分析結(jié)果
可以考慮“穩(wěn)定性”。

穩(wěn)定性考慮的是
輸入發(fā)生變化時(shí)，輸出是否會(huì)隨之發(fā)生較大的變化。

p285定義了兩種變化方式，與穩(wěn)定性的定義。

休息一會(huì)兒

計(jì)算學(xué)習(xí)理論是機(jī)器學(xué)習(xí)的一個(gè)分支，它可認(rèn)為是機(jī)器學(xué)習(xí)與理論計(jì)算機(jī)科學(xué)的交叉