Extracting Finite Automata from RNNs Using State Merging
This work addresses interpretability for RNN users by providing a method to extract discrete models, though it is incremental as it builds on existing state merging paradigms.
The authors tackled the problem of interpreting blackbox recurrent neural networks (RNNs) by proposing a new method to extract finite automata from them, inspired by state merging from grammatical inference. They demonstrated its effectiveness on the Tomita languages benchmark, extracting faithful automata from RNNs trained on all languages, with performance improved by more data and additional training epochs beyond convergence, which compresses the RNN's internal state space.
One way to interpret the behavior of a blackbox recurrent neural network (RNN) is to extract from it a more interpretable discrete computational model, like a finite state machine, that captures its behavior. In this work, we propose a new method for extracting finite automata from RNNs inspired by the state merging paradigm from grammatical inference. We demonstrate the effectiveness of our method on the Tomita languages benchmark, where we find that it is able to extract faithful automata from RNNs trained on all languages in the benchmark. We find that extraction performance is aided by the number of data provided during the extraction process, as well as, curiously, whether the RNN model is trained for additional epochs after perfectly learning its target language. We use our method to analyze this phenomenon, finding that training beyond convergence is useful because it leads to compression of the internal state space of the RNN. This finding demonstrates how our method can be used for interpretability and analysis of trained RNN models.