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