Feasibility of Learning

Feasibility of Learning

0.说在前面

1.Learning is Impossible

2.Probablity to the Rescue

3.Connection to Learning

4.Connection to Real Learning

5.作者的话

0.说在前面

前面几节主要介绍了机器学习的分类以及相关的二元分类问题及算法。

本节主要介绍的是机器学习的可行性。

1.Learning is Impossible

数据图

在本节中，林老师给出了如上图所示的例子：输入特征x是二进制的、三维的，对用有8种输入，其中训练样本D有5个。根据训练样本对应的输出y，假设有8个hypothesis，这8个hypothesis在D上，对5个训练样本的分类效果都完全正确。但是在另外3个测试数据上，不同的hypothesis表现有好有坏。

在已知数据D上，g与f近似相等，但是在未知数据上，g与f不一定成立。

而机器学习的目的是，希望我们选择的模型能在未知数据的预测贴近真实结果，而不是在已知的数据集D上寻求最佳效果。

上述这个例子中，我们知道对于数据集D以外的数据更接近目标函数似乎是做不到的，只能保证在D上有很好的分类效果。机器学习的这种特性被称为没有免费午餐(No Free Lunch)定理。

NFL定理描述为没有一个学习算法可以在任何领域总是产生最准确的学习器。不管是哪种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。从这个例子中，NFL说明了无法保证一个机器学习算法在D以外的数据集上一定分类或预测正确，除非有一定的假设条件！

2.Probablity to the Rescue

【问题】

上面提到：在训练集D以外的样本上，机器学习的模型很难，似乎做不到正确预测或分类，那问题来了，能否找到一些工具或者使用一些方法能够UI位置的目标函数做一些推论，让我们的机器学习模型能够变得更加有用呢？

【实例】

这里以实际的例子来说明问题。

假设有一个装有足够多的橙色和绿色球的罐子，我们能不能得到橙色求的比例u?

统计学办法：从罐子中随机取出N个球作为样本，计算这N个球中橙色球的比例v，那么估计出罐子中橙色球的比例约为v。

统计学图

这种随机抽取的办法不能说明罐子里橙色球的比例一定是v,但是从概率的角度来说，样本中的v很有可能接近我们未知的u。下面利用数学推导来解释v与u的接近程度。

【数学推导】

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

Hoeffding's 图

N足够大图

Hoeffding不等式说明当N很大时，v与u相差不是很大，它们之间的差值被限定在

之内。我们把结论v=u称为probably approximately correct(PAC)。

3.Connection to Learning

【迁移】

迁移图

我们将上述罐子抽球思想迁移到机器学习上来。

（1）在机器学习中hypothesis与目标函数相等的可能性，类比于罐子中橙色球的概率问题；

（2）机器学习样本空间的x类比与罐子中的球；

（3）h(x)与f不等类比与橙色球；

（4）h(x)与f相等类比与绿色球；

（5）机器学习的训练D类比与从罐子中抽取的N个球。(这两种抽样的样本与总体样本之间都是独立同分布的。

所以只要样本N足够大，且独立同分布，那么从样本h(x)不等于f(x)的概率就能推导在抽样样本外的所有样本中h(x)不等于f(x)的概率是多少。

以上类比最关键的点是抽样中橙色球的概率理解为样本数据集D上h(x)错误的概率，以此推算出所有数据上h(x)错误的概率，这也是机器学习能够工作的本质。

换句话说，我们将采样数据上得到的一个假设，推到了全局，因为两者的错误率是PAC的，只要我们保证前者小，后者也小了！

学习推测图

于是我们引入了下面两个公式：

公式图

第一个公式表示在实际样本中h(x)与f(x)不相等的概率是多少。

第二个公式表示在抽样样本中，h(x)与yn不相等的概率。

类似的，我们便可以将上述的Hoeffding's inequality表示为：

ML-Hoeffding's 图

该不等式表明上述的E(out)与E(in)也是PAC。当这两个满足PAC情况下，E(in)很小，可以推出E(out)也很小。也就是说在该数据分布P下，h与f非常接近，机器学习的模型比较准确。

h固定时图

当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

【ML上的Hoeffding's inequality】

上述主要讲固定h情况下，当h很多的情况下，又应该怎么做?

为了更直观的描述上面推论后的Hoeffding's inequality，这里展示如下图：

h很多时图

【例子】

假设现在有M个罐子，也就是有M个hypothesis，如果其中某个罐子抽样的球全是绿色，那是不是该选择这个罐子呢？

对于这个问题，先来看一个例子，150人抛硬币，那么其中至少有一个人连续5次硬币正面朝上的概率是：

概率值图

这个概率很大，但是能说明这个朝上的硬币具有代表性？

这肯定不对啊！

在统计学中，我们知道，当样本足够大，最终正面与反面概率都为0.5。

同样的道理，上述说的是抽出的全是绿球，并不能说选择这个罐子。

像以上这种情况，当罐子数目很多或者抛硬币的人数很多的时候，可能引发Bad Sample，而Bad Sample就是Ein 和 Eout差别很大，即选择过多带来的负面影响，选择过多会恶化不好的情形。

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

Bad Data图

从上面这种图中可以看到，不同的数据集D，不同的hypothesis，都有可能称为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图

那么满足这种union bound的情况，我们就可以跟之前一样，选择一个合适的演算法，选择使Ein最小的hm作为矩g，一般能够保证g近似与f，说明有不错的泛化能力。

【总结】

所以，如果hypothesis的个数M是有限的，N足够大，那么通过演算法A任意选择一个g，都有Ein近似等于Eout成立；同时，如果找到了一个g，使得Ein近似等于0，那么根据PAC得到Eout近似等于0，就证明了机器学习是可行的。

【疑问】

当M不受限，比如之前的PLA直线无数条，这些推论成立？机器还能够学习?

对于这些问题，下一节深入探讨~

5.作者的话

以上正文图片来源于林老师课程！

最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！

更多内容，请关注本公众号机器学习系列！