揭示循环语言模型的表达能力差异根源，统一分析其数学本质
An Algebraic View of the Expressivity of Recurrent Language Models
- 从代数角度统一分析不同计算模型对循环网络表达能力的影响
- 浮点数约束下无法实现模偶数计数器，整数量化下可实现所有模偶数计数器
- 为理解神经语言模型的计算极限提供新视角，适合理论研究者
循环神经语言模型能识别哪些形式语言？文献中的结论存在冲突：部分研究声称其具备图灵完备性，另一些则认为其等价于正则语言。根本原因在于底层算术模型不同。本文建立统一的代数框架，从形式化算术模型出发，将表达能力问题转化为代数问题，例如网络的句法幺半群是否整除某个拟积。以对角状态空间模型为例，同一架构在浮点递归约束下无法实现模偶数计数器，但在无符号整数量化下可实现所有模偶数计数器。
原文摘要 · Abstract (English)
What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。