Extracting Weighted Automata for Approximate Minimization in Language
  Modelling
  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.
