台湾大学林轩田《机器学习基石》学习笔记第5讲——Training versus Testing

一、Recap and Preview
我们先来看一下基于统计学的机器学习流程图：

• 该流程图中，训练样本D和最终测试h的样本都是来自同一个数据分布，这是机器能够学习的前提；
• 另外，训练样本D应该足够大，且hypothesis set的个数是有限的，这样根据霍夫丁不等式，才不会出现BadData，保证Ein≈Eout，即有很好的泛化能力；
• 同时，通过训练，得到使Ein最小的h，作为模型最终的矩g，g接近于目标函数；
• 这里注意到我们将Ein(h)≈Eout(h)这个过程称之为对h的test验证，对找到一个g使得Ein(g)≈0，这个过程称之为train训练。

• 第一节课，我们介绍了机器学习的定义，目标是找出最好的g，使g≈f，保证Eout(g)≈0；
• 第二节课，我们介绍了如何让Ein≈0，可以使用PLA、pocket等演算法来实现；
• 第三节课，我们介绍了机器学习的分类，我们的训练样本是批量数据（batch），处理监督式（supervised）二元分类（binary classification）问题；
• 第四节课，我们介绍了机器学习的可行性，通过统计学知识，把Ein(g)与Eout(g)联系起来，证明了在一些条件假设下，Ein(g)≈Eout(g)成立。

这四节课总结下来，我们把机器学习的主要目标分成两个核心的问题：

1. Ein(g)≈Eout(g)
2. Ein(g)足够小

上节课介绍的机器学习可行的一个条件是hypothesis set的个数M是有限的，那M跟上面这两个核心问题有什么联系呢？

• 当M很小的时候，由上节课介绍的霍夫丁不等式，得到Ein(g)≈Eout(g)，即能保证第一个核心问题成立。但M很小时，演算法A可以选择的hypothesis有限，不一定能找到使Ein(g)足够小的hypothesis，即不能保证第二个核心问题成立。
• 当M很大的时候，同样由霍夫丁不等式，Ein(g)与Eout(g)的差距可能比较大，第一个核心问题可能不成立。而M很大，使的演算法A的可以选择的hypothesis就很多，很有可能找到一个hypothesis，使Ein(g)足够小，第二个核心问题可能成立。
  
  从上面的分析来看，M的选择直接影响机器学习两个核心问题是否满足，M不能太大也不能太小。那么如果M无限大的时候，是否机器就不可以学习了呢？例如PLA算法中直线是无数条的，但是PLA能够很好地进行机器学习，这又是为什么呢？如果我们能将无限大的M限定在一个有限的mH内，问题似乎就解决了。

二、Effective Number of Lines
既然无限大的M会使得机器学习无效，那么M真的会是无限大么？它从哪里来的？

• M表示hypothesis的个数，而P[Bm]代表着对于hypothesis hm发生bad data的概率；
• 每个hypothesis下的BAD events Bm经过级联的形式满足不等式，不等式右边是当所有Bm都没有overlap情况下的概率最大值，是最坏的情况；
• 但实际情况下，往往不是这样的，Bm之间是有交集的，也就是说M实际上没那么大。
  

为了说明M实际上没那么大，以前面课提到的用直线把平面中的圈叉进行分开的例子进行说明：

• 当平面中只有一个点x1的时候，那么会有两种不同的线h1，h2，一种把x1划为+1，另外一种把x1划为-1；

  

• 当平面中有两个点x1、x2的时候，那么就会有如图的四种不同的分类方法；
  

• 当平面上有三个点x1、x2、x3时，那么久会有8中不同的分类方法；
• 可是当这三个点的坐标位置发生变化时，如下图：
  
• 这样的情况下，会发生其中有两种方案并不是线性可分的，因此只有6种不同的分类方法；
  
• 以此类推，我们发现随着点数的增加，分类方法即M并没有按照2^N程指数增长，而是小于2^N.
• 那么是否有可能M<<2^N，而不是无限大，从而机器学习是可能的。

三、Effective Number of Hypotheses

• 这里引入了一个新的概念——dichotomy(二分类)；
• dichotomy H与hypotheses H的关系是：hypotheses H是平面上所有直线的集合，个数可能是无限个，而dichotomy H是平面上能将点完全用直线分开的直线种类，它的上界是2N;
• 接下来，我们要做的就是尝试用dichotomy代替M。
  
• 这里再引入一个新的概念：成长函数（growth function），记为mH(N)。
• 成长函数的定义是：对于由N个点组成的不同集合中，某集合对应的dichotomy最大，那么这个dichotomy值就是mH(H)，它的上界是2^N；
• 那么如何来计算成长函数呢？以下举几个例子：

- 这是个一维的Positive Ray(正向射线)；
- 若线上有N个点，需要将其分成两个方向，一个方向是+1，一个方向是-1；
- 那么整个线可以被分为N+1段，因此mH(N)=N+1 <<2^N；

• 这个例子是个一维的Positive Intervals（区间）；
• 同样有N个点，需要将其分出其中一个区间是+1，剩下的是-1；
• 在这种情况下，mH(N)<<2^N；

- 假设在二维空间里，如果hypothesis是凸多边形或类圆构成的封闭曲线，如下图所示，左边是convex的，右边不是convex的。
- 在蓝色区域内是+1，蓝色区域以外是-1；

- 我们假设所有的N个点都在一个圆上，那么我们可以使用凸多边形把其中的几个点连起来形成一个convex，这样很轻易地我们就可以算出mH(N)=2^N；

四、Break Point
上一小节，我们介绍了四种不同的成长函数，分别是：

• 其中，我们发现positive rays和positive intervals这两种情况的成长函数都是polynomial(多项式的)，如果用mH代替M的话，当N无限大时，mH<<2^N；
• 而convex sets的成长函数是exponential(指数增长的)，即等于M，这种情况并不能保证机器学习的可行性；
• 那么，对于2D perceptrons，它的成长函数究竟是polynomial的还是exponential的呢？

• 这里再引入一个概念break point，是指当mH(k）随着k的增加在某一个k开始，mH(k)开始小于2^k，我们把这个k值定义为这个成长函数的break point；
• 当存在break point，意味着这个成长函数的成长速度开始在变慢了；
• 则根据这种推论，我们猜测2D perceptrons，它的成长函数mH(N)=O(N^k−1) ，具体分析在下一节课。

五、总结

1. 本节课，我们更深入地探讨了机器学习的可行性。我们把机器学习拆分为两个核心问题：Ein(g)≈Eout(g)和Ein(g)≈0。
2. 对于第一个问题，为了解决当M无穷大时的困境，我们探讨了M个hypothesis到底可以划分为多少种，而不是但计算个数，引入了dichotomy的概念；
3. 为了计算dichotomy set的大小，引入了另外一个概念成长函数mH(N)，并引入了break point的概念，来表征成长函数的成长速度。

Reference：https://blog.****.net/red_stone1/article/details/71104654