mlsanityData to 14 Oct 2026

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

arXiv 1904.02931 ↗First posted 5 Apr 2019cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

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

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). First posted on arXiv 5 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 4; 2024: 8; 2025: 1; 2026: 3.

21 papers.

Sort:

  1. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  2. 2023Verifying Generalization in Deep Learningcited by 11
  3. 2022Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languagescited by 10
  4. 2024On the Tractability of SHAP Explanations under Markovian Distributionscited by 10
  5. 2023Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Taskscited by 7
  6. 2023DeepSeer: Interactive RNN Explanation and Debugging via State Abstractioncited by 6
  7. 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
  8. 2021Extracting Weighted Automata for Approximate Minimization in Language Modellingcited by 3
  9. 2024Verifying the Generalization of Deep Learning to Out-of-Distribution Domainscited by 2
  10. 2022Extracting Rules from Neural Networks with Partial Interpretationscited by 1
  11. 2022When are Local Queries Useful for Robust Learning?cited by 1
  12. 2024Automata Extraction from Transformerscited by 1
9 more
  1. 2024An L^* Algorithm for Deterministic Weighted Regular Languagescited by 1
  2. 2025Extracting Robust Register Automata from Neural Networks over Data Sequencescited by 1
  3. 2026Warm Starting State-Space Models with Automata Learningcited by 1
  4. 2021A Passive Online Technique for Learning Hybrid Automata from Input/Output Tracescited by 0
  5. 2024DeepCover: Advancing RNN Test Coverage and Online Error Prediction using State Machine Extractioncited by 0
  6. 2024PDFA Distillation via String Probability Queriescited by 0
  7. 2024Learning Weighted Finite Automata over the Max-Plus Semiring and its Terminationcited by 0
  8. 2026Synthesis and Verification of Transformer Programs (Technical Report)cited by 0
  9. 2026From Transformers to Weighted Automata: Towards the Verification of Large Language Modelscited by 0