ONLINE PREDICTION AND CONVERSION STRATEGIES

We study the problem of deterministically predicting boolean values by combining the boolean predictions of several experts. Previous on-lin e algorithms for this problem predict with the weighted majority of th e experts' predictions. These algorithms give each expert an exponenti al weight beta(m) where beta is a constant in [0, 1) and m is the numb er of mistakes made by the expert in the past. We show that it is bett er to use sums of binomials as weights. In particular, we present a de terministic algorithm using binomial weights that has a better worst c ase mistake bound than the best deterministic algorithm using exponent ial weights. The binomial weights naturally arise from a version space argument. We also show how both exponential and binomial weighting sc hemes can be used to make prediction algorithms robust against noise.