VC维举例以及理解

网上看了很多VC维的讲解，但依然云里雾里，我曾听过老师讲过两遍，也搜了很多解释，可能是我理解能力比较差，我始终无法深入明白是什么意思。又由于这个概念（或许）不是特别特别重要的概念，貌似也没有特别影响我做其它的实验以及学习，因为论文中强调这个的并不多，或者说我基本没在论文中见过有人讨论VC维，以至于每次见到即便没搞懂，下完课，吃罢饭我好像就忘了。今天回看统计学习方法时，想到这个概念，便了解了一下。

这篇博客并不准备长篇大论的讲各种基本概念，公式，旨在以两个小例子帮助我以后想到这个概念时可以迅速的想起它的意思，同时也给需要了解此知识的同学有所帮助。

定义（来自于我老师上课的PPT）：可以被H散列的点的最大数量成为H的VC维。

其中H是假设空间，什么是假设空间？ 

诸如 H  =  二维空间中的直线

又如 H  =  二维空间中轴平行的矩形

我以这两个假设空间举例来说明他们的VC维是什么？

对于空间中三个点，任意三个点，不管怎么摆放，大概也就如下这个样子（暂不考虑直线排列）

如果将这三个点赋于两个类，一共有以下8种情况

我们如果用一条直线去区分这两类，可以很显然的得到，这8种情况都可以被一条直线区分开。

但是如果对于平面中4个点，一共有2的4次方，也就是16种情况，这16种情况中有些情况必定可以被一条直线分开，

但这其中必定有以下这种状况（异或）：

这种情况，无论一条直线怎么画都是无法区分开的。

所以：我们认为 H  =  二维空间中的直线   这个假设最多能区分3个点，4个以上的点就不能完全区分开了，此时VC维就是3

同样的，类比于以上情况

假设空间有4个点，分为两类的话一共有2的4次方就是16种情况。如下

那么：用一个矩形总是可以将这4个点分开：

16种情况大家可以自己尝试。

而如果空间中5个点的时候，二维空间中轴平行的矩形这个假设应该存在有些情况不能正确分配（我没有实际证明，只是出自老师的PPT，大家可以思考一下）

所以：对于4个点，H  =  二维空间中轴平行的矩形 ，最多只能处理4个点，VC维是4.

有一些疑问：这几个点为什么只能分为两类？

或许和它的定义有关吧，这张图来自Wiki的定义。

另外，以上的图片来自于老师的PPT，对于三个点，如果并排成一条直线，是不是也不一定能用一条直线分开呢？

以下图片来自：https://www.jianshu.com/p/9214c838d9b1