Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40510
Title: On a generalized notion of mistake bounds
Authors: Jain, Sanjay 
Sharma, Arun
Issue Date: 1999
Source: Jain, Sanjay,Sharma, Arun (1999). On a generalized notion of mistake bounds. Proceedings of the Annual ACM Conference on Computational Learning Theory : 249-256. ScholarBank@NUS Repository.
Abstract: The present 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 learnability 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.
Source Title: Proceedings of the Annual ACM Conference on Computational Learning Theory
URI: http://scholarbank.nus.edu.sg/handle/10635/40510
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

52
checked on Dec 9, 2017

Google ScholarTM

Check


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