REPRESENTING FORMAL LANGUAGES: A COMPARISON BETWEEN FINITE AUTOMATA AND RECURRENT NEURAL NETWORKS
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 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.
Paper Summary -
The authors trained RNNs to recognize formal languages defined by random regular expressions, then measured the accuracy of decoders that predict states of the minimal deterministic finite automata (MDFA) from the RNN hidden states. They then perform a greedy search over partitions of the set of MDFA states to find the groups of states which, when merged into a single decoder target, maximize prediction accuracy. For both the MDFA and the merged classes prediction problems, linear decoders perform as well as non-linear decoders.
Clarity - The paper is very clear, both in its prose and maths.
Originality - I don't know of any prior work that approaches the relationship between RNNs and automata in quite this way.
Quality/Significance - I have one major concern about the interpretation of the experiments in this paper.
The paper seems to express the following logic:
1 - linear (and non-linear) decoders aren't so good at predicting MDFA states from RNN hidden states
2 - if we make an "abstract" finite automata (FA) by merging states of the MDFA to optimize decoder performance, the linear (and non-linear) decoders are much better at predicting this new, smaller FA's states.
3 - thus, trained RNNs implement something like an abstract FA to recognize formal languages.
However, a more appropriate interpretation of these experiments seems to be:
1 - (same)
2 - if we find the output classes the decoder is most often confused between, then merge them into one class, the decoder's performance increases -- trivially. in other words, you just removed the hardest parts of the classification problem, so performance increased. note: performance also increases because there are fewer classes in the merged-state FA prediction problem (e.g., chance accuracy is higher).
3 - thus, from these experiments it's hard to say much about the relationship between trained RNNs and finite automata.
I see that the "accuracy" measurement for the merged-state FA prediction problem, \rho, is somewhat more complicated than I would have expected; e.g., it takes into account \delta and f(h_t) as well as f(h_{t+1}). Ultimately, this formulation still asks whether any state in the merged state-set that contains f(h) transitions under the MDFA to the any state in the merged state-set that contains f(h_{t+1}). As a result, as far as I can tell the basic logic of the interpretation I laid out still applies.
Perhaps I've missed something -- I'll look forward to the author response which may alleviate my concern.
Pros - very clearly written, understanding trained RNNs is an important topic
Cons - the basic logic of the conclusion may be flawed (will await author response)
Minor -
The regular expression in Figure 6 (Top) is for phone numbers instead of emails.
"Average linear decoding accuracy as a function of M in the MDFA" -- I don't think "M" was ever defined. From contexts it looks like it's the number of nodes in the MDFA.
"Average ratio of coarseness" -- It would be nice to be explicit about what the "ratio of coarseness" is. I'm guessing it's (number of nodes in MDFA)/(number of nodes in abstracted DFA).
What are the integers and percentages inside the circles in Figure 6?
Figures 4 and 5 are difficult to interpret because the same (or at least very similar) colors are used multiple times.
I don't see "a" (as in a_t in the equations on page 3) defined anywhere. I think it's meant to indicate a symbol in the alphabet \Sigma. Maybe I missed it.