arXiv:2506.18642cs.LG2025-06NeurIPS被引 15

语言生成在极限下不满足有限并集封闭性,无法通过组合生成器提升能力。

On Union-Closedness of Language Generation

  • 构造反例证明可生成类的并集未必可生成
  • 发现非均匀可生成类与均匀可生成类的并集可能不可生成
  • 揭示生成器无法像分类器一样通过组合实现增强,适合理论学习研究者

我们研究语言生成在极限情形下的性质——Kleinberg 和 Mullainathan [NeurIPS 2024] 提出该框架,并由 Li、Raman 与 Tewari [COLT 2025] 扩展。尽管 Kleinberg 与 Mullainathan 证明了对任意可数集合均可生成,Li 等人定义了统一、非统一和可生成三类生成概念,并探讨其在不可数集合上的可行性。本文解决两个开放问题:证明有限个可生成类或非统一可生成类的并集未必可生成。更强结果为:存在一个非统一可生成类与一个统一可生成类,其并集不可生成。这表明语言生成在极限下不同于传统统计学习理论中的分类任务(后者对有限并集封闭)。特别地,它意味着无法通过组合两个生成器获得更强大的新生成器,从而禁止了类似“提升”的机制。此外,我们的构造还回答了第三项开放问题:是否存在不满足最终无界闭包(EUC)条件的不可数非统一可生成类。方法基于精心设计的类结构与新颖的对角化论证,该技术本身可能对语言生成领域具有独立意义。

原文摘要 · Abstract (English)

We investigate language generation in the limit - a model by Kleinberg and Mullainathan [NeurIPS 2024] and extended by Li, Raman, and Tewari [COLT 2025]. While Kleinberg and Mullainathan proved generation is possible for all countable collections, Li et al. defined a hierarchy of generation notions (uniform, non-uniform, and generatable) and explored their feasibility for uncountable collections. Our first set of results resolve two open questions of Li et al. by proving finite unions of generatable or non-uniformly generatable classes need not be generatable. These follow from a stronger result: there is a non-uniformly generatable class and a uniformly generatable class whose union is non-generatable. This adds to the aspects along which language generation in the limit is different from traditional tasks in statistical learning theory like classification, which are closed under finite unions. In particular, it implies that given two generators for different collections, one cannot combine them to obtain a single "more powerful" generator, prohibiting this notion of boosting. Our construction also addresses a third open question of Li et al. on whether there are uncountable classes that are non-uniformly generatable and do not satisfy the eventually unbounded closure (EUC) condition introduced by Li, Raman, and Tewari. Our approach utilizes carefully constructed classes along with a novel diagonalization argument that could be of independent interest in the growing area of language generation.

语言生成理论分析可生成性对角化

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