引言

上一小节，我们引入了VC维的概念，用它来描述假设集合的表达能力。这一小节中，我们将从VC维的物理意义出发，进一步学习如何根据VC维传达的信息来选择模型和假设集合。

VC维的物理意义

如果我们将假设集合的数量|H|比作假设集合的自由度，那么VC维就是假设集合在做二元分类的有效的自由度，即这个假设空间能够产生多少Dichotomies的能力（VC维说的是，到什么时候，假设集合还能shatter，还能产生最多的Dichotomies）。

VC维、真实错误率、训练错误率

在上一节中，我们讨论要做到好的预测要满足两个条件，第一是训练误差要接近真实误差，即Ein(g)约等于Eout(g)；第二是训练误差要尽量接近0，即Ein(g)约等于0。
现在，我们用VC维这个工具来描述。

• 如果VC维很小，那么发生预测偏差很大的坏事情的可能性也就很小，那这有利于Ein(g)接近Eout(g)；但是，这是我们的假设空间的表达能力受到了限制，这样Ein(g)可能就没有办法做到很小。
• 如果VC维很大，那么假设空间的表达能力很强，我们很有可能选到一个Ein(g)很小的假设，但是Ein(g)和Eout(g)之差很大的坏事情发生的情况发生的可能性就变得很大，这样Ein(g)和Eout(g)根本不接近，我们就无法确定选择的假设在测试数据的时候表现的很好。

这时，VC维变成了我们一个重要的选择，我们可以用VC维提供的信息来选择更好的模型和假设空间。

模型复杂度（Model Complexity）

我们可以根据VC Bound公式，设发生坏事情的概率是δ，将其恒等变换可以得到训练误差和测试误差的差别ε。所以反过来讲，好事情（训练误差和测试误差的差别小于ε）发生时，Eout(g)被限制在一个范围内。这里根号内的式子定义为Ω(N,Η,δ)，称作模型复杂度,这个参数描述的意义是，我们的假设空间H有多么的强，使得我们的算法在泛化能力上需要付出多少代价。通俗的来讲，假设空间的容量越大，VC维越大，那么模型就越难学习。

model_complexity

VC维传递的信息

如下图所示，我们可以看出随VC维变化，Ein、Eout、模型复杂度都是如何变化的。
这里一个很直接的信息就是模型复杂度随着VC维的变大不断变大，呈正相关趋势。
因为VC维变大时，数据中可以shatter的点就变多了，那么假设空间的容量就变大了，如果是一个合理的学习算法的话，就有机会找到一个更好的假设，使得Ein更小。
而Eout呢？在一开始的时候，Eout随着Ein的下降也下降，但是到某个点，因为我们要付出的代价变大了，Eout开始上升，所以最好的Eout是在中间的某个位置。
这里得到一个重要的结论，VC维越大或者假设空间能力越强大，虽然可以使得训练误差很小，但不见得是最好的选择，因为要为模型复杂度付出代价。

VC_message

样本复杂度（Sample Complexity）

根据理论而言，样本复杂度大约是VC维的10000倍，而实际应用中，只需要VC维的10倍的量就够了。
我们这里介绍的VC Bound的条件是非常宽松的，这使得在样本复杂度的估计上可以和理论值相差很大，原因如下：

• 我们利用Hoeffding对任何的分布和任何的目标函数来推测真实的错误率
• 我们利用成长函数mH(N)来代替假设集合的数量，确保可以使用任何数据
• 用VC维表示的多项式来代替成长函数，使得我们只通过VC维就可以了解某个假设空间的性质
• 使用union bound来避免最差的状况

以上有关VC Bound传递的哲学信息可以很好的指导我们进行机器学习算法的实践。

最后一句话

最后总结一句话，如果我们假设集合的VC维是有限的，并且有足够多的数据，我们的算法又可以找到一个假设使得训练错误率很低的话，我们就可以学习到有效的模型或知识。

参考资料

机器学习基石课程，林轩田，台湾大学

转载请注明作者Jason Ding及其出处
Github主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)

【机器学习基础】VC维与模型复杂度、样本复杂度