需要多少个实例

18.5.1 需要多少个实例

为了将这些见解付诸实践，我们将需要一些符号：

• 令X为所有可能实例的集合。

• 令D为从中抽取实例的分布。

• 令H为可能假设的集合。

• 令N为训练集中实例的个数。

初始，我们假定实际的函数f是H的成员。现在我们可以在给定实例上的分布D的条件下，把假设h关于实际函数f的误差定义为h与f在某个实例上存在差异的概率：

error(h)=P(h(x) ≠f (x)|从D中抽取出来的x)

这是被前文中所示的学习曲线实验地度量的同一个量。

如果error(h) ≤ ε，其中ε是一个很小的常数，那么该假设h被称为近似正确的。进攻计划是要证明，在看到 N 个实例后，有很高的概率所有的一致假设都将是近似正确的。可以认为一个近似正确的假设在假设空间中“接近于”实际函数：它处于包围在实际函数周围的所谓ε-球的内部。如图18.12中所示，所有假设的集合H被分为两个部分：f周围的ε-球，以及被称为Hbad的其余部分。

图18.12 假设空间示意图，显示了实际函数f周围的ε-球部分

我们可以通过下面的方法计算一个“有严重错误的”假设hb∈ Hbad与前N个实例一致的概率。我们已知error(hb)＞ε。因此，该假设与一个给定实例一致的概率至多（原文为“至少”——译者注）为1−ε。N个实例的概率界限是：

P(hb与N个实例一致) ≤ (1–ε)N

Hbad至少包含一个一致假设的概率，由独立概率和所限定：

P(Hbad包含一个一致假设)≤|Hbad|(1−ε)N≤|H|(1–ε)N

这里我们利用了|Hbad|≤|H|的事实。我们希望把这个事件的概率减小到一个比较小的数δ 之下：

|H|(1–ε)N≤ δ

如果我们允许算法看到的实例个数满足

那么我们就能够得到1–ε ≤ e−ε。因此，如果一个学习算法返回的假设与这么多实例相一致，那么它的误差至多是ε的概率至少是1–δ。换句话说，它是可能近似正确的。作为ε和δ的函数，所需要的实例个数被称为假设空间的样本复杂度。

那么，看来关键问题是假设空间的规模。如我们前面所看到的那样，如果H是n个属性上的所有布尔函数的集合，那么|H|= 22 n。因此，空间的样本复杂度是以2n增长的。由于可能的实例个数也是2n，这意味着如果仅仅返回一个与所有已知实例都一致的假设，针对所有布尔函数的空间的任何学习算法不会比查找表方法做得更好。了解这个问题的另一种途径是观察一个事实：对于任何未见到过的实例，假设空间中所包含能预测正输出的假设的个数和能预测负输出的假设的个数同样多。

我们现在所面临的困境是，除非我们限制算法可以考虑的函数空间，否则不能进行学习；但是如果我们确实限制了空间，我们可能将实际函数一起排除了。现在有两条可以“摆脱”困境的途径。第一条途径是坚持要求算法不仅返回任何一致假设，而且最好是一个简单的假设（如同在决策树中所做的一样）。对这样的算法的理论分析已经超出了本书的范围，不过在寻找简单的一致假设是不可操作的情况下，样本复杂度的结果通常比仅基于一致性进行的分析要好。我们这里要追寻的第二条摆脱途径，是关注于布尔函数的整个集合中可学习的子集部分。其思想是，在很多情况下，我们不需要布尔函数的完全表示能力，可以通过比较受限的语言得到。现在，我们就来更详细地考察这样一种受限语言。