1.1.3 VC维理论

统计学习理论的一个重要内容是VC维理论，它是建立在点集被“打散”的基础上，是关于函数集学习性能的指标。假设集合T是一个由X上取值为1或者-1的函数值组成的集合，则集合T的VC维定义为

式中，当{m:N（T,m）=2m}是一个无限集合时，其VC维等于无穷大。

由VC维的定义知，对于一个假设函数集，如果存在h个样本可以被函数集中的函数按所有可能的2h种形式分开，那么就认为函数集可以把h个样本打散，函数的VC维就是它能够打散的最大样本数目h。若存在h个样本能被打散，但任意h+1个样本不能够被打散，则函数集的VC维就是h。若对于任意数目的样本都存在函数能将其打散，则称VC维是无穷大。

由Vapnik和Chervonenkis提出的VC维理论反映了函数集的学习能力，一个函数集的VC维越大，则学习机器就会越复杂，学习能力就会越强。但到目前为止，还没有确定的计算函数集VC维的理论。只一些特殊函数集的VC维可以准确知道；对于复杂的学习机器，其VC维的确定还是一个待研究的问题。