内容
一、学习VC维前概念介绍
二、breakPoint对growth function的限制
三、边界函数Bounding Function(growth function的限制)
四、VC bound的图形化定义
################################################################################
一、学习VC维前概念介绍
1.growth function
growth function也是我们前面学得effective(N),表示对数据D分类的最大结果数。比如说现在数据集有两个数据点,考虑一种二分类的情况,可以将其分类成A或者B,则可能的值有:AA、AB、BA和BB,所以这里增长函数的值为4。

注:红色方框代表成长函数的数目,假设空间H在M上最大的数目。当N=1时,有两种h;当N=2时,4种h;当N=3时,如果3个点都是散开的那么有8种可能划分,如果3个点排成直线那么有6中划分,故根据公式取值8;当N=4时,有两种是不能线性可分的,这样只有14个结果。所以不是所有结果都是2^n。这样使得m=effective(n)<M,使p小于的结果不是无穷的。
四种growth function

注:举例子在划分2个点的时候,growth function的个数是4个。因为没有限制(positive是正向必须为0),所以这是为N+1=2+1=3。去除了(o,x)的情况。(具体四种gf的描述过程见lin的第五节)
2.dichotomy(对分)
对于二分类问题来说(二分类),H中的假设对D中m个示例赋予标记的每种可能结果称为对D的一种对分(dichotomy)。
3.shatter(打散)
打散指的是假设空间H能实现数据集D上全部示例的对分,即增长函数= 2^n。
4.Break Point (断点)
如果按照2^m这种趋势增长那简直是没天理了。上面说道了,随着m的增大,一定会出现一个m使假设空间无法shatter。这种不满足2^n的情况说明增长函数从这个点开始变缓了,是一个可喜可贺的重大突破,所以我们把第一个不满足shatter的m值称为break point。(这里翻译成突破点)
二、Break Point对growth function的限制
1.growth function的个数是最大的对分个数(这里有breakpoint的限制)

注:breakpoint这个点表示此是时growth function的个数不是2^n。
2.假设对于一个问题,minimum break point k = 2(对于任意2个输入,H不能穷尽所有划分),基于该条件我们做出推论:

解释:当N=1时,growth function 的个数为2;当N=2时,growth function 的个数为3,此时2是BreakPoint。
3.那么当N=3时,growth function是多少呢?
任意3个输入(x1, x2, x3),我们一定能找到以下3个合法的划分:
Step 1:一个对分时,观察是否任意两个点被shatter(否)

Step 2:两个对分时,观察是否任意两个点被shatter(否)

Step 3:三个对分时,观察是否任意两个点被shatter(否)

Step 3:四个对分时,观察是否任意两个点被shatte
在寻找更多划分之前,我们要明确一点就是因为k=2,所以(x1, x2, x3)中任意2个点都不 能被shatter,所以下面这个划分不可能出现,因为(x2, x3)所有4种可能的划分被穷尽了:

但是接下来的划分就可能了:

再之后,你发现不论再寻找什么划分,总有两个点被shatter,所以,N=3时成长 函数的maximum possible value就是 4 了。而且 4 << 2^3=8。综上我们发现,当 N > break point k,成长函数的maximum possible value显著下降并远小于 2^N。
Step 4:得出结论

4.猜想

三、边界函数Bounding Function(growth function的限制)
1.边界函数Bounding Function B(N,k):当BreakPoint=k时,最大的可能growth function的个 数。

所以有:

当k=1时,给定任意N个输入,只能有一种划分的可能,因为任何第二种划分都会 导致有一个点被shatter,这与k=1相悖,所以:

当 N<k 时,N个输入一定都能被shatter,所以 B(N,k)=2^N:

当 N=k时,首次出现N个输入不能被Shatter,所以 B(N,k)=2^N - 1 一定没错:

综上,在确定B(N,k)的过程中我们已经把软柿子都捏了,现在讨论N>k的情况。我们猜测 B(N,k) 与 B(N-1, k-1) + B(N-1, k) 也许有关系。以B(4,3)为例,4个输入中任意3个都不能被shatter,用一个简单的程序遍历所有2^16个划分组合得到B(4,3)=11。故得出下表:

注:生成的表说明BP对growth function的限制,当N一定且K不同时, 产生growth function的个数不一样。在我们没有引入breakpoint前,举个例子,当N=3时,最大growth fnction的个数是8;当引入breakpoint,k>=4时,最大growth fnction的个数是8。
最终(边界函数的成长性为O(N^(k-1)))

四、VC bound的图形化定义
1.把备选函数集H中备选函数的数量M用成长函数代替,我们得到:

注:证明过程见 https://blog.csdn.net/songzitea/article/details/43112233
网友评论