Learning Deterministic Weighted Automata with Queries and Counterexamples
arXiv:1910.13895
Abstract
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.
Presented in NeurIPS 2019. Update: fix email address, add reference to github repo (available at https://github.com/tech-srl/weighted_lstar )
Cited by in corpus (6)
- Learning of Structurally Unambiguous Probabilistic Grammars
- Uncertainty Estimation and Calibration with Finite-State Probabilistic RNNs
- MEME: Generating RNN Model Explanations via Model Extraction
- Extracting Weighted Automata for Approximate Minimization in Language Modelling
- Optimal Approximate Minimization of One-Letter Weighted Finite Automata
- On the Complexity of Learning Description Logic Ontologies