章節(jié)思路

這章是關于機器學習的理論基礎，目的是分析學習任務的困難本質，為學習算法提供理論保證，并根據(jù)分析結果指導算法設計。

簡而言之就是分析：

①學習任務在什么條件可以學習

②它與真相能貼近到什么程度（泛化誤差界）

③算法需要至少達到什么條件

12.1 基礎知識

—— 介紹幾個概念和需要用到的不等式

12.2 PAC學習

—— PAC學習給出一個抽象地刻畫機器學習能力的框架，即以上①②③的基礎框架

12.3 有限假設空間——12.5 Rademacher復雜度

—— 分析①學習任務在不同假設空間復雜度下的可學習，得出②③，其中③一般用樣本復雜度表示

—— 這幾節(jié)是層層遞進，對假設空間的條件不斷放開限制，最終證明都是可學習

—— 以上都是僅考慮學習任務的本質，對所有學習算法都適用

12.6 穩(wěn)定性

—— 通過考慮算法的穩(wěn)定性分析，得到①學習任務在具體學習算法下的可學習

—— 分析了即使算法的輸入（訓練集）改變，仍可證假設空間的可學習

12.1 基礎知識

[1] 泛化誤差：在新樣本上的誤差

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

[2] 經(jīng)驗誤差：學習器在訓練集上的誤差

$\widehat{E}(h ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)$

[3] 兩者聯(lián)系：由于訓練集D為樣本分布的獨立同分布采樣，經(jīng)驗誤差的期望等于其泛化誤差

書內幾個常用不等式在具體推算時會運用到，本章不多做推算過程，可自行了解

12.2 PAC可學習（概率近似正確）

12.2.1 有關概念:

[1] 概念 c ：從樣本空間到標記空間的映射為概念 c

可以將所有實例按真實標記一致的方法完全分開則稱 c 為目標概率，目標概率集合為概率類 C

[2] 假設空間 H ：學習算法學得的概念 h ，其集合為假設空間 H

學習算法：若 H 存在目標概率 c ，則稱該問題對學習算法“可分的”和“一致的”；否則為“不可分的”和“不一致的”

[3] PAC概率近似正確：

因為受到因素制約（等效假設，采樣偶然性）

只能以較大概率（用置信度 δ(0,1) 表示）——近似正確

在某種誤差（用誤差參數(shù) ε(0,1) 表示）下接近目標概率 c ——可能正確

這些概念下文會直接用字母表示，不記得就回到這里看

12.2.2 有關定義：

[1] PAC辨識：

$P(E(h) \leqslant \epsilon) \geqslant 1-\delta$
① h 的泛化誤差在 ε 以內——學的 c 的?ε??近似

②可能性大于等于 1-δ——較大概率學得

【學習算法能從 H 中PAC辨識 C】??

[原理]——為什么h的泛化誤差在 ε 以內

因為只要 h 的泛化誤差盡可能接近于 c 的泛化誤差就好
$P\{E(h)-E(c) \leq \varepsilon \} \geqq 1-\sigma$

c 的泛化誤差一定為0，即 E(c)=0

$P(E(h) \leqslant \epsilon) \geqslant 1-\delta$

[2] PAC可學習：

①若學習算法能從 H 中PAC辨識 C

②樣本數(shù)目滿足多項式函數(shù)（與 ε 、 δ 、 x 和 c 的復雜度有關）

【C 對 H 是PAC可學習的】

[3] PAC學習算法：

①若 C 對 H 而言是PAC可學習的

②學習算法運行時間滿足多項式函數(shù)（當處理每個樣本的時間為常數(shù)，則等價于樣本復雜度）

【C 是高效PAC可學習的，學習算法為 C 的PAC學習算法】

[4] 樣本復雜度：

①滿足PAC學習算法

【多項式函數(shù)的最小 m 為樣本復雜度】

12.2.3 結論：

PAC學習給出了一個抽象地刻畫機器學習能力的框架，基于框架對問題進行理論探討

其中一個問題是H的復雜度

H 的復雜度：

H 與 C 一致：學習算法能力與學習任務恰好匹配，即“恰PAC可學習”，但這是不可能的啦

H 與 C 不一致： H 越大其包含任意目標概念的概率也越大，但從中找到某個具體的目標概念的難度也越大，分為“有限假設空間”和“無限假設空間”

12.3 有限假設空間

12.3.1 可分情形

c 在 H 內——存在 h 在 D 上不會出現(xiàn)標記錯誤，即為 c
? ? ? ? ? ? ? ? ? ? ??

[1] 策略：

①排除任何在 D 上出現(xiàn)標記錯誤的的 h ，得到若干個訓練誤差為0的等效假設

②為了得到唯一假設，至少需要樣本 $\frac{1}{\epsilon}\left(\ln |\mathcal{H}|+\ln \frac{1}{\delta}\right)$

[原理]——為什么樣本需要這么多

保證泛化誤差大于?ε 且在訓練集表現(xiàn)完美的所有假設出現(xiàn)概率之和不大于?δ，可得

$P(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0) 即可推出所需樣本數(shù)量</blockquote>[2] 結論：【可分的有限假設空間都是PAC可學習】h 泛化誤差隨著樣本 m 增多而收斂到0，收斂速度為<img class=$
即是讓那些等效假設中在小誤差以內接近 c 的概率大一點
為滿足這樣的概率，求出 m 的所需

[2] 結論：

【可分的有限假設空間都是PAC可學習】

h 泛化誤差隨著樣本 m 增多而收斂到0，收斂速度為 $O\left(\frac{1}{m}\right)$

12.3.2 不可分情形

c 在 H 外——所有 h 在 D 上都會出現(xiàn)標記錯誤

[1] 策略：

①計算 H 所有 h 的泛化誤差

②找出泛化誤差最小的 h* ，學得 h* 的 ? 近似

[原理]——為什么學得 h* 的 ? 近似

我們可以看回PAC可學習，他是因為 C 存在于 H 中，c 就是最好的近似目標

但當 c 在 H 外，我們就要另尋能夠近似的目標，于是選擇?H 中表現(xiàn)最好的 h ，即近似泛化誤差最小的 h*

[原理]——為什么可以用經(jīng)驗誤差近似泛化誤差

①通過Hoeffding不等式和經(jīng)驗誤差的期望等于其泛化誤差結合，再進行轉換可得

$\widehat{E}(h)-\sqrt{\frac{\ln (2 / \delta)}{2 m}} \leqslant E(h) \leqslant \widehat{E}(h)+\sqrt{\frac{\ln (2 / \delta)}{2 m}}$
闡明了當觀測集樣本數(shù)量 m 足夠大的時候，h 的經(jīng)驗誤差是其泛化誤差很好的近似

②其中在有限假設空間中，對 H 也有要求

$P(|E(h)-\widehat{E}(h)| \leqslant \sqrt{\frac{\ln |\mathcal{H}|+\ln (2 / \delta)}{2 m}}) \geqslant 1-\delta$

其泛化誤差界關于 H 和 m，解釋了當模型很復雜（H很大），就需要很多樣本（m也要大）才能保證經(jīng)驗誤差是泛化誤差很好的近似

[2] 結論：

【不可分的有限假設空間都是不可知PAC可學習】

[3] 不可知PAC可學習:（不可知—— c 不在 H 內）

①若學習算法滿足 $P\left(E(h)-\min _{h^{\prime} \in \mathcal{H}} E\left(h^{\prime}\right) \leqslant \epsilon\right) \geqslant 1-\delta$

? ? h 的泛化誤差 與其 H 中最小泛化誤差的差值不大于?ε?的可能不小于 1-δ

②樣本數(shù)目滿足多項式函數(shù)（與 ε 、 δ 、 x 和 c 的復雜度有關）

【C 對 H 是不可知PAC可學習的】

12.4 無限假設空間——VC維

12.4.1 有關概念

[1] 增長函數(shù)：假設空間 H 對 m 個示例所能賦予標記的最大可能結果數(shù)，表示 H 的復雜度

$\Pi_{\mathcal{H}}(m)=\max _{\left\{x_{1}, \ldots, x_{m}\right\} \subseteq \mathcal{X}}\left|\left\{\left(h\left(\boldsymbol{x}_{1}\right), \ldots, h\left(\boldsymbol{x}_{m}\right)\right) | h \in \mathcal{H}\right\}\right|$

顯然，H 對樣本所能賦予標簽的可能結果數(shù)越多， H 的表示能力就越強，增長函數(shù)可以用來反映 H 的復雜度

注意的是不同數(shù)據(jù)集，增長函數(shù)可能不同

[原理]——為什么要用標記的最大可能結果數(shù)表示 H 的復雜度

因為在無限假設空間下，H 無法計算，但增長函數(shù)描述的標記的可能結果是有限的，所以用增長函數(shù)刻畫 H 的復雜度

比如：只有兩個樣本A和B，有多少 h 對其標記，最終也只有①A和B都是好瓜②A是好瓜，B是壞瓜③A是壞瓜，B是好瓜④A和B都是壞瓜。這四種情況

[2] 估計經(jīng)驗誤差與泛化誤差之間的關系：

$P(|E(h)-\widehat{E}(h)|>\epsilon) \leqslant 4 \Pi_{\mathcal{H}}(2 m) \exp \left(-\frac{m \epsilon^{2}}{8}\right)$

即使在無限假設空間下，在一定條件下，經(jīng)驗誤差也可以近似泛化誤差

[3] 對分：二分類問題中，H 中 h 對 D 中示例賦予標記的每種可能結果成為 D 的一種對分

比如：只有A和B，h 標記A是好瓜B是壞瓜，這就是一種對分

[4] 打散：若 H 能實現(xiàn) D 所有對分，即可以產(chǎn)生所有的預測結果，則 D 能被 H 打散

12.4.2 VC維

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

書中例子能較好解釋

[1] VC維與增長函數(shù)的定量關系

[2] 增長函數(shù)的上界

[3] VC維的泛化誤差界

[1]-[3] 的推導過程可自行了解

其中VC維的泛化誤差界只與 m 有關，收斂速度為 $O\left(\frac{1}{\sqrt{m}}\right)$ ，與數(shù)據(jù)分布和樣例集無關，因此，基于VC維的泛化誤差界是分布無關、數(shù)據(jù)獨立，使得其可學習型分析結果具有一定的普適性

[原理]——為什么要用VC維推出泛化誤差界

在12.4.1中我們得到經(jīng)驗誤差與泛化誤差之間的關系，其泛化誤差界是有關增長函數(shù)的。于是我們特意定義VC維，用VC維與增長函數(shù)的關系，使得可以用具體數(shù)值 d 表示增長函數(shù)，以便我們求出更具體的泛化誤差界

[4] 結論：

【任何VC維有限的假設空間 H 都是（不可知）PAC可學習的】

①學習算法滿足經(jīng)驗風險最小化原則（ERM）

②若假設空間的最小泛化誤差為0 ，即 c 包含在假設空間中，則是PAC可學習；若最小泛化誤差不為0，則稱為不可知PAC可學習

經(jīng)驗風險最小化原則（ERM）

經(jīng)驗風險最小的模型是最優(yōu)的模型

12.5 Rademacher復雜度

12.5.1 Rademacher復雜度

[1] 函數(shù)空間關于集合的Rademacher復雜度

[2]?函數(shù)空間關于分布的Rademacher復雜度

衡量了函數(shù)空間與隨機噪音在集合/分布的相關性

[原理]——為什么要引入Rademacher復雜度

①與VC維中引入增長函數(shù)相似，是一種刻畫假設空間復雜度的途徑

②VC維的泛化誤差界是分布無關、數(shù)據(jù)獨立不同，因此缺少普適性。Rademacher復雜度則考慮了數(shù)據(jù)分布，能讓泛化誤差更緊一點

[原理]——為什么引入隨機噪音

考慮了數(shù)據(jù)分布，會發(fā)現(xiàn)樣例中有因為隨機因素，變得不真實的標記，于是我們與其選擇 H 中在訓練集表現(xiàn)最好的 h ，不如選擇事先考慮隨即噪音影響的 h?

12.5.2 基于Rademacher復雜度的泛化誤差界

[1] 回歸問題

[2] 二分類問題

我們由以上基于Rademacher復雜度的泛化誤差界與基于VC維泛化誤差界比較，明顯發(fā)現(xiàn)Rademacher復雜度的泛化誤差界考慮了數(shù)據(jù)分布和樣例集，類似對問題“量身定制”，因此通常比VC維泛化誤差更緊一點

12.5.3 Rademacher復雜度與增長函數(shù)的關系

由此又可推斷出基于VC維得泛化誤差界

12.6 穩(wěn)定性

12.6.1 有關概念

[1] 訓練集D的變化：

[2] 損失函數(shù)

[原理]——為什么要引入穩(wěn)定性
無論基于VC維還是Rademacher復雜度推導泛化誤差界，結果都與具體算法無關，使得能夠脫離學習算法設計考慮學習問題本質，但希望獲得算法有關分析結果，就要引用穩(wěn)定性

[原理]——怎么測量穩(wěn)定性

?穩(wěn)定性考察算法在輸入（訓練集）發(fā)生變化時，輸出是否會隨之發(fā)生較大的變化。

[1]——考察算法在輸入（訓練集）發(fā)生變化時

[2] ——輸出是否會隨之發(fā)生較大的變化

12.6.2 均勻穩(wěn)定性

$\left|\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\left.\mathfrak{L}_{D}\right|_{\mathfrak{t}}, \boldsymbol{z}\right)\right| \leqslant \beta, \quad i=1,2, \ldots, m$

若學習算法滿足以上式子，則稱之為關于損失函數(shù)滿足 β-均勻穩(wěn)定性，給出了穩(wěn)定性的判斷依據(jù)

[原理]——為什么不計算替代示例的穩(wěn)定性

$\begin{equation}\begin{array}{l}\quad\left|\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\mathfrak{L}_{D^{i}}, \boldsymbol{z}\right)\right| \\\leqslant\left|\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\mathfrak{L}_{D} | i, \boldsymbol{z}\right)\right|+\left|\ell\left(\mathfrak{L}_{D^{i}, z}\right)-\ell\left(\mathfrak{L}_{D} | i, z\right)\right| \\\leqslant 2 \beta\end{array}\end{equation}$
移除示例的穩(wěn)定性包含替代示例的穩(wěn)定性，所以我們直接用移除示例的穩(wěn)定性就同時包含了訓練集的兩者變化

12.6.3 基于穩(wěn)定性的泛化誤差界

$\begin{aligned}&\ell(\mathcal{L}, \mathcal{D}) \leq \hat{\ell}(\mathcal{L}, D)+2 \beta+(4 m \beta+M) \sqrt{\frac{\ln (1 / \delta)}{2 m}}\\&\ell(\mathcal{L}, \mathcal{D}) \leq \ell_{l o o}(\mathcal{L}, D)+\beta+(4 m \beta+M) \sqrt{\frac{\ln (1 / \delta)}{2 m}}\end{aligned}$

①損失函數(shù)有界 $0 \leqslant l\left(\mathfrak{L}_{D}, z\right) \leqslant M$
②算法滿足損失函數(shù)的β-均勻穩(wěn)定性
③對存在樣本的示例集

至少有1-δ的概率滿足以上泛化誤差界

若 $\beta=O\left(\frac{1}{m}\right)$ ，可保證收斂率為 $O\left(\frac{1}{\sqrt{m}}\right)$ ，即與基于VC維和Rademacher復雜度一樣

12.6.4 結論

【學習算法是ERM且穩(wěn)定的，則假設空間可學習】

①假設 $β\sqrt{m} \rightarrow 0$ 且 $β=\frac{1}{m}$ ，保證穩(wěn)定的學習算法具有一定的泛化能力，即經(jīng)驗損失收斂于泛化損失
②學習算法是ERM

[原理]——為什么學習算法穩(wěn)定性能導出假設空間的可學習性

兩者通過損失函數(shù)聯(lián)系

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

《西瓜書》第12章計算學習理論

《西瓜書》第12章計算學習理論

章節(jié)思路

12.1 基礎知識

12.2 PAC學習

12.3 有限假設空間——12.5 Rademacher復雜度

12.6 穩(wěn)定性

12.1 基礎知識