计算学习理论（computational learning theory）是通过“计算”来研究机器学习的理论，简而言之，其目的是分析学习任务的本质，例如：在什么条件下可进行有效的学习，需要多少训练样本能获得较好的精度等，从而为机器学习算法提供理论保证。
1）独立同分布（independent and identically distributed，简称 i.i.d. ）
在概率统计理论中，指随机过程中，任何时刻的取值都为随机变量，如果这些随机变量服从同一分布，并且互相独立，那么这些随机变量是独立同分布
2）上确界
上确界是一个集合的最小上界。具体到数学分析中。一个实数集合A，若有一个实数M，使得A中任何数都不超过M，那么就称M是A的一个上界。在所有那些上界中如果有一个最小的上界，就称为A的上确界
3）多项式函数 poly()
多项式函数 poly() 返回的是一个多项式，假定输入 n 个参数，第 i 个参数的值代表变量的第( n - i )项式的倍数，比如 poly(2, -1, 3, 1) = 2x^3 - x^2 + 3x + 1
12.1 基础知识
这一部分主要讲了两个概念，分别为泛化误差和经验误差。
泛化误差指的是学习器在总体上的预测误差，经验误差则是学习器在某个特定数据集D上的预测误差。在实际问题中，往往我们并不能得到总体且数据集D是通过独立同分布采样得到的，因此我们常常使用经验误差作为泛化误差的近似。
文中描述：
常用不等式
本章后面部分将研究经验误差与泛化误差之间的逼近程度
12.2 PAC 学习
概率近似分布（probably Approximately correct）
涉及到的是哪个定义
以上定义分别从置信度、数量（空间）、时间三个角度出发去衡量学习器学出的模型。
学习器所考虑的所有可能概念的机会称为假设空间，用符号H表示，C表示概念，对于任何样例c（x）=y成立，H与C是不相同的，学习算法会把自认为可能的目标概念集中起来构成H，但不能确定它是否是真的概念，所以叫假设（hypothesis）。
12.3 有限假设空间
12.3.1 可分情形
可分或一致的情形指的是：目标概念包含在算法的假设空间中。对于目标概念，在训练集D中的经验误差一定为0，因此首先我们可以想到的是：不断地剔除那些出现预测错误的假设，直到找到经验误差为0的假设即为目标概念。但由于样本集有限，可能会出现多个假设在D上的经验误差都为0，因此问题转化为：需要多大规模的数据集D才能让学习算法以置信度的概率从这些经验误差都为0的假设中找到目标概念的有效近似。
（个人理解，就是样本空间数量增加对学习算法是有用的，这个假设空间内必有目标概念）
书中论述：
12.12 过程 |H|为数量
对于可分情形的有限假设空间，目标概念都是PAC可学习的，即当样本数量满足上述条件之后，在与训练集一致的假设中总是可以在1-σ概率下找到目标概念的有效近似。
12.3.2 不可分情形
不可分或不一致的情形指的是：目标概念不存在于假设空间中，这时我们就不能像可分情形时那样从假设空间中寻找目标概念的近似。但当假设空间给定时，必然存一个假设的泛化误差最小，若能找出此假设的有效近似也不失为一个好的目标，这便是不可知学习(agnostic learning)的来源。
Hoeffding不等式
引出不可知PAC可学习的概念
12.4 VC维
【CSDN https://blog.csdn.net/weixin_33908217/article/details/87444615】摘抄
现实学习任务所面临的常常是无限假设空间，比如 SVM、神级网络等，前者的假设空间是 d 维空间上的所有线性超平面，后者的假设空间可以是实数域中的所有区间。欲对这种情况的可学习性进行研究，需度量假设空间的复杂度。最常见的方法是考虑假设空间的“VC维”（Vapnik-Chervonenkis Dimension）
介绍VC维之前，我们再引入几个概念：
增长函数（growth function）：增长函数表示假设空间 H 对 m 个示例所能赋予标记的最大可能结果数 n 的映射关系。
对于二分类问题（结果只有0、1两个），若 m=2，有a，b两个样例，则赋予标记的可能结果最大为4种：a=0,b=0; a=1,b=1; a=0,b=1; a=1,b=0。以此类推当 m=3 时，则可能有8种。但是，这只是最优情况，很多时候假设空间所能赋予的最大可能结果数不是 2 的 m 次方。
显然，H 对示例所能赋予的可能结果数越大，H 的表示能力越强，对学习任务的适应能力也越强。因此，增长函数描述了假设空间 H 的表示能力，由此反映出了假设空间的复杂度
对分（dichotomy）：对于二分类问题来说，H 中的假设对 D 中示例赋予标记的每种可能结果称为对 D 的一种对分
打散（shattering）：若假设空间 H 能实现示例集 D 上的所有对分，即对于 m 个示例的样本集 D 的增长函数等于 2 的 m 次方，则称示例集 D 能被假设空间 H 打散
在清晰了以上概念后，我们可以正式定义VC维了：
假设空间 H 的VC维是能被 H 打散的最大示例集的大小，记作 VC( H )
VC( H ) = d 表明存在大小为 d 的示例集能被假设空间 H 打散，但是需注意：这并不代表所有大小为 d 的示例集都能被空间 H 打散。除此之外，VC维还有一个特点，那就是它与数据分布D无关！因此数据分布未知时我们也可以算出假设空间 H 的VC维
举个例子来加深理解一下，对于二维平面的线性划分学习任务，令假设空间 H 表示二维平面上所有的线性划分所构成的集合，输入属性 X 是二维平面的坐标，输出标签 Y 是根据 X 坐标相对应假设 h 的位置而定的，被线性划分到一边的被归为一类，另一边的被归为另一类。由下图可知，存在大小为 3 的示例集可被 H 打散，但不存在大小为 4 的示例集可被 H 打散。于是，该假设空间 H 的 VC 维为 3
以上表示出VC维与增长函数有密切的关系，
以上推导没有整理，书本上有
从定理12.3我们只需要知道一个最重要的一点，那就是：泛化误差界只与样例数目 m 有关，与数据分布D和样例集 D 无关。因此，基于 VC 维的泛化误差界是分布无关（distribution-free）、数据独立（data-independent）的
在此基础上，我们可得下边这个重要的定理：
任何 VC 维有限的假设空间 H 都是（不可知）PAC可学习的
12.5 复杂度
书中给予了很多公式，基本上看不懂，也都没有相关的解释，以下是搜集相关的一些内容整理如下：
基于 VC 维的泛化误差界是分布无关、数据独立的，也就是说对于任意的数据分布都成立。这使得基于 VC 维的可学习性分析结果具有一定的“普适性”；但从另一方面来说，由于没有考虑数据自身，基于 VC 维得到的泛化误差界通常比较“松”，对那些与学习问题的典型情况相差甚远的较“坏”分布来说尤其如此
Rademacher复杂度是另一种刻画假设空间复杂度的途径，与 VC 维不同，它在一定程度上考虑了数据分布
机器学习算法的性能体现在其泛化误差足够小，但是现实中泛化误差往往无法求，所以我们只能用经验误差来进行近似！
考虑现实情况中噪音可能对假设空间的性能影响，在训练集上表现最好的假设有时还不如已考虑了随机噪音的假设，所以Rademacher 复杂度计算直接引入了 Rademacher 随机变量来代替训练样本中的标记，它以 0.5 的概率为 -1，0.5 的概率为 +1。
F等同于 H 假设空间，f等同于h是假设空间中假设，z和x一样是样本空间中的样本，是一个随机变量（取-1 +1），sup表示上确界限（最大上界限）
在一个确定的训练集上，经验 Rademacher 复杂度其实计算的是假设空间 H 与随机噪音相关性的期望，这个值越大，则说明假设空间与随机噪音拟合地越好，也说明这个假设空间越复杂。
（ Rademacher 复杂度重在考虑了噪声）
假设训练集样本采样自分布D，则 Rademacher 复杂度是分布D上的经验 Rademacher 复杂度的期望
于是通过 Rademacher 复杂度，我们可以计算出基于Rademacher 复杂度的泛化误差界。
（实在是看不懂……………………）
12.6 稳定性
定义
事实上，若学习算法符合经验风险最小化原则（ERM）且满足β-均匀稳定性，则假设空间是可学习的。稳定性通过损失函数与假设空间的可学习联系在了一起，区别在于：假设空间关注的是经验误差与泛化误差，需要考虑到所有可能的假设；而稳定性只关注当前的输出假设。
ERM经验风险最小化原则也没怎么看懂
https://blog.csdn.net/xiaocainiaodeboke/article/details/50472367
