|
NeuroCOLT
Technical Report NC-TR-97-010
On Bayes Methods
for On-line Boolean Prediction
Nicolò
Cesa-Bianchi
Università degli Studi di Milan, Italy
David
Helmbold
University of California, Santa Cruz, USA
Sandra
Panizza
Università degli Studi di Milan, Italy
Abstract
This paper proposes a general framework, based on weighting schemes,
within which the Bayes method applied to on-line Boolean prediction
can be studied. By applying standard tools in Bayes theory we propose
an improved variant of the Weighted Majority algorithm for deterministic
prediction. The mistake bound of our variant is asymptotically equal
to the mistake bound of Weighted Majority when the latter has additional
side information to optimally tune its update factor. We also show
general bounds on the number of prediction mistakes made by conservative
versions of Bayesian algorithms. Specific instances of our bounds
match bounds previously shown for different on-line prediction algorithms
proposed in the past. Finally, we study a generalization of these
methods to randomized predictions.
Download Compressed Postscript
|