Picking the Best Expert from a Sequence

Ruth Bergman, Ronald L. Rivest
Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, PMLR R0:42-48, 1995.

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 this Paper

BibTeX
@InProceedings{pmlr-vR0-bergman95a, 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}, pages = {42--48}, year = {1995}, editor = {Fisher, Doug and Lenz, Hans-Joachim}, volume = {R0}, series = {Proceedings of Machine Learning Research}, month = {04--07 Jan}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/r0/bergman95a/bergman95a.pdf}, url = {https://proceedings.mlr.press/r0/bergman95a.html}, 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.}, note = {Reissued by PMLR on 01 May 2022.} }
Endnote
%0 Conference Paper %T Picking the Best Expert from a Sequence %A Ruth Bergman %A Ronald L. Rivest %B Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 1995 %E Doug Fisher %E Hans-Joachim Lenz %F pmlr-vR0-bergman95a %I PMLR %P 42--48 %U https://proceedings.mlr.press/r0/bergman95a.html %V R0 %X 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. %Z Reissued by PMLR on 01 May 2022.
APA
Bergman, R. & Rivest, R.L.. (1995). Picking the Best Expert from a Sequence. Pre-proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R0:42-48 Available from https://proceedings.mlr.press/r0/bergman95a.html. Reissued by PMLR on 01 May 2022.

Related Material