Apple tasting

In the standard on-line model the learning algorithm fries to minimize the total number of mistakes made in a series of trials. On each trial the lear ner 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 r ejections. We apply our results to obtain a good general-purpose apple tast ing algorithm as well as nearly optimal apple tasting algorithms for a vari ety of standard classes, such as conjunctions and disjunctions of n boolean variables, We also present and analyze a simpler transformation useful whe n the instances are drawn at random rather than selected by an adversary. ( C) 2000 Academic Press.