Learning Regular Languages from Simple Positive Examples
作者:François Denis
摘要
Learning from positive data constitutes an important topic in Grammatical Inference since it is believed that the acquisition of grammar by children only needs syntactically correct (i.e. positive) instances. However, classical learning models provide no way to avoid the problem of overgeneralization. In order to overcome this problem, we use here a learning model from simple examples, where the notion of simplicity is defined with the help of Kolmogorov complexity. We show that a general and natural heuristic which allows learning from simple positive examples can be developed in this model. Our main result is that the class of regular languages is probably exactly learnable from simple positive examples.
论文关键词:grammatical inference, PAC learning, Kolmogorov complexity, regular languages, deterministic finite automata
论文评审过程:
论文官网地址:https://doi.org/10.1023/A:1010826628977