13.2.4  VC维数

VC维（Vapnik-Chervonenkis Dimension）是统计学习理论中一个重要的概念。它是一个与几何概念的维没有关系的纯粹的组合概念。它在统计学习理论中扮演着一个中心的角色。VC维是一个用来度量具有分类作用的函数集的具体分类能力高低的数值。粗略地说，为了可靠的学习，一个类所需要的样本的数量正比于那个类的VC维。因此对VC维的估计需要首先关注。

由数学知识中的排列组合理论可以知道，如果存在h个一样的相互独立的小球，现在要将这h个小球随机地放入两个不同的箱子A和B中，那么可以求出放入的方式有2^h种。可以理解为每个小球有两种选择，选择放入A箱子或者B箱子，那么h个小球共有2×2×…×2=2^h种情况。现在将A和B两个箱子看作两个不同的类别，将h个小球看作是观测样本，也就是说样本的划分情况共有2^h种。那么我们规定如果一个函数集，它最多能够实现将h个样本以任意的组合进行分类，那么称此函数集的VC维为h。如果此函数集能够实现将无穷多个样本以任意的组合进行分类，那么该函数集的VC维为∞。

虽然VC维的概念已经清晰了，但是对VC维的计算却至今没有通用的理论，所以怎样得到一个通用的计算VC维的公式是当前有待解决的问题。虽然计算公式尚未存在，但是对于某些特殊的函数集我们是知道它们的VC维的，如一个线性分类器，它的VC维是样本的维度加1；f（x，a）=sin（ax）的VC维则为∞。