文章原创,最近更新：2018-07-25

学习链接:
4-3 Connection to Learning
4-4 Connection to Real Learning

学习参考链接:
1、台湾大学林轩田机器学习基石课程学习笔记4 -- Feasibility of Learning
2、《机器学习基石》学习笔记<4>

1.Connection to Learning

那么如何通过抽弹珠这个例子跟我们的Learning相联系呢？

下面，我们将罐子的内容对应到机器学习的概念上来。机器学习中hypothesis与目标函数相等的可能性，类比于罐子中橙色球的概率问题；

• 罐子里的一颗颗弹珠类比于机器学习样本空间的x；
• 橙色的弹珠类比于h(x)与f不相等；
• 绿色的弹珠类比于h(x)与f相等；
• 从罐子中抽取的N个球类比于机器学习的训练样本D，且这两种抽样的样本与总体样本之间都是独立同分布的。

所以呢，如果样本N够大，且是独立同分布的，那么，从样本中h(x)≠f(x) 的概率就能推导在抽样样本外的所有样本中h(x)≠f(x)的概率是多少。

映射中最关键的点是讲抽样中橙球的概率理解为样本数据集D上h(x)错误的概率，以此推算出在所有数据上h(x)错误的概率，这也是机器学习能够工作的本质，即我们为啥在采样数据上得到了一个假设，就可以推到全局呢？因为两者的错误率是PAC的，只要我们保证前者小，后者也就小了。

所以呢，现在我们的算法流程增加了一些部分:

• 从H中取一个固定h
• D（训练样本）是从X来的，同时也用x去测验h会不会接近f
• 用Eout(h)来代表我们不知道的那个东西，即f(或者说前面提到的罐子的所所有球球中orange的概率u)
• 用Ein(h)来代表N个样本（即D）中的出错率(或者说前面提到的橙色球球的概率v）

备注
Ein(h)表示在抽样样本中，h(x)与yn不相等的概率；
Eout(h)表示实际所有样本中，h(x)与f(x)不相等的概率是多少。

与v,u相同，对任何固定的h,将Eout(h)，Ein(h)代入Hoeffding's Inequality中也是成立的。和之前的球球问题一样，也具有如下特性：

• Hoeffding适用于所有的N和ϵ
• 因为不取决于Eout(h)，所以我们不需要知道Eout(h),f和P都可以未知
• Ein(h)= Eout(h)是PAC的

同样，它的Hoeffding’s inequality可以表示为：

还有一个问题需要考虑，上面的证明都是针对一个固定的h的，现在我们已经可以确定对任何一个固定的h,当样本数据足够大，Ein(h)是接近Eout(h)的,那么,这样就可以证明机器会学习了（g接近f）嘛？

但是如果A是强制性选择这个固定的h的，即A不考虑别的h就选这个fixed h时,上面的句子是错误的。因为，说不定别的h更加优秀（Ein(h)接近于0）。所以，一般会通过A选择最好的h，使Ein(h)足够小，从而保证Eout(h)很小。固定的h，使用新数据进行测试，验证其错误率是多少。

备用:一般地，h如果是固定的，N很大的时候，Ein(h)≈Eout(h)，但是并不意味着g≈f。因为h是固定的，不能保证Ein(h)足够小，即使Ein(h)≈Eout(h)，也可能使Eout(h)偏大。

测试练习:

答案是2.

2.Connection to Real Learning

假设现在有很多罐子M个（即有M个hypothesis,相当于有很多个h），如果其中某个罐子抽样的球全是绿色，那是不是应该选择这个罐子呢？

不行！
从扔硬币的例子也可以看出，当选择多了以后，会恶化BAD sample,也就是说，Ein和Eout的差值很大。最简单的扔硬币的例子，虽然可能有的人扔了10次都是正面，但是我们不能说正面的概率就是1，概率还是0.5。这个例子中10次就足以造成BAD sample.

• BAD sample: Ein 和Eout的差值很大
• BAD Data for One h:Eout(h)和Ein(h)差值很大，比如，Eout很大，离f很远，但是，Ein很小（样本出错很少，可是最后结果还是很差，这时候该怪样本）

我们先来看这样一个例子：150个人抛硬币，那么其中至少有一个人连续5次硬币都是正面朝上的概率是

单从一个人来看，正面朝上的概率是1/32

• 比如我今天来扔个硬币，扔了5次，全是正面朝上，这样看起来好像正面朝上的概率是1，但是其实还是1/2,Ein和Eout差值太大了 =>BAD sample
• 所以区别是，比较的预期不一样，BAD sample是说和yn不一样，BAD D是直接和f(x)不一样了，前者是样本里的，后者就是整体的了。

可见这个概率是很大的，但是能否说明5次正面朝上的这个硬币具有代表性呢？答案是否定的！并不能说明该硬币单次正面朝上的概率很大，其实都是0.5。一样的道理，抽到全是绿色求的时候也不能一定说明那个罐子就全是绿色球。当罐子数目很多或者抛硬币的人数很多的时候，可能引发Bad Sample，Bad Sample就是E(in)和E(out)差别很大，即选择过多带来的负面影响，选择过多会恶化不好的情形。

根据许多次抽样的到的不同的数据集D，Hoeffding’s inequality保证了大多数的D都是比较好的情形（即对于某个h，保证E(in)≈E(out))，但是也有可能出现Bad Data，即E(in)和E(out)差别很大的数据集D，这是小概率事件。

也就是说，不同的数据集D(n),对于不同的hypothesis，有可能成为Bad Data。只要D(n)在某个hypothesis上是Bad Data，那么D(n)就是Bad Data。只有当D(n)在所有的hypothesis上都是好的数据，才说明D(n)不是Bad Data，可以自由选择演算法A进行建模。那么，根据Hoeffding’s inequality，Bad Data的上界可以表示为连级（union bound）的形式：

如果h的个数M是有限的，N足够大，那么通过A任意选择一个g，都有Ein≈Eout成立
如果找到一个g，使Ein≈0，PAC就能保证Eout≈0。

这样，就证明了机器学习是可行的。

但是，如上面的学习流程图右下角所示，如果M是无数个，例如之前介绍的PLA直线有无数条，是否这些推论就不成立了呢？是否机器就不能进行学习呢？这些内容和问题，我们下节课再介绍。

测试题目:

答案是1

3.总结

总结内容如下:

• 从一个图片和二进制例子告诉我们NFL定理，告诉我们ML无法做到g完全等于f
• 对于一个固定的h,用Hoeffding不等式引出Ein,Eout,证明了对于一个固定的h,当N足够大时，Ein≈Eout是PAC的
• 对于multi-h情况下，用Hoeffding和union bound证明了只要M(h的个数)是有限的，且N足够大，Ein≈Eout是PAC的
• 最后，就证明了ML是可行的。