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
Source: 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.

SCOPUSTM   
Citations

1
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 2, 2017

Page view(s)

73
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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