机器学习基石-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|无限的情况下是可行的。

。

。