.png){kind=icon}
返回
Learning DFA from simple examples
.png){kind=icon}
OA
AI
DOI：10.1023/A:1010822518073.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt has posed the following open research problem: Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution ? (Pitt, in Lecture Notes in Artificial Intelligence, 397, pp. 18-44, Springer-Verlag, 1989). We demonstrate that the class of DFA whose canonical representations have logarithmic Kolmogorov complexity is efficiently PAC learnable under the Solomonoff Levin universal distribution (m). We prove that the class of DFA is efficiently learnable under the PACS (PAC learning with simple examples) model (Denis, D'Halluin & Gilleron, STACS'96-Proceedings of the 13th Annual Symposium on the Theoretical Aspects of Computer Science, pp. 231-242, 1996) wherein positive and negative examples are sampled according to the universal distribution conditional on a description of the target concept. Further, we show that any concept that is learnable under Gold's model of learning from characteristic samples, Goldman and Mathias' polynomial teachability model, and the model of learning from example based queries is also learnable under the PACS model.
Keyword:
DFA inference
exact identification
characteristic sets
PAC learning
collusion
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
