Machine Learning Foundations 6: Theory of Generalization | Cheney Shen

Technology blog

Machine Learning Foundations 6: Theory of Generalization


 
 

一般化理论:机器是如何做到举一反三的

 
 

内容:

只要你有一个breakpoint,他其实是对未来每一个的数量都加上了很大的限制,也就是上面公式的数学归纳法,最后可以得到上限可以用一个多项式来表示,这个多项式可以取代原来公式中的M,从而证明2维情况下有了一个breakpoint一定是可以学习的。

 
 


 
 

上一节讲到:

因为M无限大的时候没有办法做机器学习,因此提出了成长函数m来取代M。

 
 

这里将探讨两个问题:

  1. 这个m到底是不是长得很慢
  2. 这个m如果真的长得很慢,那到底其能不能取代M

 
 


 
 

首先回顾一下m的定义:

这个有 N 个资料的 h 到底最多能有多少个 dichotomies(二分)

Break point就是第一个小于 2 的 N 次方个 dichotomies 的地方

 
 

再是四个上次的举例的情况回顾。

 
 

上次讲的一个非常重要的知识点就是:当k是breakpoint的时候,K + … 都是breakpoint。

 
 


 
 

假设:

我有一个hypotheses,他最小的breakpoint在2的地方。意思就是任意取h中两个点都不存在完整的四种情况(oo/ox/xo/xx)。

 
 

也就是说:

如果 N=1,m 一定等于 2(o/x),也就是说如果今天只有一个点一定有两种 dichotomies。

如果 N=2,因为breakpoint在2的地方,因此 m 就需要小于4,也就是说最多会是三个 dichotomies(oo/xx/ox/xo 任选3个)

 
 

如果 N=3(三个点),产生一种 dichotomy, 如下图的情况就是。这时候 breakpoint 也是在 k=2,也就是说随便找两个点,你都不能够产生四种不同的二分情况。也就是满足上面的假设最小的breakpoint在k=2。

 
 

看图理解:随便找两个点就是竖着选两行,这两行是否存在(oo,ox,xo,xx)。

 
 


 
 

如图,如果是两个 dichotomies。同样没有四种情况

 
 


 
 

三个 dichotomies 的情况:没有四种情况

 
 


 
 

四个 dichotomies,例如如图所示的情况。

 
 

如果看 x2,x3 上面,你就会发现存在四种情况了。这就和我们的假设,任何两个点都不存在四种情况(2的N次方)存在冲突。

因此不能加进这种情况。

 
 


 
 

因此我们回到原来的三种的情况,再加入另外的第四个,就符合假设(任意取两个点都不存在完整的四种情况)

 
 


 
 

如果是五个 dichotomies 的情况,如图所示,看x1,x3 就不符合假设。

 
 


 
 

五个的情况再换一个,一样不行。

 
 


 
 

再换一个,也不行。

 
 


 
 

经过一番尝试你会发现,在坚持假设的前提下,四个dichotomies就是极限,第五个dichotomies是加不进来的。

 
 


 
 

所以总结一下 N=3 的情况,最多最多就是4种,然后你会发现4和2的三次方已经差了很多了。

 
 

因此这边可以作如下猜想:

如果mh的最多可能性是小于一个多项式表示的,那么,mh本身也就是一个多项式级别的递增而已。

 
 


 
 

小练习

你假设的条件是一个都不能不一样,对于每一列,那么一定是最多只能有一种情况。

 
 


 
 

有了上面一小节追踪的概念,我们来为这个下一个定义。

 
 

Bounding function:我们有一个成长函数,这个成长函数的breakpoint在k的位置,你告诉我这个成长函数最多最多有多少种dichotomies。

 
 

换句话说:我不想要管我的成长函数到底长什么样子,而关心的是在排列组合上我到底能做出多少种排列组合。

在换句话说:我有一堆的向量由ooxx组成的,长度是N;但是我做出一个限制:对于这些向量我只看他其中K个维度(K列)都不希望看到满情形(2的k次方种情况)。

 
 

因此有了 bounding function的性质,我们就可以替代成长函数的作用;因此我们需要证明的是这个bounding function是一个多项式成长的。

 
 


 
 

我们来看这个 bounding function,有两个参数,一个是N(有几个点),一个是k(breakpoint位置)。

 
 

我们已知的两个加进表格。

 
 


 
 

再来考虑 k=1,这也是知道的。

 
 


 
 

我们还可以填充表的右上半部分:当N比K还来得小的时候,你最多产生的是2的N次方种。

 
 


 
 

再看一下 N=K 的情况:其中k=1/2 已知,得出的理由是不能是全部,因此就是满选择减去一种(2的N次方-1),同样的道理可以填充所有的其他k的情况。

 
 


 
 

先来个小练习

这里想说的是bounding function是上限,不一定有等号的发生。

 
 


 
 

我们接下来就要开始填表中比较困难的部分。

 
 

譬如我们开始填表中B(4,3),来考虑它与前面已知的关系。想办法让B(4,x)与B(3,x)建立联系来解。

 
 


 
 

来程式化解决这个问题:

搜寻所有种可能性16种,然后在里面选,一个个加进去看是否符合假设,符合加入,不符合不加入。做法和前面的人工解释B(3,2)一样。

结果会如上面的左图,最多可以是11种情况,可以填入表中。

 
 

又有了更多的一种情况,再去分析表中B(4,x)与B(3,x)的关系

 
 


 
 

我们把这个B(4,x)的解做一个整理:

橘色的解是成双成对的;紫色的是形单影只的。

 
 


 
 

B(4,3)就是这两部分相加,分别用 alpha/beta表示。

 
 

如果我们只看x1,x2,x3的话,我们得到的情况如上面左图:原来成双成对的减半算成一个了,原来形单影只的还在。

 
 

再有假设:B(4,3)的意思就是任何的三个点都不能满选择。

也就是说这里上面左图的 alpha+beta 也不能满选择,也就是说 alpha + neta <= B(3,3)。

 
 

这里得到第一个 B(4,x) 和 B(3,x) 的关系。

 
 


 
 

我们再来考虑:只看橘色的部分的x1,x2,x3,不管紫色的部分。

 
 

(shatter的意思就是满选择,符合2的N次方的情况)

 
 

Alpha 部分 x1,x2,x3 如果 shatter 那么就是不符合条件,因此 B(4,3) no shatter 意味着 B(3,2) 也因该是 no shatter。

 
 

因此获得第二个相关关系条件: alpha < B(3,2)

 
 


 
 

整理起来得到的结论就是 B(4,3) <= B(3,3) + B(3,2)

 
 


 
 

再推到 N,k 的情况也符合: B(N,k) <= B(N-1,k) + B(N-1, k-1)

 
 

也就是说可以把表填满了,填的是上限。

也就是说我们知道了bounding function的上限。

 
 


 
 

有了上面的这些,我们就可以证明一件事情:B(N,k) <= 上限的上限组合多项式

 
 

上限的上限组合 的最高项就是 N的k-1次方。

证明的方式就是表格和上面的推导公式,数学归纳法。

 
 

因此就得到了我们的预期:B(N,k) 一定是一个多项式级别的递增。

 
 


 
 

然后再检查一下以前的例子是否符合现在的结论。

 
 


 
 

小练习

 
 


 
 

好有了成长函数,我们来考虑能不能把其上限函数丢到原来的公式里面,然后事情就解决了。

然而没有那么简单。

 
 

我们能得到的是青色公式。这个证明非常复杂,这里我们不来推导怎么证明,只来和大家解释原理和常数的来源。证明当中的一下技巧很值得学习,得到了这些常数。

 
 


 
 

证明有三个步骤,第一个步骤:

 
 

我们有兴趣的是坏事发生的几率,一堆h里面只要有一个不满足条件就是不好的。

Ein 是有限多个,Eout还是无限多个。因此我们不能直接使用上面的公式,我们需要把Eout也变成有限多个。

我们采用一个数据集D’来验证估计结果,D’也可以得到一个估计结果Ein’,我们看能不能让Ein’来取代Eout。

这是可以的

我们来看有右边图解:Ein好的都在Eout周围,坏的Ein远离Eout。现在我们求出的Ein如果验证的时候Ein’原理Ein,也可以看作是不好的,相反如果很近就是好的。

 
 

换掉Eout后就得到最上面的公式。

 
 


 
 

Ein属于D,Ein’属于D’。也就是说如果我的h在D,D’上面的结果好,Ein,Ein’就会很近,也就是说我们可以在H里面挑好的h了。

 
 

右边的图解讲的是:分门别类(以前讲过)

你使用untion bound每次会有一个错误,当你不考虑重叠的时候,你会觉得像中间的图一样到处是问题,但是你考虑顶点归类后其实如最右边的图。

 
 

这里就引入了mh(2N)

 
 


 
 

现在我们就有了一个固定的h,然后想知道两次sampling的差别。

 
 

也就是说我们抓2N个出来,然后比较差别,通过hoeffding。

 
 


 
 

总结来说我们证明了一个定理: Vapnik-Chervonenkis(VC) bound

 
 

整理一下上面的那些参数也就出来了。

 
 

到此,我们解决了2D的perceptrons的证明。还没有证明的是任意维度的perceptrons。

 
 


 
 

小练习

这里要说明的是,这里花了大力气来推导出的bound并不是那么的准的,如何做下一步的改进,请看下一堂课的内容。

 
 


 
 

小结:

只要你有一个breakpoint,他其实是对未来每一个的数量都加上了很大的限制,也就是上面公式的数学归纳法,最后可以得到上限可以用一个多项式来表示,这个多项式可以取代原来公式中的M,从而证明2维情况下有了一个breakpoint一定是可以学习的。

 
 

下节课我们继续来探讨breakpoint。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

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

  • Categories

  • Tags