第四讲：Feasibility of Learning
1、Learning is Impossible
一个问题：给出如下的规则；
预测如下的图片的类别：
对于这个问题，有多种不同的看法，如果你说答案是1，那么我会说，你答错了，左上角是黑色的类别为-1。如果你说答案是-1，那么我会说，你答错啦，对称的图形类别是1。这些类别都是人为设定的，比如：
所以，我总是可以说，你答错了。所以，这样看起来，learning好像是不可行的，但是数学上真的是这样的么？
我们再来看一个简单的二元分类问题：
在所有的假设空间中，我们找到一个函数g，在已知的5个数据点上都可以预测准确，那么在剩下的三个数组上呢？结果可能是如下的：
我们的目标，不是在已知的数据上分类效果好，而是对于未知的数据能够正确的分类。所以，通常情况下，我们无法给出准确的结论，我们得到的函数g对于没有看到的数据的效果如何。
2、Probability to the Rescue
通过上一节，我们好像觉得learning是不可能的。那么，我们可不可以从其他的角度推断出一些东西？
例如，我们如何推断罐子中橘色的比例？
罐子中弹珠太多了，我们无法准确知道橘色的比例，但我们可以用手抓一把，在这一把中，橘色的比例我们是可以知道的，我们把抓的这一把称为样本。那么样本中橘色的比例能不能告诉我们一些关于整体中橘色的比例的东西？
对于样本比例和整体比例，我们会有如下的Hoffding 不等式，也就是说，如果我们的样本数量越来越大，那么样本的比例就越有可能近似代替整体比例，及二者会越来越接近：
3、Connection to Learning
那么如何通过抽弹珠这个例子跟我们的Learning相联系呢？在抽弹珠问题中，我们不知道总体中橘色的比例，那么在学习问题中，我们不知道的是目标的真实分类函数f(x)，或者说我们不知道我们得到的假设h(x)与f(x)是否相同？进一步，我们把橘色的弹珠认为是令h(x)<>f(x)的x,把绿色的弹珠认为是令h(x)=f(x)的x。刚才所说的可以通过下图表示：
所以，我们大概可以通过已知的样本中h和f不一样的几率来大概推断对于未知样本h和f不一样的几率。
所以，应用Hoffding不等式，我们有如下式子：
但是，问题又来了，我们假设空间h中的函数有很多，我们如何让机器得到我们想要的那个函数呢，也就是让我们的g=f呢？
即：
对于选出的样本，如果一个假设预测结果与实际结果都是对的，那么我们要不要选这个？
我们做一个硬币的游戏，150个人，每人丢一颗铜板5次，记录出现正面的次数，如果一个人扔了5次全是正面，难道这个铜板跟别人的不一样么？答案不是的，我们算一下概率就知道，150个人中，出现5次都是正面的概率大于99%。
所以，并不是这个铜板好，即它的出现正面的概率比别的铜板高。
