mlsanityData to 7 Oct 2026

Learning Deterministic Weighted Automata with Queries and Counterexamples

arXiv 1910.13895 ↗First posted 30 Oct 2019cs.LG cs.FL stat.MLcited by 22

Not on the map. Why?

Abstract (arXiv)

We present an algorithm for extraction of a probabilistic deterministic finite automaton (PDFA) from a given black-box language model, such as a recurrent neural network (RNN). The algorithm is a variant of the exact-learning algorithm L*, adapted to a probabilistic setting with noise. The key insight is the use of conditional probabilities for observations, and the introduction of a local tolerance when comparing them. When applied to RNNs, our algorithm often achieves better word error rate (WER) and normalised distributed cumulative gain (NDCG) than that achieved by spectral extraction of weighted finite automata (WFA) from the same networks. PDFAs are substantially more expressive than n-grams, and are guaranteed to be stochastic and deterministic - unlike spectrally extracted WFAs.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 5; 2023: 7; 2024: 7.

22 papers.

Sort:

  1. 2022Neuro-Symbolic Language Modeling with Automaton-augmented Retrievalcited by 60
  2. 2023Generative learning for nonlinear dynamicscited by 22
  3. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  4. 2023Latent State Models of Training Dynamicscited by 15
  5. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  6. 2022Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languagescited by 10
  7. 2024On the Tractability of SHAP Explanations under Markovian Distributionscited by 10
  8. 2023Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Taskscited by 7
  9. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  10. 2023LUNA: A Model-Based Universal Analysis Framework for Large Language Modelscited by 4
  11. 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
  12. 2021Extracting Weighted Automata for Approximate Minimization in Language Modellingcited by 3
10 more
  1. 2022Towards Efficient Active Learning of PDFAcited by 3
  2. 2024Extracting Moore Machines from Transformers using Queries and Counterexamplescited by 2
  3. 2021On the Complexity of Learning Description Logic Ontologiescited by 1
  4. 2022Learning of Structurally Unambiguous Probabilistic Grammarscited by 1
  5. 2022When are Local Queries Useful for Robust Learning?cited by 1
  6. 2024An L^* Algorithm for Deterministic Weighted Regular Languagescited by 1
  7. 2023Epicure: Distilling Sequence Model Predictions into Patternscited by 0
  8. 2024DeepCover: Advancing RNN Test Coverage and Online Error Prediction using State Machine Extractioncited by 0
  9. 2024PDFA Distillation via String Probability Queriescited by 0
  10. 2024Learning Quantitative Automata Modulo Theoriescited by 0