VC维

- 日理万妓 2022-08-07 13:49 145阅读 0赞

有关于VC维可以在很多机器学习的理论中见到，它是一个重要的概念。在读《神经网络原理》的时候对一个实例不是很明白，通过这段时间观看斯坦福的机器学习公开课及相关补充材料，又参考了一些网络上的资料（主要是[这篇][Link 1]，不过个人感觉仍然没有抓住重点），重新思考了一下，终于理解了这个定义所要传达的思想。

先要介绍打散(shatter)的概念：对于一个给定集合S=\{x1, ... ,xd\}，如果一个**假设类H能够实现集合S中所有元素的任意一种标记方式**，则称H能够打散S。例如下图S=\{x1,x2, x3\},它们的取值为\{-1,1\},就有8中组合方式，但是总能够通过二维的直线将其分开，故VC(二维线性分类器) = 3.

这样之后才有VC维的定义：H的VC维表示为VC(H) ，指能够被H分散的最大集合(样本)的数目。若H能分散任意大小的集合，那么VC(H)为无穷大。在《神经网络原理》中有另一种记号：对于二分总体F，其VC维写作VCdim(F)。

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

对于三个样本点的情况，下面的S1所有的标记方式是可以使用线性分类器进行分类的，因此其VC维至少为3（图片来自于斯坦福机器学习公开课的materials,cs229-notes4.pdf）：

![2012120316314872.jpg][]

虽然存在下面这种情况的S2，其中一种标记方式无法用线性分类器分类（图片来自于斯坦福机器学习公开课的materials,cs229-notes4.pdf）

![2012120316345533.jpg][]

但这种情况并不影响，这是因为，上一种的S1中，我们的H=\{二维线性分类器\}可以实现其所有可能标签情况的分类，这和S2不能用H分散无关。

而对于4个样本点的情况，我们的H不能实现其所有可能标签情况的分类（这是经过证明的，过程不详）如下图中某个S和其中一种标签分配情况：

![2012120316374136.jpg][]

可见，H=\{二维线性分类器\}的VC维是3。

**从这个解释过程可以看出，对于VC维定义理解的前提是先理解分散的定义。**分散中的集合S是事先选定的，而VC维是能分散集合中基数（即这里的样本数）最大的。因此，当VC(H)=3时，也可能存在S'，|S'|=3但不能被H分散；而对于任意事先给定的S"，|S"|=4，H不能对其所有可能的标签分配方式进行分散。**这里所谓“事先给定”可以看作其点在平面上位置已定，但所属类别未定（即可能是任意一种标签分配）。**

以上转载自<略有修改>：http://www.cnblogs.com/wuyuegb2312/archive/2012/12/03/2799893.html

## [VC维含义的个人理解][VC] ##

**在VC维的定义下，为了证明VC(H)至少是d，我们只需要证明至少存在一个大小是d的集合是可以被打散的。**

VC维反映了分类集的学习能力，VC维越大则学习机器越复杂（容量越大），遗憾的是，目前尚没有通用的关于任意分类集VC维计算的理论，只对一些特殊的分类集知道其VC维。 例如在 N 维空间中线形分类器的 VC 维是 N+1 。

[Link 1]: http://www.cnblogs.com/qqhfeng/archive/2012/05/16/2504035.html
[2012120316314872.jpg]: /images/20220805/ad686352ca334408a4783d80f58310ae.png
[2012120316345533.jpg]: /images/20220805/65f54680a1ae4b58bd219bf55498676c.png
[2012120316374136.jpg]: /images/20220805/777c66e0b24a4061a1244fd47dedd3fa.png
[VC]: http://www.cnblogs.com/wuyuegb2312/archive/2012/12/03/2799893.html