机器学习基石第四节 学习笔记

Feasibility（可行性） of Learning

1、Learning is impossible 学习是不可能学习的

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



2、Probability to the Rescue可能的拯救方案

已知u是罐子里橙色球的比例，v是N个抽取的样本中橙色球的比例。当N足够大的时候，v接近于u。这就是Hoeffding’s inequality：

P[|v−u|>ϵ] ≤ 2exp(−2ϵ2N)

Hoeffding不等式说明当N很大的时候，v与u相差不会很大，它们之间的差值被限定在ϵ之内。我们把结论v=u称为probably approximately correct(PAC)。

3、Connection to Learning 与机器学习的关联



我们不知道的： target f(x)

fixed hypothesis h(x) =? target f(x)



h is wrong <=> h(x) != f(x)

h is right <=> h(x) = f(x)



假设，我们已经有一个固定的h(x), 抓弹珠出来，相当于抓x出来

check h on D = {（Xn， Yn（f(x)））}

验证现有h(x) 的正确率。





修正h(x)的时候，通过已知的 Ein(h) = 1到N 的h(Xn) != Yn ，infer（推理）不知道的 Eout(h) = x到P求和 h(x) != f(x)



probably approximately correct 很可能大约错误



hypothesis 假说

exploited 开发，利用

bound 边界



这里我们引入两个值Ein(h)和Eout(h)。Ein(h)表示在抽样样本中，h(x)与yn不相等的概率；Eout(h)

表示实际所有样本中，h(x)与f(x)不相等的概率是多少。



同样，它的Hoeffding’s inequality可以表示为：

P[|Ein(h)−Eout(h)|>ϵ]≤2exp(−2ϵ2N)

该不等式表明，Ein(h)=Eout(h)也是PAC的。如果Ein(h)≈Eout(h)，Ein(h)很小，那么就能推断出Eout(h)很小，也就是说在该数据分布P下，h与f非常接近，机器学习的模型比较准确。

一般地，h如果是固定的，N很大的时候，Ein(h)≈Eout(h)，但是并不意味着g≈f。因为h是固定的，不能保证Ein(h)足够小，即使Ein(h)≈Eout(h)，也可能使Eout(h)偏大。所以，一般会通过演算法A，选择最好的h，使Ein(h)足够小，从而保证Eout(h)很小。固定的h，使用新数据进行测试，验证其错误率是多少。

4、Connection to Real Learning



假设现在有很多罐子M个（即有M个hypothesis），如果其中某个罐子抽样的球全是绿色，那是不是应该选择这个罐子呢？我们先来看这样一个例子：150个人抛硬币，那么其中至少有一个人连续5次硬币都是正面朝上的概率是



可见这个概率是很大的，但是能否说明5次正面朝上的这个硬币具有代表性呢？答案是否定的！并不能说明该硬币单次正面朝上的概率很大，其实都是0.5。一样的道理，抽到全是绿色求的时候也不能一定说明那个罐子就全是绿色球。当罐子数目很多或者抛硬币的人数很多的时候，可能引发Bad Sample，Bad Sample就是Ein和Eout差别很大，即选择过多带来的负面影响，选择过多会恶化不好的情形。



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



也就是说，不同的数据集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直线有无数条，是否这些推论就不成立了呢？是否机器就不能进行学习呢？这些内容和问题，我们下节课再介绍。

5、总结



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