上节课介绍了机器学习可以分为不同的类型。其中，监督式学习中的二元分类和回归分析是最常见的也是最重要的机器学习问题。本节课，我们将介绍机器学习的可行性，讨论问题是否可以使用机器学习来解决。

一、Learning is Impossible

首先，考虑这样一个例子，如下图所示，有3个label为-1的九宫格和3个label为+1的九宫格。根据这6个样本，提取相应label下的特征，预测右边九宫格是属于-1还是+1？结果是，如果依据对称性，我们会把它归为+1；如果依据九宫格左上角是否是黑色，我们会把它归为-1。除此之外，还有根据其它不同特征进行分类，得到不同结果的情况。而且，这些分类结果貌似都是正确合理的，因为对于6个训练样本来说，我们选择的模型都有很好的分类效果。

再来看一个比较数学化的二分类例子，输入特征x是二进制的、三维的，对应有8种输入，其中训练样本D有5个。那么，根据训练样本对应的输出y，假设有8个hypothesis，这8个hypothesis在D上，对5个训练样本的分类效果效果都完全正确。但是在另外3个测试数据上，不同的hypothesis表现有好有坏。在已知数据D上，g≈f；但是在D以外的未知数据上，g≈f不一定成立。而机器学习目的，恰恰是希望我们选择的模型能在未知数据上的预测与真实结果是一致的，而不是在已知的数据集D上寻求最佳效果。

这个例子告诉我们，我们想要在D以外的数据中更接近目标函数似乎是做不到的，只能保证对D有很好的分类结果。机器学习的这种特性被称为没有免费午餐（No Free Lunch）定理。NFL定理表明没有一个学习算法可以在任何领域总是产生最准确的学习器。平常所说的一个学习算法比另一个算法更“优越”，效果更好，只是针对特定的问题，特定的先验信息，数据的分布，训练样本的数目，代价或奖励函数等。从这个例子来看，NFL说明了无法保证一个机器学习算法在D以外的数据集上一定能分类或预测正确，除非加上一些假设条件，我们以后会介绍。

二、Probability to the Rescue

从上一节得出的结论是：在训练集D以外的样本上，机器学习的模型是很难，似乎做不到正确预测或分类的。那是否有一些工具或者方法能够对未知的目标函数f做一些推论，让我们的机器学习模型能够变得有用呢？

如果有一个装有很多（数量很大数不过来）橙色球和绿色球的罐子，我们能不能推断橙色球的比例u？统计学上的做法是，从罐子中随机取出N个球，作为样本，计算这N个球中橙色球的比例v，那么就估计出罐子中橙色球的比例约为v。

三、Connection to Learning

下面，我们将罐子的内容对应到机器学习的概念上来。机器学习中hypothesis与目标函数相等的可能性，罐子里的一颗颗弹珠类比于机器学习数据x；选择一个h，对于一个x，当f(x)==g(x)时，把该弹珠涂成绿色，否则为橙色；从罐子中抽取的N个球类比于机器学习的训练样本D，且这两种抽样的样本与总体样本之间都是独立同分布的。所以呢，如果样本N够大，且是独立同分布的，那么，从样本中h(x)=f(x)的概率就能推导在抽样样本外的所有样本中h(x)=f(x)的概率是多少。

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

这里我们引入两个值Ein​(h)和Eout​(h)。Ein​(h)表示在抽样样本中，h(x)与f(x)​不相等的概率；Eout​(h)表示实际所有样本中，h(x)与f(x)不相等的概率是多少。

四、Connection to Real Learning

如果有一个h在你的资料上与f完全一致，那么h一定是最好的？

答案是不一定，就想抛硬币时，连续5次正面的硬币一定比其他硬币要好吗？

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

其中，M是hypothesis的个数，N是样本D的数量，ϵ是参数。该union bound表明，当M有限，且N足够大的时候，Bad Data出现的概率就更低了，即能保证D对于所有的h都有Ein​≈Eout​，满足PAC，演算法A的选择不受限制。那么满足这种union bound的情况，我们就可以和之前一样，选取一个合理的演算法（PLA/pocket），选择使Ein​最小的hm​作为矩g，一般能够保证g≈f，即有不错的泛化能力。

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

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

五、总结

本节课主要介绍了机器学习的可行性。首先引入NFL定理，说明机器学习无法找到一个矩g能够完全和目标函数f一样。接着介绍了可以采用一些统计上的假设，例如Hoeffding不等式，建立Ein​和Eout​的联系，证明对于某个h，当N足够大的时候，Ein​和Eout​是PAC的。最后，对于h个数很多的情况，只要有h个数M是有限的，且N足够大，就能保证Ein​≈Eout​，证明机器学习是可行的。