2.3 结论应用
2.3.1 VC不等式
2.2节得出的不等式就是著名的VC（Vapnik-Chervonenkis）不等式的“仿真版”，真正的VC不等式有几个系数要修改，具体介绍如下。
在上式中，红色和蓝色符号显示出仿真版VC不等式和真正版VC不等式的不同之处，完整地证出那些蓝色符号需要很多的专业知识，对VC不等式证明感兴趣的读者可参见本章参考资料[2]。VC不等式右边的项被称为VC上界。
2.3.2 VC维度
给定数据集D有n个点以及假设函数空间H，下面先回忆一下打散和突破点的定义：
● 打散是n个点能被H实现所有对分。
● 突破点 是第一个无法被打散的点，记作k点。
既然k点是第一个无法被打散的点，那么k-1点一定是最后被打散的点，通常把它定义成VC维度（VC Dimension），有dvc=k-1。把VC维度带入VC不等式（即用dvc替代k-1）得到
只要dvc是有限的，那么当n很大时，不等式的最右边都是一个很小的数，即真实误差eout（g）逼近训练误差ein（g），那么假设函数g具有很好的推广能力。
训练数据+假设函数集+有限VC=机器学习可行
由VC不等式可知“有限的VC维度才是机器学习可行的条件”。从而得到下面这个结论：
● 不需要知道算法A。
● 不需要知道数据分布P（x）。
● 不需要知道目标函数c。
只需要知道训练集D和假设函数集H就能找到最优假设函数g来学习c。
左图中将不需要的元素用灰色来淡化。
2.3.3 模型复杂度
设定一个概率δ，计算样本数n和容忍度ε的关系：
因此，在大于1-δ的概率下，
在上式的最后引进了惩罚函数Ω，也被称为模型复杂度（Model Complexity）。这个参数表达的意义是，假设空间H越强，算法越需要强大的推广能力。通俗来讲，H容量越大，dvc越大，那么模型就越难学习。
如右图所示，模型复杂度是dvc的增函数（红线），而训练误差是dvc的减函数（蓝线）。
● 当dvc增大时：训练误差减小（模型越复杂，越容易解释训练集），模型复杂度增大。
● 当dvc减小时：训练误差增大（模型越简单，越难以解释训练集），模型复杂度减小。
因为真实误差=训练误差+模型复杂度，因此真实误差和dvc不是简单的单调关系，dvc变大虽然可使得训练误差变小，但不见得是最好的选择，因为它要为模型复杂度Ω付出代价。
机器学习的任务就是找到有最佳VC维度
的模型（对应着最小的真实误差）。
模型复杂度和VC维度的关系
2.3.4 样本复杂度
你还可以设定想要的容忍度ε，看看需要多少个样本n能实现，即计算出样本复杂度（Sample Complexity）：
虽然解出了n，但上式的左右两边都含有n，因此需要用迭代方法（如牛顿法）求解，比如进行以下设定：
● ε=0.1，希望真实误差和训练误差的差距的绝对值不要超过0.1。
● δ=0.1，上述情况有90%的可能性会发生。
由迭代法算出，当dvc=3时，n≈30000；当dvc=4时，n≈40000；从理论上看n≈10000dvc，但实际上n≈10dvc。为什么样本数量可以从104倍减少到10倍呢？因为VC上界是很松的，原因有以下4点。
● 霍夫丁不等式适用于任何数据分布和任何目标函数。
● 增长函数适用于任何数据。
● VC维度适用于任何假设空间。
● 联合上界适用于最差的状况。
在实践中，“任何”和“最差”同时发生的可能性不大，因而，样本复杂度的实际值和理论值可能相差很大。