用强化学习方法推断确定性有限自动机，实现数据驱动的符号模型构建。
Inference of Deterministic Finite Automata via Q-Learning
- 将Q-learning的值函数映射为自动机转移函数
- 在多个示例上验证了该方法可成功推断出目标自动机
- 为机器学习与符号系统融合提供新思路，适合对自动机学习感兴趣的读者
传统确定性有限自动机（DFA）推断方法源于符号人工智能，包括主动学习（如Angluin的L*算法及其变体）和被动技术（如Biermann and Feldman的方法、RPNI）。与此同时，子符号人工智能，特别是机器学习，提供了从数据中学习的替代范式，如监督学习、无监督学习和强化学习（RL）。本文研究了著名的强化学习算法Q-learning在被动推断确定性有限自动机中的应用。核心思想是：学习到的Q函数（将状态-动作对映射到奖励）可被重新解释为在有限域上的DFA转移函数，从而建立了子符号学习与符号表示之间的新桥梁。论文展示了如何将Q-learning适配于自动机推断，并在多个例子上进行了评估。
原文摘要 · Abstract (English)
Traditional approaches to inference of deterministic finite-state automata (DFA) stem from symbolic AI, including both active learning methods (e.g., Angluin's L* algorithm and its variants) and passive techniques (e.g., Biermann and Feldman's method, RPNI). Meanwhile, sub-symbolic AI, particularly machine learning, offers alternative paradigms for learning from data, such as supervised, unsupervised, and reinforcement learning (RL). This paper investigates the use of Q-learning, a well-known reinforcement learning algorithm, for the passive inference of deterministic finite automata. It builds on the core insight that the learned Q-function, which maps state-action pairs to rewards, can be reinterpreted as the transition function of a DFA over a finite domain. This provides a novel bridge between sub-symbolic learning and symbolic representations. The paper demonstrates how Q-learning can be adapted for automaton inference and provides an evaluation on several examples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。