目录
12.1 基础知识
12.2 PAC学习
12.3 有限假设空间
12.3.1 可分情形
12.3.2 不可分情形
12.4 VC维
12.5 Rademacher复杂度
12.6 稳定性
12.1 基础知识
计算学习理论(computational learning theory)研究的是关于通过"计算"来进行"学习"的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
经验误差和泛化误差：
假设给定训练集\(D=\{(\boldsymbol{x}_{1},y_{1}),(\boldsymbol{x}_{2},y_{2}),\ldots,(\boldsymbol{x}_{m},y_{m})\}, \boldsymbol{x}_{i}\in\mathcal{X}\)，本章主要讨论二分类问题，若无特别说明，\(y_{i}\in\mathcal{Y}=\{-1,+1\}\)。其中所有的训练样本都服从一个未知的分布\(\mathcal{D}\)，且它们都是在总体分布\(\mathcal{D}\)中独立采样得到，即独立同分布（independent and identically distributed，i.i.d.）。
令\(h\)为从\(\mathcal{X}\)到\(\mathcal{Y}\)的一个映射，其泛化误差为:
\(E(h;\mathcal{D})=P_{\boldsymbol{x}\sim\mathcal{D}}(h(\boldsymbol{x})\neq y)\)
\(h\)在D上的经验误差为:
\(\widehat{E}(h;D)=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\big(h(x_{i})\neq y_{i}\big)\)
泛化误差指的是学习器在总体上的预测误差，经验误差则是学习器在某个特定数据集D上的预测误差。
几个常用不等式：
- Jensen 不等式:对任意凸函数\(f(x)\)，有
\(f(\mathbb{E}(x))\leqslant\mathbb{E}(f(x))\)
- HoefIding 不等式[HoefIding ， 1963]: 若\(x_{1},x_{2},\ldots,x_{m}\)为m 个独立随机变
量，且满足\(0\leqslant x_{i}\leqslant1\)，则对任意\(\epsilon>0\)有\(\begin{gathered}
P\left(\frac{1}{m}\sum_{i=1}^{m}x_{i}-\frac{1}{m}\Big|\sum_{i=1}^{m}\mathbb{E}(x_{i})\geqslant\epsilon\right)\leqslant\exp(-2m\epsilon^{2}) \\
P\left(\left|\frac{1}{m}\sum_{i=1}^{m}x_{i}-\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}(x_{i})\right|\geqslant\epsilon\right)\leqslant2\exp(-2m\epsilon^{2})
\end{gathered}\)
- McDiarmid 不等式[McDiarmid ， 1989]:若\(x_{1},x_{2},\ldots,x_{m}\)为m 个独立随机变
量，且对任意\(1\leqslant i\leqslant m\)，函数\(f\)满足\(\sup_{x_1,\ldots,x_m, x_i^{\prime}}|f(x_1,\ldots,x_m)-f(x_1,\ldots,x_{i-1},x_i^{\prime},x_{i+1},\ldots,x_m)|\leqslant c_i\)
则对任意\(\epsilon>0\) ，有
\(P\left(f\left(x_{1},\ldots,x_{m}\right)-\mathbb{E}\left(f\left(x_{1},\ldots,x_{m}\right)\right)\geqslant\epsilon\right)\leqslant\exp\left(\frac{-2\epsilon^{2}}{\sum_{i}c_{i}^{2}}\right) \\P\left(\left|f\left(x_{1},\ldots,x_{m}\right)-\mathbb{E}\left(f\left(x_{1},\ldots,x_{m}\right)\right)\right|\geqslant\epsilon\right)\leqslant2\exp\left(\frac{-2\epsilon^{2}}{\sum_{i}c_{i}^{2}}\right)\)
12.2 PAC学习
PAC学习原理（Probably Approximately Correct，概率近似正确）是计算学习理论中的一个核心概念。该原理旨在解释为什么一个假设（或模型、函数）在学习了训练样本后，能够在训练样本之外的数据上有效地进行预测。
PAC学习原理的基本思想是：对于一个给定的概念类（即所有可能的目标概念的集合），如果存在一个多项式时间的学习算法，它能够从训练样本中学习到一个假设，使得该假设在训练样本之外的数据上的错误率以很大的概率（通常接近于1）低于一个预先设定的阈值，并且所需的训练样本数量和学习时间都是多项式级别的，那么我们就称这个概念类是PAC可学习的。
- \(C\)：概念类。表示从样本空间到标记空间的映射，对任意样例，都能使得\(c(x)=y\)。
- \(H\)：假设类。学习算法会把认为可能的目标概念集中起来构成\(H\)。
- 若\(c\in H\)，则说明假设能将所有示例按真实标记一致的方式完全分开，称为该问题对学习算法而言是”可分的“；否则，称为”不可分的“
对于训练集，我们希望学习算法学习到的模型所对应的假设\(h\)尽可能接近目标概念\(c\)。我们是希望以比较大的把握学得比较好的模型，也就是说，以较大的概率学得误差满足预设上限的模型，这就是"概率近似正确"的含义。形式化地说，令\(\delta\)表示置信度，可定义:
- PAC辨识：对\(0\leq\epsilon,\delta<1\)，所有的\(c\in \mathcal{C}\)和分布\(\mathcal{D}\)，若存在学习算法，其输出假设\(h\in H\)满足：
\(\mathrm P(\mathrm E(\mathrm h)\leq\epsilon)\geq1-\delta \)
则称学习算法能从假设空间\(\mathcal{H}\)中PAC辨识概念类\(\mathcal{C}\)。这样的学习算法能以较大的概率(至少\(1-\delta\)学得目标概念\(c\)的近似 (误差最多为\(\epsilon \))。在此基础上可定义:
- PAC可学习：令\(m\)表示从分布\(\mathcal{D}\)中独立同分布采样得到的样例数目，\(0\leq\epsilon,\delta<1\)，对所有分布\(\mathcal{D}\)，若存在学习算法和多项式函数\(poly(1/\epsilon,1/delta,size(x),size(c))\)（样例数目m与误差\(\epsilon \)、置信度\(1-\delta\)、数据本身的复杂度size(x)、目标概念的复杂度size(c)都有关），使得对于任何\(m\ge poly(1/\epsilon,1/delta,size(x),size(c))\)，学习算法能从假设空间中PAC辨识概念类\(\mathcal{C}\)，则称概念类\(\mathcal{C}\)对假设空间而言是PAC可学习的，有时也简称概念类\(\mathcal{C}\)是PAC 可学习的。
- PAC学习算法：满足PAC可学习的算法。（假定学习算法处理每个样本的时间为常数，因此C 的时间复杂度等价于样本复杂度。于是，我们对算法时间复杂度的关心就转化为对样本复杂度的关心）
- 样本复杂度（Sample Complexity）：满足\(m \ge poly(1/\epsilon,1/\delta,size(x),size(c))\)的最小的m。
PAC学习中一个关键因素是假设空间\(\mathcal{H}\)的复杂度。\(\mathcal{H}\)包含了学习算法所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即\(\mathcal{H}\)=\(\mathcal{C}\)，这称为"恰PAC可学习" (properly PAC learnable)。直观地看，这意味着学习算法的能力与学习任务”恰好匹配“。然而，这种让所有候选假设都来自概念类的要求看似合理，但却并不实际，因为在现实应用中我们对概念类\(\mathcal{C}\)通常一无所知，更别说获得一个假设空间与概念类恰好相同的学习算法。显然，更重要的是研究假设空间与概念类不同的情形，即\(H \neq C\)。 一般而言，\(\mathcal{H}\)越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难度也越大。\(|H|\)有限时，我们称究为"有限假设空间"，否则称为"无限假设空间"。
12.3 有限假设空间
12.3.1 可分情形
对于PAC来说，只要训练集\(\mathcal{D}\)的规模能使得学习算法以概率\(1-\delta\)找到目标假设的\(\epsilon\)近似即可。
先估计泛化误差大于\(\epsilon\)但在训练集上仍表现完美的假设出现的概率。假定\(h\)的泛化误差大于\(\epsilon\)，对分布\(\mathcal(D)\)上随机采样而得到的任何样例\((x,y)\)，有：
\(\begin{aligned}\mathrm{P}\left(\mathrm{h}(\mathrm{x})=\mathrm{y}\right)&=1-\mathrm{P}\left(\mathrm{h}(\mathrm{x})\neq\mathrm{y}\right)\\&=1-\mathrm{E}(\mathrm{h})\\&\leq1-\epsilon\end{aligned}\)
由于\(\mathcal(D)\)中包含m个样例，因此，h与\(\mathcal(D)\)表现一致的概率为：
\(\mathrm P((\mathrm h(\mathrm x_1)=\mathrm y_1)(\mathrm h(\mathrm x_2)=\mathrm y_2)\cdots(\mathrm h(\mathrm x_m)=\mathrm y_m))<(1-\epsilon)^\mathrm{m}\)
我们事先不知道学习算法会输出那个假设，但仅需要保证泛化误差大于\( \epsilon\)，且在训练集上变现完美的多有假设出现概率之和不大于\(\delta\)即可。
\(\begin{aligned}
P\big(h\in\mathcal{H}:E(h)>\epsilon\wedge\widehat{E}(h)=0\big)& <|\mathcal{H}|(1-\epsilon)^{m} \\&<|\mathcal{H}|e^{-m\epsilon} \end{aligned}\)
令上式不大于\(\delta\)
\(|\mathcal{H}|e^{-m\epsilon}\leqslant\delta \)
可得
\(m\geqslant\frac{1}{\epsilon}\bigl(\ln|\mathcal{H}|+\ln\frac{1}{\delta}\bigr)\)
由此可知，有限假设空间\(\mathcal(H)\)都是PAC可学习的，所需的样例数目如上式所示，输出假设h的泛化误差随样例数目的增多而收敛到 0，收敛速率为\(O(\frac{1}{m})\)。
12.3.2 不可分情形
不可分或不一致的情形指的是：目标概念不存在于假设空间中，这时我们就不能像可分情形时那样从假设空间中寻找目标概念的近似。但当假设空间给定时，必然存一个假设的泛化误差最小，若能找出此假设的有效近似也不失为一个好的目标，这便是不可知学习(agnostic learning)的来源。
12.4 VC维
VC维：假设空间\(\mathcal(H)\)的VC维是能被\(\mathcal(H)\)打散的最大示例集的大小：
\(\mathrm{VC}(\mathcal{H})=\max\{m:\Pi_{\mathcal{H}}(m)=2^{m}\}\)
例如对二分类问题来说，m个样本最多有\(2^m\)个可能结果，每种可能结果称为一种“对分”，若假设空间能实现数据集D的所有对分，则称数据集能被该假设空间打散。VC维指能被\(\mathcal(H)\)打散的最大示例集的大小。
VC维与数据分布\(\mathcal(D)\)无关！在数据分布未知时，仍能计算出假设空间的VC维。
若假设空间\(\mathcal(H)\)的VC维是d，则对任意整数\(m \gt d\)，有：
\(\Pi_{\mathcal{H}}(m)\leqslant\sum_{i=0}^d\binom{m}{i}\)
12.5 Rademacher复杂度
Rademacher 复杂度 (Rademacher complexity) 是另一种刻画假设空间复杂度的途径，与VC维不同的是，它在一定程度上考虑了数据分布。
考虑实值函数空间\(F \rightarrow \mathbb R\)，令\(Z=\{z_1,z_2,\cdots,z_m\}\)。函数空间F关于Z的经验Rademacher复杂度
\(\widehat{R}_{Z}(\mathcal{F})=\mathbb{E}_{\sigma}\Big[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}f(z_{i})\Big]\)
经验Rademacher复杂度衡量了函数空间F与随机噪声在集合Z中的相关性。通常我们希望了解函数空间F在Z上关于分布D的相关性，因此，对所有从D独立同分布采样而得的大小为m的集合Z求期望可得
\(R_{m}(\mathcal{F})=\mathbb{E}_{Z\subseteq\mathcal{Z}:|Z|=m}\Big[\widehat{R}_{Z}(\mathcal{F})\Big]\)
假设空间H的Rdemacher复杂度\(R_m(H)\)与增长函数\(\Pi_H(m)\)满足
\(R_m(\mathcal{H})\leqslant\sqrt{\frac{2\ln\Pi_{\mathcal{H}}(m)}{m}}\)
12.6 稳定性
顾名思义，算法的“稳定性”考察的是算法在输入发生变化时，其输出是否会随之发生较大的变化。学习算法的输入是训练集，因此下面我们先定义训练集的两种变化：
- 移除：\(D^{\backslash i}\)，表示移除D中第i个样例得到的集合
\(D^{\setminus i}=\{z_1,z_2,\ldots,z_{i-1},z_{i+1},\ldots,z_m\}\)
- 替换：\(D^{i}\)，表示替换D中第i个样本得到的集合
\(D^i=\{z_1,z_2,\ldots,z_{i-1},z_i^{'},z_{i+1},\ldots,z_m\}\)
损失函数刻画了预测标记和真实标记的差别：
- 泛化损失
\(\ell(\mathcal{L},\mathcal{D})=\mathbb{E}_{x\in\mathcal{X},z=(x,y)}\bigl[\ell(\mathcal{L}_{D},z)\bigr]\)
- ·经验损失
\(\widehat{\ell}(\mathcal{L},D)=\frac{1}{m}\sum_{i=1}^{m}\ell(\mathcal{L}_{D},z_{i})\)
- 留一(leave-one-out)损失
\(\ell_{loo}(\mathcal{L},D)=\frac{1}{m}\sum_{i=1}^{m}\ell(\mathcal{L}_{D^{\setminus i}},z_{i})\)
算法的均匀稳定性：
对任何\(x\in\mathcal{X}, z=(x,y)\)， 若学习算法￡满足
\(\left|\ell(\mathcal{L}_{D},z)-\ell(\mathcal{L}_{D\setminus i},z)\right|\leqslant\beta , i=1,2,\ldots,m,\)
则称￡关于损失函数t 满足ß-均匀稳定性
因此，移除示例的稳定性包含了替换示例的稳定性。
若学习算法符合经验风险最小化原则（ERM）且稳定的，则假设空间H是可学习的。稳定性通过损失函数与假设空间的可学习联系在了一起。
