Learning Deterministic Weighted Automata with Queries and Counterexamples

October 30, 2019 · Entered Twilight · 🏛 Neural Information Processing Systems

"Last commit was 6.0 years ago (≥5 year threshold)"

Evidence collected by the PWNC Scanner

Repo contents: Hankel.py, Helper_Functions.py, KDTree.py, LanguageModel.py, Learner.py, NGram.py, PDFA.py, README.md, RNNTokenPredictor.py, SpectralReconstruction.py, WFA.py, example_spice_data, full_example.py, our_grammars.py, spice_ndcg.py

Authors Gail Weiss, Yoav Goldberg, Eran Yahav arXiv ID 1910.13895 Category cs.LG: Machine Learning Cross-listed cs.FL, stat.ML Citations 48 Venue Neural Information Processing Systems Repository https://github.com/tech-srl/weighted_lstar ⭐ 18 Last Checked 1 month ago

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.