Machine Learning Foundations 5: Training versus Testing | Cheney Shen

Technology blog

Machine Learning Foundations 5: Training versus Testing


 
 

训练和测试过程:

 
 

首先把learning拆解成两个问题: Ein/Eout相似;Ein约等于0

然后考虑合并M的情况能有几种,也就是成长函数 growth function

再考虑成长函数的性质,到底从哪里开始出现曙光,就是break point

 
 

 
 


 
 

上一节讲到在一定条件下机器学习是可行的。

这里开始探讨无限大的 h 会造成什么样的问题。

 
 


 
 

当前的learning的整个流程图:

学习算法透过学习资料和g,通过前面的概率理论基础选择一个h。

上一节加上了两个条件:

  1. 训练资料和测试方法都来自同样的足够大的资料集,保证Ein、Eout相似
  2. 选一个Ein最小的h就可以得到一个Eout最接近0的最好结果

即可达到学习的效果。

 
 

上面12分别解释一下其实就是:

  1. 让Ein 接近0,让结果符合当前资料
  2. 让Ein 接近 Eout,让结果符合未知的资料,测试更准确

 
 


 
 

回顾一下过去四堂课学的内容

  1. 我们的数据符合的是位置的规则f,我们的盐酸法希望找出的是g,两者接近。也就是Eout(g)接近0。
  2. 我们从已有的资料可以让 Ein(g) 接近0。
  3. 我们是在一个很特定的情况下去做机器学习,就是有哪些学习类别。
  4. 处理Ein/Eout的关系:Eout 接近 Ein 最好

     
     

这里是回过头来理一遍得出上面的相同的结论的过程。

 
 

这里我们是把learning的核心问题拆解成了两个问题:

  1. 到底Ein/Eout接近不接近
  2. 怎么让Ein变得越小越好

 
 

我们再来看 H(M) 就是 所有h的集合 的重要性。

 
 


 
 

M 的两种可能性是否能满足上面的两个核心问题:

  1. M 数字比较大:坏事情发生的几率增加了,不能保证Ein/Eout相似,有足够选择能有一个Ein=0。
  2. M 数字比较小:Ein/Eout可以很接近,Ein的选择很有限,不一定能有一个可以接近0。

 
 

这里看出了 M 的重要性,选择正确的 M 和学习结果有很大关系。

无限大的M根本不好learning。

 
 


 
 

所以到这里问题是:我们要想办法解决无限大的M的问题,选择一个合适的有限大的M解决问题。

 
 

我们要把无限大的M换成一个有限大的m来解决learning的问题。如果可以换,则可以通过有限的m来解决无限M的问题。

 
 

如果能换,按上一节理论就有可能可以做机器学习。

 
 


 
 

先来个小练习。

 
 


 
 

我们首先要回答的是为啥 M 无限大的时候,没办法learning。

 
 

推导:

我们有一堆不好的事情(Ein/Eout差距太大);

我们今天有非常多的h,通过上一节讲的方法,对于一个h把所有的会发生不好的情况的几率级联起来。

问题在于: 几率的级联 小于等于 各个独立几率相加

当M无线大且有很多不好的事情的情况下,右边部分很多项不是0,则加起来的总和很有可能是无限大。这样这个上限就没有任何意义。

 
 

这个上限的

 
 


 
 

我们来看看这个上限出了什么问题:

 
 

以前我们可以使用这个上限的原因是坏事情不会重叠。1好h发生坏事情的dataset和2号h发生坏事情的dataset是不一样的dataset。

 
 

但是这件事情不大对吧。

如果存在两个很接近的h的dataset,则:Eout(h1)和Eout(h2)就很会接近,Ein(h1)=Eout(h2),也就是说发生坏事情dataset可能长成上图那样,会有很大的重叠。

我们前面在做这个上限的时候没有考虑这个叠加的情况,这样就会造成我们的上显示 over estimate,就造成了我们没有办法处理无限大的M。

 
 

所以我们要找出这些重叠的部分。

做法是看能不能把无线多的h分成有限多类,每一类里面是长得差不多像的。

 
 

下面我们讨论怎么样来对h归类。

 
 


 
 

举个例子:

考虑平面上的分割线,有无限多条。

 
 


 
 

只有一笔资料,则如果从这笔资料看出去的话,只有两种线,说这资料是正1,说这个资料是负1。

 
 



再来考虑俩个点的情况,对于两个点整体来说就有四种线。

 
 


 
 


 
 

对于三个资料,则有8种情况。

 
 


 
 

但是如果三个资料在同一直线上,则如果线性可分的化,就只有6种情况。

 
 


 
 

对于四笔资料的情况,也要注意非线性可分的情况要去掉。

 
 


 
 

因此,我们如果只从资料点看出去的话,得到的划分情况是有限的。

 
 

注意点:对于N个资料点

是小于等于2的N次方,因为要去掉非线性可分的情况。

最好是比2的N次方小很多,则原来公示里面的无限大的 M 可以被有限大的数值取代掉,当N够大的时候,整个就接近0。也就是说基本上都是好事。

 
 

条件:这个有限数字要比2的N次方小很多。

以后会证明。

 
 


 
 

小练习 22 种情况。

 
 


 
 

前面讲的是在平面上用线区分,那么对于高纬度的区分方法,我们怎么来确定到底有几种区分情况。

 
 

一个hypotheses到底可以做出多少种dichotomy?

Dichotomy: 二分

 
 

我们把h用在N个点上,用 h(x1…xn) 表示,代表的是 Dichotomy,不是 hypotheses。

两者的区别见上面的表格:主要是将无限多变成了有限多。

 
 

我们接下来会用 Dichotomy 的大小来换掉M。

 
 


 
 

Dichotomy 的大小取决于预先选好的 x1, x2 … xn,作为理论分析最好移除掉对这个预设的依赖,因此我们算最多有多少种。

也就是说我们有各式各样x的可能性,我选最大的dichotomy的大小,用mh来表示。

mh在上面平面的例子就是最多情况的那个数值。

 
 

这里给mh取个名字叫 growth function,这个值一定是有限的,最大就是2的N次方。

 
 

那我们考虑下到底能不能真的把函数数值公式写出来呢?

 
 


 
 

先看一个简单的hypothese:positive rays。

 
 

我们的输入就是一维的实数

我取某一个门槛值来区分正负1,任意一个hypothese(门槛值)结果就不一样

 
 

那么用这个hypotheses,我给你N个点可以切处多少种不一样的dichotomy。

N个点都不一样的情况切出的数量最多,最多就是N+1种。

也就是成长函数的长相: mh = N + 1

 
 

注意 N+1 远远小于 2的N次方

 
 


 
 

再看一个例子: positive intervals

某一个范围内正1,其余都为负1.

 
 

同样这样子的成长函数可以直接计算出来,如上图。

 
 

同样注意: 这个成长函数比2的n次方小很多。

 
 


 
 

再来一个例子:conves sets

凸的几何体内是正的,其余为负的

 
 


 
 

把所有的输入排在一个圆圈边上,这样保证凸,就很容易区分。

 
 

因此这个成长函数是 2的N次方。

 
 


 
 

小练习

 
 


 
 

上面讲了四个不同的成长函数。

上面也讲了我们原来想要的是用成长函数去取代原来的无限大的M

 
 

看式子右边如果成长函数小到不再是指数,当N足够大,则可以确保这个式子就会约等于0。

所以上面的例子前两个可以保证这个式子约等于0,后面两个不行。

 
 

因此重点是确认成长函数到底是多项式形式还是指数形式。

 
 


 
 

我们想要找出这个成长函数中第一个看起来很有希望的点在哪里。这样的点叫做 break point。

 
 

举例子1中:

三个点8种情况,四个点最多小于16种情况,也就是从四个点开始漏出了小于2的n次方的一线希望,这时候叫做break point。

 
 

找到第一个 break point,后面的也就统统都是 break point

 
 

 
 


 
 

因此原来的四个例子的break point在哪里,紫色字体就是答案。

 
 

通过上面的观察

会有猜想:

没有 break point 的时候一定是指数形式。

有 break point 的时候我们的成长函数的速度大概和N的k-1次方有关。

 
 

下一课的重点就是来证明。

 
 


 
 

小练习

 
 


 
 

小结:

首先把learning拆解成两个问题: Ein/Eout相似;Ein约等于0

然后考虑合并M的情况能有几种,也就是成长函数

再考虑成长函数的性质,到底从哪里开始出现曙光,就是break point

 
 

下一次课就是要来证明是不是有break point的时候,成长函数就和一个多项式差不多,远小于指数结果。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

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

  • Categories

  • Tags