arXiv:2511.07417stat.MLcs.AI2025-11被引 10

研究语言生成在无限噪声下的鲁棒性,发现只要噪声比例趋近零就可实现可靠生成。

Language Generation with Infinite Contamination

  • 提出在污染数据下生成语言的理论条件,关键在于污染比例趋于零
  • 证明稠密生成比普通生成更难容忍污染,存在本质差异
  • 揭示课程学习机制对处理海量噪声数据的关键作用

我们研究语言生成在极限情形下的表现:算法观察一个对抗性枚举序列(来自未知目标语言K),需最终生成新的、未见过的K中字符串。Kleinberg和Mullainathan [KM24] 证明生成在极广条件下可行,但其生成器存在“模式坍缩”问题,输出集中在越来越小的子集。为解决此问题,Kleinberg和Wei [KW25] 要求生成结果在目标语言中“稠密”,并证明稠密生成仍可在相同一般性下实现。但两者均假设数据完美无误,无噪声插入也无遗漏。这引出核心问题:生成能容忍多少污染?近期工作仅在有限噪声(无遗漏)或有限遗漏(无噪声)下取得部分进展。本文完整刻画了在污染枚举下的生成能力:1. 普通生成可实现当且仅当污染样本占比收敛于零;若不满足,则可刻画哪些语言集合仍可生成。2. 稠密生成对污染的鲁棒性严格弱于普通生成。作为副成果,我们解决了Raman和Raman [ICML25] 的开放问题:在有限污染情况下,仅通过成员查询访问即可实现生成。最后,我们引入超越最坏情况的课程学习模型,证明即使有无穷污染,只要污染比例趋于零,稠密生成仍可实现。这表明课程学习可能对从嘈杂网络数据中学习至关重要。

原文摘要 · Abstract (English)

We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language $K$ and must eventually generate new, unseen strings from $K$. Kleinberg and Mullainathan [KM24] proved that generation is achievable in surprisingly general settings. But their generator suffers from ``mode collapse,'' producing from an ever-smaller subset of the target. To address this, Kleinberg and Wei [KW25] require the generator's output to be ``dense'' in the target language. They showed that generation with density, surprisingly, remains achievable at the same generality. Both results assume perfect data: no noisy insertions and no omissions. This raises a central question: how much contamination can generation tolerate? Recent works made partial progress on this question by studying (non-dense) generation with either finite amounts of noise (but no omissions) or omissions (but no noise). We characterize robustness under contaminated enumerations: 1. Generation under Contamination: Language generation in the limit is achievable for all countable collections iff the fraction of contaminated examples converges to zero. When this fails, we characterize which collections are generable. 2. Dense Generation under Contamination: Dense generation is strictly less robust to contamination than generation. As a byproduct, we resolve an open question of Raman and Raman [ICML25] by showing that generation is possible with only membership oracle access under finitely many contaminated examples. Finally, we introduce a beyond-worst-case model inspired by curriculum learning and prove that dense generation is achievable even with infinite contamination provided the fraction of contaminated examples converges to zero. This suggests curriculum learning may be crucial for learning from noisy web data.

语言生成鲁棒性课程学习稠密生成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。