这几天跟着B站的视频教程读了《Learning From Data》这本书，找个地方总结下自己的理解。
为什么可以学习
做机器学习需要解决的第一个问题就是为什么机器学习是可行的？这个直觉上看起来没啥可讨论的问题，细化分析之后可以得出不少有趣的结论。
假设集合H，测试集误差Ein和实际误差Eout
机器学习的过程抽象起来就是从一个假设集合H中，根据测试数据上的误差Ein，选取最合适的假设h的过程，这中间就涉及两个主要问题：
如何保证Eout
我们只能在测试数据上进行测试，得到测试误差Ein，但是如何保证在真实数据上应用这个假设时，Eout的大小也是可控的呢？如何选择h
H的大小很可能是无限大，我们不可能把所有的假设都在测试数据上跑一遍，那么如何在有限的尝试中选取合适的h呢？
如何保证Eout好像直觉上很简单，如果保证测试数据是在真实数据中独立随机采样到的，那么在测试数据上Ein和真实数据上的Eout的大小就有一个概率关系，也就是霍夫丁不等式：
是吧，看起来很简单，Ein保证了，Eout就有保证了。但是我们忽略了一个过程，选择最终的假设h时，我们是在H集合里选的，一般都是选择Ein最小的那一个，这个过程会干扰Eout。
怎么理解呢，我们举一个例子，假设我们需要预测一个有无限个球的罐子里，各种颜色球（红黄蓝）的比例，然后球一共有3种颜色，实际上各种颜色球的比例是1：1：1，实验方法是从罐子里取出3个球，来看哪种假设符合。
我们的假设集合本来只有两个假设，红黄蓝1：1：1和全蓝，全蓝命中的概率只有(1/3)^3，很明显全蓝是个错误的假设。
现在我们为了“更好的训练”，扩充了假设集合，把全红，全黄都加了进来。结果呢反而导致出错的概率从(1/3)^3到了 (1/3)^3 * 3。
细品一下，测试数据总是有可能出现一些极端分布，会使得一些错误假设Ein特别低，当假设集合特别大的时候，每一个错误假设都可能撞上对它来说match的数据分布，最终：
假设集合的增大，可以让我们找到更低的Ein，但同时也导致Eout的范围扩大
VC维
实际上，Eout的扩大和H的大小是正比的，这样对于我们通常大小是无限的H来说，机器学习似乎失去了意义，当假设集合太大时，我们总是可能选到一个正好在测试数据上表现特别好的“错误假设”。为了解决这个问题，我们对假设进行了分类，引入了VC维的概念。
VC维从某种程度上描述了某一个假设的“变化能力”，还是继续刚才那个拿球的例子，因为“全黄，全红”的假设加入，导致我们出错概率变大，那么有一个做法就是继续拿球，拿n个球，出错概率会变成 (1/3)^n * 3，随着n变大，出错概率也会变小。但是如果我们的假设还包含“n-1:1:0", "n-2:1:1"这种呢？结果就是无论我们拿多少个球，总会有一个莫名其妙的假设正好撞上，最后稀里糊涂成为我们的最终假设。
所以虽然H是无限的，但我们仍然要限制假设的实际能力，比如我们规定，假设只能估计10个球内红黄蓝的分布，这样虽然10个球以内怎么拿都会有一个奇葩假设能match，但是如果拿了10+K个球，多的K个球，每个球都是对假设集合的一个检验。
限制假设的能力，有几个办法
一个是对假设进行分析，找到它本身的能力范围，就是VC维，如果假设的VC维不是无限的，那么增大采样数据，就可以减小假设集合选出一个错误假设的概率。
第二个就是强行约束我们模型的”能力“，当模型的VC维太大时，我们可以得到很小的Ein，但是Eout会很大，就是我们常说的过拟合。过拟合常见的一个方案是增加regulator，regulator的作用方式是对模型参数增加一个限制，从某个角度看，就是限制了模型的表达能力，降低了其VC维。
