🤖 machine learning

Strategic PAC Learnability via Geometric Definability

本文表明，尽管策略性行为可使甚至简单假设类变得不可学习，但基于 $\mathbb{R}_{\mathtt{exp}}$ 上的一阶公式施加几何可定义性假设，通过确保诱导的策略复杂性保持可控，从而恢复了 PAC 可学习性。

原作者： Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich

发布于 2026-05-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich

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

想象你是一名大学招生官，正在决定谁能够被录取。你有一套基于成绩和考试分数的规则（一个“分类器”）。但这里的陷阱在于：申请者并非被动的数据点；他们是聪明且精于算计的参与者。如果他们知道了你的规则，他们可能会更加努力学习、重考，甚至伪造某项爱好，仅仅为了跨过那条线并被录取。

这就是策略性分类（Strategic Classification）的世界。研究人员提出的核心问题是：如果我们能为普通人学习到一个好的规则，那么当人们积极试图操纵系统时，我们是否仍能学习到一个好的规则？

本文《通过几何可定义性实现策略性 PAC 可学习性》（Strategic PAC Learnability via Geometric Definability）以坏消息、好消息以及一个非常具体的数学“安全网”相结合的方式，探讨了这个问题。

坏消息：策略可能毁掉一切

作者们从一个令人惊讶的发现开始。你可能会认为，如果你的学习问题很简单（例如，基于单个数字将人们分类为“是”或“否”），那么即使人们试图作弊，它也应该保持简单。

类比：想象你在玩一个游戏，你需要猜一个 0 到 10 之间的秘密数字。这很容易。但现在，想象一下，在你猜测之前，那个藏数字的人被允许将数字上下移动 1 个单位。你可能会想：“没什么大不了的，我只需要猜一个范围。”

论文证明，在某些情况下，这种微小的移动能力会将一个简单的游戏变成一个不可能完成的任务。他们构建了一个场景，其中原始规则极其简单（简单到其“复杂度得分”为 1），但一旦允许申请者稍微移动他们的特征（例如在半径为 1 的范围内移动），学习问题就变得无限复杂。

结论：仅仅因为一个问题看起来很简单，且作弊的“成本”很低，并不意味着该问题仍然可学习。策略性行为可以将一项简单的任务变成一项崩溃的任务。

好消息：几何学力挽狂澜

那么，所有的希望都破灭了吗？不。作者们意识到，他们构建的那些“坏”例子在数学上是“狂野”且人为的。他们寻找一种方法来说：“好吧，让我们只关注那些遵循正常几何和算术规则的问题。”

他们引入了一个名为几何可定义性（Geometric Definability）的概念。

类比：把数学世界想象成一个巨大的工具箱。

“狂野”工具箱：包含可以绘制无限、蜿蜒、重复图案的工具（例如永不停歇的正弦波）。这些工具会破坏学习。
“温顺”工具箱：只包含标准工具：加法、减法、乘法、除法，也许还有少数特殊的工具，如指数函数（ $e^x$ ）和对数函数（ $\log x$ ）。这些工具可以绘制圆形、直线、曲线和形状，但它们无法绘制那些无限、疯狂、重复的图案。

论文论证道，如果你的规则和“作弊成本”仅能用温顺工具箱来描述（数学家称之为结构 $\mathbb{R}_{exp}$ ），那么学习就被挽救了。

如果你的系统是基于这些“温顺”的几何规则构建的：

它仍然是可学习的。你仍然可以找到一个好的分类器。
我们可以计算成本。他们提供了公式，可以精确计算你需要多少个样本（例子）来学习该规则。描述你规则的公式越复杂，你需要的数据就越多，但这始终是一个有限的、可管理的数字。

“操作指南”：从理论到数字

这篇论文不仅仅说“它有效”；它还给你一把尺子，用来衡量它有多有效。

定性保证：如果你的规则是“温顺”的（在 $\mathbb{R}_{exp}$ 中可定义），那么你可以保证学习是可能的。
定量保证：如果你的规则甚至更简单（仅使用多项式，不使用指数函数），作者们会给你一个具体的公式，用来计算你需要面试多少学生才能获得完美的录取规则。
“存在性”捷径：他们表明，许多现实世界的问题（例如测量人与人之间的距离或比较概率分布）自然地符合一种特定类型的“温顺”公式，称为“存在性公式”（existential formula）。对于这些情况，他们提供了关于需要多少数据的明确且精确的界限。

他们涵盖的现实世界示例

作者们表明，这不仅仅是抽象的数学；它涵盖了许多我们实际使用的东西：

距离：如果“作弊”意味着以某种距离移动你的特征（例如欧几里得距离或 $L_p$ 范数），这是可行的。
信息论：如果“作弊”涉及改变概率分布（使用 KL 散度），这是可行的。
神经网络：如果你的分类器是一个具有标准激活函数（如 ReLU 或 Sigmoid）的神经网络，且改变输入的代价是“温顺”的，那么该系统就是可学习的。

局限性（“细则”）

论文诚实地指出了这个安全网失效的地方。

无限循环：如果你的规则涉及无限、重复的图案（例如永不停歇的正弦波），“温顺”数学就不适用了，问题可能会再次变得不可学习。
积分：如果作弊的代价是由一个复杂的积分（无限范围的总和）定义的，且无法简化为一个整洁的公式，那么当前的方法就不涵盖这种情况。

总结

简而言之，论文指出：

不要假设策略是安全的。如果人们试图以奇怪的方式操纵系统，一个简单的学习问题可能会变得不可能。
但是，如果规则是“几何温顺”的，你就是安全的。如果你的规则和作弊成本可以用标准数学运算（加上 $e$ 和 $\log$ ）来描述，那么问题仍然是可解的。
我们可以衡量难度。论文提供了数学方法，可以精确计算你需要多少数据来学习这些策略性规则，将模糊的担忧转化为具体的计算。

它是策略性行为的混乱现实与数学学习理论的有序世界之间的桥梁，向我们展示了桥梁在哪里坚固，又在哪里可能会坍塌。

技术摘要：基于几何可定义性的战略 PAC 可学习性

问题陈述
战略分类研究的是个体以一定成本修改其特征以影响分类器决策的学习场景。该领域的一个基本问题是：当个体采取战略行为时，底层假设类 $\mathcal{H}$ 的可学习性是否得以保留。具体而言，由战略行为诱导的战略假设类 $\mathcal{H}^N$ （其中 $N$ 表示由成本诱导的邻域关系）是否保持 PAC 可学习性，以及其样本复杂度如何与 $\mathcal{H}$ 的复杂度及成本结构相关联？

先前的研究已在特定设定下取得了积极成果，例如带有范数成本的线性分类器或在输入缩放下封闭的类。然而，组合简单性（如低 VC 维）与战略可学习性之间的一般关系仍未解决。本文探讨了“简单”的成本结构和假设类是否足以保证战略行为不会使学习问题变得不可处理。

方法论与框架
作者采用双重方法：一方面证明在一般组合设定下可学习性的失效，另一方面通过基于模型论的几何可定义性假设来恢复可学习性。

负面结果（组合简单性不足）：
本文构造了一个反例，表明即使在最简单的设定下，战略行为也可能破坏可学习性。作者在实数线 $\mathbb{R}$ 上定义了一个 VC 维为 1 的假设类 $\mathcal{H}$ ，并采用均匀区间邻域系统（点可在固定半径 $r$ 内移动）。尽管该类和成本结构的复杂度均极小，但诱导出的战略类 $\mathcal{H}^N$ 被证明具有无限 VC 维，从而导致其不可 PAC 学习。该构造依赖于将任意索引子集编码到不相交的区间中，使得战略变换能够打散任意大的有限集合。
正面结果（几何可定义性）：
为了克服上述负面结果，作者引入了一个结构性假设：几何可定义性。他们利用模型论中的结构 $\mathbb{R}_{\exp}$ （即添加了指数函数的实数域）上的一阶公式来建模假设类和邻域关系。
- $\mathbb{R}_{\exp}$ -可定义性：假设和邻域由涉及算术运算（ $+, \cdot$ ）、比较（ $<, =$ ）以及指数函数（ $\exp$ ，进而包含对数）的公式定义。这涵盖了广泛的自然类，包括线性分类器、多项式阈值函数、具有标准激活函数的神经网络，以及基于 $\ell_p$ 范数、Wasserstein 距离和 KL 散度的成本函数。
- 战略变换作为存在量词：诱导的战略假设 $h^N(x) = 1$ 当且仅当存在 $x' \in N_x$ 使得 $h(x') = 1$ 。这在定义公式中引入了一个存在量词。
- 模型论工具：分析利用了 $\mathbb{R}_{\exp}$ 是o-极小结构（Wilkie 定理）这一事实。在 o-极小结构中，可定义集 admits 有限单元分解，且具有多项式有界的增长函数。作者利用了来自驯化拓扑（tame topology）和有效单元分解（特别是针对受限 Pfaffian 集）的结果，对诱导战略类的增长函数进行了界定。

主要贡献与结果

战略不可学习性：
本文证明了即使在简单的区间邻域下，战略行为也能将一个可学习的问题（VC 维为 1）转化为不可学习的问题（无限 VC 维）。这表明仅凭组合简单性不足以保证战略可学习性。
通过 $\mathbb{R}_{\exp}$ 实现定性可学习性：
主要定理 2 确立了如果假设类 $\mathcal{H}$ 和邻域系统 $N$ 均在 $\mathbb{R}_{\exp}$ 中可定义，则诱导的战略类 $\mathcal{H}^N$ 是 PAC 可学习的。样本复杂度由定义公式中使用的参数数量 $k$ 控制。具体而言，增长函数 $\Pi_{\mathcal{H}^N}(m)$ 被 $C m^k$ 界定，这意味着有限的 VC 维。该结果依赖于 $\mathbb{R}_{\exp}$ 的 o-极小性以及可定义族的多项式增长定理。
定量界（半代数情形）：
主要定理 3 为定义限制在实数域 $\mathbb{R}$ 语言（即涉及多项式的无量词公式，亦即半代数集）的情形提供了显式的、构造性的界。通过应用定量量词消去（Tarski-Seidenberg），作者根据描述复杂度 $D$ （多项式的数量及其次数）推导出了 VC 维和样本复杂度的显式界。
- 结果： $VC(\mathcal{H}^N) = O(k^2 l \log D)$ ，且样本复杂度以类似方式缩放。
定量界（存在性 $\mathbb{R}_{\exp}$ 情形）：
主要定理 4 将定量分析扩展到完整的 $\mathbb{R}_{\exp}$ 设定，但限制在存在公式（ $\Sigma_1$ ）范围内。这涵盖了许多自然的战略设定（例如 $\ell_p$ 球、Earth Mover 距离），其中邻域关系由存在量词定义。
- 作者为这些公式定义了“格式”（ $F$ ）和“次数”（ $D$ ）。
- 结果： $VC(\mathcal{H}^N) = O_F(\log D)$ ，样本复杂度为 $O\left(\frac{k \log(1/\varepsilon) + \gamma(F) \log D + \log(1/\delta)}{\varepsilon}\right)$ ，其中 $\gamma$ 是一个可显式计算的函数。
- 证明利用受限 Pfaffian 结构的有效单元分解定理来处理指数函数。

意义与主张
本文声称通过识别几何驯化性（geometric tameness）作为关键因素，解决了组合简单性与战略可学习性之间的张力。

组合度量的局限性：该工作表明，基础类的低 VC 维并不能保证在战略操纵下的可学习性；成本函数和假设类的结构从根本上至关重要。
通过可定义性恢复：通过将注意力限制在“驯化”的几何类（在 $\mathbb{R}_{\exp}$ 中可定义）上，本文表明战略可学习性得以恢复。战略类的复杂度由定义公式的逻辑复杂度（参数数量、格式和次数）控制，而非诱导类的原始组合复杂度。
范围：该框架涵盖了广泛的实际设定，包括多项式分类器、决策树、具有常见激活函数的神经网络以及各种距离度量（ $\ell_p$ 、KL、Wasserstein）。
局限性：作者指出，其正面结果依赖于结构的“驯化性”。具有无界振荡或周期结构的邻域（例如由 $\sin$ 定义的）超出了 $\mathbb{R}_{\exp}$ 框架的范围，并可能导致不可学习性。此外， $\mathbb{R}_{\exp}$ 的定量界目前仅限于存在公式；全称量词仅在定性层面处理。

总之，本文确立了虽然战略行为在一般情况下可能灾难性地增加学习复杂度，但对于由实数域上带指数的一阶逻辑定义的广泛且自然的几何问题类而言，这种病态是可以避免的。这些问题的样本复杂度由底层几何定义的描述复杂度所支配。