Q：学习的最终目的是什么？
A：学到去解决未知事物的能力。
Q：机器学习的目的是什么？
A：我们期望计算机能够在它没看过的案例中有同样好的表现，得出令人满意的结果。

统计学小故事

我们想知道，一个超级超级大的罐子里橙色弹珠比例μ是多少，但是我们没办法一个个数，因为太大了，所以我们只能用trick做一个小推论。

那么我们能够从手上已知的橙色弹珠比例ν去推断出整体未知的橙色弹珠比例μ吗？

谁给你的勇气？梁静茹吗？
不，是下面这个

Hoeffding’s不等式

直观来解释这个式子，ν跟μ超过我们错误的容忍范围ϵ的概率P小于等于一个很小的值（该值由我们的样本容量N和错误容忍度ϵ）

所以，这个不等式告诉我们一个事情，只要我们的样本数量N足够大，大致上ν跟μ会很接近。

延伸到Machine Learning

现在做个类比，

• 未知橙色弹珠的分布：当前选定的候选函数h(x)是否与目标函数f(x)相等。
• 橙色弹珠：h(x) ≠ f(x)
• 绿色弹珠：h(x) ＝ f(x)

那么，我们从罐子里抽一把弹珠出来，弹珠数量为N。如果资料量N足够大，而且这些x是随机 独立抽样产生的，我们就通过在一定数量范围N内，已知的当前选定的候选函数h(x)与目标函数f(x)的相似程度去推断：在整体上，未知的当前选定的候选函数h(x)与目标函数f(x)的相似程度。

该不等式表明，Ein(h)=Eout(h)也是PAC的。如果Ein(h)≈Eout(h)，Ein(h)很小，那么就能推断出Eout(h)很小，也就是说在该数据分布P下，h与f非常接近，机器学习的模型比较准确。

一般地，h如果是固定的，N很大的时候，Ein(h)≈Eout(h)，但是并不意味着模型最终训练结果g≈目标函数f。

因为h是固定的，不能保证Ein(h)足够小，即使Ein(h)≈Eout(h)，也可能使Eout(h)偏大。所以，一般会通过机器学习算法A，选择最好的h，使Ein(h)足够小，从而保证Eout(h)很小。固定的h，使用新数据进行测试，验证其错误率是多少。

所以，我们现在仅能做到的事情就是，确认当前选择的h(x)的表现好不好，只是一个验证！不是学习！

继续讨论（泛化误差上界 ）

现在我们有一个Hypothesis Set了！

对包含了很多h的hypothesis set，就不能简单的用Hoeffing结论了。一个小概率事件如果重复多次，其发生概率就会很大（如有150个人每人抛5次硬币，至少有一人五次均正面朝上的概率为99.15%，而单就一个人而言这个概率是1/32），这使得以下情形很有可能发生：基于样本D，在H中挑选出错误率最小的h，但实际上该h在整体上的错误率很大，即该样本D对于该h来说是BAD样本。

根据许多次抽样得到不同的数据集D，Hoeffding’s不等式保证：对于某个候选函数h(x)，大多数的D都是比较好的情形（即保证Ein≈Eout），但是也有可能出现Bad Data，即Ein和Eout差别很大的数据集D，这是小概率事件。

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

The Union Bound定义

其中，M是候选函数h(x)的个数(|H|)，N和ϵ与之前同义。该union bound表明，当M有限，且N足够大的时候，Bad Data出现的概率就更低了，即能保证D对于所有的h(x)都有Ein≈Eout，满足PAC，算法A的选择不受限制。那么满足这种union bound的情况，我们就可以和之前一样，选取一个合理的算法A，选择使Ein最小的hmin作为g，一般能够保证g≈f，即有不错的泛化能力。

所以，如果候选函数h(x)的个数M是有限的，N足够大，那么通过算法A任意选择一个g，都有Ein≈Eout成立；同时，如果找到一个g，使Ein≈0，PAC就能保证Eout≈0。至此，就证明了机器学习是可行的。

结语

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

主要介绍了机器学习的可行性。首先引入了可以采用一些统计上的假设，例如Hoeffding不等式，建立Ein和Eout的联系，证明对于某个h，当N足够大的时候，Ein和Eout是PAC的。最后，对于h个数很多的情况，只要有h个数M是有限的，且N足够大，就能保证Ein≈Eout，证明机器学习是可行的。