ISSN:
0885-6125
Keywords:
On-line learning
;
conversion strategies
;
noise robustness
;
binomial weights
;
exponential weights
;
weighted majority algorithm
;
expert advice
;
mistake bounds
;
Ulam's game
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We study the problem of deterministically predicting boolean valuesby combining the boolean predictions of several experts.Previous on-line algorithms for this problem predict with the weightedmajority of the experts' predictions.These algorithms give each expert an exponential weight βmwhere β is a constant in [0,1) and m is the number of mistakesmade by the expert in the past. We show that it is better to usesums of binomials as weights.In particular, we present a deterministic algorithmusing binomial weights that has a better worst case mistake bound than thebest deterministic algorithm using exponential weights.The binomial weights naturally arise from a version space argument.We also show how both exponential and binomial weighting schemes can beused to make prediction algorithms robust against noise.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1018348209754
Permalink
