D. P. Helmbold, N. Littlestone
and P. M. Long.
Apple tasting. Information and
Computation, 161(2):85-139, 2000.
(Available in Postscript and PDF formats.)
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.