大纲

Learning is Impossible

No Free Lunch Theory

假设有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,然后通过随机采样抽取出一部分球，计算黄球的比例v,我们可以说v可很能和u很接近，但不绝对。

Hoeffding不等式告诉我们，当抽样数目越多时，v于u接近的可能性越大
这时候，我们可以用v来推断u

Connection to Learning

我们把机器学习问题与上面那个罐子取球问题建立联系，对于一个固定的假设来说，

• 假设与目标函数的接近的可能性，可以类比为罐子中黄球的比例；
• 机器学习问题的输入空间的x可以类比为罐子中的球，黄球代表假设h(x)与目标函数f(x)不等，绿色代表假设h(x)与目标函数f(x)相等。
• 从罐子中抽取N个球类比于机器学习问题的训练集D{(xn,yn)},两者都是随机抽样，并且两种抽样样本和总体都是独立同分布的

所以当N足够大时，从训练集中h(x)≠y的概率就可以推论所有样本中h(x)≠f(x)的概率，这里假设没有噪声，即y=f(x)

因此这就是我们为什么在采样数据上得到一个假设，就可以推到全局。因为两者的错误率是PAC的，前者小了，后者也小了。

接下来我们引入两个概念

• Ein(h)：在采样数据中,h(x)≠y的概率
• Eout(h)：在所有样本中h(x)≠f(x)的概率

我们也可以写出数学形式

对于固定的假设，当数据足够大时，Ein(h)=Eout(h)是PAC(probably approximately correct )的,所以，当Ein(h)小的时候，Eout(h)也小

注意，对于一个固定的h，当数据足够大时，Ein(h)=Eout(h)是PAC，但不意味着h=f是PAC,只有通过演算法在假设空间中挑一个比较好的h，使Ein(h)比较小，从而使Eout(h)也比较小。这样我们才可以说h=f是PAC

Connection to Real Learning

在真正的学习中，我们往往面临多个选择，也就是说我们有很多个h,如下图所示，不同的罐子对应不同的假设。

如果有一个罐子中抽出来全是绿色的球，是否代表这个罐子对应的假设一定是好的？下面看一个抛硬币的例子

150个同学抛硬币，问至少有一个同学连续5次都是正面朝上的概率

可见这是一个大概率事件，但其实硬币的正面朝上的概率是12,一样的道理，抽到全是绿色球的时候也不能一定说明那个罐子就全是绿色球。当罐子数目很多或者抛硬币的人数很多的时候，可能引发Bad Sample，Bad Sample就是Ein和E_{out}差别很大，即选择过多带来的负面影响，选择过多会恶化不好的情形。

对于一个假设h的Bad Sample是指，在这个Sample上，Ein(h)和E_{out}(h)差别很大,但根据Hoeffding不等式来说，在单个h上，Bad Sample发生的几率很小

但在很多h的情况下，只要Dn在某个假设h上是Bad Sample，那我们就说Dn是Bad Sample,反之不是Bad Sample,这时候我们可以利用演算法在假设空间H中自由的选择h,

假设有假设空间有M个假设m,那么Bad Sample发生的上界是

当|H|=M有限时，N足够大，我们知道，Bad Sample发生的记录记得，我们可以认为从假设空间选取任意的h都有Ein(h)≈Eout(h)

如果我们通过我们的演算法选取yi个Ein(h)≈0的假设h,那么有Eout(h)=0是PAC的，所以学习是有可能的

但是如果|H|=M无限时，还怎么办呢？下节课解答