# Approximating probabilistic models as weighted finite automata

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2019.

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

- [Federated Learning Meets Natural Language Processing: A Survey](https://mlsanity.com/paper/2107.12603/) (2021)
- [Extracting Weighted Automata for Approximate Minimization in Language Modelling](https://mlsanity.com/paper/2106.02965/) (2021)
- [Understanding Robust Generalization in Learning Regular Languages](https://mlsanity.com/paper/2202.09717/) (2022)
- [VQ-T: RNN Transducers using Vector-Quantized Prediction Network States](https://mlsanity.com/paper/2208.01818/) (2022)
- [Markov Constraint as Large Language Model Surrogate](https://mlsanity.com/paper/2406.10269/) (2024)
- [Neural Search Space in Gboard Decoder](https://mlsanity.com/paper/2410.15575/) (2024)

## Abstract (arXiv)

Weighted finite automata (WFA) are often used to represent probabilistic models, such as n-gram language models, since they are efficient for recognition tasks in time and space. The probabilistic source to be represented as a WFA, however, may come in many forms. Given a generic probabilistic model over sequences, we propose an algorithm to approximate it as a weighted finite automaton such that the Kullback-Leiber divergence between the source model and the WFA target model is minimized. The proposed algorithm involves a counting step and a difference of convex optimization step, both of which can be performed efficiently. We demonstrate the usefulness of our approach on various tasks, including distilling n-gram models from neural models, building compact language models, and building open-vocabulary character models. The algorithms used for these experiments are available in an open-source software library.