Learning is Impossible?
考虑如下二元分类的例子：
给出5条数据，设计一个算法找出一个g∈H并且所有的g(xn)=yn，并且说明g和理想的那个f是否近似。
既然输入xn有3个维度，那么输入一共只有8种情况，而输出有2种情况，一共有28=256种输入输出组合。我们可以找到一些h∈H使得在训练数据D上所有样本的分类结果都正确，而D之外的数据集上不同的h分类结果不同。即在训练样本中g=f而在训练样本之外g!=f。但是机器学习的目的恰恰是根据训练样本找到一个模型使得该模型在未知数据上的预测与真实结果大体一致。
上面的例子说明我们想要在训练数据D以外的数据中找到接近f的g似乎是不可能的，这就是“没有免费的午餐”定理（No Free Lunch Theorem）。只有在某些假设条件下，我们才能评价机器学习算法的好与坏。
Probability to the Rescue
既然我们从D以外的数据中推断出未知的f是很困难的，那么我们能不能通过其他的方式推断出某些未知的东西呢？下面我们先来看一个弹珠的例子。
假设我们有一个罐子，里面装满了橙色和绿色的弹珠，现在我们想要知道罐子里橙色弹珠的比例，我们该如何做呢？最直观的想法就是把罐子里的弹珠拿出来，一个一个地数；另外，还可以从罐子里随便抓一把（以下简称样本），计算这一把弹珠中橙色的比例，然后由这个比例推断罐子里橙色弹珠的比例。
样本中的ν和样本之外的μ有什么样的关系呢？我们能不能通过ν推断出μ呢？
我们知道，当罐子里大部分都是橙色弹珠时，样本中基本上不可能出现较多的绿色弹珠。也就是说，样本中橙色弹珠的比例υ大致与罐子里橙色弹珠的比例μ相接近。下面我们来看一下，υ和μ到底有多接近。
在样本数量较大的情况下，二者之间的差距可以由以下不等式衡量：
P[|ν−μ|>ϵ]≤2e−2ϵ2N
也就是说，
ν和
μ之差的绝对值大于
ϵ的概率小于
2e−2ϵ2N。上面的不等式叫霍夫丁不等式（Hoeffding’s Inequality），根据这个不等式，我们就可以说“
ν=μ”这句话是大概接近正确的（Probably Approximately Correct，简称PAC）。
仔细观察上面的不等式，我们可以发现它有以下几个特点：
- 对所有的N和ϵ都有效
- 和μ无关，也就是说我们不需要知道μ
-
N越大或者ϵ越小，μ约等于ν的概率越高
Connection to Learning
那么抓弹珠和机器学习之间有什么关系呢？下面我们把抓弹珠和机器学习对应起来：
| 罐子 |
机器学习 |
| 未知的橙色弹珠比例μ
|
需要寻找的与目标f(x)相近的假设h(x) |
| 罐子里的弹珠 |
输入空间中的每个向量 |
| 橙色弹珠 |
假设h是错的，即h(x)≠f(x)
|
| 绿色弹珠 |
假设h是对的，即h(x)=f(x)
|
| 从罐子抓取的N个样本（独立同分布） |
训练数据D={(xn,yn)}（独立同分布） |
如果样本容量N足够大并且向量xn是独立同分布的，那么我们就有可能由已知的h(xn)≠f(x)推断出h(x)≠f(x)。
所以，现在机器学习的过程就变成了下图所示的样子，其中虚线表示我们不知道的东西：
一个更正式的描述：
上面的不等式和抓弹珠很像：
- 对于所有的N和ν都成立
- 和Eout(h)无关，也就是不需要知道Eout(h)，f和P也不需要知道
-
Ein(h)=Eout(h)是PAC的
如果Ein(h)≈Eouth并且Ein(h)很小的话，那么就可以推断出Eout(h)也很小，那么h≈f就在P上成立。
但是新的问题又出现了。对于任意一个h，当数据量足够大的时候，Ein(h)≈Eout(h)，那么我们能断言这一定是一个好的学习结果（g≈f）吗？
当某个h的Ein很小并且A选择了那个h作为最后的g，那么g=f是PAC的；如果A不得不选择某一个h当作最后的g，通常来说此时Ein不会太小，所以g≠f是PAC的。也就是说，真正的学习是A在H中做选择（就像PLA）而不是被迫地选择某个h。所以我们需要验证某个h相对于f好还是不好。验证过程如下：
Connection to Real Learning
如果找到一个h，它在数据集D上表现的很完美，那么选不选它作为最后的g呢？
拿抛硬币举例，150个人同时抛5次硬币，有的人抛了5次正面，那么这枚硬币出现正面的概率是不是真的比其他硬币高？还是只是运气好抛出了5次正面呢？
根据统计学的知识，即使当每一枚硬币正反面出现的概率都是12，150个人抛5次硬币，有人抛出5次正面的概率为
1−(3132)150>99%
根据上面的例子，我们引入了坏样本（BAD sample），也就是那些
Ein和
Eout差别很大的样本，这些坏样本让选择结果变得更糟。比如抛硬币，
Eout=12，但是我们抛出5次正面（
Ein=0）！同理，对于某个
h来说，如果某些数据关于它的
Eout和
Ein差别很大，比如
Eout很大（和
f差很远）但是
Ein很小（在很多样本上都正确），那么那些数据就是坏数据（BAD Data）。
那么对于单个
h来说，坏数据出现的可能性是多少呢？请看下图：
当我们有很多h的时候，如果某个数据集对于一个h来说是坏数据，那么对于整个假设空间来说它也是坏数据，只有那些在所有h上不是坏数据的数据集才不是整个假设空间的坏数据，如下图的D1126：
那么对于M个假设，坏数据出现的几率上界是多少呢？下面给出相关证明：
现在，机器学习的流程变成了下图：
如果M是有限的，数据量N足够大，对于A选择的所有g，都有Eout(g)=Ein(g)；如果A找到了一个g且Ein(g)≈0时，PAC保证了Eout(g)≈0，这时候我们就说学习是可行的。新的问题又出现了，当M无限大的时候（就像在PLA里有无数条线一样），那么我们应该怎么办呢？请听下回讲解。
