Please use this identifier to cite or link to this item:
|Title:||Structural results about on-line learning models with and without queries|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 22, 2018
WEB OF SCIENCETM
checked on Jan 29, 2018
checked on Feb 19, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.