机器学习基石-Training versus Testing

Training versus Testing

Lecture4中我们学习了learning的可行性问题,我们发现在有足够的观测数据并且|H|有限的条件下,learning是PAC可能的,然后我们来研究|H|是无限的情况。

Recap and Preview

首先我们回顾一下整体的学习流程,在足够的资料N并且|H|是finite的条件下,根据Hoeffding,我们任取一个g有Ein(g)≈Eout(g)成立,然后我们选取一个Ein≈0,那么相应地实现了Eout也接近于0。

接下来,我们将前四节课的内容做一个总结。lecture1中我们的主要目的是找到一个g与我们的目标函数f尽可能接近,,lecture2中我们主要实现在使用PLA和pocket实现Ein(g)尽可能小,lecture3中我们主要研究批次数据、监督学习的二元分类问题,然后最后我们通过Hoeffding的推导实现Eout和Ein尽可能接近,整体上我们最终实现了Eout(g)接近于0。

于是我们可以将learning转化成两个主要的问题:1、能否确保Ein(g)和Eout(g)尽可能接近;2、能否做到Ein(g)足够小。

接下来我们看看|H|的大小M在这两个关键问题中扮演的角色:当M比较小时,根据Hoeffding问题1满足,但是由于选择较少所以不一定能实现问题2;当M比较大时,问题2满足但是问题1不满足。所以选择合适的M的大小是比较重要的。

然后,我们研究下M是无限大的时候,我们能不能实现Ein和Eout尽可能接近,我们知道的是Hoeffding的公式,然后我们的思路是能不能找到一个有限的数mh来替换M,最终达到证明的目的。

Effective Number of Lines

我们回到Hoeffding公式上,M表示hypothesis的个数,每个hypothesis下的BAD events Bm级联满足上图的不等式,我们发现如果M趋于无穷大的时候,不等式的右边将是一个非常大的数字,即Ein和Eout不接近。

但是值得注意的是,我们推导上面不等式时考虑的是最坏的情况(Bm之间都没有交集),然而实际情况是hypothesis间存在交集,所以M实际上没有这么大,也就是union bound目前是被高估了的。所以我们的目的是找出存在重叠的Bad events,并将它们归类为一类,最后看看我们的整体能否被拆分成有限个类别。

我们先看最经典的二元线性分类问题(二维),经过分析,我们知道平面上线的种类是有限的,一个点的分类最多有两种线,两个点最多有4种线,三个点最多有6种线,4个点最多有14(

我们发现,有效直线的数量总是满足

Effective Number of Hypotheses

首先我们定义一个新的概念:二分类(dichotomy)。二分类是将空间的点(如二维平面)用一条直线分成正类和负类,令dH为能将平面上所有点用直线分开的直线种类,他的上界是2^N,接下来我们尝试用二分类代替M。

我们再定义一个概念,成长函数(growth function),记为mH(N)。成长函数的定义为:对某个由N个点组成的不同集合,所有集合中二分类最大的那个值就是mH(N),他的上界是2^N,实际上成长函数对应的就是我们之前讲的effective lines的数量最大值。

接下来,我们讨论一下成长函数的计算过程。

我们先看一维的Positive Rays(分类上已切割点为分界点,两边对应不同类型)和Positive Intervals(分类上已切割区间为分界点,区间内外对应不同类型),容易计算相关的成长函数,发现两种情况都是远远小于2^N的。

最后我们看看二维空间中凸多边形或圆组成的封闭曲线的情况,当数据集按照凸分布时,我们容易计算它的成长函数为2^N。

Break Point

上节课我们的到来四个成长函数,其中positive rays和positive intervals的成长函数都是polynomial的,这样的情况下用成长函数替代M是可行的,但是convex sets的成长函数是exponential的,并不能保证机器学习的可行性。下面我们具体来看看2D perceptrons的成长函数的类型。

我们先定义一个概念break point,满足mH(k)≠2^k的k的最小值就是break point。

通过观察我们已经学的四种成长函数,我们猜测成长函数可能与break point间存在着某种关系:mH(N)=O(Nk-1)。如果这个条件能成立,我们似乎就完成了可行性的证明,这将是我们下节课的内容。

本节课,我们进一步分析机器学习的可行性问题,我们将机器学习拆分成两个核心问题,然后我们主要证明Ein和Eout相等的问题,我们的思路是想找到一个有限的数来替换Hoeffding中的M,我们最终定义了成长函数来描述hypothesis set的大小,然后猜想了成长函数和break point间的关系,如果能证明这个猜想成立,那么机器学习在|H|无限的情况下是可行的。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180409G15Z6Y00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励