# Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network

arXiv: https://arxiv.org/abs/2402.02627 · HTML: https://mlsanity.com/paper/2402.02627/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 4 Feb 2024.

## Builds on (most cited first, 22 of 22)

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [An Empirical Study on Learning Bug-Fixing Patches in the Wild via Neural Machine Translation](https://mlsanity.com/paper/1812.08693/) (2018)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [RNNs can generate bounded hierarchical languages with optimal memory](https://mlsanity.com/paper/2010.07515/) (2020)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [On Learning Meaningful Code Changes via Neural Machine Translation](https://mlsanity.com/paper/1901.09102/) (2019)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)
- [An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks](https://mlsanity.com/paper/1709.10380/) (2017)
- [On the Linguistic Capacity of Real-Time Counter Automata](https://mlsanity.com/paper/2004.06866/) (2020)
- [Evaluating the Ability of LSTMs to Learn Context-Free Grammars](https://mlsanity.com/paper/1811.02611/) (2018)
- [On Multiplicative Integration with Recurrent Neural Networks](https://mlsanity.com/paper/1606.06630/) (2016)
- [Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning](https://mlsanity.com/paper/1807.01406/) (2018)
- [On the Ability and Limitations of Transformers to Recognize Formal Languages](https://mlsanity.com/paper/2009.11264/) (2020)
- [State-Regularized Recurrent Neural Networks](https://mlsanity.com/paper/1901.08817/) (2019)
- [The Neural State Pushdown Automata](https://mlsanity.com/paper/1909.05233/) (2019)
- [On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks](https://mlsanity.com/paper/2309.14691/) (2023)
- [A provably stable neural network Turing Machine](https://mlsanity.com/paper/2006.03651/) (2020)
- [Neural Guided Constraint Logic Programming for Program Synthesis](https://mlsanity.com/paper/1809.02840/) (2018)
- [Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack](https://mlsanity.com/paper/2004.07623/) (2020)

## Built on by (most cited first, 3 of 3)

- [Investigating Symbolic Capabilities of Large Language Models](https://mlsanity.com/paper/2405.13209/) (2024)
- [Tight Stability, Convergence, and Robustness Bounds for Predictive Coding Networks](https://mlsanity.com/paper/2410.04708/) (2024)
- [Precision, Stability, and Generalization: A Comprehensive Assessment of RNNs learnability capability for Classifying Counter and Dyck Languages](https://mlsanity.com/paper/2410.03118/) (2024)

## Abstract (arXiv)

This paper analyzes two competing rule extraction methodologies: quantization and equivalence query. We trained 3600 RNN models, extracting 18000 DFA with a quantization approach (k-means and SOM) and 3600 DFA by equivalence query(L*) methods across 10 initialization seeds. We sampled the datasets from 7 Tomita and 4 Dyck grammars and trained them on 4 RNN cells: LSTM, GRU, O2RNN, and MIRNN. The observations from our experiments establish the superior performance of O2RNN and quantization-based rule extraction over others. L*, primarily proposed for regular grammars, performs similarly to quantization methods for Tomita languages when neural networks are perfectly trained. However, for partially trained RNNs, L* shows instability in the number of states in DFA, e.g., for Tomita 5 and Tomita 6 languages, L* produced more than 100 states. In contrast, quantization methods result in rules with number of states very close to ground truth DFA. Among RNN cells, O2RNN produces stable DFA consistently compared to other cells. For Dyck Languages, we observe that although GRU outperforms other RNNs in network performance, the DFA extracted by O2RNN has higher performance and better stability. The stability is computed as the standard deviation of accuracy on test sets on networks trained across 10 seeds. On Dyck Languages, quantization methods outperformed L* with better stability in accuracy and the number of states. L* often showed instability in accuracy in the order of 16% - 22% for GRU and MIRNN while deviation for quantization methods varied in 5% - 15%. In many instances with LSTM and GRU, DFA's extracted by L* even failed to beat chance accuracy (50%), while those extracted by quantization method had standard deviation in the 7%-17% range. For O2RNN, both rule extraction methods had deviation in the 0.5% - 3% range.