机器学习基石第五周

一.Recap and Preview

首先对之前的内容进行一下总结，首先我们希望学习一个g，这个g越接近于f越好。然后我们有一个假设空间H，这个假设空间包含了有限多的假设h，我们希望利用数据D即sample从H中选出一个最好的h作为g。在之前的课程中我们假设H中只有一个h，那么我们用D能够测出这个h的分类正确率（即h与f的差距大小），然后我们用这个分类正确率来判断这个h好或者不好。而这个h对D的分类正确率与对所有数据的分类正确率的差别大小满足霍夫丁定理即大概率下h对D的分类正确率近似于对整个数据的分类正确率，这样我们才能够通过h对D的分类正确率判断这个h好不好。
接着我们假设H里面有M（有限）个不同的h，我们需要从H里面选择一个 最好的h作为g，所以我们要求H里面的所有假设h对D所做的判断都和h对所有数据所做判断的正确率相差不多。这样根据结果选出的最好的一个h才可信。
而D对其中某个h是坏数据（即h对其的判断与对所有数据判断像差很大）的概率为

这里就出现了一个问题：
当M很小的时候我们能保证出现坏数据的概率很小，但是H里面的假设太少，里面不一定有与f接近或相等的h。
当M很大时，我们又不能保证数据是好数据，这就出现了矛盾，我们接下来要做的就是解决矛盾。

我们用mH代替M并找出mH的性质来保证上诉矛盾在可控范围内。

二. Effective Number of Lines

我们在计算错误率上限的时候是采取直接相加的形式，即默认所有的假设都完全独立不相关，实际上并不是这样的，所以我们能够仅仅考虑相互独立不相关的h那么我们的M就会小很多。如下图b1,b2,b3是大部分重合的，如果我们把这些重合的圈圈当成一类圈圈进行计数，那么M就能减小很多。

下面举个例子：
假设我们的假设空间H={all lines in R^2}这个假设空间的M是无穷的。

假如我们的输入只有一个点，那么假设空间中真正能产生区分的线条只能分成两类即h1和h2，即输入D对h1类线所产生的效果是相同的即在计算坏数据概率时M=2而不是无限。
当输入为2个点时：

当输入为3个点时：

这时出现一个问题，有几种情形是不能够靠线段来实现分类的，所以实际线条比分类数要少，所以归纳出如下规则。

二维数据输入中输入点为N，那么我们能将H中的线条分为effective(N)类且effective(N)<<2^N.那么M就是effective(N)而不是无限大，那么我们就能学习到东西了。

三.Effective Number of Hypotheses

对于一个二维分类，其假设空间是无穷多条线，我们将对于N个点能进行的分类的最多种可能称为dichotomies计做:

而其满足

例如：对于一维数据：

找凸多边形：

四.Break Point

之前的四种问题有四种成长函数，前三种为多项式成长函数，第四种为指数成长函数，前三种带入霍夫丁能有效较少概率，第四种带入错误概率会增大。

我们称成长函数小于2^N开始的点为breakPoint.

以上为上诉四种问题的breakPoint点。
有如下猜想：

breakPoint越小,成长速率越小。