Congruence-based Learning of Probabilistic Deterministic Finite Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916520585592832 |
|---|---|
| author | Carrasco, Matías Mayr, Franz Yovine, Sergio |
| author_facet | Carrasco, Matías Mayr, Franz Yovine, Sergio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09760 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Congruence-based Learning of Probabilistic Deterministic Finite Automata Carrasco, Matías Mayr, Franz Yovine, Sergio Formal Languages and Automata Theory Artificial Intelligence 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. |
| title | Congruence-based Learning of Probabilistic Deterministic Finite Automata |
| topic | Formal Languages and Automata Theory Artificial Intelligence |
| url | https://arxiv.org/abs/2412.09760 |