On Efficiently Representing Regular Languages as RNNs
OPEN ACCESS
Loading...
Author / Producer
Date
2024-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Recent work by Hewitt et al. (2020) provides an interpretation of the empirical success of recurrent neural networks (RNNs) as language models (LMs). It shows that RNNs can efficiently represent bounded hierarchical structures that are prevalent in human language. This suggests that RNNs' success might be linked to their ability to model hierarchy. However, a closer inspection of Hewitt et al.'s (2020) construction shows that it is not inherently limited to hierarchical structures. This poses a natural question: What other classes of LMs RNNs can efficiently represent? To this end, we generalize Hewitt et al.'s (2020) construction and show that RNNs can efficiently represent a larger class of LMs than previously claimed-specifically, those that can be represented by a pushdown automaton with a bounded stack and a specific stack update function. Altogether, the efficiency of representing this diverse class of LMs with RNN LMs suggests novel interpretations of their inductive bias.
Permanent link
Publication status
published
Book title
Findings of the Association for Computational Linguistics: ACL 2024
Journal / series
Volume
Pages / Article No.
4118 - 4135
Publisher
Association for Computational Linguistics
Event
62nd Annual Meeting of the Association for Computational Linguistics (ACL 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
Notes
Funding
204667 - The Forgotten Role of Inductive Bias in Interpretability Research in NLP (SNF)
Related publications and datasets
Is supplemented by: https://github.com/rycolab/bpdas