本栏目（机器学习）下机器学习基石专题是个人对Coursera公开课机器学习基石（2014）的学习心得与笔记。所有内容均来自Coursera公开课Machine Learning Foundations中Hsuan-Tien Lin林轩田老师的讲解。（https://class.coursera.org/ntumlone-002/lecture）
第5讲——-Training versus Testing
从这一讲开始，讲的问题就是属于WhyCan Machines Learn的范畴了。
一、Hypothesis set大小的重要性
上一讲的一开始我们说Learning好像不可行，后来我们逐步发现Learning在某些条件下是可行的。这些条件就是，Learning的Data符合统计学意义上的某种分布（因此可以映射为从罐子里抽弹珠这样的问题），另外hypothesis set的选择是有限的。这样看起来Learning是可行的。
过去的四节课，第一节课就是说Learning的目标就是想找到一个g可以尽可能地接近未知的f；第二节课的时候我们不知道怎么做，但是决定先在看过的训练资料上做到尽可能好，也就是想办法让E_in(g)≈ 0；第三节课我们承认其实是在很特定的情况下做Learning，用批次batch的数据、用supervised监督式的学习、用二元分类等等；第四节课我们终于想办法把E_in(g)和E_out(g)连起来约等于了。那，第二节课做的事情——将E_in(g)弄得越小越好，便就真的实现了我们一开始实现的目标：我希望E_out(g)要很小。
由此可见，Learning的核心已经被拆成如下的两个问题，那hypothesis set的大小M是否会影响这两个问题的解决呢：M很小的时候，E_in(g)与E_out(g)可以认为是很接近了，可是学习算法选择有限了，不一定能选到一个E_in(g)很小接近0的hypothesis；M很大的时候，选择很多，学习算法可以选到一个很好的hypothesis，但是E_in(g)与E_out(g)不一致的坏情况发生的概率就变大了。
因此如此看来，M的正确选择是很重要的。至于无限大的M到底是不是会很糟糕，这个问题可能需要接下来的多节课之后才能得到答案。
二、无限的M，Hoeffding不等式
如果我们回顾一下Hoeffding不等式推导的过程，就会发现不等式右边求解的是一个概率上限，是将M种hypothesis坏事件发生的概率直接加和得到的结果。仔细想一下，如果两条直线很接近，那么他们出现坏事件的情况是会overlap的，所以直接加和的结果是over-estimate的。这样看来，，针对M是无限的情况，我们有必要将hypothesis set进行分类，从而得到更准确的概率上限。
很明显，训练数据是有限的，尽管hypothesis set中有无限多条线，但是可以按照对训练数据分类情况进行分类。举个例子，当训练数据只有1个时，无限的hypothesis set中就只有两类：1类将其分为+1，另一类将其分为-1；同理，当训练数据只有2个时，无限的hypothesis set中就只有8类。当训练数据只有3个时呢，初步看起来好像是8个，真的如此吗？考虑如下一种特殊的情况：
How about训练数据有4个时？如下图所示，画大叉的分类结果是没法用一条直线分出来的，也就是说这个时候hypothesis的结果只有7 x 2 = 14种，还下图对于完全相反的分类结果没有画出，例如第一幅全部分类为圈圈对应的就是分类结果全部分类为叉叉。
由此可见，对于N大小的训练数据，超平面有效的种类数量是有限的，肯定小于2^N个，那么我们就可以用这个有限的种类数量来代替原来Hoeffding不等式右边无限的M，如下所示。
三、Dichotomies的有效数量
上一节讲的将无限的hypothesis set按照对训练数据的分类情况，有一个专有名词叫做Dichotomies。它就是指hypothesis set将大小为N的训练数据分成的不同情形的集合。本节主要想求出Dichotomies的大小，这样就可以用来替换原来Hoeffding不等式中无限的M了。
经过上一节的分析，我们发现Dichotomies的大小是依赖于训练数据的分布情况的。那么我们就定义Grow Function为所有训练数据的Dichotomies最大者好了。
要想现在求出PLA的hypothesis set的Dichotomies大小还比较困难，我们可以先来看一些简单的hypothesis set的Dichotomies大小的求解。
案例一。h(x) = sign(x – a)。那么这种情况下Dichotomies大小为N+1。
案例二。h(x) = +1 iff x 在一个凸形状中，否则=-1。假设N个训练数据都分布在一个圆形上，任意选希望被分为+1的数据点连成一个凸多边形，只要将这个凸多边形稍微扩大一点点就达到了效果。这样看来Dichotomies大小为2^N，因为任何想要的分类情形都可以实现。
四、Break Point
再想一想，我们想做的事情是什么？想用Growth Function去取代原来无限的M。根据上一节的分析，Growth Function可能为polynomial多项式的，good；也可能为exponential指数级的，bad，因为不等式右边后面一部分随着N指数级减少，而Growth Function却又指数级上升的时候，我们就没法保证在N够大的时候不等式右边是一个很小的概率值。
既然如此，那我们对PLA的Growth Function到底是polynomial还是exponential就更感兴趣了。以前的分析我们只知道它随着N的增大<2^N，但仍不知道它究竟是怎样。
放弃等于又一次可以选择的机会。
