前两篇文章已经完成了大部分的工作，这篇文章主要是讲VC bound和 VC dimension这两个概念。
（一）前文的一点补充
根据前面的讨论，我们似乎只需要用
来替代来源的M就可以了，但是实际公式却不是这样的，我们需要数学上处理几个小细节。具体的处理方法不讲，只提供大体思路。
可以看出，真实情况下，公式中多了3个参数。
这三个参数是怎么来的？
（1）我们无法计算Eout，所以我们另外采样N个数据，用它来计算E'in，代替Eout，这对于固定的一个h是可行的。
（2）现在我们就变成了取2N个点了
（3）使用Hoffding定理
（4）最终结论称之为VC bound
注意：整个证明过程中没有具体到PLA算法，也即这个过程对所有的机器学习算法都适用。
（二）VC Dimension
定义breakpoint –1 为VC dimension。表示为dvc
可以证明对于PLA算法：dvc(H)=d+1 (d为w的维度)。
其物理意义是是自由度。这一点非常重要，让我们可以直观地认识一个hypothesis set的dvc 。
（三）VC bound的两种解释。
（1）Penalty for Model Complexity
根据上述的关系，可以得出如下结论：
这里的一个重要结论是：一般情况下，最好的选择一般不会出现在Ein最小的地方。
（2）Sample Complexity。
dvc可以提供给我们关于D大小的信息。
可以看出，当δ，ε，dvc确定的时候，我们就基本可以确定样本量N的大小。
为什么理论上N≈10000dvc，实际上通常使用10dvc呢？因为我们得到的这个理论值非常宽松！为什么这么宽松呢？四条理由。
