Representing Formal Languages: A Comparison Between Finite Automata and Recurrent Neural Networks
Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Richard G. Baraniuk, Swarat Chaudhuri, Ankit B. Patel
Abstract
We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an {\em abstraction} obtained by clustering small sets of MDFA states into ``''superstates''. A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.
BibTeX
@inproceedings{
michalenko2018finite,
title={Finite Automata Can be Linearly Decoded from Language-Recognizing {RNN}s},
author={Joshua J. Michalenko and Ameesh Shah and Abhinav Verma and Swarat Chaudhuri and Ankit B. Patel},
booktitle={International Conference on Learning Representations},
year={2019},
url={https://openreview.net/forum?id=H1zeHnA9KX},
}