Machine Learning Foundations 7: The VC Dimension

Machine Learning Foundations 7: The VC Dimension


 
 

介绍Dvc是什么:最大的non break point。

从 perception 上来说就正好是 d+1。

从物理意义上来说就是有多少个自由度。

Dvc可以用来决定我们大概需要多少资料,让你不需要再去考虑H的细节,一个变量就决定了其性质。

 
 


 
 

上节课讲过的:我们可以确保我们的Ein(训练时的表现)和Eout(测试的时候的表现)一致,当我们的成长函数露出一线曙光且资料量足够大。

 
 

从这里触发我们可以引入 VC 维度的概念。

 
 


 
 

如果我们的成长函数在K处露出一线曙光,这个成长函数会被某个上限函数bound住,这个上限函数又会被某个多项式bound住,这个多项式的次方是K-1次方。

 
 

我们把上限函数的表格列出来,然后再把N的k-1次方列出来,我们来做比较。当N,K比较大的时候(这里N>2,K>3的时候),我们发现 N的K-1 次方就已经比我们的上限函数都大了,也就是说比我们的成长函数来得大。

 
 

因此我们就可以得到 我们的成长函数 会被 N的K-1次方 bound住。就化简了多项式。

 
 


 
 

上一节课证明的是:如果在我的H集合里面有任何一个h发生坏事情,这件事的几率很小很小,小的边界是:


 
 

这个结论的意义是,既然我们保证了大部分的时候都不会有坏的事情发生,也就是说我们的演算法被bound的情况下做的选择,这时候做出的选择g,这个g的Ein,Eout离得很远的几率也很小很小。

 
 

然后我们将上面的成长函数里面的 m 也可以替换成 N的K-1次方,如上面的式子的结论。这个替换的要求是N,k够大,原来的推倒的条件是N够大,这里更加严格要求k也要够大。

 
 

结论:所以下面两个条件让我们可以做机器学习:

  1. 我们要有一个好的h,就是他的成长函数要在某个地方存在一线曙光
  2. 我们要有一个好的data,就是说数据量够大

这样我们就可以说:训练的表现和未来测试的表现会是一致的,也就是可以机器学习。

这个时候如果配合一个好的演算法,能够选出一个g使得Ein很小的话,那就是学到东西了。

最后以上都是绝大几率的情况,不能做出完全的保证,应此还需要一点点运气。

 
 


 
 

VC 维度是什么?

 
 

我们试图给 break point 一个正式的名称,在这里我们真正标记的是最大的 non-break point。

VC 维度是:到这个点(维度)为止都是可以shatter的,超过这个点(维度)就是不能够shatter的,就是露出一线曙光的。

 
 

符号代表: Dvc = 最小的 breakpoint – 1。

不存在就是无限大。

 
 

N <= Dvc 表示有可能shatter,也就是存在某个资料会被shatter

k > Dvc 表示一定不能被shatter

 
 

符号换一下就可以说:

当N够大,Dvc也够大的时候,我们的成长函数比N的Dvc次方来的小。

 
 


 
 

再来看一下以前的例子怎么说。

 
 

所以:什么是好的h,就是露出一线曙光的h,也就是Dvc是有限的的时候。

 
 


 
 

那我们来看一下如果是一个好的h的时候,到底有什么好事。

好事就是 Ein/Eout 接近,且这个结论和演算法无关,和我们的资料的生成模型无关,和我们的目标f长什么样也没关系。

也就是说在最坏最坏的情况下我们都能确保Ein.Eout是非常接近的。

 
 


 
 

小练习。

 
 


 
 

有了上面的理论基础,我们重新回头来看我们讲过的第一种机器学习的方法:二维的PLA。我们来对应理论来分析一下这个算法。

 
 

资料线性可分PLA才可行,也就是说Ein=0。

资料都是从某个目标函数产生的,那就可以确保 Ein,Eout 有很大机会接近。

最后可以得到Eout接近0,也就是说这个演算法可用。

 
 

那接下来我们考虑在多维度的时候,这演算法还好不好用。

 
 


 
 

我们来分析如果今天是多维度的话,Dvc会是多少。

例子:

1维的时候,Dvc是2

2维的时候,Dvc是3

d维的时候,Dvc是d+1?

 
 

我们如何来证明 d维的时候就是 d+1,那就同时要满足下面两个条件,就可以满足:

Dvc <= d+1

Dvc >= d+1

 
 


 
 

先来个小练习

任意d+1笔资料都要能够shatter

 
 


 
 

首先来举一个特别的例子。

一共 d+1 笔资料,第一笔是原点,第二笔是在第一个维度有一个分量,第三笔是在第二个维度有一个分量。其他的都是0,以此类推,d 维度总共有 d + 1 笔资料。

把所有的资料排列成一个矩阵,矩阵最左边一列都是1,就是我们塞进去的 x0,第0个维度那个常数thershold所代表的资料。

 
 

譬如如果今天是二维,这个矩阵就包含原点,10这个点,01这个点三笔数据,这三个点是可以被shatter的。

我们要证明的是在d维度,这个矩阵我们也是可以被shatter的。

 
 

在数学上这个矩阵是存在反矩阵的,而且是唯一的。

 
 


 
 

要可以shatter,就意味着我们给任意一种排列组合y(任意一组ooxx组合),我们都能够做到 X乘上w等于正负y。

由于反矩阵的存在,也就是说如果 X乘上w等于负y,就可以有 X的-1次方乘上y等于w,用这个新的w,就有 X乘上新的w等于y 的存在。就是说我shatter了这一组y。

 
 

因此在这一组特别的资料上任意一组y都可以得到这个结论,所以这里就有 Dvc >= d+1 成立。

 
 


 
 

小练习。

任意D=2笔资料我们都不能够shatter。

 
 


 
 

我们要证明所有可能性比较麻烦,这里先回到上面的例子。在上面的基础上再加一笔资料来处理。

 
 

这里首先举一个2笔资料的情况,我们穷举就会有四种情况(00,10,01,11)。那么如图如果上下脚是oo,左下角是x的话,问号的那个点是x的话是不行的。

 
 

公式表示来解释:

因为有线性依赖的关系就可以得到


每项都乘上w以后也是相等的,就得到上面的情况。

蓝色红色各自對應,就会有


也就是说 wx4 这一项是大于0的,就是o,不可能是x。

 
 

也就解释了不能是oxox的情况。

 
 

结论就是:如果今天我们把x4表示成其他三个的线性组合,那么这个线性依赖的关系就会限制我们产生dichotomies的数量。

 
 


 
 

上面是特例,这里考虑d+2笔资料的情况。列出d+2笔的公式如上面,因为存在线性依赖就可以这么表示,每一项的正负号标识的ox。

 
 

我们考虑 d+1 的情况,都已经确定,也就是有


这个项存在正负号,也就决定了d+2这个项的符号是正还是负。也就是说我们没办法产生所有的dichotomies。也就是说任意的 d+2 个点我们都没有办法shatter。也就是证明了 Dvc <= d+1。

 
 


 
 

练习。

 
 


 
 

从上面就可以发现维度的重要性,h的参数可以用w的数量来表示,表示有多少自由度,每个自由度都可以自由调整。

 
 

VC 维度的物理意义就是 hypothiese自由度的维度。

 
 


 
 

举个例子:

positive ray的时候,我们有一个自由度可以调整。

Positive interval的时候,我们有两个自由度。

 
 

Dvc 的物理概念大概是:hypothiese的自由度。

 
 


 
 

我们回过头来看 learning 里面的两个关键问题:

  1. Ein,Eout是否接近。
  2. Ein是否够小。

 
 

以前我们用M来衡量:

M不太大的话对于第一个问题来说很好;M很大的时候对于第二个问题来说是好的。

 
 

现在我们用Dvc来衡量:

如果Dvc很小:对第一个问题很好,自由度小,坏事情几率小

如果Dvc很大:对第二个问题很好,自由度高,坏事情发生几率变大

 
 

因此我们再来看h的时候,Dvc就是我们要关注的h的性质。

 
 


 
 

小测验。

过原点的线性分割,去掉了w0,所以是d

 
 


 
 

我们再继续深入了解Dvc的意义。

首先我们用Dvc来更新一下 vc bound 的公式,得到如上面的写法,公示右边的项很小很小,我们用delta来表示。

 
 

坏事情发生的机会很小,也就是好事情发生的机会很大,也就是 1 – delta 的可能性。通过如上面的推导,我们可以得到:有很高的机会,Ein/Eout的差别会限制在e这个数值内。

 
 

 
 


 
 

这样进一步整理这个公式,就可以得到Eout的范围会被限制在两个范围内,见上式。在统计上就可以看作是置信区间。

 
 

注意:

左边的部分标做灰色,因为通常我们不大重视这部分;右边部分表示的是Eout最糟糕的情况会是怎样,这个我们比较重视。

根号里面的部分我们叫做model complexity。就是用来表示的意义是我们的 hypothiese 到底有多么的powerful。用大写的omgia来表示(三个变量:N表示多少个点,H表示Dvc是多少,dltea表示你觉得你有多幸运)。

 
 


 
 

VC 告诉我们的事情就是 有很高的几率Eout <= Ein + omega

 
 

也就是说我们可以用上面的图来表示,横轴Dvc,纵轴Error,趋势是Dvc变大的时候,Ein变小,omega变大,Eout是一个山谷型,最好的Ein会在中间。我们在未来会利用这个图来想办法设计更好的机器学习演算法。

 
 

这类也可以看出强大的h也不一定是最好的选择,因为你会付出更高的modelcomplexity的代价。因此我们不是要把Ein做到最低就好,而是要考虑在h的付出成本。

这一点非常重要,是机器学习算法设计的重要考虑因素。

 
 


 
 

VC bound 还包含另外一层意思就是样本的复杂度。

举例解释:你的老板想要的是Ein、Eout差最多0.1,我希望坏事情发生的机会最多10%,learning model的Dvc是3,那么我们需要多少资料才够?

我们先来试如果你采用100笔资料,这样你带入公式算一下会发现bound达到10的7次方,1000笔资料,10000笔资料的结果如上面所示,如果是100000笔资料的化,就会变得非常小,这样才算是真的学到东西了。

而这个满足上面所描述的规格,代入公式差不多会发现需要29300笔资料就可以满足要求。

 
 

你会发现需要的资料量理论上大概是 10000倍的Dvc 这么多。 但事实上确实不需要那么多,大概 10倍的Dvc 就够了。

这边就是说明了这个VC bound是非常宽松的。

 
 


 
 

宽松的来源是:

  1. Hoeffding 对于任何的分布,任何的目标函数都可以确保满足这个结论。
  2. 采用 mh(成长函数) 来替代 H,就是说我们可以采用里面的任何的资料集都满足这个结论。
  3. 用一个多项式来替代 mh(成长函数),这里取的是上限的上限的上限,这样使得我们只需要看Dvc就可以知道能不能机器学习,不用去管H的细节。
  4. 我们对于最差的状况采用了union bound,也就是说我们考虑最差的情况,但事实上我们没那么容易踩到最差的状况。

 
 

这边就解释了为什么理论上需要那么多资料。

 
 


 
 

练习

怎么减少坏事情发生的机会。

 
 


 
 

总结:

介绍Dvc是什么:最大的non break point。从 perception 上来说就正好是 d+1。从物理意义上来说就是有多少个自由度。Dvc可以用来决定我们大概需要多少资料。

 
 

这里只是说资料从某个distribuction出来经过某个目标函数,没考虑noise,只能对于binary classification。下一节我们尝试延伸Dvc的概念到不同的learning问题上面。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

1 Comment for “Machine Learning Foundations 7: The VC Dimension”

Comments are closed.