如何理解VC dimension?

  统计/机器学习 开放问题    浏览次数: 1132
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)。

枪炮师   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。


高代兄   2017-05-05 09:55



  相关主题

非参模型是什么意思?有哪些模型算是非参的?   2回答

Bagging是什么意思?   3回答

如何理解PAC Learning?   1回答

人类的第一个机器学习算法是什么?   2回答

bias-variance tradeoff是什么意思?   1回答

机器学习如何快速入门?   1回答

ensemble模型时,bagging和stacking有什么区别?   2回答

推荐开放数据库   5回答

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

机器学习中的奥卡姆剃刀原理是什么意思   5回答

机器学习算法的鲁棒性是什么意思?   1回答

hyperparameter与parameter的区别?   3回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!