机器学习基石的泛化理论及VC维部分整理（第五讲）

第五讲 Training versus Testing

一、问题的提出 

  $P_{\mathcal{D}}\left [ BAD \mathcal{D} \right ] \leq 2M \cdot exp(-2\epsilon^2N)$  

$\leftrightarrow P_{\mathfrak{D}}\left [ \left | E_{out} - E_{in} \right | > \epsilon \right ] \leq 2M \cdot exp(-2\epsilon^2N)$  

 （1） 当 $M < \infty$ 时， $N$ 足够大，则说明犯错误的概率是比较小的，可推导出 $E_{in} \approx E_{out}$ ，如果 $E_{in}$ 接近于 0 时，则  $E_{out}$ 接近于零。

（2） 上一节林老师也说了，当 $M = \infty$ 时，就没法学习了，因为上界比较大，犯错误的概率比较大，得出无法进一步的学习。学出来的错误概率比较大。

其中 $M$ 是 Hypothesis Set 中 Hypothesis的个数

但是上一节的时候，算出的概率是 or 的关系，为各个犯错的概率之和， 那么这里面就应该有一部分可能存在着重复了，上界就显得过大了。当 $M = \infty$ 时，是无法进行有效学习的；实际上，由于不同的hypothesis下发生坏事情是有很多重叠的，其实我们可以得到比 $M$ 小很多的上界。

我们可以将这些具有很多重叠的hypothesis进行分组，根据组数来考虑hypothesis set的大小。

二、以二值分类为例来解决hypothesis set的个数上界问题。

从有限个输入数据的角度来看 hypothesis的种类，

（1）最简单的，一个数据，会有两种hypothesis， $h_{1}(x) = +1 或 h_{2}(x) = -1$

（2）两个数据，会有四种hypothesis, 具体如下:

　　　　　　 $h_{1}(x_{1}) = +1, h_{1}(x_{2}) = +1$

　　　　　　 $h_{2}(x_{1}) = +1, h_{2}(x_{2}) = -1$

　　　　　　 $h_{3}(x_{1}) = -1, h_{3}(x_{2}) = +1$

　　　　　　 $h_{4}(x_{1}) = -1, h_{4}(x_{2}) = -1$

以此类推，对于 $N$ 个点来说，最多有 $2^N$ 个假设；这里说的是最多，也是最理想的，事实上还会小，那么在什么情况下会小呢？ 比如有四个点时，对角线相同的四个点就是不可行的，如下图

就是说找不到一条直线把上面四个点分开，那么上述四个点到底有多少个呢？除了上图，还有圈圈和叉叉交换的情况，应该是 $2^4 - 2 = 14$ 种

同理可知，当 $N$ 比较大的时候，有效 hypothesis的数量应该是远远小于  $2^N$ 的，

在这种情况下，林老师给了一个定义，叫做dichotomy，字面意思是二分法，其实就是 Effective Hypothesis

看到论坛里也有同学问道什么叫 from the eyes of data, 其实就是从数据的角度去看，我们有多少个有效的Hypothesis，那么这里有效的Hypothesis个数会随着数据的个数变化而变化，从上面的例子可以看出来，这个个数将随着数据的个数增加而增加，在林老师的视频里，又给出了一个函数，叫做 Growth Function.

$Growth Function = m_{H}(N)$ ，具体的函数就记为 $m_{H}(N)$ 了。

林老师举例说明了几类问题的Growth Function：

（1） $\mathcal{X}=\mathcal{R}$  （一维实属空间）, $positive ray, h(x) = sign(x-a)$ ，就是说当 $x > a$ 时， $h(x) = +1, otherwise h(x) = -1$

（2）

机器学习基石的泛化理论及VC维部分整理（第五讲）

原文：http://www.cnblogs.com/tsat/p/3543254.html