VC维

vc维是支持向量机的核心概念，理解vc维的一些概念有助于掌握svm的本质。

我们知道在学习算法中需要选择适当的假设集F。实际上，这里的关键因素是假设集F的大小，或F的丰富程度，或者说F的表达能力，由老瓦和Chervonenkis提出的VC维 ，是对这种表达能力的一种描述。F上的VC为概念是建立在点击被F“打散”的基础之上的，首先引入点集被F打散的概念。

定义1. N（F，Zm） 设F是一个假设集，即由在X（n维欧氏空间的一个子集）上取值为1或者－1的若干函数组成的集合。记Zm＝{x1,x2,...,xm}为X中的m个点组成的集合。考虑当f取遍F中的所有可能的假设是产生的m维向量（f（x1），f（x2），...，f（xm））。定义N（N（F，Zm））为上述m为向量中不同的向量的个数。
这个向量无非是由1，－1组成的向量，每个分量只有两种可能的取值，因此max（N（F，Zm））＝2^m，于是有如下的定义：

定义2.（Zm被F打算） 设F是一个假设集，Zm={x1,x2,...,xm}为X中的m个点组成的集合。称Zm被F打散，如果N（F,Zm）=2^m.

定义3（增长函数） 增长函数N（F，m）定义为

N（F，m）＝max{N（F,Zm）:Zm包括于X}，

其中Zm={x1,...,xm}是X中的m个点组成的集合，max{.}是对这些点跑遍X而言的。

假设集F能打散的点的个数越多，表明F的“表达能力”越强。F的VC维就是使得N（F，m）=2^m成立的最大的m值。确切地，有如下的定义：

定义4（VC维）假设集F是一个由X上取值为1或者－1的函数值组成的集合。定义F的VC维为
VCdim（F）＝max{m:N(F,m)=2^m}.当{m:N(F,m)=2^m}是一个无限集合时，定义VCdim(F)=inf(无穷)。

由上面的定义可以看出F的VC为就是它能打算X中的点的最大个数。换句话说，若存在m个点组成的集合Zm能被F打算，且任一m＋1个点的集合都不能被F打散，则F的VC为就是m；若对于任给的正整数m都存在m个点组成的集合Zm能被F打散，则F的VC维就是无穷大。