证明在预测下一个符号的设定下，正则语言仍难以学习。
Hardness of Learning Regular Languages in the Next Symbol Prediction Setting
- 用新符号预测设定分析语言学习，提供更丰富标签
- 在密码学假设下，学习确定有限自动机依然计算困难
- 适合研究语言模型可学习性与神经序列模型的学者
我们研究了在下一个符号预测（NSP）设置下的语言可学习性，其中学习者仅接收来自语言的正例，并对每个前缀提供：(i) 该前缀是否属于语言；(ii) 哪些后续符号能导致接受串。该设定被用于先前工作对神经序列模型的实证分析，此外我们观察到，高效的NSP算法可用于学习语言模型的（截断）支持集。我们形式化该设定以使其适用于帕累托-阿克曼（PAC）学习分析。尽管该设定比传统分类设置提供了更丰富的标签，但我们表明学习如确定有限自动机（DFAs）和布尔公式等概念类依然是计算上困难的。证明通过构造几乎使所有额外标签无信息量的实例，实现从传统学习问题到带有NSP标签学习问题的归约。在密码学假设下，该归约表明在NSP设定中学习DFAs是计算困难的。
原文摘要 · Abstract (English)
We study the learnability of languages in the Next Symbol Prediction (NSP) setting, where a learner receives only positive examples from a language together with, for every prefix, (i) whether the prefix itself is in the language and (ii) which next symbols can lead to an accepting string. This setting has been used in prior works to empirically analyze neural sequence models, and additionally, we observe that efficient algorithms for the NSP setting can be used to learn the (truncated) support of language models. We formalize the setting so as to make it amenable to PAC-learning analysis. While the setting provides a much richer set of labels than the conventional classification setting, we show that learning concept classes such as DFAs and Boolean formulas remains computationally hard. The proof is via a construction that makes almost all additional labels uninformative, yielding a reduction from the conventional learning problem to learning with NSP labels. Under cryptographic assumptions, the reduction implies that the problem of learning DFAs is computationally hard in the NSP setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。