正确数据也可能有害，关键看学习算法是否稳定。
When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory
- 提出插入稳定性概念，确保增加正确数据不会扩大错误区域。
- 证明某些类在非稳定学习器下误差率会恶化至 log(n)/n 阶。
- 适合关注模型鲁棒性与数据添加风险的研究者。
添加已知正确的数据本应安全，但并非总是如此。本文通过单调对抗者模型分析失败情况：该对手可任意追加正确标签样本，只要目标假设能一致标注它们。Mehrotra 已证明，对于 VC 维 d ≥ 2 的类别，任何学习器的期望误差均无法优于 Θ((d/n)log(en/d))，即比干净 PAC 率高出对数因子。由于这是最坏情况下的结果，无法说明哪些具体类别会受罚，而答案取决于学习器本身。我们定义插入稳定性：若学习器在加入更多正确标签样本后，其错误区域不会扩大，则该学习器免疫于对抗者攻击，且高概率保证不变。闭包类（如交封闭类）始终插入稳定，保持干净率 E[Err] ≤ (21d+34)/n。然而，经典维度无法预测这种免疫性——两个同为 VCdim = Ldim = 2 的类，一个误差率为 Θ(1/n)，另一个为 Θ(log(en)/n)；而区间类虽具无界 Littlestone 维，仍免疫。在 Mehrotra 的困难类上，我们进一步证明：不存在任何有限大小、单调且置换不变的压缩方案能达到干净率。因此，问题不在于类别是否困难或学习器是否优秀，而在于二者是否匹配。若使用在干净数据上最优的插入稳定学习器，正确数据是免费的；否则代价由类别承担，换学习器也无法避免。
原文摘要 · Abstract (English)
Adding data known to be correct ought to be safe. Not always. Larsen, Pabbaraju and Shetty model the failure with a monotone adversary, which reads an i.i.d. training sample and may append as many further examples as it likes, provided the target hypothesis labels them all. Mehrotra has since settled the cost, showing that for classes of VC dimension d >= 2 no learner can guarantee expected error better than Theta((d/n)log(en/d)), a logarithmic factor above the clean PAC rate. Because that rate is a worst case over all classes, it says nothing about which classes actually suffer the penalty, and the answer turns on the learner. We call a learner insertion-stable if feeding it more correctly labeled examples can only shrink the region where it errs. Such learners are immune to the adversary, since on any given sample the risk after insertions never exceeds the risk on the clean part alone, however much is added and however cleverly it is chosen. High- probability guarantees carry over unchanged, and because Closure is insertion-stable every intersection-closed class keeps its clean rate of E[Err] <= (21d+34)/n. Immunity is not something the classical dimensions can predict. Two classes can agree on VCdim = Ldim = 2 and still split, one at Theta(1/n) and the other at Theta(log(en)/n), while intervals have unbounded Littlestone dimension and are immune anyway. On Mehrotra's hard class we prove more than the failure of a single algorithm, showing that no monotone permutation-invariant compression scheme of any finite size attains the clean rate. The question is therefore not whether a class is hard, nor whether a learner is good, but whether the two suit each other. Given an insertion-stable learner that is optimal on clean data, correct additions are free, and without one the cost belongs to the class, so changing the learner will not avoid it.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。