|
NeuroCOLT
Technical Report NC-TR-96-010
On-line Prediction
and Conversion Strategies
Nicolò
Cesa-Bianchi
DSI
Università di Milano
Yoav
Freund
AT&T Bell Laboratories
David
P. Helmbold
University of California Santa Cruz
Manfred
K.Warmuth
University of California Santa Cruz
Abstract
We study the problem of deterministically predicting boolean values
by combining the boolean predictions of several experts. Previous
on-line algorithms for this problem predict with the weighted majority
of the experts' predictions. These algorithms give each expert an
exponential weight $\beta^m$ where $\beta$ is a constant in $[0,1)$
and $m$ is the number of mistakes made by the expert in the past.
We show that it is better to use sums of binomials as weights. In
particular, we present a deterministic algorithm using binomial weights
that has a better worst case mistake bound than the best 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 be used to make prediction algorithms
robust against noise.
Download Compressed
Postscript
|