📊 statistics

An Optimal Agnostic PAC Algorithm

本文提出了一种用于二分类的不可知 PAC 学习算法，该算法通过匹配已建立的下界，在常数项范围内确定了样本复杂度，从而实现了统计最优风险界。

原作者： Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

发布于 2026-08-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图教一个机器人分辨猫和狗。你给它看了成千上万张照片，但世界是混乱的：有时猫躲在黑暗中，有时狗戴着帽子，有时你给机器人的标签本身就是错误的。这就是机器学习的世界，具体来说是一个被称为统计学习理论的领域。这里有一个核心问题：机器人需要看到多少个例子才能变得擅长猜测？

为了回答这个问题，科学家们使用了一个概念——VC 维（以 Vapnik 和 Cheronenkis 命名）。把 VC 维想象成衡量机器人大脑“混乱程度”或“复杂程度”的指标。一个只看耳朵形状的简单大脑具有较低的 VC 维；而一个观察每一个像素点的超级复杂的脑则具有较高的 VC 维。目标是找到一个“甜点”，让机器人的学习速度足够快以发挥作用，同时又不会因为过于复杂而仅仅是死记硬背训练照片而非学习规则。几十年来，数学家们一直试图寻找一个完美的公式，告诉我们给定一定数量的样本和一定程度的复杂度时，一个机器人产生的误差与绝对完美的机器人相比，究竟会有多少“额外”误差。

长期以来，我们的知识领域存在着一个空白。我们知道在数据完美（标签没有错误）时的最佳学习速度，也知道在数据非常混乱时的学习速度。但中间地带呢？如果数据只是有一点点噪声怎么办？以往试图解决这一问题的尝试就像是在背着沉重背包的情况下跑步；它们很接近目标，但却背负着额外的“对数级”重量，使得速度比理论上需要的要慢。大问题在于：我们能否构建一个无论数据中有多少噪声，都能以绝对最快速度运行的学习器，且不携带这些额外的重量？

这篇题为《一种最优不可知 PAC 算法》（An Optimal Agnostic PAC Algorithm）的论文回答了这个问题，并给出了肯定的答案。作者 Markus Engelund Mathiasen、Jian Qian 和 Nikita Zhivotovskiy 构建了一种特定的学习算法，实现了统计最优风险界限。用通俗的话说，这意味着他们找到了一种训练分类器的方法，可以使错误率降到最低，并在数学上证明了没有任何其他方法能超越他们（在某些通用常数范围内），无论噪声水平如何。他们不仅仅是在猜测；他们进行了证明。

以下是他们是如何做到的，我们将使用一个关于组织有序的图书馆以及一个聪明的“一包含游戏”（one-inclusion game）的故事来解释。

问题：嘈杂的图书馆

想象一个巨大的图书馆，这里的每一本书都是一张图片，并且每本书的脊线上都有一个标签写着“猫”或“狗”。然而，图书管理员有点笨手笨脚。有时他们会标错书，或者书本身受损了。你想建立一个系统，通过观察一本新的、未标记的书来正确猜测它的标签。

“最完美”的系统（我们称之为先知/Oracle）了解宇宙的真实规则。即使是先知也会犯一些错误，因为图书管理员的标签有时是错误的。这种最小误差率被称为 $L^*$ 。你的目标是建立一个系统，使其性能尽可能接近先知的表现，使用的是从图书馆中提取的有限数量的书籍（ $n$ ）。

论文证明，他们的系统（我们称之为优化器/The Optimizer）的误差率（ $L(\hat{h})$ ）受限于：
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
不要被数学吓到。关键部分是平方根项。这个公式表明，你多犯的错误（即“超额风险”）会随着你获得的图书数量（ $n$ ）的增加而减少，并且它以概率定律允许的最快速度缩减。以往的方法都有额外的因子（如 $\log(n)$ ）拖慢了它们，但“优化器”去掉了这些。

秘诀：立方体与定向

他们是如何做到的？他们巧妙地结合了两个想法：一包含图（One-Inclusion Graph）和后缀平均法（Suffix Averaging）。

1. 一包含图（立方体游戏）
想象所有可能的书籍标签组合方式。如果你有 $n$ 本书，就会有 $2^n$ 种可能的标签组合。你可以将这些组合可视化为一个巨大的多维立方体（“布尔立方体”）的顶点。

如果两个顶点之间的差异仅在于其中一本书的标签，则它们由一条边连接。
“先知”（最好的规则）就生活在这个立方体的某个地方。
目标是弄清楚当你处于一个顶点时，应该朝哪个方向指，以便向先知靠近。

作者使用了**定向（orientation）**技术。想象你站在这个立方体的某个顶点上。你需要决定下一步往哪走。论文引入了一个新的数学工具，即 Lemma 2.1，它是一个“类相关的边等周不等式”（class-dependent edge isoperimetric inequality）。在我们的图书馆类比中，这就像是一条规则，它规定：“你为了找到正确方向而需要检查的路径数量，取决于你距离先知有多远，以及图书馆有多复杂。”

他们证明了你可以为这个巨大立方体中的每一条边分配一个方向，使得无论你从哪里开始，你永远不需要走超过特定步数就能接近最佳答案。这一步至关重要，因为它将一个混乱的猜测游戏变成了一个确定性的路径。

2. 后缀平均法（委员会投票）
一旦有了这种完美的定向，他们就需要将其转化为一个现实世界的预测器。他们使用了后缀平均法。
想象你正在组建一支专家团队。你不仅仅是询问一位专家的意见。相反，你询问一系列看过不同数量数据的专家。

专家 1 看过了前 $k$ 本书。
专家 2 看过了前 $k+1$ 本书。
……
专家 $m$ 看过了前 $2k-1$ 本书。

最终的预测是所有这些专家意见的平均值。这非常强大，因为它平滑了随机性。如果一位专家因为遇到一本带有噪声的书而运气不佳，其他专家会平衡掉这种偏差。论文证明，这种平均过程结合他们完美的立方体定向，即使在数据有噪声的情况下也能保持低误差率。

3. 最后的润色：阈值处理
平均结果是一个介于 -1 和 1 之间的数字（一个“分数”）。为了得到最终的“猫”或“狗”的答案，他们使用了一个阈值。他们在另一组验证集书籍上测试几个不同的切分点，以挑选出效果最好的那个。这一步确保了最终结果是一个简单的、确定性的规则（二元分类器），而不是一个模糊的概率。

为什么这很重要

在这篇论文之前，如果你想要最快的学习速率，你必须在“适用于完美数据的算法”和“适用于嘈amas数据的算法”之间做出选择。你无法在不付出代价的情况下兼得两者。

这篇论文表明，你可以兼得两者。他们构建了一个学习器，它：

不需要知道噪声水平： 它在不知道数据有多乱（ $L^*$ ）或你希望有多大信心（ $\delta$ ）的情况下也能工作。
是优化的： 它达到了由 Devroye、Györfi 和 Lugosi 等研究人员建立的理论下界（学习速度限制）。
是确定性的： 它不依赖于运气；在同一份数据上运行时，它每次都会给出相同的答案。

作者明确排除了这样一种观点，即我们需要“多项式对数级”（polylogarithmic）因子才能在不可知（agnostic）设置下获得最优结果。他们证明了这些因子是不必要的。他们还表明，虽然一些之前的方法（如简单的多数投票）在处理完美数据时表现良好，但在引入噪声后无法保持最优速度。

简而言之，这篇论文为机器学习理论的历史画上了一个长期的句号。它为现实世界中的二元分类提供了一个“完美”的算法，在现实世界中，数据从来不是完美的。这有点像找到了一张地图，无论路上有多少坑洼，它都能保证你以最少的步数到达宝藏。作者不仅暗示了这是可能的，而且构建了这张地图并证明了它的有效性。

技术摘要：一种最优的无偏置 PAC 算法

问题陈述
本文解决了在二元分类的无偏置（agnostic）概率近似正确（PAC）学习中确定锐利风险界限（sharp risk bounds）这一基本问题。设 $H \subseteq \{-1, +1\}^{\mathcal{X}}$ 为一个 VC 维为 $d \geq 1$ 的假设类。给定来自 $\mathcal{X} \times \{-1, +1\}$ 分布的规模为 $n$ 的 i.i.d. 样本 $S$ ，目标是构建一个学习器，输出一个分类器 $\hat{h}$ ，使其风险 $L(\hat{h})$ 接近最优风险 $L^* = \min_{h \in H} L(h)$ 。

历史上，该设置下的界限是通过两种截然不同的机制推导出来的：

可实现情况（Realizable Case, $L^*=0$ ）： 使用诸如一包含图（one-inclusion graph，由 Haussler, Littlestone, Warmuth 提出）或特定的聚合方案等组合论证，可以实现 $O(d/n)$ 的最优速率。
无偏置情况（Agnostic Case, $L^* > 0$ ）： 当 $L^*$ 远离零时，经典的经验过程方法（链式法则、覆盖法）会产生 $O(\sqrt{d/n})$ 的最优速率。

由 Devroye, Györfi, 和 Lugosi 给出的下界所确立的一个开放性问题是：是否存在一个单一算法，能够在整个 $L^*$ 谱系中实现最优速率，特别是匹配以下界限：
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
此前的上界要么在快速项（fast rate term）中引入了次优的多项式对数因子，要么要求对 $L^*$ 有特定条件（例如 $L^* \lesssim (d+\log(1/\delta))/n$ ）才能实现最优性。

方法论
作者构建了一个确定性的、通常是非适定的（generally improper）学习器，该学习器无需预先知道 $L^*$ 或置信参数 $\delta$ 即可实现最优界限。其方法论分为三个主要阶段：

类相关的边等周性（第 2 节）：
核心理论创新是 引理 2.1，即布尔立方体上的类相关边等周不等式。不同于以往仅通过 VC 维或到迹（trace）的距离来限制边数的结论，该引理引入了权重 $w_{v,p}$ ，这些权重同时满足：
- $w_{v,p} + w_{v \oplus p, p} = 1$ （划分边）；
- $\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ ，其中 $\rho_F(v)$ 是到迹 $F$ 的汉明距离， $R_D(F)$ 是 $F$ 在坐标 $D$ 上的投影的未归一化 Rademacher 宽度。
该不等式允许对子图中的诱导边数 $|E_U|$ 进行局部化控制，通过结合到最优迹的距离和投影的复杂度来进行控制。
最优留一留定向（第 2 节）：
利用 Hall 婚姻定理，作者将该边等周不等式转化为全布尔立方的确定性定向 $\sigma$ 。这种定向确保对于任何顶点 $v$ ，其出度满足：
$\text{out}(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
这导致了一个留一留规则（leave-one-out rule），其期望误差被限制在最优经验风险加上一个随 $\sqrt{d L^*/n}$ 和 $d/n$ 缩放的项。
从留一留到 PAC 界限（第 3 节）：
为了将留一留规则转化为高概率 PAC 保证，作者采用了两步去随机化和平均化过程：
- 对称化与后缀平均化： 将确定性的留一留规则在排列上进行对称化。通过对样本的后缀（索引 $k$ 到 $2k-1$ ）对这些对称化得分进行平均，构造出一个随机预测器 $\hat{p}$ 。这一步利用了改编自 Aden-Ali 等人的正向和反向鞅论（引理 3.1 和 3.2）来控制经验风险的方差和偏差，从而确保界限在 $L^*$ 范围内均匀成立。
- 阈值化与 ERM： 将取值在 $[-1, 1]$ 之间的随机预测器 $\hat{p}$ 转换为确定性的二元分类器。这是通过考虑一类阈值化假设 $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ 来实现的。使用独立的验证样本从该类中选择一个经验风险最小化器（ERM）。至关重要的是，阈值类的嵌套结构允许在不引入额外样本量对数因子的情况下实现局部熵界限，从而保留了 $L^*$ 的最优系数。

主要贡献与结果
本文证明了 定理 1，确立了存在这样一个确定性学习器：对于任何分布、样本量 $n$ 和置信度 $\delta$ ，它输出的分类器 $\hat{h}$ 满足：
$L(\hat{h}) \leq 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
其概率至少为 $1-\delta$ 。定理 1 证明中的最终推导得到了一个约为 $3.1 \cdot 10^7$ 的更紧凑常数。

最优性： 该界限在通用常数意义上匹配了 Devroye, Györfi, 和 Lugosi 的下界。这是第一个在每个固定的 $L^*$ 下都能实现最优速率的结果，弥合了可实现情况与完全无偏置情况之间的差距，且没有引入次优的多项式对数因子。
算法属性： 该学习器是确定性的、通常是非适定的（输出的分类器不一定属于 $H$ ），且不需要预知 $L^*$ 或 $\delta$ 。
技术新颖性： 证明依赖于新的类相关边等周不等式（引理 2.1），该不等式通过结合近似误差和投影 Rademacher 宽度的手段来控制诱导边数，这一技术有别于以往的组合论或纯经验过程方法。

意义
本文声称解决了无偏置 PAC 学习在常数意义下的样本复杂度问题。通过构建一个在每个固定的 $L^*$ 下都能达到二元分类极小极大经验风险（minimax excess risk）的算法，作者解决了一个长期存在的开放问题，即是否存在一个在所有噪声水平谱系中都具有最优性的单一算法。这项工作表明，在不牺牲 $L^*$ 项的主导系数的情况下，实现最优速率是可能的，而此前由于实现情况与完全无偏置分析技术之间的张力，这一目标被认为难以实现。

问题：嘈杂的图书馆

秘诀：立方体与定向

为什么这很重要

技术摘要：一种最优的无偏置 PAC 算法

类似论文