第四讲介绍了机器学习是否可行的问题。

1. 从给定的资料D中，找出一个接近目标f的假设g是可行的。比如PLA。但是，找到的这个g能否用于D以外的地方，这就难说了。

2. Hoeffding‘s inequality回答了g是否能用于D以外的问题：

　　（1）In probability theory, Hoeffding‘s inequality provides an upper bound on the probability that the sum of random variables deviates from its expected value.

　　（2）将所有可能的输入X想象成一个罐子，罐子中的每一个球代表了一个输入的数据点x。对于找到的一个假设h以及目标f，若h(x) ≠ f(x)，则把x漆成橙色；若h(x) = f(x)，则把x漆成绿色。因为罐子X中有很多球x，无法直接得到橙色球的比例，所以从罐子中抽出N个球作为样本，估算整个罐子中橙色球的比例。由Hoeffding不等式可知，当N足够大时，样本中橙色球比例和罐子中橙色球比例的差距是有上界的。

　　（3）对于给定的h，称h在样本中的错误率为E_in(h)，而在整个输入空间的错误率为E_out(h)，由Hoeffding不等式有，P[|E_in(h) - E_out(h)| > ε] ≤ 2exp(-2ε²N)。因此，E_out(h)是无需知道。当E_in(h) ≈ E_out(h)且E_in(h)很小是，可以说E_out(h)很小，h大概很接近f。

3. 上面给出了验证某一个h是否接近f的办法，但仍不是学习。真正的学习是要从一堆假设中做出选择，而不是每次都给出相同的某个h。比如PLA，用不同的资料学习就会得到不同的直线，而不是得到同一条直线。若某个算法总给出相同的h，那么这个算法很可能是没有用的，不能学到什么。

4. 当有很多个假设时，可以想象每个不同的h把罐子中的球漆成不同的颜色：

很有可能选到的假设h的E_in很小，但是这个E_in很小的h，可能是偶然的。例：抛一个硬币5次，5次均为正面的概率很小。但抛50个硬币，每个硬币抛5次，其中一个硬币5次均为正面的概率就很大了。Hoeffding不等式说明的是只有一个h时，E_in和E_out差别很小。称E_in和E_out差别很大为BAD事件。如果某一份数据，使某一个h的E_in和E_out很大，称这份数据为BAD。由Hoeffding不等式可知，对于某个h，一份数据为BAD的概率上界为2exp(-2ε²N)。若某一份数据，对于假设集至少一个假设是BAD，则认为这份数据对于整个假设集是BAD，有

从上面可知，当假设集大小有限时，数据为BAD这件事发生的概率仍然是有上界的，所以只要N足够大，能保证E_in约等于E_out。如果算法A能找到一个E_in很小的假设，就可以认为机器学习到了东西。

机器学习基石第四讲笔记