《西瓜書》第12章計(jì)算學(xué)習(xí)理論

章節(jié)思路

這章是關(guān)于機(jī)器學(xué)習(xí)的理論基礎(chǔ)，目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)嫉柴，為學(xué)習(xí)算法提供理論保證，并根據(jù)分析結(jié)果指導(dǎo)算法設(shè)計(jì)。

簡而言之就是分析：

①學(xué)習(xí)任務(wù)在什么條件可以學(xué)習(xí)

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

③算法需要至少達(dá)到什么條件

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

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

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

—— PAC學(xué)習(xí)給出一個(gè)抽象地刻畫機(jī)器學(xué)習(xí)能力的框架嘹吨，即以上①②③的基礎(chǔ)框架

12.3 有限假設(shè)空間——12.5 Rademacher復(fù)雜度

—— 分析①學(xué)習(xí)任務(wù)在不同假設(shè)空間復(fù)雜度下的可學(xué)習(xí)，得出②③境氢，其中③一般用樣本復(fù)雜度表示

—— 這幾節(jié)是層層遞進(jìn)蟀拷，對假設(shè)空間的條件不斷放開限制碰纬，最終證明都是可學(xué)習(xí)

—— 以上都是僅考慮學(xué)習(xí)任務(wù)的本質(zhì)，對所有學(xué)習(xí)算法都適用

12.6 穩(wěn)定性

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

—— 分析了即使算法的輸入（訓(xùn)練集）改變悦析，仍可證假設(shè)空間的可學(xué)習(xí)

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

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

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

[2] 經(jīng)驗(yàn)誤差：學(xué)習(xí)器在訓(xùn)練集上的誤差

$\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)系：由于訓(xùn)練集D為樣本分布的獨(dú)立同分布采樣，經(jīng)驗(yàn)誤差的期望等于其泛化誤差

書內(nèi)幾個(gè)常用不等式在具體推算時(shí)會(huì)運(yùn)用到此衅，本章不多做推算過程强戴，可自行了解

12.2 PAC可學(xué)習(xí)（概率近似正確）

12.2.1 有關(guān)概念:

[1] 概念 c ：從樣本空間到標(biāo)記空間的映射為概念 c

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

[2] 假設(shè)空間 H ：學(xué)習(xí)算法學(xué)得的概念 h 挡鞍，其集合為假設(shè)空間 H

學(xué)習(xí)算法：若 H 存在目標(biāo)概率 c 骑歹，則稱該問題對學(xué)習(xí)算法“可分的”和“一致的”；否則為“不可分的”和“不一致的”

[3] PAC概率近似正確：

因?yàn)槭艿揭蛩刂萍s（等效假設(shè)墨微，采樣偶然性）

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

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

這些概念下文會(huì)直接用字母表示道媚，不記得就回到這里看

12.2.2 有關(guān)定義：

[1] PAC辨識(shí)：

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

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

【學(xué)習(xí)算法能從 H 中PAC辨識(shí) C】??

[原理]——為什么h的泛化誤差在 ε 以內(nèi)

因?yàn)橹灰?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可學(xué)習(xí)：

①若學(xué)習(xí)算法能從 H 中PAC辨識(shí) C

②樣本數(shù)目滿足多項(xiàng)式函數(shù)（與 ε 翘县、 δ 最域、 x 和 c 的復(fù)雜度有關(guān)）

【C 對 H 是PAC可學(xué)習(xí)的】

[3] PAC學(xué)習(xí)算法：

①若 C 對 H 而言是PAC可學(xué)習(xí)的

②學(xué)習(xí)算法運(yùn)行時(shí)間滿足多項(xiàng)式函數(shù)（當(dāng)處理每個(gè)樣本的時(shí)間為常數(shù)，則等價(jià)于樣本復(fù)雜度）

【C 是高效PAC可學(xué)習(xí)的锈麸，學(xué)習(xí)算法為 C 的PAC學(xué)習(xí)算法】

[4] 樣本復(fù)雜度：

①滿足PAC學(xué)習(xí)算法

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

12.2.3 結(jié)論：

PAC學(xué)習(xí)給出了一個(gè)抽象地刻畫機(jī)器學(xué)習(xí)能力的框架镀脂，基于框架對問題進(jìn)行理論探討

其中一個(gè)問題是H的復(fù)雜度

H 的復(fù)雜度：

H 與 C 一致：學(xué)習(xí)算法能力與學(xué)習(xí)任務(wù)恰好匹配，即“恰PAC可學(xué)習(xí)”忘伞，但這是不可能的啦

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

12.3 有限假設(shè)空間

12.3.1 可分情形

c 在 H 內(nèi)——存在 h 在 D 上不會(huì)出現(xiàn)標(biāo)記錯(cuò)誤虑省，即為 c
? ? ? ? ? ? ? ? ? ? ??

[1] 策略：

①排除任何在 D 上出現(xiàn)標(biāo)記錯(cuò)誤的的 h 匿刮，得到若干個(gè)訓(xùn)練誤差為0的等效假設(shè)

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

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

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

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

[2] 結(jié)論：

【可分的有限假設(shè)空間都是PAC可學(xué)習(xí)】

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

12.3.2 不可分情形

c 在 H 外——所有 h 在 D 上都會(huì)出現(xiàn)標(biāo)記錯(cuò)誤

[1] 策略：

①計(jì)算 H 所有 h 的泛化誤差

②找出泛化誤差最小的 h* 光羞，學(xué)得 h* 的 ? 近似

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

我們可以看回PAC可學(xué)習(xí)，他是因?yàn)?C 存在于 H 中怀大，c 就是最好的近似目標(biāo)

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

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

①通過Hoeffding不等式和經(jīng)驗(yàn)誤差的期望等于其泛化誤差結(jié)合潜慎，再進(jìn)行轉(zhuǎn)換可得

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

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

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

其泛化誤差界關(guān)于 H 和 m铐炫，解釋了當(dāng)模型很復(fù)雜（H很大）垒手，就需要很多樣本（m也要大）才能保證經(jīng)驗(yàn)誤差是泛化誤差很好的近似

[2] 結(jié)論：

【不可分的有限假設(shè)空間都是不可知PAC可學(xué)習(xí)】

[3] 不可知PAC可學(xué)習(xí):（不可知—— c 不在 H 內(nèi)）

①若學(xué)習(xí)算法滿足 $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ù)目滿足多項(xiàng)式函數(shù)（與 ε 、 δ 倒信、 x 和 c 的復(fù)雜度有關(guān)）

【C 對 H 是不可知PAC可學(xué)習(xí)的】

12.4 無限假設(shè)空間——VC維

12.4.1 有關(guān)概念

[1] 增長函數(shù)：假設(shè)空間 H 對 m 個(gè)示例所能賦予標(biāo)記的最大可能結(jié)果數(shù)科贬，表示 H 的復(fù)雜度

$\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 對樣本所能賦予標(biāo)簽的可能結(jié)果數(shù)越多鳖悠， H 的表示能力就越強(qiáng)榜掌，增長函數(shù)可以用來反映 H 的復(fù)雜度

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

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

因?yàn)樵跓o限假設(shè)空間下乘综，H 無法計(jì)算憎账，但增長函數(shù)描述的標(biāo)記的可能結(jié)果是有限的，所以用增長函數(shù)刻畫 H 的復(fù)雜度

比如：只有兩個(gè)樣本A和B卡辰，有多少 h 對其標(biāo)記鼠哥，最終也只有①A和B都是好瓜②A是好瓜，B是壞瓜③A是壞瓜看政，B是好瓜④A和B都是壞瓜。這四種情況

[2] 估計(jì)經(jīng)驗(yàn)誤差與泛化誤差之間的關(guān)系：

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

即使在無限假設(shè)空間下抄罕，在一定條件下允蚣，經(jīng)驗(yàn)誤差也可以近似泛化誤差

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

比如：只有A和B呆贿，h 標(biāo)記A是好瓜B是壞瓜嚷兔，這就是一種對分

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

12.4.2 VC維

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

書中例子能較好解釋

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

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

[3] VC維的泛化誤差界

[1]-[3] 的推導(dǎo)過程可自行了解

其中VC維的泛化誤差界只與 m 有關(guān)冒晰，收斂速度為 $O\left(\frac{1}{\sqrt{m}}\right)$ ，與數(shù)據(jù)分布和樣例集無關(guān)竟块，因此壶运，基于VC維的泛化誤差界是分布無關(guān)、數(shù)據(jù)獨(dú)立浪秘，使得其可學(xué)習(xí)型分析結(jié)果具有一定的普適性

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

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

[4] 結(jié)論：

【任何VC維有限的假設(shè)空間 H 都是（不可知）PAC可學(xué)習(xí)的】

①學(xué)習(xí)算法滿足經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則（ERM）

②若假設(shè)空間的最小泛化誤差為0 夺衍，即 c 包含在假設(shè)空間中狈谊，則是PAC可學(xué)習(xí)；若最小泛化誤差不為0，則稱為不可知PAC可學(xué)習(xí)

經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則（ERM）

經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的模型是最優(yōu)的模型

12.5 Rademacher復(fù)雜度

12.5.1 Rademacher復(fù)雜度

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

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

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

[原理]——為什么要引入Rademacher復(fù)雜度

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

②VC維的泛化誤差界是分布無關(guān)壁榕、數(shù)據(jù)獨(dú)立不同，因此缺少普適性丧裁。Rademacher復(fù)雜度則考慮了數(shù)據(jù)分布护桦，能讓泛化誤差更緊一點(diǎn)

[原理]——為什么引入隨機(jī)噪音

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

12.5.2 基于Rademacher復(fù)雜度的泛化誤差界

[1] 回歸問題

[2] 二分類問題

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

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

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

12.6 穩(wěn)定性

12.6.1 有關(guān)概念

[1] 訓(xùn)練集D的變化：

[2] 損失函數(shù)

[原理]——為什么要引入穩(wěn)定性
無論基于VC維還是Rademacher復(fù)雜度推導(dǎo)泛化誤差界哟绊，結(jié)果都與具體算法無關(guān)因妙，使得能夠脫離學(xué)習(xí)算法設(shè)計(jì)考慮學(xué)習(xí)問題本質(zhì)，但希望獲得算法有關(guān)分析結(jié)果票髓，就要引用穩(wěn)定性

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

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

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

[2] ——輸出是否會(huì)隨之發(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$

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

[原理]——為什么不計(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)定性就同時(shí)包含了訓(xù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復(fù)雜度一樣

12.6.4 結(jié)論

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

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

[原理]——為什么學(xué)習(xí)算法穩(wěn)定性能導(dǎo)出假設(shè)空間的可學(xué)習(xí)性

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

最后編輯于：2020.03.23 13:55:58

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市缎岗，隨后出現(xiàn)的幾起案子静尼，更是在濱河造成了極大的恐慌，老刑警劉巖传泊，帶你破解...
沈念sama閱讀 216,470評論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件茅郎，死亡現(xiàn)場離奇詭異，居然都是意外死亡或渤，警方通過查閱死者的電腦和手機(jī)系冗，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,393評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來薪鹦，“玉大人掌敬，你說我怎么就攤上這事惯豆。” “怎么了奔害？”我有些...
開封第一講書人閱讀 162,577評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵楷兽，是天一觀的道長。經(jīng)常有香客問我华临，道長芯杀，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,176評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任雅潭，我火速辦了婚禮揭厚，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘扶供。我一直安慰自己筛圆，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,189評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布椿浓。她就那樣靜靜地躺著太援，像睡著了一般。火紅的嫁衣襯著肌膚如雪扳碍。梳的紋絲不亂的頭發(fā)上提岔，一...
開封第一講書人閱讀 51,155評論 1贊 299
城市分裂傳說
那天，我揣著相機(jī)與錄音笋敞，去河邊找鬼唧垦。笑死，一個(gè)胖子當(dāng)著我的面吹牛液样，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播巧还，決...
沈念sama閱讀 40,041評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼鞭莽，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了麸祷？” 一聲冷哼從身側(cè)響起澎怒，我...
開封第一講書人閱讀 38,903評論 0贊 274
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎阶牍，沒想到半個(gè)月后喷面，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,319評論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡走孽，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,539評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年惧辈，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片磕瓷。...
茶點(diǎn)故事閱讀 39,703評論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡盒齿，死狀恐怖念逞，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情边翁，我是刑警寧澤翎承，帶...
沈念sama閱讀 35,417評論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站符匾，受9級(jí)特大地震影響叨咖，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜啊胶，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,013評論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一甸各、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧创淡，春花似錦痴晦、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,664評論 0贊 22
一樁弒父案誊酌，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至露乏，卻和暖如春碧浊，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背瘟仿。一陣腳步聲響...
開封第一講書人閱讀 32,818評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工箱锐，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人劳较。一個(gè)月前我還...
沈念sama閱讀 47,711評論 2贊 368
代替公主和親
正文我出身青樓驹止，卻偏偏與公主長得像，于是被迫代替她去往敵國和親观蜗。傳聞我的和親對象是個(gè)殘疾皇子臊恋，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,601評論 2贊 353

《西瓜書》第12章 計(jì)算學(xué)習(xí)理論

章節(jié)思路

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

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

12.3 有限假設(shè)空間——12.5 Rademacher復(fù)雜度

12.6 穩(wěn)定性

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

12.2 PAC可學(xué)習(xí)（概率近似正確）

12.2.1 有關(guān)概念:

12.2.2 有關(guān)定義：

12.2.3 結(jié)論：

12.3 有限假設(shè)空間

12.3.1 可分情形

12.3.2 不可分情形

12.4 無限假設(shè)空間——VC維

12.4.1 有關(guān)概念

12.4.2 VC維

12.5 Rademacher復(fù)雜度

12.5.1 Rademacher復(fù)雜度

12.5.2 基于Rademacher復(fù)雜度的泛化誤差界

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

12.6 穩(wěn)定性

12.6.1 有關(guān)概念

12.6.2 均勻穩(wěn)定性

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

12.6.4 結(jié)論

推薦閱讀更多精彩內(nèi)容

《西瓜書》第12章計(jì)算學(xué)習(xí)理論