提纲：

1. 机器学习为什么可能？
   1. 引入计算橙球概率问题
   2. 通过用Hoeffding's inequality解决上面的问题，并得出PAC的概念，证明采样数据学习到的h的错误率可以和全局一致是PAC的
   3. 将得到的理论应用到机器学习，证明实际机器是可以学习

机器学习的大多数情况下是让机器通过现有的训练集（D）的学习以获得预测未知数据的能力，即选择一个最佳的h做为学习结果，那么这种预测是可能的么？为什么在采样数据上得到的h可以认为适用于全局，也就是说其泛化性的本质是什么？

课程首先引入一个情景：

如果有一个装有很多（数量很大以至于无法通过数数解决）橙色球和绿色球的罐子，我们能不能推断橙色球的比例？

很明显的思路是利用统计中抽样的方法，既然我们无法穷尽数遍所有罐子中的球，不如随机取出几个球，算出其中两种颜色球的比例去近似得到我们要的答案，

这样真的可以么？我们都知道小概率事件也会发生，假如罐子里面大部分都是橙色球，而我们恰巧取出的都是绿色，这样我们就判断错了，那么到底通过抽样得出的比例能够说明什么呢？似乎两者不能直接划等号。

由此，课程中引入了一个非常重要的概念，PAC，要理解这个，先得理解一个超级重要的不等式：Hoeffding's inequality

这个不等书说明了对于未知的那个概率，我们的抽样概率可以根它足够接近只要抽样的样本够大或者容忍的限制变松，这个和我们的直觉是相符的。式子最后给出了PAC的概念，即概率上几乎正确。所以，我们通过采用算出的橙球的概率和全局橙球的概率相等是PAC的。

这些和机器学习有什么关系？其实前文中提到的例子可以和机器学习问题一一对应：

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

整体证明机器可以学习分了两个层面，首先对于单个假设，根据Hoeffding不等式，当N很大时，其泛化能力强是PAC的；而实际上机器学习是从众多假设中挑Ein最小的（通过测试集找）假设，这个的理论基础是当M不大，N大，选到泛化能力差的假设概率低（用到了单个假设的结论）。