如何理解VC dimension?

  统计/机器学习 开放问题    浏览次数:10262        分享
5

怎么理解VC dimension?看了一些资料,依然不是很明白

 

数据痴汉   2017-04-05 08:10



   2个回答 
7

楼上的回答有一点不太正确,并不需要随意给出n个样本都可以正确分类。实际上,只要能找出某一种n样本,hypothesis class H 可以正确分类这个样本,那么我们就说VC 维度至少是n。直到我们确定任意的n+1样本都无法被正确归类,我们就得出结论VC维度是n。

实际上,如果hypothesis class H 是有限的,那么不用VC维度也可以得到一个对于generalization error的上界。但是对于无限的hypothesis class,我们用VC 维度来描述这个class的分类能力。可以想象,如果两个不一样的hypotheses,他们在某个样本空间上是无法被区分开,那么即使这两个hypotheses是不一样的,我们也并不需要去考虑他们的区别。换句话说,VC维度是一种更加精确的描述H能力的维度 (比起简单的数H有多少的hypotheses)。

SofaSofa数据科学社区DS面试题库 DS面经

枪炮师   2017-05-11 07:22

2

VC维度是以Vapnik和Chervonenkis的名字缩写命名的。

VC维度描述的是一个模型的复杂程度。


对于一个二元分类器F,F的VC维度等于F能够以0误差训练的训练集样本的数量。换句说说,如果F的VC维数是n,那么随意给出n个样本点以及它们的标签,F总能以100%的正确率去学习这个训练集,也就是训练误差为0。

比如1-近邻算法的VC维度是无穷大,因为对于任何n,1-NN的训练误差总是0。


SofaSofa数据科学社区DS面试题库 DS面经

高代兄   2017-05-05 09:55



  相关讨论

机器学习如何快速入门?

如何学习机器学习?有没有好的经验。

函数型数据分析

数据产品具体指的是什么?

baseline模型和benchmark模型的差别?

机器学习中的投票算法是指什么?

Bagging是什么意思?

强人工智能的研究现在怎么样了?

建立一个预测模型的流程是什么

bias-variance tradeoff是什么意思?

  随便看看

推荐系统中的召回(recall)是什么意思?

二维numpy.array转为一维的numpy.array或者list

二元分类为什么不能用MSE做为损失函数?

python里清除已经定义过的变量

随机梯度下降(sgd)的收敛问题