提出新等价关系，让语言模型可被高效学习为概率确定有限自动机。
Congruence-based Learning of Probabilistic Deterministic Finite Automata
- 基于概率分布的等价关系，扩展经典Myhill-Nerode定理。
- 设计主动学习算法，能正确识别规则语言模型的结构。
- 为大模型可解释性提供理论基础，适合形式化方法研究者。
本文研究从语言模型中学习概率确定有限自动机的问题。为此，分析了字符串代数结构上由概率分布等价与相似性定义的关系。引入一种新等价关系，扩展了经典Myhill-Nerode等价关系。该等价关系是定义语言模型正则性的基础。提出一种主动学习算法，当语言模型为正则时，可计算其关于该等价关系的商。论文还定义了语言模型的可识别性，并证明其与等价关系下的正则性一致。对于非等价关系，则不成立。最后讨论该结果对语言模型学习的影响。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。