The approximate minimization problem of weighted finite automata and applications to language modelling: an approach based on Adamyan-Arov-Krein theory
Clara Lacroce · eScholarship@McGill (McGill) · 2022
In this thesis, we leverage classical results from the theory of Hankel operators to tackle the approximate minimization problem and its applications to language modelling. In this context, we apply our analysis to weighted finite automata (WFAs) as well as black-box models on sequential data. Given one of these models, we are concerned with finding an approximately minimal realization of the language that it is computing. In particular, we want to construct a weighted finite automaton that fits within a given size constraint and mimics the behaviour of the original model while minimizing the approximation error. We reformulate the problem in terms of low-rank approximation of infinite Hankel matrices and apply Adamyan-Arov-Krein (AAK) approximation theory to solve it. We first solve the optimal spectral-norm approximate minimization problem for irredundant WFAs over a one-letter alphabet. We present a theoretical analysis based on AAK theory, and provide a closed-form solution, and an algorithm, to compute the optimal approximation of a given size in polynomial time. We then extend these results to black boxes trained for language modelling. We study the conditions under which AAK theory can be applied to find the optimal approximation of a black-box model, without accessing the training data. Moreover, we prove that the proposed method returns an asymptotically-optimal approximation and allows us to use the spectral norm to measure the distance between the black box and the WFA. Finally, we present a framework to apply noncommutative multivariable operator theory to the study of models defined over multi-letter alphabets. We highlight the main obstacles towards a generalization of AAK methods to the multi-letter setting and we conclude by providing possible directions for future work