An L * Algorithm for Deterministic Weighted Regular Languages (2024)

Abstract: Extracting finite state automata (FSAs) fromblack-box models offers a powerful approachto gaining interpretable insights into complexmodel behaviors. To support this pursuit, wepresent a weighted variant of Angluin’s (1987)L* algorithm for learning FSAs. We stay faithful to the original formulation, devising a wayto exactly learn deterministic weighted FSAswhose weights support division. Furthermore,we formulate the learning process in a mannerthat highlights the connection with FSA minimization, showing how L* directly learns aminimal automaton for the target language.

## introduction learning formal languages from data is a classic problem in computer science. unfortunately, learning only from positive examples is impossible @xcite . by granting the learner access to more than just positive examples, @xcite introduced the active learning scheme l ˚, where the learner interacts with an oracle by asking it queries. concretely, @xcite l ˚algorithm learns regular languages in the form of deterministic finite-state automata (dfsas) from membership queries (analogous to asking for a ground truth label of a string in the training dataset) and equivalence queries (analogous to asking whether a hypothesis is correct). weighted formal languages, where strings are assigned weights such as probabilities or costs, naturally generalize membership-based (boolean) formal languages. weighted languages, especially probabilistic languages, serve as a cornerstone in the conceptual framework of many nlp problems @xcite . their significance is twofold: first, in practical applications, where they underpin algorithms for tasks such as parsing @xcite and machine translation @xcite , and second, as an analytical framework for better understanding modern language models @xcite @xcite . this has motivated the development of various weighted extensions of @xcite l ˚algorithm. for instance, @xcite describes a generalization that (approximately) learns a probabilistic dfsa by querying a neural language model to interpret it. less faithfully to the original l ˚algorithm, multiple algorithms for learning non-deterministic weighted fsas have been proposed @xcite @xcite @xcite . these algorithms involve the solution of a linear system of equations, and therefore they cannot be used when the underlying algebraic structure lacks subtraction. we present a novel weighted generalization of the l ˚algorithm that learns semifieldweighted deterministic fsas. in contrast to other algorithms inspired by l ˚, ours is a more faithful generalization of the original learning scheme. we generalize @xcite original algorithm, resulting in a familiar procedure that, just like the original, learns a dfsa exactly in a finite number of steps if the automaton can be determinized. foot_0 additionally, we loosen the requirement for field-weighted fsas; our algorithm works for semifield-weighted fsa. our exposition further illuminates the connection between weighted minimization @xcite and l ˚. ## a weighted l ˚algorithm like @xcite , we assume we have access to an oracle that answers the following queries about a deterministic regular language l ‹ : σ ˚ñ k: at a high level, the algorithm iteratively constructs empirical hankel systems of increasing dimensions that capture observed patterns of the target language l ‹ . once sufficient observations are accumulated, the automaton derived from these hankel systems will generate exactly l ‹ . ## conclusion we introduce a weighted l ˚algorithm, an oraclebased algorithm for learning weighted regular languages, building upon the paradigm pioneered by @xcite . while similar methods have been proposed before, our method is novel in that it learns an exact deterministic wfsa, akin to the original @xcite unweighted version.