台大机器学习基石个人笔记（第四章）

机器学习 Coursera

台大这门课真的很棒，前面几讲探讨了一个很基础但是很基石的问题。即训练误差与测试误差的关系。假设有N个训练样本，如果我们使用分类器在这些样本上得到了很低的训练误差，我们是否可以保证在测试数据上依然可以得到很低的误差呢？

第四章：

• Learning is impossible
  对于每一种训练数据的分布，都有无数多的函数来完美拟合（0误差），所以在训练数据上表现好不能确定在测试数据上也得到相同的表现。即，对于训练数据之外的东西，我们一无所知。

• Probability to the Rescue
  想象这么一种情况，有个大罐子，里面有很多绿色与橙色的球，橙色球的比例未知。要预测橙色球的比例，只能从罐子中抽样取出N个球，数一下N个球中有多少橙色的球，来近似。这个过程可以形式化为如下问题：
  假设真正的橙色概率为$u$，那么绿色的概率就是$1-u$（$u$是未知的）。在我们抽出的N个球中，橙色球的比例为$v$，绿色球为$1-v$($v$是已知的）。
  我们想知道的就是$u,v$到底有多大的区别，用什么参数可以来刻画这个区别。这个时候就引出了Hoeffding不等式：
  

  $$P[|v-u| > \epsilon] \le 2exp(-2\epsilon^2N)$$
  也就是说，在N足够大的时候，$v,u$是接近的。似乎迈出了一小步。下面就是要建立起Hoeffding与学习之间的关系。

• Connection to Learning
  首先上图，将罐子里的球与学习问题联系起来。
  简单地说，假设原来的样本服从分布（函数）$f(x)$，我们学习出的函数是$h(x)$，我们利用Hoeffding，就能够知道，在样本足够多的时候，训练误差$E_{in}(h)$与测试误差$E_{out}(h)$会很接近，即：
  

  $$P[|E_{in}(h)-E_{out}(h)| > \epsilon] \le 2exp(-2\epsilon^2N)$$
  所以，现在的问题就变成要如何选择h，来让测试误差最小。

• Connection to Real Learning
  如果只抽样一次数据，由于可选的函数很多（比如svm），可能就有一些函数在训练数据上表现很好，可是并不能说明这些函数就真的好。（老师举了个丢硬币的例子，让1000个人丢一样的硬币5次，总会有人拿到5次向上，可是就能说明他的硬币有魔力吗？）
  现在的问题就是，可能你会想，抽一次数据，可能总有几个$h$在这份数据上表现很好（然而又在测试集上表现很差），那怎么办？
  这个时候Hoeffding又来帮忙了，假设一份数据$D$，只要有一个$h$在$D$上的训练误差与测试误差相差太大，即$|E_{in}(h)-E_{out}(h)|$很大，那么就把这份数据称为是不好的(BAD)。
  那么一份数据不好的概率是多少呢？
  
  这个公式前两行好理解，$P_D[BAD\ D\ for\ h_1]$ 其实就是在D上，$|E_{in}(h)-E_{out}(h)| > \epsilon$的概率，所以刚好用Hoeffding可以展开。
  $M$就是所有$h$的数量，所以在有限的$M$，大量的$N$情况下，训练误差与测试误差基本是相似的。
  这解决了一个最基本的问题，就是可用的Hypothesis是有限的情况下应该怎么选择，但是就拿最简单的线性分类器来说，它的Hypothesis大小很显然是无限的，那应该如何选择呢？见第五章第六章。