Apple tasting
| Autor: | Philip M. Long, David P. Helmbold, Nick Littlestone |
|---|---|
| Rok vydání: | 2000 |
| Předmět: |
Computer science
business.industry 0102 computer and information sciences 02 engineering and technology Machine learning computer.software_genre Variety (linguistics) 01 natural sciences Computer Science Applications Theoretical Computer Science Transformation (function) Computational Theory and Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Natural (music) 020201 artificial intelligence & image processing Artificial intelligence Wine tasting business computer Information Systems Standard model (cryptography) |
| Zdroj: | Information and Computation. 161:85-139 |
| ISSN: | 0890-5401 |
| DOI: | 10.1006/inco.2000.2870 |
| Popis: | In the standard on-line model the learning algorithm tries to minimizethe 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”) whereu• 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect