论文标题
关于实时计数器自动机的语言能力
On the Linguistic Capacity of Real-Time Counter Automata
论文作者
论文摘要
反机器已经与自然语言处理领域（NLP）实现了新发现的相关性：最近的工作表明，某些表现出色的复发性神经网络利用其记忆作为计数器。因此，了解这些网络成功的一种潜在方法是重新审视反计算理论。因此，我们将实时反机器的能力研究为正式的语法，重点是与NLP模型相关的正式属性。我们首先表明，计数器的几种变体会收敛以表达同一类的形式语言。我们还证明，根据补充，工会，十字路口和许多其他普通集合操作，反语言是关闭的。接下来，我们表明反机无法评估布尔表达式，即使它们可以微弱地验证其语法。这对神经网络系统的可解释性和评估具有影响：成功匹配句法模式并不能保证对抗记忆准确地编码组成语义。最后，我们考虑反语言是否是半线性的。这项工作为理解复发性神经网络具有潜在兴趣的正式语言理论做出了总体贡献。
Counter machines have achieved a newfound relevance to the field of natural language processing (NLP): recent work suggests some strong-performing recurrent neural networks utilize their memory as counters. Thus, one potential way to understand the success of these networks is to revisit the theory of counter computation. Therefore, we study the abilities of real-time counter machines as formal grammars, focusing on formal properties that are relevant for NLP models. We first show that several variants of the counter machine converge to express the same class of formal languages. We also prove that counter languages are closed under complement, union, intersection, and many other common set operations. Next, we show that counter machines cannot evaluate boolean expressions, even though they can weakly validate their syntax. This has implications for the interpretability and evaluation of neural network systems: successfully matching syntactic patterns does not guarantee that counter memory accurately encodes compositional semantics. Finally, we consider whether counter languages are semilinear. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
