Picking the Best Expert from a Sequence
Abstract
We examine the problem of finding a good expert from a sequence of experts. Each expert has an "error rate"; we wish to find an expert with a low error rate. However, each expert’s error rate is unknown and can only be estimated by a sequence of experimental trials. Moreover, the distribution of error rates is also unknown. Given a bound on the total number of trials, there is thus a tradeoff between the number of experts examined and the accuracy of estimating their error rates. We present a new expert-finding algorithm and prove an upper bound on the expected error rate of the expert found. A second approach, based on the sequential ratio test, gives another expert-finding algorithm that is not provably better but which performs better in our empirical studies.
Cite
Text
Bergman and Rivest. "Picking the Best Expert from a Sequence." Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, 1995.Markdown
[Bergman and Rivest. "Picking the Best Expert from a Sequence." Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, 1995.](https://mlanthology.org/aistats/1995/bergman1995aistats-picking/)BibTeX
@inproceedings{bergman1995aistats-picking,
title = {{Picking the Best Expert from a Sequence}},
author = {Bergman, Ruth and Rivest, Ronald L.},
booktitle = {Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics},
year = {1995},
pages = {42-48},
volume = {R0},
url = {https://mlanthology.org/aistats/1995/bergman1995aistats-picking/}
}