机器学习-特征选择-VC维的理解

vc维含义的个人理解

在看斯坦福机器学习公开课的第10课特征选择中，Andrew Ng老师引入了VC维的概念，可能是字幕翻译不准确的原因，不是很理解，自己在网上查了一些资料，下面说说自己的理解。

必要定义：

分散(shatter)：对于一个给定集合S={x1, … ,xd}，如果一个假设类H能够实现集合S中所有元素的任意一种标记方式，则称H能够分散S。

VC维：H的VC维表示为VC(H) ，指能够被H分散的最大集合的大小。若H能分散任意大小的集合，那么VC(H)为无穷大。

通常定义之后，会用二维线性分类器举例说明为什么其VC维是3，而不能分散4个样本的集合，这里也就是容易产生困惑的地方。下面进行解释。

上图中是对于三个样本点的情况，所有的标记方式（这里的标记方式指的是：三个点按照一定的位置摆好，然后给每一个点标记成X或者O）是可以使用线性分类器进行分类的。 因此二维线性分类器VC维至少为3。也就是说 对于三个点，只要能找出一种摆放方式，这种摆放方式无论怎么标记点的类别都能被线性分类器进行分类，那么就可以说集合S的VC维至少为3。

上图中三个点的摆放方式只是很多方式的一种，还有可能是三点一线的或者是三个点重合在同一个位置的情况。如下图：

上图这种情况不能被线性分类器进行分类，但是并不影响二维线性分类器的VC维。因为上面已经找到了一种无论怎么标记三个点，它们都能很好的被划分的摆放方式。（上图中左图表示摆放方式，右图表示划分类别）

而对4个点的情况：

无论怎么摆放4个点，都找不出一种摆放方式，使得把这几个摆放之后的点随机划分类别之后能被线性分类器成功分类（这是经过证明的，可以自己简单举几个例子），所以二维线性分类器的VC维为3。（上图中左图表示摆放方式，右图表示划分类别）