Congruence-based Learning of Probabilistic Deterministic Finite Automata
This provides a theoretical foundation for learning probabilistic automata from language models, which could benefit researchers in formal language theory and machine learning, though it appears incremental in extending classical concepts.
The paper tackles the problem of learning probabilistic deterministic finite automata from language models by introducing a new congruence that extends the classical Myhill-Nerode congruence, and presents an active learning algorithm that computes this quotient for regular language models. It shows that recognizability coincides with regularity for congruences but not for non-congruences.
This work studies the question of learning probabilistic deterministic automata from language models. For this purpose, it focuses on analyzing the relations defined on algebraic structures over strings by equivalences and similarities on probability distributions. We introduce a congruence that extends the classical Myhill-Nerode congruence for formal languages. This new congruence is the basis for defining regularity over language models. We present an active learning algorithm that computes the quotient with respect to this congruence whenever the language model is regular. The paper also defines the notion of recognizability for language models and shows that it coincides with regularity for congruences. For relations which are not congruences, it shows that this is not the case. Finally, it discusses the impact of this result on learning in the context of language models.