更多正确数据何时有害？插入稳定性与维度理论的局限性

# 更多正确数据何时有害？插入稳定性与基于维度理论的局限  
来源：https://arxiv.org/html/2608.14020 2026年8月14日  

###### 摘要  
添加已知正确的数据通常应是安全的，但并非总是如此。Larsen、Pabbaraju 和 Shetty 用**单调对手**模型来描述失败情况：对手读取独立同分布的训练样本，并可随意追加任意数量的额外样本，只要目标假设能对这些样本正确标注即可。Mehrotra 随后确定了这一模型下的最优误差界，证明对于VC维 \(d \geq 2\) 的假设类，任何学习器的期望误差下界为 \(\Theta\left( (d/n) \log(en/d) \right)\)，比干净的 PAC 速率高出一个对数因子。由于该速率是所有类上的最坏情况，并不能指出哪些类实际会受此惩罚，答案取决于学习器的选择。我们称学习器具有**插入稳定性**，若向其提供更正确的标注样本仅能缩小其误差区域。此类学习器可免疫对手攻击，因为无论添加多少样本、对手如何设计，其在任意样本上的风险都不会超过仅使用干净样本时的风险。高概率保证同样成立；由于闭包算法具有插入稳定性，每个交集封闭类都能保持干净速率为 \(\mathbb{E}[\text{Err}] \leq (21d + 34)/n\)。这种免疫性无法被经典维度理论预测：两个类可具有相同的 \(VC\text{dim} = \text{Ldim} = 2\)，但速率可能分别为 \(\Theta(1/n)\) 和 \(\Theta(\log(en)/n)\)；而区间类的 Littlestone 维度无界，却同样具有免疫性。在 Mehrotra 构造的困难类上，我们证明了不仅单一算法会失败，任何有限规模的单调置换不变压缩方案均无法达到干净速率。因此，问题不在于类是否困难，也不在于学习器是否优秀，而在于两者是否匹配。若存在在干净数据上最优且具有插入稳定性的学习器，则正确的数据添加是无代价的；否则惩罚归属于该类本身，更换学习器也无法避免。  

## 1 引言  
假设你扩展训练集：为已有的每张图像添加一个旋转副本并保留相同标签；或发现稀有类样本太少，因而复制其样本。你所添加的内容完全正确，且仅在查看已有数据后选择添加内容。从业者常规执行此类操作，预期最多无害，因为标准泛化界要求数据独立或可交换，而数据增强似乎不威胁标签或样本覆盖。然而，它确实破坏了这种对称性，而保证正基于此。  

Larsen、Pabbaraju 和 Shetty 的模型将此效应从数据集可能出现的其他问题中隔离出来。其对手读取干净样本，然后追加任意样本，但有一个限制：每个追加样本的标签必须与目标假设给出的标签一致。没有错误标签，因此所有追加约束都是有效的；若存在能识别原始样本的预言机，学习器可无代价地忽略其余样本。追加样本破坏了独立性：它们在选择时已知晓干净样本，而学习器收到的是混合后的样本池，两组样本不可区分，因此既无法隔离干净子样本，也无法将其视为可交换的。  

Mehrotra 确定了该模型下的最优速率：对于 VC 维 \(d \geq 2\) 的类，该速率为 \(\Theta\left( (\min\{d, n\}/n) \log(en/\min\{d, n\}) \right)\)，比干净速率 \(\Theta(d/n)\) 高出一个对数因子，且对抗任何随机化、可能非一致的学习器均成立；若用 Littlestone 维度替代 \(d\)，相同速率仍成立，因此有限错误界限也无济于事。反直觉的是，正确标注的插入提高了问题的统计难度。  

#### 本文工作  
Mehrotra 的界是所有类的上确界，由特定构造给出，其提出的首个公开问题是：  
> *“在单调插入下，固定二元类的哪些结构属性决定其速率？”*  

我们的回答是两面的，这两面正是最坏情况速率所掩盖的。决定结果的不是类的规模或其经典维度，而是**学习器在该类上误差区域的几何形状**。若存在某个学习器，其误差区域在正确样本到来时只能缩小，则插入完全无代价：不仅代价可承受，而且是零代价，无论预算多少。若不存在此类学习器，则惩罚是该类的属性，且 Mehrotra 的下界表明每个学习器都需支付此惩罚。因此，该现象附着于学习器与类的配对关系。  

#### 贡献  
1. **插入稳定性引理**（第3节）。若学习器的误差区域在正确标注插入下仅缩小，其对抗风险**几乎必然**被其干净风险控制。适应性、任意数量插入、重复样本、分布外样本、随机化对手以及高概率保证均为免费推论。证明通过归约实现：独立同分布假设仅限于引用干净样本的定理中，从未应用于被污染样本。  
2. **闭包算法具有插入稳定性**（第4节），因此每个交集封闭类在任意多的适应性单调插入下均保持干净速率，期望误差明确为 \((21d + 34)/n\)。我们还注意到 Mehrotra 本身的有限预算反例使用了*负数*重复样本，因此对闭包算法不仅是可承受的，更是*不可见*的。  
3. **维度独立性**（第5节）。\(\mathcal{H}_{\leq 2}\) 与 \(\mathcal{H}_{\mathrm{prime}}\) 具有相同的 VC 维和 Littlestone 维度，但速率相差 \(\Theta(\log n)\)；区间的 Littlestone 维度无界，却仍保持干净速率。VC 维和 Littlestone 维的任何函数均无法决定单调插入速率。  
4. **否定性结果强化至算法族**（第5节）。对于 \(\mathcal{H}_{\mathrm{prime}}\)，我们证明*不存在*任何有限规模的一致单调置换不变压缩方案能达到干净速率。这排除了一整类潜在解决方案而非单一算法，是本文的主要技术成果。  

#### 未声称的内容  
我们给出的是充分条件而非完全刻画。相反方向（即非插入稳定结构强制对数惩罚）仍为开放问题，第7节明确指出了缺失部分。第6节的候选度量仅为记账工具，而非理论：它重组了已知定理的假设，且我们明确说明目前无法在未知类速率的情况下评估该类。我们的工具借鉴自 Hanneke；贡献在于使此工具适用于本场景的归约，以及上述否定结果。所有关于特定类的组合断言均通过穷举计算验证。  

## 2 模型与预备知识  
符号和模型陈述遵循文献[9]。设 \(\mathcal{D}\) 为 \(\mathcal{X}\) 上的分布，\(g, h: \mathcal{X} \to \{0,1\}\)，记 \(\text{Err}_{\mathcal{D}}(g, h) = \mathbb{P}_{X \sim \mathcal{D}} \{ g(X) \neq h(X) \}\)。多重集并记为 \(\uplus\)，每个重复点均作为独立出现计数。对数取自然底数 \(e\)。  

###### 问题 1（单调对手下的学习[8,9]）  
固定非空类 \(\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}\)，整数 \(n \geq 1\)，\(m \geq 0\)，目标假设 \(h^\star \in \mathcal{H}\)，以及 \(\mathcal{X}\) 上的分布 \(\mathcal{D}\)。精确预算 \(m\) 的确定性单调对手是一个映射 \(A: \mathcal{X}^n \to \mathcal{X}^m\)。数据集生成如下：  
1. 自然过程抽取有序干净样本 \(X = (X_1, \dots, X_n) \sim \mathcal{D}^n\)。  
2. 对手观测 \(X\) 并返回 \(A(X) = (\widetilde{X}_1, \dots, \widetilde{X}_m)\)。对手可重复样本或选择 \(\text{supp}(\mathcal{D})\) 外的样本，但必须为每个追加样本标注 \(h^\star\)。  
3. 自然过程为 \(n+m\) 个出现抽取独立的均匀置换 \(\Pi\)，并交给学习器 \(T_{h^\star, A}(X, \Pi) = \Pi\big( (X_i, h^\star(X_i))_{i=1}^n \uplus (\widetilde{X}_j, h^\star(\widetilde{X}_j))_{j=1}^m \big)\)。  

学习器已知 \(\mathcal{H}\)、\(n\) 和 \(m\)，但不知哪些样本来自 \(\mathcal{D}\)。其评分基于来自 \(\mathcal{D}\) 的新独立点上的 \(\text{Err}_{\mathcal{D}}(\hat{h}, h^\star)\)。  

模型四个关键特征（均在[9]中明确）：所有标签正确；对手可重复样本及使用 \(\text{supp}(\mathcal{D})\) 外样本；学习器接收均匀混合，因此是*多重集*的函数而非序列；对手是*适应性的*，在选择插入前观测整个 \(X\)。最后一点是难点的唯一来源；在非知情情况下，干净速率 \(\Theta(d/n)\) 已可达到[8]。对手随机化不改变图景：如 Mehrotra 所指，上界在对手随机性条件下仍成立。  

*带标签多重集*是有限个 \((x, y) \in \mathcal{X} \times \{0,1\}\) 对的多重集；若每个出现均满足 \(y = h^\star(x)\)，则称其被 \(h^\star\) 正确标注。我们记 \(S \subseteq T\) 表示多重集包含关系，即 \(T\) 可包含 \(S\) 中点的额外副本。\(\mathcal{H}\) 在带标签多重集 \(L\) 上的*版本空间*为 \(V_{\mathcal{H}}(L) = \{ h \in \mathcal{H} : h(x) = y \text{ 对所有 } (x,y) \in L \}\)。  

回忆：若 \(\{ \{ x : h(x)=1 \} : h \in \mathcal{H} \}\) 对成员的两两交集封闭，则 \(\mathcal{H}\) 是*交集封闭的*。\(\{0,1\}^p\) 上的合取式、\(\mathbb{R}^p\) 上的轴对齐矩形以及 \(\mathcal{H}_{\leq d} = \{ h : | \{ x : h(x)=1 \} | \leq d \}\) 均是交集封闭类[7]。（采用成员两两交集封闭的标准约定；部分作者还要求 \(\mathcal{X}\) 本身属于该族，但 \(\mathcal{H}_{\leq d}\) 在 \(\|\mathcal{X}\| > d\) 时不满足此条件。）  

对于此类，闭包算法在带标签多重集 \(L\)（满足 \(V_{\mathcal{H}}(L) \neq \emptyset\)）上返回分类器 \(\hat{h}_L\)，其满足：  
\[
\{ x : \hat{h}_L(x) = 1 \} = \bigcap_{h \in V_{\mathcal{H}}(L)} \{ x : h(x) = 1 \}.
\]  
(1)  

## 3 插入稳定性  
对于学习器 \(A\) 和被 \(h^\star\) 正确标注的带标签多重集 \(T\)，定义*误差区域*为：  
\[
\text{ErrReg}_{h^\star}(A(T)) = \{ x \in \mathcal{X} : A(T)(x) \neq h^\star(x) \}.
\]  

###### 定义 2（插入稳定）  
学习器 \(A\) 是*插入稳定的*，若它满足：  
1. (i) *置换不变*：\(A(T)\) 仅依赖于带标签多重集 \(T\)；  
2. (ii) *超集单调*：对所有 \(h^\star \in \mathcal{H}\) 及所有被 \(h^\star\) 正确标注的有限带标签多重集 \(S \subseteq T\)，有 \(\text{ErrReg}_{h^\star}(A(T)) \subseteq \text{ErrReg}_{h^\star}(A(S))\)。  

对于随机化 \(A\)，要求 (ii) 对每个与样本独立抽取的硬币实现成立。  

三个细节值得注意且被有意允许：包含是*多重集*包含，因此 \(T\) 可重复 \(S\) 的点（这在 Mehrotra 的构造中常用）；无约束将 \(T\) 的点与 \(\text{supp}(\mathcal{D})\) 关联，事实上 \(\mathcal{D}\) 在定义2中根本不出现，这使下文的归约对所有 \(\mathcal{D}\) 同时成立；置换不变性被融入定义而非附加条件，因为模型的混合已提供此特性。  

###### 定理 3（插入稳定性引理）  
设 \(A\) 为插入稳定的。则对任意 \(\mathcal{D}\)、任意 \(h^\star \in \mathcal{H}\)、任意有限预算 \(m \in \mathbb{N}\) 及任意可能随机化的适应性单调对手，在包含干净样本、对手硬币、混合及学习器硬币的单个概率空间上，有：  
\[
\text{Err}_{\mathcal{D}}(A(T), h^\star) \leq \text{Err}_{\mathcal{D}}(A(S), h^\star) \quad \text{几乎必然},
\]  
其中 \(S\) 是被 \(h^\star\) 标注的干净样本，\(T\) 是学习器的输入。  

###### 证明  
固定干净样本 \(X\)、对手硬币、置换 \(\Pi\) 及学习器硬币的实现。  
*步骤1：\(T\) 是 \(S\) 的正确标注超集*。由问题1，\(T\) 由 \(n\) 个干净出现及 \(m\) 个插入出现混合而成。每个插入出现被 \(h^\star\) 标注，干净出现亦然，故 \(T\) 被 \(h^\star\) 正确标注；丢弃插入出现即展示 \(S \subseteq T\)（作为多重集）。  
*步骤2：误差区域缩小*。由 (i)，\(A(T)\) 不依赖 \(\Pi\)，仅是带标签多重集的函数。将 (ii) 应用于 \(S \subseteq T\) 得 \(\text{ErrReg}_{h^\star}(A(T)) \subseteq \text{ErrReg}_{h^\star}(A(S))\)。  
*步骤3：测度的单调性*。由于 \(\mathcal{D}\) 是测度，且对任意 \(L\) 有 \(\text{Err}_{\mathcal{D}}(A(L), h^\star) = \mathcal{D}(\text{ErrReg}_{h^\star}(A(L)))\)，步骤2给出：  
\[
\text{Err}_{\mathcal{D}}(A(T), h^\star) \leq \text{Err}_{\mathcal{D}}(A(S), h^\star)
\]  
对此实现成立。由于实现任意，不等式几乎必然成立。∎  

###### 推论 5（迁移）  
设 \(A\) 为插入稳定的。因定理3是显式耦合下的几乎必然控制，且两个学习器在*相同*干净样本上运行，风险的任何单调泛函均可从干净设置迁移到对抗设置。特别地，对任意有限预算 \(m\) 和任意随机化适应性单调对手（因而对注4的 \(R^{\infty}_{\mathcal{D}}\) 亦然）：若 \(\mathbb{E}[\text{Err}_{\mathcal{D}}(A(S), h^\star)] \leq B(n)\)，则