2024/12/12 by Matías Carrasco, Carrasco, Matías, Franz Mayr +3
Computer Science · #Machine Learning and Algorithms #semigroups and automata theory #Formal Methods in Verification
paper · pdf · doi:10.48550/arxiv.2412.09760
This work studies the question of learning probabilistic deterministic\nautomata from language models. For this purpose, it focuses on analyzing the\nrelations defined on algebraic structures over strings by equivalences and\nsimilarities on probability distributions. We introduce a congruence that\nextends the classical Myhill-Nerode congruence for formal languages. This new\ncongruence is the basis for defining regularity over language models. We\npresent an active learning algorithm that computes the quotient with respect to\nthis congruence whenever the language model is regular. The paper also defines\nthe notion of recognizability for language models and shows that it coincides\nwith regularity for congruences. For relations which are not congruences, it\nshows that this is not the case. Finally, it discusses the impact of this\nresult on learning in the context of language models.\n