林轩田-机器学习基石 课堂笔记（五）Training versus Testing
1、 Recap and Preview
第一堂课我们告诉大家learning想做的事情，就是有一个未知的f，我们的演算法能找出一个g，使这个g≈f，保证Eout≈0。
第二堂课我们引入了PLA算法，可以将线性可分的样本正确的进行分类处理，并针对线性不可分的情况提出了噪音的概念和Pocket算法，这些算法目的都是让Ein≈0。
第三堂课我们介绍了机器学习的种类，知道目前我们的训练样本属性为batch & supervised & binary classification。
第四堂课我们主要介绍了机器学习的可行性。虽然由NFL定理，ML看似是不可行的，但根据之后统计学知识的分析，我们发现，如果hypothesis数量M有限且样本数据足够大，那么机器学习一般情况下是可行的，即在合适的情况下，Ein≈Eout。
因此我们机器学习的主要目标就具体为下面两个核心问题：
①Ein≈Eout
②Ein≈0
从而我们需要考虑到M与这两个问题之间的关系：
我们发现，选择一个合适的M是非常重要的。M很小时，Bad Sample出现的概率非常小，可以满足①，但由于假设空间过小，我们不一定能找到一个合适的方案满足②；M很大时，虽然因此会有很多选择方案使得满足②，但因此Bad Sample出现的概率会增大。如果M无限大，学习一定是无效的嘛？答案是否定的。比如之前学习的感知机，即使划分直线的方案有无限多，但是PLA依然可以很好的做出正确分类。
我们知道假设空间H的大小为M，通过上述公式，当M 无限大时，无法有效进行机器学习。这主要是由于我们通过union bound计算出的上界过分大了。实际上，由于假设下发生的坏事情是有很多几乎重叠的，其实我们可以得到更小的上界，因此我们想办法建立一个有限的mH代替无限的M，其中mH的值与h有关。
2、Effective Number of Lines
上面说到，当M=∞时，Bad events会很大，Ein和Eout也不接近。但这种union bound的形式得到的上界过分大，实际情况并不如此，很多情况下的h都是有交集的，例如：
所以我们需要找到重叠部分，将无限的M变成有限的数。比如：
①一个平面上如果只有一个点x1，则直线的种类有两种：将x1划分为+1或者将x1划分为-1
②一个平面上有两个点x1、x2，则直线的种类有四种：
③一个平面上有三个点x1、x2、x3，则直线的种类有八种：
PS：有时还可能小于八种（出现线性不可分的情况）
④一个平面上有四个点x1、x2、x3、x4，最多有十四种
我们发现，有效直线的数量总是＜=2^N（N为点的个数）。如果用effective(N)代替M，有effective(N)<=2^N，Hoeffding不等式可表示为：
如果可以使得effective(N)<<2^N，即右边等式接近于0，那么即使M无限大，直线的种类也是有限的，此时学习是可能的。
3、Effective Number of Hypotheses
引入两个概念：
①dichotomy（二分），相当于所说的有效假设的集合。输入规模为N时dichotomy的上界为2^N。
②growth function（成长函数），记为mH(H)，表示由N个点组成的所有集合中对应dichotomy最大的集合的值，其上界为2^N。例如之前的例子：
例1：一维的Positive Rays
可知如果直线上存在N个点，则有N+1种方式，可以得出它的成长函数为mH(N)=n+1。
例2：一维的Positive Intervals
可知如果直线上存在N个点，则要找出两个位置来区分这些点，利用排列组合，在N+1个位置中插入两个位置即可，再加上全为-1的情况，它的成长函数为mH(N)=1/2(N^2+N)+1。
例3：二维的Convex Set（任意凸多边形内部为+1，外部为-1）
（左图是Convex的，满足要求；右图不是Convex的，不满足）
显然可知，如果图上存在N个点，将它们按照如下的凸分布时，其成长函数为mH(N)=2^N。
4、Break Point
由之前的内容我们讨论出了四组情况下的成长函数
我们发现positive rays和positive intervals的成长函数都是polynomial的，因此用mH代替M时，情况就比较好；但是convex sets的成长函数等于M，是exponential的，因此不能保证机器学习的可行性，情况比较坏。对于2D perceptrons，下面我们来分析它的成长函数的情况。
首先引入一个概念— —Break Point（突破点）：对于某种假设空间H，如果m(k)<2^k， 则k是它的突破点。
PS：如果k是Break Point，那么k+1、k+2...都是Break Point。
显然我们得出四组情况下的Break Point
我们猜测成长函数的成长速度可能与break point存在某种关系。没有Break Point时，例如convex sets，它的成长函数是2的N次方；但有Break Point时，例如positive rays，Break Point k=2，成长函数是O(N)；positive intervals，Break Point k=3，成长函数是O(N^2)。因此我们可以假设如果Break Point存在且为k，那么成长函数的增长速度大概与N^(k-1)有关，比如2D perceptron的break point k=4，搞不好它的成长函数就在O(N^3)左右，如果能用多项式形式的成长函数代替M，就满足了机器学习可行的条件。