Please use this identifier to cite or link to this item:
https://doi.org/10.1007/978-3-540-87987-9_30
Title: | Iterative learning of simple external contextual languages | Authors: | Becerra-Bonache, L. Case, J. Jain, S. Stephan, F. |
Issue Date: | 2008 | Citation: | Becerra-Bonache, L.,Case, J.,Jain, S.,Stephan, F. (2008). Iterative learning of simple external contextual languages. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5254 LNAI : 359-373. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-87987-9_30 | Abstract: | It is investigated for which choice of a parameter q, denoting the number of contexts, the class of simple external contextual languages is iteratively learnable. On one hand, the class admits, for all values of q, polynomial time learnability provided an adequate choice of the hypothesis space is given. On the other hand, additional constraints like consistency and conservativeness or the use of a one-one hypothesis space changes the picture - iterative learning limits the long term memory of the learner to the current hypothesis and these constraints further hinder storage of information via padding of this hypothesis. It is shown that if q∈>∈3, then simple external contextual languages are not iteratively learnable using a class preserving one-one hypothesis space, while for q∈=∈1 it is iteratively learnable, even in polynomial time. For the intermediate levels, there is some indication that iterative learnability using a class preserving one-one hypothesis space might depend on the size of the alphabet. It is also investigated for which choice of the parameters, the simple external contextual languages can be learnt by a consistent and conservative iterative learner. © 2008 Springer-Verlag Berlin Heidelberg. | Source Title: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | URI: | http://scholarbank.nus.edu.sg/handle/10635/40733 | ISSN: | 03029743 | DOI: | 10.1007/978-3-540-87987-9_30 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.