VC维相关知识

假设空间H（Hypothesis Set）

输入空间D（X1...Xn）

1.增长函数（grown function）

是关于输入空间尺寸n的函数

假设空间对于D中所有实例实现分类（赋予标记）的分类方式的最大种数（有多少种分类方式）

最大值为2^n，但是很多增长函数都达不到最大值。

2.对分（dichotomies）

H对D的一种分类方式就是一种对分

3.打散（shatter）

H能实现D上全部n个实例的全部对分，就是打散，不能实现就是不打散。

4.Break Point

当n增大到一个值m时，增长函数就不能达到最大值2^n，m就是Break point，也就是第一个不打散的n

5.VC维

假设空间H的VC维是能被H打散的最大的示例集（数据集）的大小，即有： $VC(H)=max\{m:\prod(m)=2^m\}$ 其中 $\prod(m)$ 为假设空间在数据集大小为m时的增长函数。

对于一个假设空间H，如果存在m个数据样本能够被假设空间H中的函数按所有可能的 $2^h$ 种形式分开，则称假设空间H能够把m个数据样本打散（shatter）。假设空间H的VC维就是能打散的最大数据样本数目m。若对任意数目的数据样本都有函数能将它们shatter，则假设空间H的VC维为无穷大。

参考：https://www.zhihu.com/question/38607822/answer/149407083

巴特西