Please use this identifier to cite or link to this item:
https://doi.org/10.1006/inco.2000.3001
Title: | On a generalized notion of mistake bounds | Authors: | Jain, S. Sharma, A. |
Issue Date: | 2001 | Citation: | Jain, S., Sharma, A. (2001). On a generalized notion of mistake bounds. Information and Computation 166 (2) : 156-166. ScholarBank@NUS Repository. https://doi.org/10.1006/inco.2000.3001 | Abstract: | This paper proposes the use of constructive ordinals as mistake bounds in the on-line learning model. This approach elegantly generalizes the applicability of the on-line mistake bound model to learnabilily analysis of very expressive concept classes like pattern languages, unions of pattern languages, elementary formal systems, and minimal models of logic programs. The main result in the paper shows that the topological property of effective finite bounded thickness is a sufficient condition for on-line learnability with a certain ordinal mistake bound. An interesting characterization of the on-line learning model is shown in terms of the identification in the limit framework. It is established that the classes of languages learnable in the on-line model with a mistake bound of α are exactly the same as the classes of languages learnable in the limit from both positive and negative data by a Popperian, consistent learner with a mind change bound of α. This result nicely builds a bridge between the two models. © 2001 Academic Press. | Source Title: | Information and Computation | URI: | http://scholarbank.nus.edu.sg/handle/10635/39138 | ISSN: | 08905401 | DOI: | 10.1006/inco.2000.3001 |
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.