Please use this identifier to cite or link to this item:
Title: Structural results about on-line learning models with and without queries
Authors: Auer, P.
Long, P.M. 
Issue Date: 1999
Citation: Auer, P., Long, P.M. (1999). Structural results about on-line learning models with and without queries. Machine Learning 36 (3) : 147-181. ScholarBank@NUS Repository.
Abstract: We solve an open problem of Maass and Turan, showing that the optimal mistake-bound when learning a given concept class without membership queries is within a constant factor of the optimal number of mistakes plus membership queries required by an algorithm that can ask membership queries. Previously known results imply that the constant factor in our bound is best possible. We then show that, in a natural generalization of the mistake-bound model, the usefulness to the learner of arbitrary `yes-no' questions between trials is very limited. We show that several natural structural questions about relatives of the mistake-bound model can be answered through the application of this general result. Most of these results can be interpreted as saying that learning in apparently less powerful (and more realistic) models is not much more difficult than learning in more powerful models.
Source Title: Machine Learning
ISSN: 08856125
DOI: 10.1023/A:1007614417594
Appears in Collections:Staff Publications

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


checked on Feb 19, 2020


checked on Feb 19, 2020

Page view(s)

checked on Feb 19, 2020

Google ScholarTM



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