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. 
 Recurrent neural networks (RNNs) seem "unreasonably" effective at modeling patterns in noisy realworld sequences. In particular, they seem effective at recognizing grammatical structure in sequences, as evidenced by their ability to generate structured data, such as source code (C++, LaTeX, etc.) , with few syntactic grammatical errors BID9 . The ability of RNNs to recognize formal languages -sets of strings that possess rigorously defined grammatical structure -is less well-studied. Furthermore, there remains little systematic understanding of how RNNs recognize rigorous structure. We aim to explain this internal algorithm of RNNs through comparison to fundamental concepts in formal languages, namely, finite automata and regular languages.In this paper, we propose a new way of understanding how trained RNNs represent grammatical structure, by comparing them to finite automata that solve the same language recognition task. We ask: Can the internal knowledge representations of RNNs trained to recognize formal languages be easily mapped to the states of automata-theoretic models that are traditionally used to define these same formal languages? Specifically, we investigate this question for the class of regular languages, or formal languages accepted by finite automata (FA).In our experiments, RNNs are trained on a dataset of positive and negative examples of strings randomly generated from a given formal language. Next , we ask if there exists a decoding function: an isomorphism that maps the hidden states of the trained RNN to the states of a canonical FA. Since there exist infinitely many FA that accept the same language, we focus on the minimal deterministic finite automaton (MDFA) -the deterministic finite automaton (DFA) with the smallest possible number of states -that perfectly recognizes the language.Our experiments, spanning 500 regular languages, suggest that such a decoding function exists and can be understood in terms of a notion of abstraction that is fundamental in classical system theory. An abstraction A of a machine M (either finite-state, like an FA, or infinite-state, like a RNN) is a machine obtained by clustering some of the states of M into "superstates". Intuitively, an abstraction Figure 1: t-SNE plot (Left) of the hidden states of a RNN trained to recognize a regular language specified by a 6-state DFA (Right). Color denotes DFA state. The trained RNN has abstracted DFA states 1(green) and 2(blue) (each independently model the pattern [4-6] * ) into a single state.A loses some of the discerning power of the original machine M, and as such recognizes a superset of the language that M recognizes. We observe that the states of a RNN R, trained to recognize a regular language L, commonly exibit this abstraction behavior in practice. These states can be decoded into states of an abstraction A of the MDFA for the language, such that with high probability, A accepts any input string that is accepted by R. Figure 1 shows a t-SNE embedding BID13 of RNN states trained to perform language recognition on strings from the regex [(([4-6] {2}[4-6]+)?)3[4-6]+]. Although the MDFA has 6 states, we observe the RNN abstracting two states into one. Remarkably, a linear decoding function suffices to achieve maximal decoding accuracy: allowing nonlinearity in the decoder does not lead to significant gain. Also, we find the abstraction has low "coarseness", in the sense that only a few of the MDFA states need be clustered, and a qualitative analysis reveals that the abstractions often have simple interpretations. We have studied how RNNs trained to recognize regular formal languages represent knowledge in their hidden state. Specifically, we have asked if this internal representation can be decoded into canonical, minimal DFA that exactly recognizes the language, and can therefore be seen to be the "ground truth". We have shown that a linear function does a remarkably good job at performing such a decoding. Critically, however, this decoder maps states of the RNN not to MDFA states, but to states of an abstraction obtained by clustering small sets of MDFA states into "abstractions". 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.We see our work as a fundamental step in the larger effort to study how neural networks learn formal logical concepts. We intend to explore more complex and richer classes of formal languages, such as context-free languages and recursively enumerable languages, and their neural analogs.
Finite Automata Can be Linearly decoded from Language-Recognizing RNNs using low coarseness abstraction functions and high accuracy decoders. 
{"src": "scitldr-AIC_train", "paper_id": "H1zeHnA9KX"}