NIPS Proceedingsβ

Learning Deterministic Weighted Automata with Queries and Counterexamples

Part of: Advances in Neural Information Processing Systems 32 (NIPS 2019)

[PDF] [BibTeX] [Supplemental] [Reviews] [Author Feedback] [Meta Review] [Sourcecode]


Conference Event Type: Poster


We present an algorithm for reconstruction 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 work in a probabilistic setting under noise. The key insight of the adaptation is the use of conditional probabilities when making observations on the model, and the introduction of a variation tolerance when comparing observations. When applied to RNNs, our algorithm returns models with better or equal word error rate (WER) and normalised distributed cumulative gain (NDCG) than achieved by n-gram or weighted finite automata (WFA) approximations of the same networks. The PDFAs capture a richer class of languages than n-grams, and are guaranteed to be stochastic and deterministic -- unlike the WFAs.