多分类学习竟被2维问题难倒？单调污染下AI直接“失忆”，只需n个假样本就崩盘！
When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
📖 AI 总结
本文研究单调对抗性污染对机器学习模型的影响，挑战了经典PAC模型中独立同分布数据的假设。作者发现，当训练样本被来自无关甚至对抗性来源的正确标记数据污染时，最优二元分类器的错误率从PAC模型的O(d/n)恶化至Ω(d log(n/d)/n)。研究进一步揭示，在多元分类和部分二元概念类等更广泛场景中，单调对抗者的破坏力更为惊人：一个DS维度仅为2的可学习多元分类问题，在对抗者仅需插入线性数量n个污染数据点后即变得完全不可学习。作为补充，作者证明当自适应添加的数据量为o(n)时，所有类别仍可学习，这一界限与多元分类下界相匹配。此外，研究还发现，在对抗者预算受限（常数级）、半自适应或不知情对抗者等特定条件下，经典多元分类错误率O(d_DS/n)仍可维持。该研究为理解数据污染对学习算法鲁棒性的影响提供了重要理论边界。
🔑 关键词速览
| 单调对抗性污染 | 一种数据污染模型，其中对手只能插入正确标记的样本，但不能修改或删除现有样本。 |
| PAC模型 | 概率近似正确学习框架，假设训练样本独立同分布，是机器学习理论的基础模型。 |
| DS维度 | 一种衡量概念类复杂度的指标，用于刻画多分类问题的样本复杂度。 |
| 自适应对手 | 能够查看原始训练集并基于其内容决定插入哪些污染样本的对抗性攻击者。 |
| 半自适应对手 | 只能查看训练集的一部分（如p比例）来决定插入污染样本的对手。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅