题目三VC维的理解.docx

题目：VC维的理解，列举几个函数的VC维并说明自己的理解。 最初研究VC维是为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性收敛的速度，研究人员通过分析得出结论：经验风险最小化学习过程一致的必要条件是函数集的VC维有限，且这时的收敛速度是最快的。更为直观的等价定义如下：假如存在一个h个样本的样本集能够被一个函数集中的函数按照所有可能的2^h种形式分为两类，则称函数集能够把样本数为h的样本集打散（shattering）。指示函数集的VC维就是用这个函数集中的函数所能够打散的最大样本集的样本数目。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在h+1个样本集能够被函数集打散，则函数集的VC维就是h。如果对于任意的样本数，总能找到一个样本集能够被这个函数集打散，则函数集的VC维就是无穷大。有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂，所以VC维又是学习机器复杂程度的一种衡量。从另一个角度讲，如果用函数类{f(z,a)}代表一个学习机，a 确定后就确定了一个判别函数了EF，而VC维为该学习机能学习的可以由其分类函数正确给出的所有可能二值标识的最大训练样本数。从而可以得到这样的结论，平面内以圆为形状的函数集只能打散2个点，而不能打散三个点，同理平面内直线（线性函数集）最多只能打散三个点（1）面内以圆为形状的函数集只能打散2个点：平面内圆把一堆点分成两堆，对于2个点，要分成两类加上顺序就有2^2种。其中A、B表示2个点，+1，-1表示堆的类别， {A→-1,B→+1}表示A分在标号为-1的那堆，B分在标号为+1的那堆。这就是一种分发。以此类推。则有如下4种分法：{A→-1,B→+1}，{A→+1,B→-1}{AB→-1}，{AB→+1}圆都可以把两个点以以上四种形式打散，如下图所示：（2） 不能打散三个点：如下分布的三个点就不能用圆打散（3）平面内线性函数集只能打散3个点：直线只能把一堆点分成两堆，对于3个点，要分成两堆加上顺序就有2^3种。其中A、B、C表示3个点，+1，-1表示堆的类别， {A→-1,BC→+1}表示A分在标号为-1的那堆，B和C分在标号为+1的那堆。这就是一种分发。以此类推。则有如下8种分法：{A→-1,BC→+1}，{A→+1,BC→-1}{B→-1,AC→+1}，{B→+1,BC→-1}{C→-1,AB→+1}，{C→+1,BC→-1}{ABC→-1}，{ABC→+1}如下图所示：（3）找不到4个点。假设有，则应该有24=16分法，但是把四个点分成两堆有：一堆一个点另一对三个点（1，3）；两两均分（2，2）；一堆四个另一堆没有（0，4）三种情况。对于第一种情况，4个点可分别做一次一个一堆的，加上顺序就有8种：{A→-1,BCD→+1}，{A→+1,BCD→-1}{B→-1,ACD→+1}，{B→+1,ACD→-1}{C→-1,ABD→+1}，{C→+1,ABD→-1}{D→-1,ABC→+1}，{D→+1,ABC→-1}；对于第二种情况有4种：{AB→-1,CD→+1}，{AB→+1,CD→-1}{AC→-1,BD→+1}，{AC→+1,BD→-1}没有一条直线能使AD在一堆，BC在一堆，因为A、D处在对角线位置，B、C处在对角线位置。如图所示：对于第三种情况有2种；{ABCD→-1}{ABCD→+1}所以总共加起来只有8+4+2=14种分法，不满足24=16分法，所以平面找不到4个点能被直线打散总结：VC维反映了/view/15061.htm函数集的学习能力，VC维越大则学习机器越复杂（容量越大），遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N/view/674157.htm维空间中线形/view/895803.htm分类器和线形实函数的VC维是N+1。