背景:
The sample complexity bounds of the previous chapter are uninformative when dealing with infinite hypothesis sets.
解释: 在无限的假设集的基础上，怎样数量的样本对于训练是充分的？这要根据样本复杂度来定. 那么，样本假设集复杂度应该怎样定义？这就引出了growth function 和VC-dimension. 也就是生长函数和VC 维.
首先被引出的是Rademacher complexity的概念:
其实，笔者理解就是用Loss定义了复杂度.
growth function
排除growth function的一堆公式，直接上生长函数的定义吧:
Definition:
也就是说，生长函数就是x->y 所用的函数集的个数. 函数集的数目越大，说明数据集越复杂.
VC dimension
先给出定义, 再给出笔者自己的理解，和几个例子.
Definition:
笔者自己的理解, VC dim就相当于样本需要提取的特征.
example:
若H为一条直线(real line), VC dim 是多少？
若H为一个平面(Hyperplanes), VC dim 是多少？
若H为一个矩形(Axis-aligned rectangles), VC dim是多少?
分析: * 若H为一条直线, 那么数据集为(+-),(++),(-+),(--)的话怎么区别呢.可以通过一下的区分方法区别开:
+|-, -|+,++|, |--.
但是，如果数据集变成(++-) 之类的特征维度为3的就区别不开了.
因此, 若H为一条直线，VC dim =2；
若H为一个平面, 那么，数据集的(+，+，-),(+,+,+),(-,-,+) 可以通过在平面内，平面上方，平面下方来区别.
若特征变成4，就没有办法区分了. 因此，VC dim=3；
若H为一个矩形, 那么，数据集可以变成在每条边的里面还是外面，如下:
___
-| + |-
|__+__|
因此，VC dim=4
两个定理
1. VC dim(H=R^d的超平面)，那么VC dim=d+1;
2. growth function与VC dim的关系:
因此，在一般场景下，通过使用一个假设集的VC dimension来判断该假设集H可以cover的复杂度.
根据N维空间的定义:
其中，xi 表示第i个空间向量. 也就是说，该空间可以用n个空间向量来表示。可以用这样的方法理解一下VC维的具体定义，可以用n个特征向量来表征训练样本中所有的样本.
