Please use this identifier to cite or link to this item:
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.
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
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.


checked on Apr 16, 2019


checked on Apr 16, 2019

Page view(s)

checked on Apr 8, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.