Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1007614417594
Title: Structural results about on-line learning models with and without queries
Authors: Auer, P.
Long, P.M. 
Issue Date: 1999
Source: 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. https://doi.org/10.1023/A:1007614417594
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39266
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.

SCOPUSTM   
Citations

6
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

5
checked on Nov 3, 2017

Page view(s)

43
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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