Weighted Automata Extraction from Recurrent Neural Networks via\n Regression on State Spaces

2019/04/05 by Takamasa Okudono, Okudono, Takamasa, Masaki Waga +5 · 1 citation
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1904.02931

openalex publication_date 2019/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a method to extract a weighted finite automaton (WFA) from a\nrecurrent neural network (RNN). Our algorithm is based on the WFA learning\nalgorithm by Balle and Mohri, which is in turn an extension of Angluin's\nclassic lstar algorithm. Our technical novelty is in the use of\n\regression methods for the so-called equivalence queries, thus\nexploiting the internal state space of an RNN to prioritize counterexample\ncandidates. This way we achieve a quantitative/weighted extension of the recent\nwork by Weiss, Goldberg and Yahav that extracts DFAs. We experimentally\nevaluate the accuracy, expressivity and efficiency of the extracted WFAs.\n

Cited by

• Extracting Robust Register Automata from Neural Networks over Data Sequences

Related

• Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples
• Learning Deterministic Weighted Automata with Queries and Counterexamples
• Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languages
• Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
• Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks