从数据中学习什么时候起作用（数学从基本概率开始）

VC 维度和统计学习基本定理 — 从头开始​​ 2026 年 5 月这篇文章回答了一个问题：从数据中学习何时真正起作用？您在样本上训练模型，它在这些样本上表现良好，并且您希望它在新数据上表现良好。这种希望什么时候是合理的？答案是完全等价的：假设类当且仅当它具有有限的 VC 维数时才是可学习的。这是统计学习的基本定理。我们将从头开始构建每一个部分：马尔可夫不等式、霍夫丁引理、集中不等式、并集界限、VC 维、Sauer-Shelah 引理、对称化以及将它们联系在一起的泛化界限。除了基本概率（期望、独立性、指标随机变量）之外，没有任何假设。我们证明了等价的两个方向：上限（有限 VC 维意味着可学习性）和下限（通过信息论：总变差、KL 散度、平斯克不等式和勒卡姆方法）。这是两部分中的第 1 部分。第 2 部分继续讲述 Rademacher 复杂性（一种 VC 维度的概率细化，提供更紧密、依赖于数据的界限），并展示所有部分如何连接成一条美丽的链条。 1. 设置：“学习”意味着什么？我们在最简单有趣的环境中工作：二元分类。定义（学习问题）实例空间 \(\mathcal{X}\)：所有可能输入（图像、文档、特征向量等）的集合。标签空间 \(\mathcal{Y} = \{0, 1\}\)：二进制标签。分布 \(\mathcal{D}\)：\(\mathcal{X} \times \mathcal{Y}\) 上的未知概率分布。大自然绘制\((x, y) \sim \mathcal{D}\)。假设类 \(\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}\)：学习者可以从中选择的一组固定分类器 \(h : \mathcal{X} \to \{0,1\}\)。训练样本 \(S = ((x_1, y_1), \ldots, (x_m, y_m))\)：绘制独立同分布来自\(\mathcal{D}\)。定义（真实风险和经验风险） 假设 \(h\) 的真实风险（或人口损失）为 $$ L_{\mathcal{D}}(h) = \Pr_{(x,y)\sim\mathcal{D}}[h(x) \neq y]。 $$ 大小为 \(m\) 的样本 \(S\) 的经验风险（或训练误差）为 $$ L_S(h) = \frac{1}{m}\sum_{i=1}^m \mathbf{1}[h(x_i) \neq y_i]。 $$ 示例（垃圾邮件分类）假设 \(\mathcal{X}\) = 所有可能的电子邮件，且 \(\mathcal{Y} = \{0, 1\}\)，其中 1 = 垃圾邮件。大自然在（电子邮件，标签）对上有一些分布 \(\mathcal{D}\) - 这捕获了显示的电子邮件以及它们的标签方式。我们不知道 \(\mathcal{D}\);我们只看到一组\(m\)个带标签的电子邮件的训练集。真正的风险 \(L_{\mathcal{D}}(h)\) 是分类器 \(h\) 对未来随机电子邮件进行错误分类的概率。我们永远不知道这一点——它涉及所有可能到达的电子邮件。经验风险 \(L_S(h)\) 是训练电子邮件中 ​​\(h\) 出错的比例。这个我们可以计算一下。根本问题：小\(L_S(h)\)什么时候保证小\(L_{\mathcal{D}}(h)\)？学习者只看到 \(S\) 并希望找到 \(h \in \mathcal{H}\) 且具有较小的 \(L_{\mathcal{D}}(h)\)。最自然的策略是经验风险最小化（ERM）：选择任何 \(h \in \mathcal{H}\) 来最小化 \(L_S(h)\)。简而言之：选择在训练数据上犯错误最少的假设。但ERM有一个明显的失效模式：过度拟合。如果 \(\mathcal{H}\) 具有足够的表达能力，那么 \(\mathcal{H}\) 中的某些 \(h \) 纯粹通过记忆训练数据就会得到 \(L_S(h) = 0\)，同时具有可怕的真实风险。因此，我们需要了解 ERM 何时值得信赖。这引出了本文其余部分将回答的两个问题：什么时候可以学习？在 \(\mathcal{H}\) 上什么条件下任何算法都可以泛化？ ERM具体在什么时候发挥作用？训练误差何时同时跟踪每个假设的真实误差？这些问题通过两个定义来形式化：PAC 可学习性（问题 1）和统一收敛（问题 2）。让我们为每一项做好准备。 “可学习”应该意味着什么？我们想要一个定义：“如果有足够的数据，学习者可能会做得很好。”需要做好三件事：做得如何？学习器的误差应该在 \(\mathcal{H}\) 中最佳可能误差的 \(\epsilon\) 范围内。我们使用\(\epsilon\)（“精度参数”）是因为我们不能要求完美——对于有限的数据，总是存在一些近似误差。大概有多少？由于 \(S\) 是随机的，学习者可能会不走运（例如，所有训练电子邮件都是垃圾邮件）。我们允许失败概率 \(\delta\)（“置信参数”）。反对什么？该保证必须适用于每个分布 \(\mathcal{D}\)。我们不知道大自然如何生成数据，因此我们无法对此做出任何假设。定义（PAC 学习） 如果存在学习算法 \(A\) 和函数 \(m_{\mathcal{H}} ： (0,1)^2 \to \m，则假设类 \(\mathcal{H}\) 是 PAC 可学习的（可能近似正确）