How to use expert advice

Nicoló Cesa-Biancht, Yoav Freund, David P. Helmbol, David Haussled, Robert E. Schapire, Manfred K. Warmuth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

63 Scopus citations

Abstract

We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictions. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We give implications of this result on the performance of batch learning algorithms in a FAC setting which improve on the best results currently known in this context. We also extend our analysis to the case in which log loss is used instead of the expected number of mistakes.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages382-391
Number of pages10
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Externally publishedYes
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
CountryUnited States
CitySan Diego
Period5/16/935/18/93

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'How to use expert advice'. Together they form a unique fingerprint.

Cite this