Please use this identifier to cite or link to this item: https://doi.org/10.1006/inco.2000.2870
Title: Apple tasting
Authors: Helmbold, D.P.
Littlestone, N.
Long, P.M. 
Issue Date: 2000
Source: Helmbold, D.P.,Littlestone, N.,Long, P.M. (2000). Apple tasting. Information and Computation 161 (2) : 85-139. ScholarBank@NUS Repository. https://doi.org/10.1006/inco.2000.2870
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39219
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.

SCOPUSTM   
Citations

20
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

11
checked on Nov 3, 2017

Page view(s)

62
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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