# 计算学习理论

## 第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个样例得到的集合。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.cweihang.io/ml/zzh_ml_notes/melon/ch12.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.