> For the complete documentation index, see [llms.txt](https://blog.cweihang.io/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.cweihang.io/ml/zzh_ml_notes/melon/ch12.md).

# 计算学习理论

## 第12章 计算学习理论

* Page267: 计算学习理论（computational learning theory）

  计算学习理论研究的是关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
* Page268: Jensen不等式

  $$f(\mathbb{E}(x)) \leqq \mathbb{E}(f(x))$$

  期望的函数小于函数的期望
* Page268: Hoeffding不等式

  若$$x\_1,x\_2,...,x\_m$$为$$m$$个独立随机变量，且满足$$0\leqq x\_i\leqq 1$$，则对于任意$$\epsilon\geqq 0$$有： $$P(\frac{1}{m}\sum\_{i=1}^{m}x\_i-\frac{1}{m}\sum\_{i=1}^m\mathbb{E}(x\_i)\geqq \epsilon)\leqq exp(-2m\epsilon^2)$$ $$P(\mid \frac{1}{m}\sum\_{i=1}^{m}x\_i-\frac{1}{m}\sum\_{i=1}^m\mathbb{E}(x\_i)\mid \geqq \epsilon)\leqq 2exp(-2m\epsilon^2)$$
* Page268: McDiarmid 不等式

  若$$x\_1,x\_2,...,x\_m$$为$$m$$个独立随机变量，且对任意$$1\leqq i\leqq m$$，函数$$f$$满足

  $$\sum\_{x\_1,x\_2,...,x\_m, x^{'}*i } |f(x\_1,...,x\_m) - f(x\_1, ... , x*{i-1}, x^{'}*i, x*{i+1}, ..., x\_m)| \leqq c\_i$$，

  则对任意$$\epsilon\geqq 0$$，有 $$P(f(x\_1,...,x\_m)-E(f(x\_1,...,x\_m))\geqq \epsilon)\leqq exp(\frac{-2\epsilon^2}{\sum\_i c\_i^2})$$ $$P(\mid f(x\_1,...,x\_m)-E(f(x\_1,...,x\_m))\mid \geqq \epsilon)\leqq exp(\frac{-2\epsilon^2}{\sum\_i c\_i^2})$$
* Page268: 概率近似正确
* Page268: 概念类(concept class)

  令c表示概念，这是从样本空间$$\mathcal{X}$$到标记空间$$\mathcal{Y}$$的映射，它决定示例x的真实标记y，若对任何样例(x,y)有c(x)=y成立，则称c为目标概念，所有我们希望学得的目标概念所构成的集合称为概念类，用符号$$\mathcal{C}$$表示。
* Page268: 假设空间（hypothesis space）

给定学习算法$$\mathfrak{L}$$，它所考虑的所有可能概念的集合称为“假设空间”，用符号$$\mathcal{H}$$表示。由于学习算法事先并不知道概念类的真实存在，因此假设空间和概念类往往不同。

* Page269: PAC辨识(PAC Identify)

  对于$$0<\epsilon, \delta<1$$，所有$$c\in\mathcal{C}$$和分布$$\mathcal{D}$$，若存在学习算法$$\mathfrak{L}$$，其输出假设$$h\in\mathcal{H}$$满足

  $$P(E(h)\leqq \epsilon)\geqq 1-\delta$$

  则称学习算法$$\mathfrak{L}$$能从假设空间$$\mathcal{H}$$中PAC辨识概念类$$\mathcal{C}$$，这样的学习算法$$\mathfrak{L}$$能从假设空间$$\mathcal{H}$$中PAC辨识概念类$$\mathcal{C}$$.
* Page269: PAC可学习(PAC Learnable)

  令$$m$$表示从分布$$\mathcal{D}$$中独立同分布采样得到的样例数目，$$0<\epsilon,\delta<1$$，对所有分布$$\mathcal{D}$$，若存在学习算法$$\mathfrak{L}$$和多项式函数$$poly(.,.,.,.)$$，使得对于任何$$m\geqq poly(1/\epsilon,1/\delta,size(x),size(c))$$, $$\mathfrak{L}$$能从假设空间$$\mathcal{H}$$中PAC辨识概念类$$\mathcal{C}$$，则称概念类$$\mathcal{C}$$对假设空间$$\mathcal{H}$$而言是PAC可学习的，也简称概念类$$\mathcal{C}$$是PAC可学习的。对于计算机算法来说，必须考虑时间复杂度，于是：
* Page270: PAC学习算法（PAC Learning Algorithm）

  若学习算法$$\mathfrak{L}$$使概念类$$\mathcal{C}$$为PAC可学习的，且$$\mathfrak{L}$$的运行时间也是多项式函数$$poly(1/\epsilon,1/\delta,size(x),size(c))$$，则称概念类$$\mathcal{C}$$是高效PAC可学习的，称$$\mathfrak{L}$$为概念类$$\mathcal{C}$$的PAC学习算法。
* Page269: 时间复杂度

  假定学习算法$$\mathfrak{L}$$处理每个样本的时间为常数，则$$\mathfrak{L}$$的时间复杂度等价于样本复杂度。
* Page270: 样本复杂度

  满足PAC学习算法$$\mathfrak{L}$$所需的$$m\geqq poly(1/\epsilon,1/\delta,size(x),size(c))$$中最小的m，称为学习算法$$\mathfrak{L}$$的样本复杂度。
* Page269: 不可分(272)(non-seperable)

  对于较为困难的学习问题，目标概念$$c$$往往不存在于假设空间$$\mathcal{H}$$中，假定对于任何$$h\in\mathcal{H}, \hat{E(h)}\neq0$$，也就是说，$$\mathcal{H}$$中的任意一个假设都会在训练集上出现或多或少的错误。$$\mathcal{H}$$中不存在任何假设能将所有示例完全正确分开，则称该问题对于学习算法$$\mathfrak{L}$$是不可分的，亦称不一致的。
* Page269: 不一致(non-consistent)

  即不可分。
* Page269: 可分(270)(seperable)

  可分情形意味着目标概念$$c$$属于假设空间$$\mathcal{H}$$， 即 $$c\in\mathcal{H}$$，$$\mathcal{H}$$中存在假设能将所有示例按与真实标记一致的方式完全分开，我们将该问题对学习算法$$\mathfrak{L}$$是可分的，亦称一致的。
* Page270: 恰PAC可学习(properly PAC learnable)

  若学习算法$$\mathfrak{L}$$使概念类$$\mathcal{C}$$为PAC可学习的，且$$\mathfrak{L}$$的运行时间也是多项式函数$$poly(1/\epsilon, 1/\delta, size(x), size(c))$$，则称概念类$$\mathcal{C}$$是高效PAC可学习的，称$$\mathfrak{L}$$为概念类$$\mathcal{C}$$的PAC学习算法。若在PAC学习中假设空间与概念类完全相同，称为恰PAC可学习，这意味着学习算法的能力与学习任务恰好匹配。
* Page270: 有限假设空间

  一般而言，$$\mathcal{H}$$越大，其包含任意目标概念的可能性越大，但从中找到某个具体概念的难度也越大，$$|\mathcal{H}|$$有限时，我们称$$\mathcal{H}$$为有限假设空间，否则称为“无限假设空间”。
* Page273: 不可知PAC可学习(agnostic PAC learnable)

  令$$m$$表示从分布$$\mathcal{D}$$中独立同分布采样得到的样例数目，$$1<\epsilon, \delta < 1$$，对所有分布$$\mathcal{D}$$，若存在学习算法$$\mathcal{L}$$和多项式函数$$poly(.,.,.,.)$$，使得对于任何$$m\leqq poly(1/\epsilon, 1/\delta, size(x), size(c))$$，$$\mathfrak{L}$$能从假设空间$$\mathcal{H}$$中输出满足$$P(E(h)-min\_{h^{'} \in \mathcal{H}})\leqq\epsilon\geqq 1 - \delta$$的假设h,则称假设空间$$\mathcal{H}$$是不可知PAC可学习的。
* Page273: 增长函数

  给定假设空间$$\mathcal{H}$$和示例集$$D={x\_1, x\_2, ..., x\_m}$$，$$\mathcal{H}$$中每个假设h都能对$$D$$中示例赋予标记，标记结果可表示为

  $$h|\_D = {h(x\_1), h(x\_2), ... , h(x\_m)}$$

  随着m的增大，$$\mathcal{H}$$中所有假设对D中的示例所能赋予标记的可能结果数也会增大。

  对所有$$m\in\mathbb{N}$$，假设空间$$\mathcal{H}$$的增长函数

  $$\prod\_{\mathcal{H}}(m)= max\_{{x\_1, ..., x\_m\subseteq \mathcal{H}}}|{h(x\_1), h(x\_2),..., h(x\_m)|h\subseteq \mathcal{H}}|$$，

  表示假设空间$$\mathcal{H}$$对m个示例所能赋予标记的最大可能结果数，可能结果数越大，假设空间的表示能力越强，对学习任务的适应能力也越强，可以利用增长函数来估计经验误差与泛化误差之间的关系。
* Page273: 对分

  假设空间$$\mathcal{H}$$中不同的假设对于$$\mathcal{D}$$中示例赋予标记的结果可能相同，也可能不同；尽管$$\mathcal{H}$$可能包含无穷多个假设，但其对$$\mathcal{D}$$中示例赋予标记的可能结果是有限的。对m个示例，最多有$$2^m$$个可能结果，对二分类问题来说，$$\mathcal{H}$$中的假设对$$\mathcal{D}$$中示例赋予标记的每种可能结果称为对$$\mathcal{D}$$的一种对分。
* Page273: 打散

  若假设空间$$\mathcal{H}$$能实现示例集$$\mathcal{D}$$上的所有对分，即$$\prod\_{\mathcal{H}}(m)=2^m$$，则称示例集$$\mathcal{D}$$能被假设空间$$\mathcal{H}$$打散。
* Page273: VC维(274)

  假设空间的VC维是能被$$\mathcal{H}$$打散的最大示例集的大小，即$$VC(\mathcal{H})=max{m: \prod\_{\mathcal{H}}(m)=2^m}$$，可用于度量假设空间的复杂度。
* Page278: 经验风险最小化(Empirical Risk Minimization, ERM)

  令h表示学习算法$$\mathfrak{L}$$输出的假设，若$$h$$满足$$\hat{E}(h)=min\_{h'}$$，则称$$\mathfrak{L}$$为满足经验风险最小化原则的算法。
* Page279: Rademacher复杂度

  经验误差最小的假设是

  $$argmax\_{h\in\mathcal{H}}\frac{1}{m}\sum\_{i=1}^m y\_i h(x\_i)$$，

  然而现实任务中的标记y有时候会收到噪声影响，不再是真实标记，再此情形下，选择假设空间$$\mathcal{H}$$中在训练集上表现最好的假设，有时还不如选择$$\mathcal{H}$$中事先考虑了随机噪声影响的假设。考虑随机变量$$\sigma\_i$$，它以0.5的概率取值-1,0.5的概率取值+1，称为Rademacher随机变量，基于$$\sigma\_i$$可将上式改写为

  $$sup\_{h\in\mathcal{H}}\frac{1}{m}\sum^m\_{i=1}\sigma\_i h(x\_i)$$,

  期望为

  $$\mathbb{E}*{\sigma}\[sup*{h\in\mathcal{H}}\sum\_{i=1}^m \sigma\_ih(x\_i)]$$，

  考虑实值函数空间 $$\mathcal{F}:\mathcal{Z}\rightarrow\mathcal{R}$$， 令$$Z={z\_1,z\_2,...,z\_m}$$，

  其中$$z\_i\in\mathcal{Z}$$, 将$$\mathcal{X}$$和$$\mathcal{H}$$替换成$$Z$$和$$F$$可得，函数空间$$\mathcal{Z}$$g关于$$\mathcal{F}$$的经验Rademacher复杂度

  $$\hat{R}*Z(\mathcal{F})=\mathbb{E}*{\sigma}\[sup\_{f\in\mathcal{F}}\frac{1}{m}\sum\_{i=1}^m\sigma\_i f(z\_i)]$$，

  其衡量了函数空间$$\mathcal{F}$$与随机噪声在集合$$\mathcal{Z}$$中的相关性。对所有从$$\mathcal{D}$$独立同分布采样而得的大小为m的集合Z求期望可得函数空间$$\mathcal{F}$$关于上$$\mathcal{Z}$$分布的$$\mathcal{D}$$Rademacher复杂度。
* Page284: 稳定性

  算法在输入发生变化时，输出是否会随之发生较大的变化。
* Page285: 均匀稳定性

  对任何$$x\in\mathcal{X},z=(x,y)$$，若学习算法$$\mathcal{L}$$满足

  $$|l(\mathcal{L}*D, z) - l(\mathcal{L}*{D\_i},z)|\leqq\beta$$，

  则称$$\mathcal{L}$$关于损失函数$$l$$满足$$\beta$$均匀稳定性。

  其中l为泛化损失，$$D\_i$$为移除$$D$$中第i个样例得到的集合。