内容
- 3.1 Rademacher complexity
- 3.2 Growth function
- 3.3 VC-dimension
- 3.4 Lower bounds
- 3.5 Chapter notes
- 3.6 Exercises
介绍
-
机器学习中通常使用的假设集是无限的。
-
然而，在处理无限假设集时，上一章的样本复杂度界限是没有参考价值的。
-
人们可能会问，当假设集是无限的情况下，是否仍有可能通过有限样本进行有效学习。
-
我们对轴对齐矩形族的分析（示例 2.4（学习轴对齐矩形）(learning axis-aligned rectangles)）表明，
- 在某些情况下，这确实是可能的，因为我们证明了那个无限概念类是PAC可学习的。
-
本章的目标是将这一结果进行推广，
- 并推导出无限假设集的一般学习保证。
-
一种实现这一目标的通用方法是将无限情况简化为有限假设集的分析，然后按照上一章的方法进行。
-
这种简化有多种技术，每种技术依赖于假设集的一种不同复杂性概念。
-
我们将首先使用的是Rademacher复杂度的概念。
-
这将帮助我们利用基于McDiarmid不等式的相对简单的证明推导出学习保证，
- 同时获得高质量的界限，包括数据依赖的界限，
- 这些界限我们将在后续章节中频繁使用。
-
然而，对于某些假设集，计算经验Rademacher复杂度是NP难问题。
-
因此，我们随后引入了另外两种纯粹的组合概念，即
- 增长函数
- VC维度。
-
我们首先将Rademacher复杂度与增长函数联系起来，然后根据VC维度来界定增长函数。
- VC维度通常更容易界定或估计。
- 我们将通过一系列例子来回顾如何计算或界定VC维度，然后将增长函数与VC维度联系起来。
- 这将引导我们基于VC维度推导出泛化界限。
-
最后，我们将基于VC维度提出两种不同情况下的下界：
- 一种是可实现情况下，在这种情况下，考虑的假设集中至少有一个假设能达到零期望误差；
- 另一种是不可实现的情况下，在这种情况下，假设集中没有任何假设能达到零期望误差。