Learning Deterministic Weighted Automata with Queries and Counterexamples
This work addresses the need for interpretable and reliable automata extraction from neural networks, though it is incremental as it adapts existing learning algorithms to a probabilistic setting.
The authors tackled the problem of extracting probabilistic deterministic finite automata (PDFAs) from black-box language models like RNNs, achieving better word error rate (WER) and normalized distributed cumulative gain (NDCG) compared to spectral extraction methods.
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.