计算学习理论

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