一点点思考

再次总结上周的收获～

首先，上周回顾了机器学习的流程，六个字概括：数据、假设、算法。我需要一些数据，在观察数据之后我需要作出一定的假设，形成一个假设的集合，我还需要一个算法，这个算法可以帮助我在假设空间中选择一个最好的假设作为产生的模型。

在这样一个完美的流程之中，不禁我们会产生如下思考：机器学习为什么可以学到好的模型？

这样的思考是很自然的，因为我的假设空间中可以有无限个假设，算法衡量假设之间的优劣只能看这个假设能不能很好的fit我手上的数据。事实上，完全fit数据集的假设会有很多个，在这些假设中算法会如何再次筛选？换句话说，算法如何评价在数据集上表现一样好的假设？本周的工作主要集中在此，记录本周一点点思考如下。

在周志华的《机器学习》中，作者给出了这样的说法：每一个算法都会有归纳偏好，这些偏好会在表现一样好的假设中再次筛选出一个“最好的”，在此并没有太明白，我想周教授的意思大概是说对假设h的评价有多种指标，并非所有的指标表现都会一样，所以算法会在某一指标一定的情况下利用另一指标再次筛选。这部分确实很不明白，下周会努力思考这个问题。

当然，本周对这个问题还有一些其他的思考。从概率的角度看，上述问题的出现是因为抽样有问题。数据集内表现很好，但数据集外可能会表现很差，根据Hoeffding不等式，只要我的抽样N（数据集大小）足够大，Ein，Eout不相似的概率会很小，换句话说，对于每一个假设\\\\H_i，只要数据集足够大，样本内误差样本外误差相差很大的事情不容易发生。也就是说，我有足够的数据集，我就可以probably approximately correct验证H_i的表现。机器可以学到东西。

但是显然，我的算法要评价假设空间所有的假设的表现，虽然对每一个假设，泛化误差很大的概率都很小，但是所有假设中存在一个假设出现此问题的概率就会很大。就好比说某一疾病发病率只有万分之一，但是一万个人里面很有可能会出现一个患者。也就是说，算法有可能会选到一条样本内表现好，样本外表现不好的假设。如果假设有无限多个，即使单个假设发生坏事情的概率很小，总体的坏事情发生也似乎是一定的。

对于上述问题的补救可以这样考虑，虽然假设空间有无限个假设，但是总的来说大部分假设之间会相似，比如临近的直线分类效果很相似，可以看作一类。我们按照假设给数据集分类结果来把假设空间做一下归类，我们认为只要两个假设在数据集上分类结果一样，就看作一类，那么总共有多少分类方式，就有多少类假设。对于K分类问题，有K的N次方类。由此我们把假设空间大小看作一个有限的K的N次方，但是Hoedding不等式仍然bound不住坏事情发生的概率，我们需要把K的N次方降低到polynomial才行。

中间台大林轩田教授做了很复杂的推理，最终证明了降低到多项式大小是可行的。

现在重新思考机器学习路上所在的位置。

我首先学了机器学习的流程

然后讨论了为什么可以学到东西。

那么接下来要学的是如何学到最好的假设，作为输出模型g，即Ein Eout可以在大数据集上保证相近，那么如何降低Ein呢？