Co-Learning of Recursive Languages from Positive Data
Co-Learning of Recursive Languages from Positive Data
复制标题
从实证数据中共同学习递归语言
DOI：
10.1007/3-540-62064-8_12
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Zeugmann
中科院分区：
文献类型：
--
作者：
R. Freivalds;T. Zeugmann
The present paper deals with the co-learnability of enumerable familiesLof uniformly recursive languages from positive data. This refers to the following scenario. A familyLof target languages as well as hypothesis space for it are specified. The co-learner is fed eventually all positive examples of an unknown target languageLchosen fromL. The target languageLis successfully co-learned iff the co-learner can definitely delete all but one possible hypotheses, and the remaining one has to correctly describeL.The capabilities of co-learning are investigated in dependence on the choice of the hypothesis space, and compared to language learning in the limit, conservative learning and finite learning from positive data.Class preservinglearning (Lhas to be co-learned with respect to some suitably chosen enumeration of all and only the languages fromL),class comprisinglearning (Lhas to be co-learned with respect to some hypothesis space containing at least all the languages fromL), andabsolute co-learning(Lhas to be co-learned with respect to all class preserving hypothesis spaces forL) are distinguished.Our results are manyfold. First, it is shown that co-learning is exactly as powerful as learning in the limit provided the hypothesis space is appropriately chosen. However, while learning in the limit is insensitive to the particular choice of the hypothesis space, the power of co-learning crucially depends on it. Therefore the properties a hypothesis space should have in order to be suitable for co-learning are studied. Finally, a sufficient conditions for absolute co-learnability is derived, and it is separated from finite learning.
