VC维度的确切定义是什么?

数据挖掘 机器学习 分类 vc理论
2021-09-14 23:47:31

我正在从 Andrew Ng 斯坦福大学的讲座中学习机器学习,并且刚刚遇到了 VC 维度的理论。根据讲座和我的理解,VC维度的定义可以如下:

如果你能找到一组n点,以便它可以被分类器粉碎(即分类所有可能的2n标签正确),你找不到任何一组n+1 可以粉碎的点(即对于任何一组 n+1 点有至少一个标注顺序,使得分类器不能正确分离所有点),则 VC 维度为 n.

教授还举了一个例子,很好地解释了这一点。这是:

让,

H={se F l一世ne一个r Cl一个ss一世F一世ers 一世n 2 D一世ens一世ns}

那么任何3个点都可以分类为 H 正确分离超平面,如下图所示。

在此处输入图像描述

这就是为什么 VC 维度 H是 3。因为对于 2D 平面中的任意 4 个点,线性分类器不能粉碎所有点的组合。例如,

在此处输入图像描述

对于这组点,无法绘制分离超平面来对这组点进行分类。所以VC维度是3。

直到这里我才明白。但是,如果我们遵循某种模式呢?

在此处输入图像描述

或者三点重合的图案,这里也不能画出三点之间的分离超平面。但在 VC 维度的定义中仍然没有考虑这种模式。为什么?在 16:24观看的讲座也讨论了同一点,但教授没有提到这背后的确切原因。

任何直观的解释示例将不胜感激。谢谢

3个回答

VC维的定义为:如果存在n个点的集合可以被分类器粉碎,并且不存在n+1个点的集合可以被分类器粉碎,则分类器的VC维数为n。

定义并没有说:如果任何一组n个点都可以被分类器粉碎......

如果分类器的 VC 维度为 3,则它不必破坏3 点的所有可能排列。

如果在所有 3 个点的排列中,你至少可以找到一个可以被分类器粉碎的排列,并且找不到 4 个可以被粉碎的点,那么 VC 维度是 3。

在考虑 VC 维度之前,这些点应满足一般条件的点。在此处输入图像描述

所以根据我们需要找到的定义 2n可以被线性边界打破的排列,如图所示。所以,有没有其他不能破的安排也无所谓。

为了 n=4 我们找不到 2n=16 可以被线性边界打破的安排,因此我们说我们不能打破 4 在 2D 平面中具有线性边界的点。