VC维
目录

模式识别是一种基于数据的机器学习,学习的目的不仅是要对训练样本能够正确分类, 而且要能够对所有可能的样本正确分类(这体现在测试样本上),这种能力叫做推广(generalization)能力。 对于线性可分问题,分类器可以得到训练误差为0的无数多种可能的解,其中的最优解应该是推广能力最大的那个解。

对于样本x,其真实类别为y,权值参数为w,f(x,w)表示x分类结果,L(y,f(x,w))表示分类决策损失。 那么对某个w下所有训练样本的分类决策损失就是:

$R_{emp}(w) = \frac{1}{N} \sum_{i=1}^{N}L(y_i,f(x_i,w))$

这称作经验风险。在线性可分的情况下,通过感知器、Fisher、MSE等算法已经能使经验风险达到0。

当测试样本来临时,其错误率或风险为:

$R(w) = \int L(y,f(x,w))\mathrm{d}F(x,y)$

这称作期望风险。其中F(x,y)表示所有可能出现的样本及其类别的联合概率模型

统计学习理论指出,在有限样本下,经验风险和期望风险符合下面规律:

$R(w) \leq R_{emp}(w) + p(\frac{h}{N})$

其中p(h/N)称为置信范围,可以看出它与样本数N成反比,与h成正比。 这个h是依赖模式识别算法设计的,称为VC维(Vapnik-Chervonenkis Dimension)。 VC维反映了所设计的学习机器(函数集)的复杂性。

因此上式给出了有限样本下期望风险的上界。它告诉我们,在训练误差相同的情况下,学习机器的复杂度越低(VC维越低), 期望风险与经验风险的差别就越小,因而推广能力就越好。

发表评论