基础知识
计算学习理论（computational learning theory）是通过“计算”来研究机器“学习“的理论，其目的是分析学习任务的困难本质。例如：在什么条件下可进行有效的学习，需要多少训练样本能获得较好的精度等，从而为机器学习算法提供理论保证。
几个基本概念回顾：
泛化误差：学习器在总体上的预测误差
经验误差：学习器在某个特定数据集D上的预测误差；
不合disagreement：
几个用到的不等式：
PAC学习
PAC：概率近似正确学习理论；
- 注：以比较大的把握学得比较好的模型，即，以较大的概率学得误差满足预设上限的模型；
概念c：样本空间X到标记空间Y的映射；
目标概念c：样本空间X到标记空间Y的映射，且对任何样例（x,y）有c(x)=y成立；
概念类C：希望学到的目标概念所构成的集合；
假设空间H：样本空间X到标记空间Y的映射；
可分/一致：
不可分/不一致：
PAC辨识
解析：对于某种学习算法，如果能以一个置信度学得假设满足泛化误差的预设上限，则称该算法能PAC辨识概念类，即该算法的输出假设已经十分地逼近目标概念。
PAC可学习
解析：将样本数量考虑进来，当样本超过一定数量时，学习算法总是能PAC辨识概念类，则称概念类为PAC可学习的。
PAC学习算法
解析：将学习器运行时间也考虑进来，若运行时间为多项式时间，则称PAC学习算法。
样本复杂度：
总结：
PAC学习中的一个关键因素就是假设空间的复杂度，对于某个学习算法，若假设空间越大，则其中包含目标概念的可能性也越大，但同时找到某个具体概念的难度也越大。一般假设空间分为有限假设空间与无限假设空间。
有限假设空间
可分情形：目标概念包含在算法的假设空间中。
对于目标概念，在训练集D中的经验误差一定为0，因此首先我们可以想到的是：不断地剔除那些出现预测错误的假设，直到找到经验误差为0的假设即为目标概念。但由于样本集有限，可能会出现多个假设在D上的经验误差都为0，因此问题转化为：需要多大规模的数据集D才能让学习算法以置信度的概率从这些经验误差都为0的假设中找到目标概念的有效近似。
不可分情形：目标概念不存在于假设空间中
当假设空间给定时，必然存一个假设的泛化误差最小，若能找出此假设的有效近似也不失为一个好的目标，这便是不可知学习(agnostic learning)的来源。
一堆定理，拿笔做吧！
VC维
刻画假设空间复杂度的途径一：VC维；
增长函数：对于给定数据集D，假设空间中的每个假设都能对数据集的样本赋予标记，因此一个假设对应着一种打标结果，不同假设对D的打标结果可能是相同的，也可能是不同的。随着样本数量m的增大，假设空间对样本集D的打标结果也会增多，增长函数则表示假设空间对m个样本的数据集D赋予标标记的最大可能结果数，因此增长函数描述了假设空间的表示能力与复杂度。结果越大表示能力越强。
打散：例如对二分类问题来说，m个样本最多有2^m个可能结果，每种可能结果称为一种“对分”，若假设空间能实现数据集D的所有对分，则称数据集能被该假设空间打散。
概念：因此尽管假设空间是无限的，但它对特定数据集赋予标记的不同结果数是有限的，假设空间的VC维正是它能打散的最大数据集大小。
定义：若存在大小为d的数据集能被假设空间打散，但不存在任何大小为d+1的数据集能被假设空间打散，则其VC维为d。
案例：
假设空间VC维与增长函数的两个关系：
将（12.28）代入（12.22）可得：
在有限假设空间中，根据Hoeffding不等式便可以推导得出学习算法的泛化误差界；但在无限假设空间中，由于假设空间的大小无法计算，只能通过增长函数来描述其复杂度，因此无限假设空间中的泛化误差界需要引入增长函数。
上式给出了基于VC维的泛化误差界，同时也可以计算出满足条件需要的样本数（样本复杂度）。若学习算法满足经验风险最小化原则（ERM），即学习算法的输出假设h在数据集D上的经验误差最小，可证明：任何VC维有限的假设空间都是（不可知）PAC可学习的，换而言之：若假设空间的最小泛化误差为0即目标概念包含在假设空间中，则是PAC可学习，若最小泛化误差不为0，则称为不可知PAC可学习。
Rademacher复杂度
刻画假设空间复杂度的途径二：Rademacher复杂度---与VC维不同的是在一定程度上考虑了数据分布。
VC为的泛化误差界很不无关、数据独立，对任何数据发布都成立，“普适”但泛化误差界“松”。
经验Rademacher复杂度：衡量函数空间F和随机噪声在集合Z中的相关性；
函数空间F在Z上的关于D的相关性：
基于Rademacher复杂度可得关于函数空间F的泛化误差界。
针对回归问题：
针对二分类问题---基于Rademacher复杂度的泛化误差界：
Rademacher复杂度与增长函数：
稳定性
稳定性考察的是当算法的输入发生变化时，输出是否会随之发生较大的变化，输入的数据集D有以下两种变化：
关于假设的几种损失：
算法的均匀稳定性：
即原学习器和剔除一个样本后生成的学习器对z的损失之差保持β稳定，称学习器关于损失函数满足β-均匀稳定性。
同时若损失函数L的上界为M（即原学习器对任何样本的损失函数不超过M），0<の<1,以至少1-の的概率则有如下定理：
事实上，若学习算法符合经验风险最小化原则（ERM）且满足β-均匀稳定性，则假设空间是可学习的。
稳定性通过损失函数与假设空间的可学习联系在了一起，区别在于：
- 假设空间关注的是经验误差与泛化误差，需要考虑到所有可能的假设；
- 稳定性只关注当前的输出假设。
