Lower Bounds on the Expressivity of Recurrent Neural Language Models
<|reference_start|>Lower Bounds on the Expressivity of Recurrent Neural Language Models: The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability. Describing their computational abilities through LMs' \emph{representational capacity} is a lively area of research. However, investigation into the representational capacity of neural LMs has predominantly focused on their ability to \emph{recognize} formal languages. For example, recurrent neural networks (RNNs) with Heaviside activations are tightly linked to regular languages, i.e., languages defined by finite-state automata (FSAs). Such results, however, fall short of describing the capabilities of RNN \emph{language models} (LMs), which are definitionally \emph{distributions} over strings. We take a fresh look at the representational capacity of RNN LMs by connecting them to \emph{probabilistic} FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.<|reference_end|>
@article{svete2024lower,
    title={Lower Bounds on the Expressivity of Recurrent Neural Language Models},
    author={Anej Svete, Franz Nowak, Anisha Mohamed Sahabdeen, Ryan Cotterell},
    journal={arXiv preprint arXiv:2405.19222},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19222},
    primaryClass={cs.CL}
}