Please use this identifier to cite or link to this item:
Title: Apple tasting
Authors: Helmbold, D.P.
Littlestone, N.
Long, P.M. 
Issue Date: 2000
Citation: Helmbold, D.P., Littlestone, N., Long, P.M. (2000). Apple tasting. Information and Computation 161 (2) : 85-139. ScholarBank@NUS Repository.
Abstract: In the standard on-line model the learning algorithm tries to minimize the total number of mistakes made in a series of trials. On each trial the learner sees an instance, makes a prediction of its classification, then finds out the correct classification. We define a natural variant of this model ("apple tasting") where • the classes are interpreted as the good and bad instances, • the prediction is interpreted as accepting or rejecting the instance, and • the learner gets feedback only when the instance is accepted. We use two transformations to relate the apple tasting model to an enhanced standard model where false acceptances are counted separately from false rejections. We apply our results to obtain a good general-purpose apple tasting algorithm as well as nearly optimal apple tasting algorithms for a variety of standard classes, such as conjunctions and disjunctions of n boolean variables. We also present and analyze a simpler transformation useful when the instances are drawn at random rather than selected by an adversary. © 2000 Academic Press.
Source Title: Information and Computation
ISSN: 08905401
DOI: 10.1006/inco.2000.2870
Appears in Collections:Staff Publications

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


checked on Feb 17, 2020


checked on Feb 17, 2020

Page view(s)

checked on Feb 5, 2020

Google ScholarTM



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