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），有d_vc=k-1。把VC维度带入VC不等式（即用d_vc替代k-1）得到

只要d_vc是有限的，那么当n很大时，不等式的最右边都是一个很小的数，即真实误差e_out（g）逼近训练误差e_in（g），那么假设函数g具有很好的推广能力。

由VC不等式可知“有限的VC维度才是机器学习可行的条件”。从而得到下面这个结论：

● 不需要知道算法A。

● 不需要知道数据分布P（x）。

● 不需要知道目标函数c。

只需要知道训练集D和假设函数集H就能找到最优假设函数g来学习c。

左图中将不需要的元素用灰色来淡化。

2.3.3 模型复杂度

设定一个概率δ，计算样本数n和容忍度ε的关系：

因此，在大于1-δ的概率下，

在上式的最后引进了惩罚函数Ω，也被称为模型复杂度（Model Complexity）。这个参数表达的意义是，假设空间H越强，算法越需要强大的推广能力。通俗来讲，H容量越大，d_vc越大，那么模型就越难学习。

如右图所示，模型复杂度是d_vc的增函数（红线），而训练误差是d_vc的减函数（蓝线）。

● 当d_vc增大时：训练误差减小（模型越复杂，越容易解释训练集），模型复杂度增大。

● 当d_vc减小时：训练误差增大（模型越简单，越难以解释训练集），模型复杂度减小。

因为真实误差=训练误差+模型复杂度，因此真实误差和d_vc不是简单的单调关系，d_vc变大虽然可使得训练误差变小，但不见得是最好的选择，因为它要为模型复杂度Ω付出代价。

机器学习的任务就是找到有最佳VC维度的模型（对应着最小的真实误差）。

2.3.4 样本复杂度

你还可以设定想要的容忍度ε，看看需要多少个样本n能实现，即计算出样本复杂度（Sample Complexity）：

虽然解出了n，但上式的左右两边都含有n，因此需要用迭代方法（如牛顿法）求解，比如进行以下设定：

● ε=0.1，希望真实误差和训练误差的差距的绝对值不要超过0.1。

● δ=0.1，上述情况有90%的可能性会发生。

由迭代法算出，当d_vc=3时，n≈30000；当d_vc=4时，n≈40000；从理论上看n≈10000d_vc，但实际上n≈10d_vc。为什么样本数量可以从10⁴倍减少到10倍呢？因为VC上界是很松的，原因有以下4点。

● 霍夫丁不等式适用于任何数据分布和任何目标函数。

● 增长函数适用于任何数据。

● VC维度适用于任何假设空间。

● 联合上界适用于最差的状况。

在实践中，“任何”和“最差”同时发生的可能性不大，因而，样本复杂度的实际值和理论值可能相差很大。