Learning From Data Lecture 7 VC维度

Segment1 VC维度的定义

VC维度是针对假说集合H而定义的一个量,即给定一个假说集合,有一个数值称为VC维度。

给定假说集合H的VC维度记作:

  • dvc(H)

定义其数值等于假说集合H所能“打碎”的最大样本数据量。即:

  • 满足mH(N)=2N的N的最大值。

注意:

  • 并不是说任何N个数据的样本数据都能被假说集合H打碎,而是只要存在任何一个N个数据的样本能被假说集合H打碎,这个N就是我们要的。

假设已知一个假说集合H的VC维度dvc(H),

  • 如现有样本中数据量N<=dvc(H),则假说集合H有可能能打碎这N个数据点。
  • 如果有样本中数据量k>dvc(H),则假说集合H没有可能打碎这k个数据点。

dvc(H)这个值实际上等于转折点k的最小值-1,因此可以改写之前得出的成长函数上限:

由:

grwoth function bound in term of break point

改为:

grwoth function bound in term of vc dimension

下面举例说明VC维度:

  • 对于正射线假说集合,最小转折点为2,VC维度为1
  • 对于2维感知器假说集合,最小转折点为4,VC维度为3
  • 对于凸集合假说集,不存在转折点,VC维度为无穷大

下面看VC维度与机器学习之间的关系:

最重要的结论是:

  • 如果假说集合H的VC维度是有限的,在给定训练数据D的前提下,假说集合H中挑选出的最终假说g有非常高的概率可以一般化(g≈f)。

这个结论与学习算法A无关,与生成训练集数据的概率P无关,与目标函数f无关。

原因是:

  • 在得到VC维度的过程中,我们一直考虑的都是最糟糕情况时的上限,因此使得这个结论是可以一般化的。
    (无论Hoeffding 不等式还是成长函数都是考虑最糟糕的情况)

learning digram

因此在VC理论中关心的内容仅剩下:

  1. 希望得到的g≈f
  2. 假说集合H,VC维度的来源
  3. 训练数据D

segment 2 感知器假说集合的VC维度

考虑1维感知器假说集合实际上就相当于正射线假说集合,其VC维度是已知的2。

已知,2维感知器假说集合的VC维度为3。

考虑3维情况下的感知器,这时候的感知器将对应于3维空间内的一个2维平面。

很明显,2维空间中无法被直线模型所打碎的4个数据点的情况在3维空间中非常容易被2维平面所打碎。

3dpecptron

因此,3维感知器假说集合的VC维度至少为4。

猜想说对于d维感知器假说集合,其VC维度为d+1。

从两个方向上加以证明,即:

  1. dvc(H)<= d + 1
  2. dvc(H)>= d + 1

首先证明dvc(H)>= d + 1 :

为了证明dvc(H)>= d + 1,我们只要尝试在d维输入数据空间(Rd)中构建特定的N=d+1个数据点,并且使得这d+1个数据点能被d维感知器打碎即可。

用如下矩阵来构建这d+1个数据点。

trivial matrix

矩阵相当于是令单位矩阵的第1列全部都为1。

这个矩阵的行列式为1,因此是可逆的。

对于任意的

y

我们都需要找到一个向量w,使得sign(Xw) = y。

实际上,对于这样构建的输入数据X,我们完全可以可以使得Xw=y,只需要令w=X−1y即可(X可逆)。

接着证明dvc(H)<= d + 1 :

为了证明dvc(H)<= d + 1,我们需要证明对于d维输入数据空间(Rd)中的任意d+2个数据点,d维感知器均不能将其打碎。

对于任意d+2个数据点:x1,x2…xd+1,xd+2

数据点的数量超过空间的维度。如果我们有超过维度的向量数量,则其中必然存在线性相关,即至少存在一个xj和其余所有xi满足:

linear dependent 

ai为相应的系数,必然的ai不可全为0。

在上述结论的基础上,考虑如下二分法:

  • 对于所有ai非0的ai,令yi = sign(ai),并且令yj=-1。

这样的一个二分法是d维感知器假说所不能实现的。

原因如下,由线性相关性知:

signal coeff

由于wTXi = yi = sign(ai),sign(ai)×ai显然>0

因此上面右边的和必然为一正数,即知道wTXj = yj必然>0,不可能满足yj=-1。

综合两个结论,得证对于感知器假说集合其VC维度满足:dvc(H)= d + 1 。

对于感知器假说而言,这个d+1与假说中的参数(w0,w1,…,wd)数量相同。

将感知器假说的VC维度与其参数数量做比较,是为了在直观感受上,给你这样一种感觉:假说的参数越多,假说集合的VC维度越高。


segment 3 VC维度的解读

一种理解VC维度含义的方法是看自由度(degree of freedom)。

给定一个假说集合,区分这个假说集合中不同假说的是参数,拥有不同参数值的两个假说是不同的假说。

也就是说,参数给了我们创造不同具体假说的自由度。

将参数想象成旋钮。

switch

当给定假说集合的时候,就相当于扔给你一个带有固定数量旋钮的控制面板,你可以通过调整各个旋钮来产生不同的假说。

  • 参数的个数是“模拟”(analog)自由度(含义为:连续地,对任何一个旋钮进行任何调整都会产生新的假说)。
  • 而VC维度则是将上面的模拟自由度转变为二元(binary)自由度(含义为:二元地,对任何一个旋钮进行任何调整都只可能产生两种不同的假说)。

因此VC维度所做的是对低层的数学推导进行抽象,让人只关心假说集合的自由度(表达力)。

考虑几个老伙计:

正射线假说集合:

positive ray

区别不同地正射线假说的是参数a的取值,仅仅这一个参数。而正射线假说集合的VC维度也为1。

正区间假说集合:

postive interval

区别不同地正区间假说的是区间的两个端点的取值,是两个参数。而正区间假说集合的VC维度也为2。

  • 因此实践中,我们大致可以认为假说集合的参数数量近似于VC维度的值。

但并不总是如此。

考虑如下感知器:

perceptron

其输入为单个变量x,输出结果为+1或-1,该感知器的参数为w0,w1两个,VC维度为2。

但是这不是我们的完整假说集合,我们完整的假说集合是若干感知器的套用:

counter examples

每个感知器都有2个参数,完整的假说集合一共有8个参数,但是这些参数重叠严重,实际的自由度仍然只有2。

  • 因此,实际上VC维度告诉我们的是假说集合中有效参数的数量。

下面考虑在已知假说集合的VC维度情况下,我们如何知道所需要的训练数据量。

回顾VC不等式:

inequality

其中有两个我们希望能够非常小的量,即ε和不等式的整个右边部分。

已知mH(2N)=Ndvc(H)。 令δ=不等式的右边部分。

在给定dvc(H),ε和δ的情况下,我们可以求解N。

(例如,我希望我的2维感知器假说至多10%的情况下误差大于5%,则dvc(H)=3,ε=0.05,δ=0.1)

在求解之前,先来看简单一点的情况,看Nde-N的曲线集合中N与d对曲线的影响:

d=4时曲线如下:

4

先增后减,我们希望这个值要足够小,因此需要N足够大。

d=5时曲线如下:

5

变化的规律依然是先增后减,同样希望这个值足够小,需要N足够大。

并且可以看到,对于同样的小值,d更大时,需要的N更大。

3

考虑对于给定的Nde-N值,看d与N的关系:

下图中y值(即Nde-N值)是取log后的结果,从里到外分别为d=5,d=10,d=15,d=20,d=25,d=30时的曲线。

plot

如果用一条水平线来截这些曲线,发现两两曲线被截之处的值几乎是与d的取值成比例增长的。

直观上说明为:了达到同样的Nde-N值,随着d的增长,所需要的N值是成比例增长的。

直观的结论是VC维度越大,需要的训练数据量越大,而且所需数据量几乎与VC维度成正比。

经验结果是通常需要N>=10dvc(H)的数据量。

补充一个林老师课上的例子,通过理论计算出的量会远大于经验结果:

vc N

原因是,VC理论由始至终都考虑到是最糟情况。


segment4 一般化的上限

从δ的表达式中求解出ε的表达式:

solve for epsilon

我们称右边这个根号项为Ω。

明显地有:

  • 在所有其他量均不变的情况下,VC维度越大,ε越大。
  • 在所有其他量均不变的情况下,训练数据量N越大,ε越小。

对原先的VC不等式做一个转变:

我们有1-δ的概率,选定的假说h的一般化误差的上限小于Ω

  • P[|Ein(h)-Eout(h)|<=Ω(N,H,δ)] >=(1-δ)

这相当于我们最终的一般化的上限:

  • P[Eout(h)<=Ω(N,H,δ)+Ein(h)] >=(1-δ)

对于这个式子,我们可以看出:

如果假说集合H变得更加复杂,VC维度上升,则Ein(h)变小,假说能够更好地拟合样本内数据,但是Ω随着VC维度上升而上升,导致Eout(h)不是一定变小,而是要看前两者变化的综合结果。

这部分内容在以后归一化部分继续讨论。

课程地址:

http://work.caltech.edu/telecourse.html

Leave a Reply

Your email address will not be published. Required fields are marked *