# Learning Deterministic Weighted Automata with Queries and Counterexamples

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

## Key facts

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

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

- [Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval](https://mlsanity.com/paper/2201.12431/) (2022)
- [Generative learning for nonlinear dynamics](https://mlsanity.com/paper/2311.04128/) (2023)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [Latent State Models of Training Dynamics](https://mlsanity.com/paper/2308.09543/) (2023)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languages](https://mlsanity.com/paper/2206.14621/) (2022)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks](https://mlsanity.com/paper/2306.14040/) (2023)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [LUNA: A Model-Based Universal Analysis Framework for Large Language Models](https://mlsanity.com/paper/2310.14211/) (2023)
- [Simulating Weighted Automata over Sequences and Trees with Transformers](https://mlsanity.com/paper/2403.09728/) (2024)
- [Extracting Weighted Automata for Approximate Minimization in Language Modelling](https://mlsanity.com/paper/2106.02965/) (2021)
- [Towards Efficient Active Learning of PDFA](https://mlsanity.com/paper/2206.09004/) (2022)
- [Extracting Moore Machines from Transformers using Queries and Counterexamples](https://mlsanity.com/paper/2410.06045/) (2024)
- [On the Complexity of Learning Description Logic Ontologies](https://mlsanity.com/paper/2103.13694/) (2021)
- [Learning of Structurally Unambiguous Probabilistic Grammars](https://mlsanity.com/paper/2203.09441/) (2022)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [An L^* Algorithm for Deterministic Weighted Regular Languages](https://mlsanity.com/paper/2411.06228/) (2024)
- [Epicure: Distilling Sequence Model Predictions into Patterns](https://mlsanity.com/paper/2308.08203/) (2023)
- [DeepCover: Advancing RNN Test Coverage and Online Error Prediction using State Machine Extraction](https://mlsanity.com/paper/2402.06966/) (2024)
- [PDFA Distillation via String Probability Queries](https://mlsanity.com/paper/2406.18328/) (2024)
- [Learning Quantitative Automata Modulo Theories](https://mlsanity.com/paper/2411.10601/) (2024)

## 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.