7 非均匀可学习性

到目前为止，在书中讨论的 PAC 可学性的概念允许样本大小取决于准确性和置信度参数，但在标记规则和底层数据分布方面，他们是一致的。因此，在这方面可学习的类是有限的(它们必须有一个有限的vc维，如定理6.7所述)。在本章中，我们将考虑更轻松、更弱的可学性概念。我们讨论这些概念的有用性，并提供使用这些定义可学习的概念类的特征。

我们通过定义“非均匀可学习性”的概念开始讨论，该概念允许样本大小取决于与学习者进行比较的假设。然后我们提供了非均匀可学习性的特征，并证明非均匀可学性是对不可知论的 PAC 可学性的严格放宽。我们还证明了非均匀可学性的一个充分条件是 $\mathcal H$ 是假设类的一个可数并集，每个类都具有一致收敛性。这些结果将在第7.2节中通过引入一个新的学习范式来证明，该范式称为结构风险最小化( SRM )。在第7.3节中，我们为可数假设类指定 SRM 范式，它产生最小描述长度( MDL )范式。MDL 范式为一种被称为奥卡姆剃刀的归纳法哲学原理提供了一种形式的论证。接下来，在7.4节中，我们将一致性作为学习性的一个更弱的概念来介绍。最后，我们讨论了可学习性的不同概念的意义和有用性。