Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples

Abstract

We present a novel algorithm that uses exact learning and abstraction to extract a deterministic finite automaton describing the state dynamics of a given trained RNN. We do this using Angluin's L* algorithm as a learner and the trained RNN as an oracle. Our technique efficiently extracts accurate automata from trained RNNs, even when the state vectors are large and require fine differentiation.

arXiv commentAccepted in ICML 2018, (Feb 2020: added link to code, at https://github.com/tech-srl/lstar_extraction )

References in corpus (3)

• Scikit-learn: Machine Learning in Python
• Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
• Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples

Cited by in corpus (28)

• Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples
• Memorize or generalize? Searching for a compositional RNN in a haystack
• A Survey of Safety and Trustworthiness of Deep Neural Networks: Verification, Testing, Adversarial Attack and Defence, and Interpretability
• Using Machine Learning Safely in Automotive Software: An Assessment and Adaption of Software Process Requirements in ISO 26262
• DeepCruiser: Automated Guided Testing for Stateful Deep Learning Systems
• Discovering the Compositional Structure of Vector Representations with Role Learning Networks
• Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning
• Compositionality decomposed: how do neural networks generalise?
• Verification of Recurrent Neural Networks Through Rule Extraction
• A Comparative Study of Rule Extraction for Recurrent Neural Networks
• Stability of Internal States in Recurrent Neural Networks Trained on Regular Languages
• Overestimation of Syntactic Representationin Neural Language Models
• Explainable Goal-Driven Agents and Robots -- A Comprehensive Review
• DeepSeer: Interactive RNN Explanation and Debugging via State Abstraction
• The Complexity of Aggregates over Extractions by Regular Expressions
• Learning Graph Structure With A Finite-State Automaton Layer
• Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results
• Extracting Rules from Neural Networks with Partial Interpretations
• Query Learning Algorithm for Residual Symbolic Finite Automata
• Weight Annotation in Information Extraction
• Towards Interpreting Recurrent Neural Networks through Probabilistic Abstraction
• Analyzing Robustness of Angluin's L${}^{\ast }$ Algorithm in Presence of Noise
• Tensor Product Representations of Subregular Formal Languages
• Evaluating Syntactic Properties of Seq2seq Output with a Broad Coverage HPSG: A Case Study on Machine Translation
• Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack
• NNSynth: Neural Network Guided Abstraction-Based Controller Synthesis for Stochastic Systems
• Shapley Homology: Topological Analysis of Sample Influence for Neural Networks