语言生成在理论上可行，但实际学习所需样本量可能超出现实承受能力。
Language Generation: Complexity Barriers and Implications for Learning
- 研究不同语言类别的生成样本复杂度，揭示学习可行性边界。
- 即使对简单语言如正则语言，也需极大量样本才能保证生成正确。
- 适合关注语言学习理论与数据效率的研究者阅读。
Kleinberg和Mullainathan指出，在可计算性层面，只要拥有足够多的正例，学习者最终能生成与目标语言无法区分的数据。然而，这类存在性结论未涉及实际可行性。本文研究了几类典型形式语言在极限情况下的语言生成样本复杂度。结果表明，对于上下文无关语言和正则语言，不可行性已显现，并持续存在于更严格的子类（如局部阈值可判定语言）以及不相交类（如非擦除模式语言，该类在语言识别理论中被广泛研究）。总体而言，本研究明确建立了语言生成在极限情况下理论可能性与实际计算可行性之间的鸿沟。
原文摘要 · Abstract (English)
Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually generate data indistinguishable from a target language. However, such existence results do not address feasibility. We study the sample complexity of language generation in the limit for several canonical classes of formal languages. Our results show that infeasibility already appears for context-free and regular languages, and persists even for strict subclasses such as locally threshold testable languages, as well as for incomparable classes such as non-erasing pattern languages, a well-studied class in the theory of language identification. Overall, our results establish a clear gap between the theoretical possibility of language generation in the limit and its computational feasibility.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。