# Extracting Weighted Automata for Approximate Minimization in Language Modelling

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 66 references that are in the map.
- First posted on arXiv 5 Jun 2021.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks](https://mlsanity.com/paper/1709.10380/) (2017)
- [Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces](https://mlsanity.com/paper/1904.02931/) (2019)
- [Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning](https://mlsanity.com/paper/1807.01406/) (2018)
- [Explaining Black Boxes on Sequential Data using Weighted Automata](https://mlsanity.com/paper/1810.05741/) (2018)
- [Approximating probabilistic models as weighted finite automata](https://mlsanity.com/paper/1905.08701/) (2019)
- [Distillation of Weighted Automata from Recurrent Neural Networks using a Spectral Approach](https://mlsanity.com/paper/2009.13101/) (2020)
- [Interpreting Finite Automata for Sequential Data](https://mlsanity.com/paper/1611.07100/) (2016)
- [Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results](https://mlsanity.com/paper/2004.00478/) (2020)

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

- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [Simulating Weighted Automata over Sequences and Trees with Transformers](https://mlsanity.com/paper/2403.09728/) (2024)

## Abstract (arXiv)

In this paper we study the approximate minimization problem for language modelling. We assume we are given some language model as a black box. The objective is to obtain a weighted finite automaton (WFA) that fits within a given size constraint and which mimics the behaviour of the original model while minimizing some notion of distance between the black box and the extracted WFA. We provide an algorithm for the approximate minimization of black boxes trained for language modelling of sequential data over a one-letter alphabet. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. This allows us to use the spectral norm to measure the distance between the black box and the WFA. We provide theoretical guarantees to study the potentially infinite-rank Hankel matrix of the black box, without accessing the training data, and we prove that our method returns an asymptotically-optimal approximation.