PAC（ProbablyApproximatelyCorrect，概率近似正确）
PAC的意思
Probably Approximate Correct直译过来就是”可能近似正确”，这⾥⾯⽤了两个描述”正确”的词，可能和近似。
“近似”是在取值上，只要和真实值的偏差⼩于⼀个⾜够⼩的值就认为”近似正确”；”可能”是在概率上，即只要”近似正确”的概率⾜够⼤就认为”可能近似正确”。
泛化误差随学习复杂性变⼤
冰糖柚子茶
上节查漏补缺中了解到了，如果训练集不是很⼤，也就是⽤来给学习机器学习的样本数量⽐较有限的情况下，如果过于追求让经验风险⼩，学习复杂性太⾼，会导致过学习现象，也就是学习出来的模型的推⼴能⼒变差，这可以⽤泛化误差变⼤来表征。
机器学习所做的事情
先看看到现在为⽌理解的，机器学习所做的事情是，从假设空间(暂时理解成要选择的函数集/模型集)中选取⼀个假设(暂时理解成函数/模型)，对于训练集中的样本能较好的完成任务，并且对于外来的样本，也能较好的完成任务(泛化误差较⼩)。这样学习到的学习机器才是⼀个有效的模型。
PAC所做的事情
上⾯那张图能看出来，机器学习关⼼的是从假设空间中以什么样的⽅式选出的假设才是最优的，也就是选哪个。⽽PAC关⼼的是能不能从假设空间空选出⼀个最优的假设，也就是说在这样有限的训练集下，能不能在假设空间中找到⼀个好的假设来完成任务。也就是说PAC可以⽤来判断达没达到可以选择出⾜够好的假设来解决问题的下限。
以近似正确(AC)代替正确(C)
如果是完全意义上的正确，那么肯定是对实例空间⾥的样本经验风险为0，同时⼜对外来的实例泛化误差为0，这显然是不可能的。⽽且经验风险太⼩也不是⼀件好事(过学习从⽽推⼴能⼒下降)，所以只要设定⼀个阈值，只要选取出的假设h的泛化误差E(h)不超过这个值(即近似正确)就认为是”正确”的了，⽽不是去追求完全的”正确”。
以可能近似正确(PAC)代替近似正确(AC)
实际上，对于所有外来的实例，假设h都能做到”近似正确”，这也⼏乎是不可能的⼀件事。只要对于多数的外来实例，都能做到”近似正确”，也就是说设定⼀个概率的阈值，只要”近似正确”的频率不⼩于这个概率阈值(即可能近似正确)，就认为是”近似正确”的了，⽽不是去追求对所有训练集外的实例都”近似正确”。
这⾥常常给出显著性⽔平，也就是说只要机器学习对外来的随机样本失败的频率被限定在这个值以内。⽤总的概率1减去它就是置信度，作为判断”可能近似正确”的阈值。
精彩的自我介绍
PAC可学习
如果学习机器在短时间(多项式级别)内根据少量的(多项式级别)的训练集样本m，能够找到⼀个好的假设h，满⾜上⾯的那个式⼦，那么就说这个问题是PAC可学习的。
⼀般理论边界
显然在给定的泛化误差和显著性⽔平，⼀个PAC可学习的问题也必须要有⾜够多的样本m才能完成任务，⽽这个样本数m有⼀个⼀般理论边界M，如果m⼤于M那么就⾜以在预期的泛化误差和显著性⽔平下⽤机器学习找到的最优的假设h解决问题。
这⾥|H|表⽰假设空间的⼤⼩。这个式⼦的意思可以这样理解，在这个问题下训练样例的数⽬如果是m，⾜以保证机器学习得到的最优假设h 是可能(置信度是1-δ)近似(泛化误差是ε)正确的。
⼀般理论边界的局限性
慕容恪这个式⼦局限性还很⼤，⼀⽅⾯M只是m的⼀个上界，⽽且可能还⽐较宽松，对于m<=M也不见得PAC不可学习；另⼀⽅⾯|H|是假设空间的⼤⼩，单纯地⽤它刻画样本复杂度不够合理(显然样本复杂度凭什么随着假设空间的⼤⼩线性增长呢)，对于⽆限假设空间的情形显然这个式⼦完全失效。
函数集的VC维
对团委的认识这⾥的指⽰函数可以理解成能指⽰这个结果属于哪个类别的函数，⽐如结果为0或1表⽰两个类别。如果是有界的实函数，可以设定⼀个阈值，那么就可以根据函数结果转换成⼆分类的指⽰函数。
如果问题给的实例只要分成2类，那么对于⼀个指⽰函数集H，如果m个样本能被H中的函数按照所有可能的2^m种⽅式区分开，那么就说这个函数集能把m个样本打散。
战疫手抄报
函数集H的VC维VC(H)也就是它所能打散的最⼤样本数⽬。很显然对于有限的函数集H，VC维有界：
这很好理解，试想这|H|个函数每个都能产⽣⼀种互异的⼆分类⽅式，也就有了|H|种⼆分类⽅式，⽽有|H|种⼆分类⽅式的样本最多也就是以2为底|H|的对数这么多个了，所以VC(H)绝不会超过它。小学作文怎么写
⼀个⽤烂了的例⼦
监守自盗电影⽬前没有通⽤的关于任意函数VC维计算的⽅法，对⼀些特殊的函数知道其VC维。这个平⾯上的点被线性决策线⼆分类的例⼦到处都是，可以⽤来理解⼀下VC维。
假如函数集H是平⾯上的所有线性决策线(其实也就是直线，但是根据把点分成两边能做⼆分类所以叫线性决策线)，显然|H|=+∞。给定的实例是平⾯上的点，现在⽤线性决策线尝试把给定的⼀些点打散。
对于3个以内的点，还是能打散的：
儿童故事下载⽽对于4个样本点，就不能打散了，试想要把下图中的两个紫⾊点分到⼀起，线性决策线做不到：
所以这个问题的VC维VC(H)=3。
VC维衡量假设空间复杂度
⽤VC维代替前⾯的|H|来刻画假设空间下的样本复杂度，不仅能够把边界M做的更紧凑，⽽且可以去刻画⽆限假设空间下的样本复杂度。这时候新的PAC可学习边界：
