內容導讀

可分意味著目標概念c屬於假設空間H 得到一個結論： 有限假設空間H都是PAC可學習的。現實中任務大多是無限假設空間。概念1.增長函數 表示假設空間H對m個示例所能賦予標記的最大可能結果數。定理12.4 任何VC維有限的假設空間H都是不可知PAC可學習的。基於12.4和12.5來推到泛化誤差界，所得到的結果都和具體的學習算法無關。穩定性考慮的是 輸入發生變化時，輸出是否會隨之發生較大的變化。

p267 - p292

今天一定要早睡！= =

這一章挺枯燥的= =

第12章 計算學習理論

12.1 基礎知識

計算學習理論研究的是關於通過“計算”來進行“學習”的理論

即關於機器學習的理論基礎

目的是分析學習任務的困難本質，並根據分析結果指導算法設計。

泛化誤差 vs 經驗誤差 數學定義（p267）

若樣本符合獨立同分布，則經驗誤差的期望等於其泛化誤差。

定義泛化誤差的上界：稱為誤差參數

對任意兩個映射，可通過其“不合”來度量他們之間的差別（見p267）

給出了三個常用不等式

Jensen不等式、Hoeffding不等式、McDiarmid不等式。

見p268

12.2 PAC學習

PAC：概率近似正確學習理論。

PAC學習給出了一個抽象刻畫機器學習能力的框架。

學習算法是否“可分”？

給出了幾個定義：

定義12.1 PAC辨識

定義12.2 PAC可學習

定義12.3 PAC學習算法

定義12.4 樣本複雜度

12.3 有限假設空間

12.3.1 可分

可分意味著目標概念c屬於假設空間H

得到一個結論：

有限假設空間H都是PAC可學習的。

12.3.2 不可分情形

當c不屬於H時，學習算法是無法學得目標概念c的ε近似。

但是當假設空間H給定時， 其中必存在一個泛化誤差最小的假設。

找到這個假設也是個不錯的選擇。

這稱為“不可知學習”

12.4 VC維

現實中任務大多是無限假設空間。

如實數中的所有區間。

這時需要度量假設空間的複雜度，用到的是"VC維“

概念1.增長函數

表示假設空間H對m個示例所能賦予標記的最大可能結果數。

概念2.對分

H中的假設對D中示例賦予標記的每種可能結果稱為對D的一種"對分"

概念3.打散

若假設空間H能實現示例集D上的所有對分，則稱D能被H打散。

大概念.VC維

H的VC維是能被H打散的最大示例集的大小。

VC維的定義與數據分佈D無關！

p275的兩個例子。很形象。

例12.1 實數域中的區間[a,b]

例12.2 二維實平面上的線性劃分

p275-278一堆定理。

定理12.4 任何VC維有限的假設空間H都是不可知PAC可學習的。

12.5 Rademacher複雜度

VC維不考慮數據分佈，使得普適。但對於特殊情況就很不好。

Rademacher複雜度，另一種刻畫假設空間複雜度的途徑。

它在一定程度上考慮了數據分佈。

p279 - 284

12.6 穩定性

基於12.4和12.5來推到泛化誤差界，所得到的結果都和具體的學習算法無關。

但在另一方面，若希望獲得與算法有關的分析結果

可以考慮“穩定性”。

穩定性考慮的是

輸入發生變化時，輸出是否會隨之發生較大的變化。

p285定義了兩種變化方式，與穩定性的定義。

休息一會兒

計算學習理論是機器學習的一個分支，它可認為是機器學習與理論計算機科學的交叉