网站地图
3936.net
学霸百科 没有你查不到的
vc维

「官网地址0365.tv」-「永久地址0365.tv」

VC维(外文名Vapnik-Chervonenkis Dimension)的概念是为了研究学习过程一致收敛的速度和推广性,由统计学理论定义的有关函数集学习性能的一个重要指标。

传统的定义是:对一个指示函数集,如果存在H个样本能够被函数集中的函数按所有可能的2的H次方种形式分开,则称函数集能够把H个样本打散;函数集的VC维就是它能打散的最大样本数目H。若对任意数目的样本都有函数能将它们打散,则函数集的VC维是无穷大,有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。

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

如果一个假设空间存在突破点,则一定存在成长函数

可以得出:

如果输入数据量N(或者用k表示)大于VC维,则有k一定是假设空间H的突破点。

在N≥2,

一个有限的VC维总是能够保证寻找到的近似假设g是泛化的,即近似假设g满足

同时这一结论与下述部分没有关系:1.使用的算法,即使使用某种算法使得

即VC维可应对任意的假设空间,任意的数据分布情况,任意的目标函数。满足这一性质可以得到如图所示的流程图,其中灰色的部分表示上述几个不会影响

对于假设集合,这是一个由人工产生的集合,而VC维会告诉我们哪一个可以泛化,而哪一些不行。

对于数据集,VC维只能用一种概率性的说法解释,它只能告诉你在高概率下可以泛化;而如果恰好用了一个非常不好的数据集,就没有必要去对其进行泛化 。

以下两个条件保证了2维线性可分的数据是可以学习的:

1.线性可分的数据通过PLA算法运行足够长的时间(T步骤足够大),则会找出一条可以正确分类的直线,使得样本中没有产生分错类的情况,即

2.在训练样本和整个数据集都服从同一分布P的前提下,有VC限制保证了,在

由VC维的定义知:只要求出

证明:1.

取出N=d+1个在

对于任意的

因为y向量可以是任意一种形式的二分类,如果我们能够对任意一个y向量都能找到对应的

因此我们证明了

2.

对于任意d+2个样本点,X1,X2,…,Xd+1,Xd+2的维度均为d+1。那么当维度大于点的个数的时候,可以知道他们一定线性相关,即

构造一组

因此

假设不成立,因此在任何d+2个输入数据集中必然都存在不能满足的二分类,即

证明了

如果从假设空间的数量|H|角度上描述,则自由度是无限大的;但是从感知器在二元分类上这一限制条件入手,则可以使用VC维作为自由度的衡量 。

VC维和假设空间参数之间的关系:

当dvc=1时,假设空间有1个参数,即阈值。

当dvc=2时,假设空间有2个参数,即左右边界点。因此在大部分情况下,dvc大致等于假设空间参数的个数。

将一个1D的感知器输出连接到下一个1D感知器的输入,如下图所示,这样就得到了8个参数,然而它的自由度并没有增加。根据dvc,我们可以得出只需要一个感知器就足够的结论。