Lec5：Training versus Testing

tips：符号含义参照Lec1

上一节中我们得到在一些条件下，learning is feasible！这一节我们将接着上一节探讨在 M = | H | 无限大时是怎样的？

learning实际可以分两部分看待：

1）Ein（g）≈ 0：在in - sample上应该尽量小，这是在train时希望的事情。

2）Eout（g）≈ Ein（g）：Eout要和Ein接近，这是test阶段希望的事情，在 Out -of -sample 上表现好才是目标！

1、Trade-off on M

上面的回顾说learning可以分为两个问题：1）Eout是不是和Ein足够接近？2）Ein是不是足够小？

那么 M 跟这两个问题有什么关系？

small M：1）yes！但  2）no！（选择太少）；

large M：1）No！（P[Bad]几率增加）但  2）yes！  

所以M太大太小都不好，trade off！当M无限大时显然bad，那之前的PLA是不对的吗？after 3 more lectures (；′⌒`)

我们要想办法解决large M，甚至无限大M 。已知：

如果我们可以用一个有限的 mH 代替M，似乎就可以解决这个问题了。下面将从理论上说明这件事是可以的。

2、H的kind有限

先回想一下M从何而来的？级联上限！通俗点讲，霍夫丁不等式只能保证一个h遇到bad data的概率小，M个h遇到bad data的概率就乘以M，如果保证union bound小，这时候A就可以在H中随意做选择。但是M无限大时boom！这个“上限”是哪里有问题呢？

考虑 h1 ≈ h2的情况，union bound 时区别对待h1和h2，实际上并不需要加两次霍夫丁，这就造成级联上限over-estimating过度估计！这就是问题所在。为了解决这个问题，我们可以把类似的hypothesis分类。如何归类？以perceptron为例，line的个数是无限多的，种类呢？

1个input时，x1，只有2种kind，一种是类似h1的，将x1划分为+1；另一种是类似h2的，将x1划分为-1.

2个input时，x1、x2，有4种kind，圈代表+1，叉代表-1，如下图：

3个input时，x1、x2、x3，有8种kind，如图：

到这你是不是觉得自己已经发现规律了，kind就是2的N方嘛！不要急，接着看3个input的情况，会一直有8个kind吗？考虑三点共线的情况，实际上会有2个kind不存在，这时只有6个kind。此外，当input重叠时，kind也会小于2的N次方。

接着看有4个input的情况，x1、x2、x3、x4，会有16种kind吗？

图中只给出了8张图，另外8张是跟此图对称的。其中一个kind无论如何都是实际不存在的，所以4个input的时候，最多14个kind。

把N个输入时最多的kind数量叫做effective number of lines，有效数量 ≤ 2的N次方。无限多的lines的kind有限，如果可以用有限的有效数量取代M，并且effective（N）<<2的N次方，那么M无限大时learning is possible！下面证明这是可以的。

3、Growth Function

先来介绍个新名词dichotomies，表示kind，在（x1，x2，...，xN）上，H包括所有的dichotomies.

不同的data，dichotomies的数量也会有不同，如上节3个输入的情况。所以我们只考虑dichotomies的最大值，用m（H）表示，称为“成长函数”growth function。

怎么计算成长函数？perceptron的较难计算，先看几个简单的例子：

1）positive rays：

h（x）= sign（x - a），实际就是1维的perceptron，mH（N）= N + 1，当N很大的时候，N+1 << 2的N次方；

2）positive intervals：

h（x）= +1 iff x∈[l，r），-1otherwise ，mH（N）= 1/2（N*N+N）+1，就是C N 2，从N个里面选两个点，再加上全部是叉的情况。当N很大时，mH（N）H<<2的N次方。

3）convex sets：

平面上凸region的集合，下图蓝色部分就是一个convex region：

h（x）=+1 iff x in region，mH（N）= 2的N次方。why？对于N个输入，不管哪些x为+1，我们都能做出一个凸多边形将+1包括在内，-1排除在外，如下图：

我们将mH（N）= 2的N次方的情况称为 exist N inputs can be “shattered”！

小summary，这节有三个新名词：dichotomies、growth function、shattered

4、Break Point

总结一下四个不同的成长函数：

如果我们要用成长函数取代M，m是多项式时，exp下降很快：good；m是指数型时，指数增长 * 指数下降exp，并不能确保bound小：bad.

那么perceptron的成长函数是指数的还是多项式的呢？下一章证明。在此之前再来介绍一个新名词：break point！

如果mH（k）< 2的k次方，k就是一个break point . 而且k+1、k+2、k+3......都是break point！我们通常关心最小的那个break point k.如2维perceptron 最小的break point 是4。如果shattered，就没有break point，如convex sets！

下一章我们将证明，如果有k，则mH（N）= O（N的k-1次方），即多项式。欢迎继续关注~~~

【如果您坚持读到了最后～就点个赞、打个赏激励下吧，哈哈～】