林轩田《机器学习基石》（四）—— Feasibility of learning
我们将介绍机器学习的可行性，讨论问题是否可以使用机器学习来解决。
一、不能学习的问题
首先考虑如下问题，依据6个旧图形判断新图形的类别。
如果根据是否是对称图像：该图形被分类为+1
是否左上角的小方块是黑色的：该图形被分类为-1
可以看到规则可以随人说，而且还在已知资料上分的很好。所以如果没有限制无论你答什么，你对还是错都是随人说的。
另一个例子：
灰色部分是数据D，y是真实的标签，g是理想的使得，可以看到
都可以使得已知样本正确分类，所以看样子都满足g的条件。但是给了三个新样本，这些
的结果各不相同。所以同样的，你随便选了一个作为g，如果没有限制，在下面三个样本上你对还是错都是随人说的。
值得注意的是，我们想要的就是在新样本上表现好，而不是说给了一个旧样本来判断旧样本的情况。
上述在机器学习中被称为：没有免费午餐（No Free Lunch）定理。即没有一个学习算法可以在任何领域总是产生最准确的学习器。平常所说的一个学习算法比另一个算法更“优越”，效果更好，只是针对某确定情况。
所以好像不加一些假设条件的话，机器学习没有学到什么，也不能解决上面的问题。
二、用样本代替全部1
现在就详细介绍上面要添加的一些“假设条件”。我们尝试添加一些东西，使得对未知的东西也有一些推论。
举一个球的例子：
如果有一个装有很多橙色球和绿色球的罐子，我们想推断橙色球的比例u。可以运用统计学上抽样的方法，从罐子中随机取出N个球作为样本，计算这N个球中橙色球的比例v，那么就估计出罐子中橙色球的比例约为v。当N足够大的时候，v接近于u。Hoeffding’s inequality：
当N很大的时候，v与u相差不会很大，它们之间的差值被限定ϵ之内，把结论v=u称为probably approximately correct(PAC)。
三、用样本代替全部2
这部分主要内容是说，在h固定时，会让机器学习有一些好的结果。
现在，我们把橙色球与绿色球分别代表机器学习中可能发生的事情：
橙色球：
绿色球：
如果抓了一把球，就大概知道整个罐子中球的比例。我们把抓出的球看做已知的样本，所以我们不知道的概率但可以知道
的概率（这是在样本上的，有限个哪怕可以数出来）。
这里我们引入两个值和
。
表示在抽样样本中，h(x)与
不相等的概率；
表示实际所有样本中，h(x)与f(x)不相等的概率是多少。所以我们不知道
但可以知道。（后者可以计算出来）
同理，可以得到：
所以从已知样本上发生了什么可以推测出在所有样本上发生了什么，也就是说，当样本足够大，想要泛化误差小那么就要尽量使得样本上验证误差小。
一个新问题：当我们手上已经有了一个h，且
我们是不是可以说已经学到了什么，即
一般地，h如果是固定的，很小，且A选择h作为g，那么
是PAC的。如果A选择每次选择特定的h作为g（哪怕有一千个h供选择，但是A只选择那个特定的，选到别的不行。个人理解因为机器学习中不可能每次都选到同样的h，所以如果每次选到它一定是出错了），那么
不一定很小（因为可能出错了），从而
是PAC的。真正的学习中A是有选择的。
所以上面我们说的是固定了h后的表现如何，而没有说A选不同的h会如何。
四、如果很多个h，学习还有效吗？
这部分主要内容是说，要想让学习有效要添加约束：h个数有限。
如果有10个罐子，每个罐子抽球，其中有一个罐子全部抽出绿色，那么是不是要选这个瓶子？
如果有n个h，有一个h在样本上结果全对，要不要选这个h？
出现全对的几率其实是很大的。
比如一个例子：150个人抛硬币，那么其中至少有一个人连续5次硬币都是正面朝上的概率是
所以这个硬币比其他好吗？要选这个硬币吗？
随着150人的增大，那么概率会越来越大。所以，“选择”会恶化不好的情形。当罐子数目很多或者抛硬币的人数很多的时候，可能引发“不好的资料”（Bad Sample），这时和
t差别很大。
是把每个资料按概率分的类。
“不好的资料”（Bad Sample）：和
t差别很大
把所有可能的资料列出来，可以发现其实BAD的几率很小。这里几率很小和上面几率很大在区别在于：出现BAD的几率大，但BAD的个数少（BAD少，但一定会有）。对每一个h，都会有BAD，但是一行的BAD加起来不多。竖着看，有些数据集BAD多，有些数据集BAD少。只要
在某个h上是BAD，那么
就是BAD。只有当
在所有的h上都是好的数据，才说明
不是BAD，在好资料上算法A可以自由自在做选择h进行建模。
那么，总共BAD加起来有多少？（上界）
M表示h的个数。资料量足够多（可能是让N大，可能是使他满足前面的“罐子多”的前提），那么我们可以说每一个h都是安全的，那么从而我们可以选到一个h作为g，和
t差别很小。这里添加了一个约束：h是有限的。
这样我们可以找到最小的h，将它作为g。