这次Lecture主要讨论的是有限假设下的机器学习可行性。我们为什么能通过算法选出的定作，而又为什么一定与相接近呢？

Learning is Impossible?

这一部分主要讨论了这么一个问题：能够在数据集上满足的是否一定能有？

上图就说明了，在以外的数据中更接近目标函数是不确定的，而我们希望机器学习能做到所选模型能在数据集之外也有与真实结果一致的预测结果，而不是仅限于数据集中。

这就是机器学习的No Free Lunch（NFL）定理，表明了没有一个机器学习算法能在任何问题上都取得完美的结果，在未知数据集无限大的情况下，也一定存在另一个算法B能够在特定数据集上有更好的表现。

这就告诉我们，在机器学习中要具体问题具体分析，所说的一个学习算法比另一个算法效果更好，只是针对特定的问题，特定的先验信息，数据的分布，训练样本的数目等等。

Probability to the Rescue

接下来的问题是，在以上的背景下机器学习还能取得我们想要的结果吗？

那我们不妨先来看看我们是怎么对其他未知的东西进行推论的？

在一个装有很多球的罐子里，有橙色和绿色两种颜色的球，我们是怎么知道橙色球占多少的呢？统计学上的方法是抽样一部分，获得样本中的橙色球占比，从而推论出整个罐子中的分布情况。

但是是否样本内的比例是否能保证罐中的比例也是呢？答案是否定的，但是从概率来看，有较大概率能确定和是接近的，从数学上就用Hoeffding's Inequality来说明这一点：

不等式说明，在N很大的时候就能推断和是很相近的，而时就被称为probably approximately correct(PAC)。

从而，在不知道的情况下，我们就能通过大样本N下用来估计。

Connection to Learning

现在我们知道了在“罐子”问题中如何知道橙色球的分布，那在机器学习问题中又如何解决呢？

每个数据被视作一个球，映射中最关键的点是将抽样中橙球的概率理解为样本数据集D上h(x)错误的概率，以此推算出在所有数据上h(x)错误的概率，那我们通过什么来进行推论呢？就是Hoeffding's Inequality能证明两者是在大样本下PAC的。

从而引入两个值——

• 表示在已知样本中的概率，也就是在训练集上犯错概率；
• 表示在所有数据中的概率，也就是在整个输入空间中犯错的概率。

这是两个概率的数学定义。

从而Hoeffding不等式可以改写为——

这就表示也是PAC的。那在下，如果比较小，也就能推断也比较小，从而在该数据分布下h与f比较接近，机器学习的模型也就比较准确。

但是，h只是H中的一个特定hypothesis，学习算法会在H中选择一个h来作为g，而不是强制固定的某一个h。如果是确定某一个hypothesis的话，只能是“确认”而不是在“学习”。 强制选出的某一个h很有可能在其他数据上会比较大，同时也会比较大，这就不满足对机器学习的要求。

Connection to Real Learning

现在有M个罐子（M个hypothesis），其中某个罐子抽样全部都是绿色（全部满足），这种情况下我们能不能选这个罐子呢？或者说这个hypothesis是不是我们想要的g？

我们先看一个简单问题：150枚硬币，每个硬币投掷5次，其中至少有一枚硬币5次都是正面的概率有多大？这个事件是非常幸运的吗？结果是，这表示出现这个事件的概率是很大的，同时也说明本来是的概率会因为多次尝试而被放大发生概率。

当次数多时可能会引发BAD sample，也就是和相差很远，这是选择过多带来的负面作用。

根据许多次抽样得到不同的数据集D，Hoeffding’s inequality保证了大多数的D都是比较好的情形，但是也有可能出现Bad Data，即和差别很大的数据集D，这是小概率事件。

就像在上图中，所有合起来是整个输入空间，而满足不等式的h能保证其中BAD的是很少的，用数学表达式如下——

如果有M个hypothesis让学习算法进行选择，那么有BAD Data的时候就有

如果算法不能随意选择，按照算法标准选出的h有可能导致和相差较远，这就是BAD Data。就比如像下面这样的M个hypothesis中，有些D就是不好的数据，而像 这样完全没有BAD的，才是我们想要的，某列只要有BAD就不要。

在这种情况下，如果让算法自由自在选择h的话，选中BAD Data发生的几率有多少？也就是在M个hypothesis下的Hoeffding’s inequality。

以上就是在有限个hypothesis下的Hoeffding。在足够多的N，就能保证自由选择的算法是安全的，也就是是PAC的。

从而“合理的”算法就可以找到一个满足最低的作为，Hoeffding能保证也比较小。

于是就有更新的流程，机器学习是可行的——

而以上的都基于hypothesis是有限个，那无限个的情况呢？之后的课程继续讲解～

 

p.s. 这次Lecture感觉有点难懂，我的笔记上可能比较啰嗦，试图把内容说清楚。难免有些内容还理解得不到位，也可能会有错误的情况，欢迎学习这个课程的同学们一起来讨论交流指正错误 : )